Bdtjtk

I was curious if sqlite index stores the max and min of a column to help optimize queries against it. I was thinking that if we had a large file with millions of records if the index happened to store the max and min and we had a greater then or less then criteria on the column than the query could instantaneously tell us that the record does not exist and not have to bother searching the db file in the first place. Would anyone happen to know if a max and min is normally stored in a db index in something such as sqlite?

The minimum and maximum values are not stored separately.

However, they are the first and last entries in the index, so they can be read quickly. This is called the MIN/MAX optimization:

Queries that contain a single MIN() or MAX() aggregate function whose argument is the left-most column of an index might be satisfied by doing a single index lookup rather than by scanning the entire table. Examples:

SELECT MIN(x) FROM table;

SELECT MAX(x)+1 FROM table;

And if you are searching for a specific value that is outside the range of the column values, a binary search on the index will quickly determine that there is no page that contains a matching value. (The upper levels of the index B-tree are cached anyway, so it would not make sense to create a copy elsewhere.)

As far as I am aware SQlite doesn't store such values independent of the data. However, you could easily do so by creating a table to store the min and max values and every time a row is inserted.

Updates and deletes could however be more time consuming when a min or max would have to change.

It would probably be more efficient to also store the rowid of the rows.

A table such along the lines of :-

CREATE TABLE IF NOT EXISTS minmax_store(max_value INTEGER, max_rowid INTEGER, min_value INTEGER, min_rowid INTEGER);

The following is a demo that may suit. It uses triggers to maintain the minmax_store table :-

DROP TABLE IF EXISTS mydata;

CREATE TABLE IF NOT EXISTS mydata(id INTEGER PRIMARY KEY, myvalue INTEGER);

DROP TABLE IF EXISTS minmax_store;

CREATE TABLE IF NOT EXISTS minmax_store (max_value INTEGER, max_rowid INTEGER, min_value INTEGER, min_rowid INTEGER);

INSERT INTO minmax_store VALUES(-9223372036854775806,-1,9223372036854775807,-1);

DROP TRIGGER IF EXISTS maintain_minmax_after_insert;

CREATE TRIGGER IF NOT EXISTS maintain_minmax_after_insert AFTER INSERT ON mydata

    BEGIN

        UPDATE minmax_store SET max_value = new.myvalue, max_rowid = new.id WHERE max_value < new.myvalue;

      UPDATE minmax_store SET min_value = new.myvalue, min_rowid = new.id WHERE min_value > new.myvalue;    

    END

;

DROP TRIGGER IF EXISTS maintain_minmax_after_delete;

CREATE TRIGGER IF NOT EXISTS maintain_minmax_after_delete AFTER DELETE ON mydata 

    WHEN (SELECT max_value FROM minmax_store) = old.myvalue OR (SELECT min_value FROM minmax_store) = old.myvalue

    BEGIN

        UPDATE minmax_store 

            SET max_value = (SELECT max(myvalue) FROM mydata), max_rowid = (SELECT rowid FROM mydata ORDER BY myvalue DESC LIMIT 1),

            min_value = (SELECT min(myvalue) FROM mydata), min_rowid = (SELECT rowid FROM mydata ORDER BY myvalue ASC LIMIT 1);

    END

;

DROP TRIGGER IF EXISTS maintain_minmax_after_update;

CREATE TRIGGER IF NOT EXISTS maintain_minmax_after_update AFTER UPDATE ON mydata

    WHEN (SELECT max_value FROM minmax_store) = old.myvalue 

        OR (SELECT min_value FROM minmax_store) = old.myvalue  

        OR (SELECT max_value FROM minmax_store) < new.myvalue

      OR (SELECT min_value FROM minmax_store) > new.myvalue

    BEGIN

        UPDATE minmax_store

            SET max_value = (SELECT max(myvalue) FROM mydata), max_rowid = (SELECT rowid FROM mydata ORDER BY myvalue DESC LIMIT 1),

            min_value = (SELECT min(myvalue) FROM mydata), min_rowid = (SELECT rowid FROM mydata ORDER BY myvalue ASC LIMIT 1);

  END

;   



INSERT INTO mydata (myvalue) VALUES(1),(4),(6),(7),(8),(3),(5),(0),(9),(100),(200),(55),(66),(33),(4421);

SELECT * FROM minmax_store;



SELECT *, 

    CASE 

        WHEN myvalue = (SELECT max_value FROM minmax_store) THEN 'MAX VALUE HERE' ELSE '' END AS isrowmaxvalue,

    CASE

        WHEN myvalue = (SELECT min_value FROM minmax_store) THEN 'MIN VALUE HERE' ELSE '' END AS isrowminvalue

    FROM mydata;



DELETE FROM mydata WHERE myvalue = (SELECT min(myvalue) FROM mydata);



SELECT * FROM minmax_store;

SELECT *, 

    CASE 

        WHEN myvalue = (SELECT max_value FROM minmax_store) THEN 'MAX VALUE HERE' ELSE '' END AS isrowmaxvalue,

    CASE

        WHEN myvalue = (SELECT min_value FROM minmax_store) THEN 'MIN VALUE HERE' ELSE '' END AS isrowminvalue

    FROM mydata;



UPDATE mydata SET myvalue = (SELECT max_value FROM minmax_store) + 10 WHERE myvalue = (SELECT min_value FROM minmax_store);

SELECT * FROM minmax_store;

SELECT *, 

    CASE 

        WHEN myvalue = (SELECT max_value FROM minmax_store) THEN 'MAX VALUE HERE' ELSE '' END AS isrowmaxvalue,

    CASE

        WHEN myvalue = (SELECT min_value FROM minmax_store) THEN 'MIN VALUE HERE' ELSE '' END AS isrowminvalue

    FROM mydata

The first query returns (the minmax_store table):-

The second query returns :-

The third query, after the minimum row (value of 0) has been deleted, shows the changed minmax_store as :-

The fourth query returns (same query as 2nd) returns :-

The fifth query, after the row with the minimum value is amended to be the maximum value + 10 (4431), shows the changed minmax_store as :-

The sixth query returns (same as 2nd and 4th queries) returns :-

• 
  Note the above is provided as in-principle code, it has not been extensively tested and may therefore contains some errors and in-efficiencies.