-- Summary posting sets (DESIGN.md §32). -- -- A summarized key column keeps, after its values, one SUMMARY entry per -- bucket of consecutive keys holding the union of their posting sets; a range -- over the column is then the summaries of the buckets it covers whole and the -- keys of the two buckets at its edges. Every answer here is checked against -- a sequential scan with the pushdown off, and lion_index_verify() - which -- compares every summary with the keys of its bucket - runs after every kind -- of change: build, appends that open new buckets, inserts in the middle and -- below every key, updates, deletes and VACUUM. \set VERBOSITY terse SET client_min_messages = warning; LOAD 'pg_lion'; CREATE EXTENSION IF NOT EXISTS pg_lion; CREATE EXTENSION IF NOT EXISTS pageinspect; RESET client_min_messages; -- VACUUM can only set all-visible once the commit record is on disk SET synchronous_commit = on; SET max_parallel_workers_per_gather = 0; /* * lion_sm() runs q with the pushdown on and every other scan disabled, and * again as a sequential scan with the pushdown off, and compares the answers. * It reports how the node evaluated a range and how many summaries it summed. */ CREATE FUNCTION lion_sm(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE j jsonb; node jsonb; how text; got text; want text; BEGIN PERFORM set_config('enable_seqscan', 'off', true); PERFORM set_config('enable_bitmapscan', 'off', true); PERFORM set_config('pg_lion.enable_plain_scan', 'off', true); PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true); EXECUTE 'EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF, SUMMARY OFF, BUFFERS OFF, FORMAT JSON) ' || q INTO j; node := jsonb_path_query_first(j, 'strict $.** ? (@."Custom Plan Provider" == "LionCount")'); IF node IS NULL THEN how := 'not pushed down'; ELSE how := coalesce(node ->> 'Range Evaluation', 'no range') || ', summaries ' || coalesce(node ->> 'Summaries Summed', '0'); END IF; EXECUTE format('SELECT coalesce(string_agg(s::text, '' '' ORDER BY s::text), ''(none)'') FROM (%s) s', q) INTO got; PERFORM set_config('pg_lion.enable_count_pushdown', 'off', true); PERFORM set_config('enable_seqscan', 'on', true); EXECUTE format('SELECT coalesce(string_agg(s::text, '' '' ORDER BY s::text), ''(none)'') FROM (%s) s', q) INTO want; PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('pg_lion.enable_plain_scan', 'on', true); PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true); IF got IS DISTINCT FROM want THEN RETURN format('MISMATCH: %s, pushed %s, seqscan %s', how, got, want); END IF; RETURN how || ': ' || got; END $$; /* The same answer through a bitmap scan of the index, against a seqscan. */ CREATE FUNCTION lion_sm_bitmap(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE got text; want text; BEGIN PERFORM set_config('pg_lion.enable_count_pushdown', 'off', true); PERFORM set_config('enable_seqscan', 'off', true); PERFORM set_config('pg_lion.enable_plain_scan', 'off', true); EXECUTE format('SELECT coalesce(string_agg(s::text, '' '' ORDER BY s::text), ''(none)'') FROM (%s) s', q) INTO got; PERFORM set_config('enable_seqscan', 'on', true); PERFORM set_config('enable_bitmapscan', 'off', true); EXECUTE format('SELECT coalesce(string_agg(s::text, '' '' ORDER BY s::text), ''(none)'') FROM (%s) s', q) INTO want; PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('pg_lion.enable_plain_scan', 'on', true); PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true); IF got IS DISTINCT FROM want THEN RETURN format('MISMATCH: bitmap %s, seqscan %s', got, want); END IF; RETURN got; END $$; -- ---------- the table ---------- -- u: unique and in heap order; r: 9000 values in no order; g: 7 values; -- k: 800 values, NULL in every 11th row; t: 3000 text values of every length CREATE TABLE lion_sm (id int NOT NULL, u int NOT NULL, r int NOT NULL, g int NOT NULL, k int, t text, pad text); INSERT INTO lion_sm SELECT i, i, (i * 7919) % 9001, i % 7, CASE WHEN i % 11 = 0 THEN NULL ELSE (i * 13) % 800 END, 'k' || repeat('x', i % 23) || ((i * 31) % 3000)::text, repeat('p', 30) FROM generate_series(1, 20000) i; -- small buckets, so that twenty thousand rows make hundreds of them CREATE INDEX lion_sm_urg ON lion_sm USING lion (u, r, g) WITH (summaries = on, summary_tids = 32); NOTICE: lion index "lion_sm_urg": column "u" has about one row per key CREATE INDEX lion_sm_k ON lion_sm USING lion (k) WITH (summaries = on, summary_tids = 64); CREATE INDEX lion_sm_t ON lion_sm USING lion (t) WITH (summaries = on, summary_tids = 48); NOTICE: lion index "lion_sm_t": column "t" has about one row per key VACUUM (FREEZE, ANALYZE) lion_sm; -- every ordered scalar column got summaries, and they hold every row with a -- value; the NULL rows are in none SELECT attno, entries, ntids, null_tids, summary_entries, summary_tids, summary_bytes > 0 AS has_bytes FROM lion_index_stats('lion_sm_urg'); attno | entries | ntids | null_tids | summary_entries | summary_tids | has_bytes -------+---------+-------+-----------+-----------------+--------------+----------- 1 | 20000 | 20000 | 0 | 625 | 20000 | t 2 | 9001 | 20000 | 0 | 613 | 20000 | t 3 | 7 | 20000 | 0 | 7 | 20000 | t (3 rows) SELECT attno, entries, ntids, null_tids, summary_entries, summary_tids FROM lion_index_stats('lion_sm_k'); attno | entries | ntids | null_tids | summary_entries | summary_tids -------+---------+-------+-----------+-----------------+-------------- 1 | 801 | 20000 | 1818 | 267 | 18182 (1 row) SELECT summary_tids = ntids AS covers FROM lion_index_stats('lion_sm_t'); covers -------- t (1 row) SELECT lion_index_verify('lion_sm_urg', true); lion_index_verify ------------------- (1 row) SELECT lion_index_verify('lion_sm_k', true); lion_index_verify ------------------- (1 row) SELECT lion_index_verify('lion_sm_t', true); lion_index_verify ------------------- (1 row) -- ---------- 1. ranges alone: the sum over the range, from its summaries ---------- SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 100'); lion_sm -------------------------------- inside, summaries 621: (19901) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 100'); lion_sm -------------------------------- inside, summaries 621: (19900) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u < 19000'); lion_sm -------------------------------- inside, summaries 593: (18999) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u <= 19000'); lion_sm -------------------------------- inside, summaries 593: (19000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 5000 AND 15000'); lion_sm -------------------------------- inside, summaries 311: (10001) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 5000 AND u < 15000'); lion_sm ------------------------------- inside, summaries 311: (9999) (1 row) SELECT lion_sm('SELECT count(u) FROM lion_sm WHERE u >= 1 AND u <= 20000'); lion_sm -------------------------------- inside, summaries 624: (20000) (1 row) -- within one bucket, and empty or inverted SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 40 AND 45'); lion_sm -------------------------- inside, summaries 0: (6) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 45 AND u < 46'); lion_sm -------------------------- inside, summaries 0: (0) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 900 AND 300'); lion_sm -------------------------- inside, summaries 0: (0) (1 row) -- outside the keys, and cross-type bounds outside the int4 domain SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 20000'); lion_sm -------------------------- inside, summaries 0: (0) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u < 5000000000::int8'); lion_sm -------------------------------- inside, summaries 625: (20000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= -5000000000::int8 AND u < 7000'); lion_sm ------------------------------- inside, summaries 217: (6999) (1 row) -- the column in no order in the heap SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r >= 1000'); lion_sm -------------------------------- inside, summaries 544: (17778) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r BETWEEN 2000 AND 6000'); lion_sm ------------------------------- inside, summaries 271: (8889) (1 row) -- a nullable column: its NULL rows are in no bucket and never counted SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k >= 0'); lion_sm -------------------------------- inside, summaries 266: (18182) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k < 400'); lion_sm ------------------------------- inside, summaries 133: (9091) (1 row) SELECT lion_sm('SELECT count(k) FROM lion_sm WHERE k BETWEEN 10 AND 700'); lion_sm -------------------------------- inside, summaries 229: (15705) (1 row) -- text keys of every length SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE t >= ''kx'''); lion_sm -------------------------------- inside, summaries 398: (19131) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE t BETWEEN ''k1'' AND ''kxxxxx'''); lion_sm ------------------------------ inside, summaries 89: (4349) (1 row) -- ---------- 2. beside other clauses: inside, complement, full domain ---------- SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 100 AND g = 3'); lion_sm --------------------------------- complement, summaries 3: (2843) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u < 300 AND g = 3'); lion_sm --------------------------- inside, summaries 9: (43) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 3000 AND 11000 AND g IN (1, 2)'); lion_sm ------------------------------- inside, summaries 249: (2286) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 0 AND g = 5'); lion_sm ---------------------------------- full domain, summaries 0: (2857) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r >= 100 AND g = 3'); lion_sm --------------------------------- complement, summaries 6: (2823) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r < 8900 AND (g = 1 OR k = 7)'); lion_sm --------------------------------- complement, summaries 7: (2839) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k >= 3 AND g = 2'); lion_sm --------------------------------- complement, summaries 1: (2588) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k >= 3 AND k < 790 AND u > 1000'); lion_sm -------------------------------- inside, summaries 854: (16992) (1 row) -- ---------- 3. two bounds on one side (DESIGN.md §32: the tightest one) ---------- SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u < 19900 AND u <= 19950 AND g = 3'); lion_sm --------------------------------- complement, summaries 3: (2843) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u <= 19950 AND u < 19900 AND g = 3'); lion_sm --------------------------------- complement, summaries 3: (2843) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 50 AND u >= 20 AND g = 3'); lion_sm --------------------------------- complement, summaries 1: (2850) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 20 AND u > 50 AND u < 19000 AND u <= 19990'); lion_sm -------------------------------- inside, summaries 591: (18949) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u < 19900 AND u < 19950::int8 AND g = 4'); lion_sm --------------------------------- complement, summaries 3: (2843) (1 row) -- ---------- 4. walks that must not use summaries: per-key groups ---------- SELECT lion_sm('SELECT u, count(*) FROM lion_sm WHERE u BETWEEN 100 AND 140 GROUP BY u'); lion_sm ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- no range, summaries 0: (100,1) (101,1) (102,1) (103,1) (104,1) (105,1) (106,1) (107,1) (108,1) (109,1) (110,1) (111,1) (112,1) (113,1) (114,1) (115,1) (116,1) (117,1) (118,1) (119,1) (120,1) (121,1) (122,1) (123,1) (124,1) (125,1) (126,1) (127,1) (128,1) (129,1) (130,1) (131,1) (132,1) (133,1) (134,1) (135,1) (136,1) (137,1) (138,1) (139,1) (140,1) (1 row) SELECT lion_sm('SELECT count(DISTINCT r) FROM lion_sm WHERE r BETWEEN 100 AND 400'); lion_sm ------------------------------ no range, summaries 0: (301) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k IS NOT NULL'); lion_sm -------------------------------- no range, summaries 7: (18182) (1 row) SELECT lion_sm('SELECT g, count(*) FROM lion_sm GROUP BY g'); lion_sm --------------------------------------------------------------------------------------- no range, summaries 0: (0,2857) (1,2858) (2,2857) (3,2857) (4,2857) (5,2857) (6,2857) (1 row) -- and the bitmap and plain scans of the same index, which read no summary SELECT lion_sm_bitmap('SELECT count(*) FROM lion_sm WHERE u BETWEEN 5000 AND 5100'); lion_sm_bitmap ---------------- (101) (1 row) SELECT lion_sm_bitmap('SELECT count(*) FROM lion_sm WHERE k IS NOT NULL'); lion_sm_bitmap ---------------- (18182) (1 row) SELECT lion_sm_bitmap('SELECT count(*) FROM lion_sm WHERE t >= ''kxxxxxxxxxxxxxxxxxxxxx'''); lion_sm_bitmap ---------------- (1738) (1 row) SELECT lion_sm_bitmap('SELECT count(*) FROM lion_sm WHERE g = 3 AND r > 8000'); lion_sm_bitmap ---------------- (314) (1 row) -- ---------- 5. inserts: new buckets above every key, keys between and below ---------- -- appends above every key open a new bucket each time the last one is full INSERT INTO lion_sm SELECT i, i, (i * 7919) % 9001, i % 7, NULL, 'kz' || i::text, 'q' FROM generate_series(20001, 21500) i; -- keys between existing ones join the bucket that covers them INSERT INTO lion_sm SELECT 30000 + i, 2 * i, 9001 + i, i % 7, i % 800, 'kb' || i::text, 'q' FROM generate_series(1, 700) i; -- and keys below every key join the first bucket INSERT INTO lion_sm SELECT 40000 + i, -i, -i, i % 7, -i, '' || i::text, 'q' FROM generate_series(1, 300) i; SELECT attno, summary_entries > 600 AS many, summary_tids = ntids AS covers FROM lion_index_stats('lion_sm_urg'); attno | many | covers -------+------+-------- 1 | t | t 2 | t | t 3 | f | t (3 rows) SELECT lion_index_verify('lion_sm_urg', true); lion_index_verify ------------------- (1 row) SELECT lion_index_verify('lion_sm_k', true); lion_index_verify ------------------- (1 row) SELECT lion_index_verify('lion_sm_t', true); lion_index_verify ------------------- (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 100'); lion_sm -------------------------------- inside, summaries 668: (22052) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 20500'); lion_sm ------------------------------ inside, summaries 31: (1000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 1 AND 20700 AND g = 2'); lion_sm ---------------------------------- complement, summaries 25: (3057) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u < 0'); lion_sm ---------------------------- inside, summaries 0: (300) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r < 100 AND g = 1'); lion_sm --------------------------- inside, summaries 6: (81) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k < 5'); lion_sm ---------------------------- inside, summaries 1: (417) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE t < ''kc'''); lion_sm ------------------------------ inside, summaries 18: (1869) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE t > ''kz1'''); lion_sm ------------------------------ inside, summaries 31: (1500) (1 row) -- ---------- 5b. an open bucket that is a posting tree, its key raised ---------- -- inline_limit = 64 spills a summary to a chain of its own after a few rows, -- and the appends after a VACUUM land in the free space it left all over the -- heap: the open bucket is a chain whose key every append raises. Its pages -- are stamped with its entry's hash (§18), which is why a summary's hash is a -- constant and not its key's: the key changes, the stamp may not. CREATE TABLE lion_sm_chain (k int NOT NULL, pad text); INSERT INTO lion_sm_chain SELECT i, repeat('p', 200) FROM generate_series(1, 4000) i; CREATE INDEX lion_sm_chain_k ON lion_sm_chain USING lion (k) WITH (summaries = on, summary_tids = 64, inline_limit = 64); DELETE FROM lion_sm_chain WHERE k % 3 <> 0; VACUUM (FREEZE) lion_sm_chain; INSERT INTO lion_sm_chain SELECT 4000 + i, repeat('p', 200) FROM generate_series(1, 3000) i; SELECT summary_entries > 60 AS many, summary_tids = ntids AS covers, summary_pages > 0 AS chained FROM lion_index_stats('lion_sm_chain_k'); many | covers | chained ------+--------+--------- t | t | t (1 row) SELECT lion_index_verify('lion_sm_chain_k', true); lion_index_verify ------------------- (1 row) VACUUM (FREEZE, ANALYZE) lion_sm_chain; SELECT lion_sm('SELECT count(*) FROM lion_sm_chain WHERE k > 3000'); lion_sm ------------------------------ inside, summaries 63: (3333) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_chain WHERE k BETWEEN 2000 AND 6500'); lion_sm ------------------------------ inside, summaries 69: (3167) (1 row) DROP TABLE lion_sm_chain; -- ---------- 5c. the open bucket's empty leaves leave its set ---------- -- A column whose every row is in its open bucket, a posting set of several -- leaves (rows of 200 bytes, every other one NULL), and then no row at all: -- the open bucket stays, empty (DESIGN.md §32), and its empty leaves leave -- the set as the leaves of a key's set do (§22, "Empty leaves"), but for -- the head and the last one. The next rows go into what is left. CREATE TABLE lion_sm_open (k int, pad char(200) NOT NULL DEFAULT 'x') WITH (autovacuum_enabled = off); CREATE INDEX lion_sm_open_k ON lion_sm_open USING lion (k) WITH (summaries = on, summary_tids = 16777216); INSERT INTO lion_sm_open SELECT CASE WHEN i % 2 = 0 THEN i END FROM generate_series(1, 200000) i; SELECT summary_entries, summary_tids, summary_pages > 4 AS leaves FROM lion_index_stats('lion_sm_open_k'); summary_entries | summary_tids | leaves -----------------+--------------+-------- 1 | 100000 | t (1 row) DELETE FROM lion_sm_open; -- FREEZE: a plain VACUUM leaves the dead rows of a heap page it cannot have -- the cleanup lock of at once (one the checkpointer is writing out, say) to -- the next VACUUM, and the leaf that holds their TIDs with them VACUUM (FREEZE) lion_sm_open; SELECT entries, summary_entries, summary_tids, summary_pages <= 2 AS emptied, deleted_pages > 0 AS freed FROM lion_index_stats('lion_sm_open_k'); entries | summary_entries | summary_tids | emptied | freed ---------+-----------------+--------------+---------+------- 0 | 1 | 0 | t | t (1 row) SELECT lion_index_verify('lion_sm_open_k', true); lion_index_verify ------------------- (1 row) INSERT INTO lion_sm_open (k) SELECT i FROM generate_series(1, 3000) i; SELECT summary_entries, summary_tids FROM lion_index_stats('lion_sm_open_k'); summary_entries | summary_tids -----------------+-------------- 1 | 3000 (1 row) SELECT lion_index_verify('lion_sm_open_k', true); lion_index_verify ------------------- (1 row) VACUUM (FREEZE, ANALYZE) lion_sm_open; SELECT lion_sm('SELECT count(*) FROM lion_sm_open WHERE k > 1000'); lion_sm ----------------------------- inside, summaries 0: (2000) (1 row) DROP TABLE lion_sm_open; -- ---------- 6. a dirty heap, and VACUUM ---------- UPDATE lion_sm SET pad = 'dirty' WHERE id % 5 = 0; UPDATE lion_sm SET u = u + 100000 WHERE id % 97 = 0; DELETE FROM lion_sm WHERE id % 13 = 0; SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 100'); lion_sm -------------------------------- inside, summaries 674: (20360) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 5000 AND 15000 AND g = 3'); lion_sm ------------------------------- inside, summaries 311: (1305) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 100000'); lion_sm ---------------------------- inside, summaries 5: (210) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r > 50 AND r < 8000'); lion_sm -------------------------------- inside, summaries 540: (17529) (1 row) SELECT lion_index_verify('lion_sm_urg', true); lion_index_verify ------------------- (1 row) VACUUM (FREEZE) lion_sm; SELECT lion_index_verify('lion_sm_urg', true); lion_index_verify ------------------- (1 row) SELECT lion_index_verify('lion_sm_k', true); lion_index_verify ------------------- (1 row) SELECT lion_index_verify('lion_sm_t', true); lion_index_verify ------------------- (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 100'); lion_sm -------------------------------- inside, summaries 674: (20360) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 5000 AND 15000 AND g = 3'); lion_sm ------------------------------- inside, summaries 311: (1305) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u > 100000'); lion_sm ---------------------------- inside, summaries 5: (210) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE r > 50 AND r < 8000'); lion_sm -------------------------------- inside, summaries 540: (17529) (1 row) -- a run of whole buckets deleted: their summaries are emptied and removed DELETE FROM lion_sm WHERE u BETWEEN 2000 AND 9000; VACUUM (FREEZE) lion_sm; SELECT lion_index_verify('lion_sm_urg', true); lion_index_verify ------------------- (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u >= 100'); lion_sm -------------------------------- inside, summaries 456: (13964) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 1000 AND 10000'); lion_sm ------------------------------ inside, summaries 62: (2010) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE u BETWEEN 1990 AND 9010 AND g = 3'); lion_sm -------------------------- inside, summaries 0: (3) (1 row) -- ... and every row of a column: every summary goes but the open one, which -- stays empty (DESIGN.md §32), and the next insert goes into it again DELETE FROM lion_sm WHERE k IS NOT NULL; VACUUM (FREEZE) lion_sm; SELECT summary_entries, summary_tids FROM lion_index_stats('lion_sm_k'); summary_entries | summary_tids -----------------+-------------- 1 | 0 (1 row) INSERT INTO lion_sm VALUES (50001, 50001, 1, 1, 42, 'x', 'q'), (50002, 50002, 2, 2, 41, 'y', 'q'); SELECT summary_entries, summary_tids FROM lion_index_stats('lion_sm_k'); summary_entries | summary_tids -----------------+-------------- 1 | 2 (1 row) SELECT lion_index_verify('lion_sm_k', true); lion_index_verify ------------------- (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k >= 0'); lion_sm -------------------------- inside, summaries 0: (2) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm WHERE k > 41'); lion_sm -------------------------- inside, summaries 0: (1) (1 row) -- ---------- 7. an index without summaries, and REINDEX ---------- -- The format version, read off the meta page (block 0: LionMetaPageData -- follows the 24-byte page header, with its version at +4), and how many key -- columns have summaries. CREATE FUNCTION lion_sm_meta(idx regclass, OUT version int, OUT summary_cols int) LANGUAGE sql AS $$ SELECT get_byte(p, 28) | (get_byte(p, 29) << 8), (SELECT count(*)::int FROM lion_index_stats(idx) s WHERE s.summary_entries > 0) FROM get_raw_page(idx::text, 0) p $$; CREATE TABLE lion_sm_old (u int NOT NULL, g int NOT NULL); INSERT INTO lion_sm_old SELECT i, i % 5 FROM generate_series(1, 5000) i; -- summaries = off is the default; the format version is 9 either way CREATE INDEX lion_sm_old_u ON lion_sm_old USING lion (u, g); VACUUM (FREEZE, ANALYZE) lion_sm_old; SELECT * FROM lion_sm_meta('lion_sm_old_u'); version | summary_cols ---------+-------------- 1 | 0 (1 row) SELECT attno, summary_entries FROM lion_index_stats('lion_sm_old_u'); attno | summary_entries -------+----------------- 1 | 0 2 | 0 (2 rows) SELECT lion_sm('SELECT count(*) FROM lion_sm_old WHERE u >= 100 AND g = 2'); lion_sm -------------------------------- complement, summaries 0: (980) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_old WHERE u BETWEEN 100 AND 4000'); lion_sm ----------------------------- inside, summaries 0: (3901) (1 row) -- setting the option changes nothing until the index is rebuilt: inserts -- never make summaries for a column the build did not give them ALTER INDEX lion_sm_old_u SET (summaries = on, summary_tids = 64); INSERT INTO lion_sm_old SELECT i, i % 5 FROM generate_series(5001, 5100) i; SELECT attno, summary_entries FROM lion_index_stats('lion_sm_old_u'); attno | summary_entries -------+----------------- 1 | 0 2 | 0 (2 rows) SELECT lion_sm('SELECT count(*) FROM lion_sm_old WHERE u >= 100 AND g = 2'); lion_sm --------------------------------- complement, summaries 0: (1000) (1 row) REINDEX INDEX lion_sm_old_u; SELECT * FROM lion_sm_meta('lion_sm_old_u'); version | summary_cols ---------+-------------- 1 | 2 (1 row) SELECT attno, summary_entries > 0 AS has FROM lion_index_stats('lion_sm_old_u'); attno | has -------+----- 1 | t 2 | t (2 rows) SELECT lion_index_verify('lion_sm_old_u', true); lion_index_verify ------------------- (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_old WHERE u >= 100 AND g = 2'); lion_sm --------------------------------- complement, summaries 1: (1000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_old WHERE u BETWEEN 100 AND 4000'); lion_sm ------------------------------ inside, summaries 60: (3901) (1 row) -- ... and off again ALTER INDEX lion_sm_old_u SET (summaries = off); REINDEX INDEX lion_sm_old_u; SELECT * FROM lion_sm_meta('lion_sm_old_u'); version | summary_cols ---------+-------------- 1 | 0 (1 row) SELECT attno, summary_entries FROM lion_index_stats('lion_sm_old_u'); attno | summary_entries -------+----------------- 1 | 0 2 | 0 (2 rows) DROP FUNCTION lion_sm_meta(regclass); -- ---------- 8. auto: the build decides per column from the data ---------- CREATE TABLE lion_sm_auto (u int NOT NULL, g int NOT NULL, b bool, e int[]); INSERT INTO lion_sm_auto SELECT i, i % 4, i % 2 = 0, ARRAY[i % 10] FROM generate_series(1, 8000) i; -- u has many keys of one row each; g and b have a few keys of many rows; an -- array column extracts keys and never has summaries CREATE INDEX lion_sm_auto_i ON lion_sm_auto USING lion (u, g, b) WITH (summaries = auto, summary_tids = 64); SELECT attno, summary_entries > 0 AS has FROM lion_index_stats('lion_sm_auto_i'); attno | has -------+----- 1 | t 2 | f 3 | f (3 rows) CREATE INDEX lion_sm_auto_e ON lion_sm_auto USING lion (e) WITH (summaries = on); SELECT attno, summary_entries FROM lion_index_stats('lion_sm_auto_e'); attno | summary_entries -------+----------------- 1 | 0 (1 row) -- an empty table gives auto nothing to decide from, and on its every column. -- u arrives in ascending order and fills bucket after bucket; v arrives in no -- text order ('v10' sorts below 'v9'), and once 'v99' is in, every later key -- sorts below the open bucket's key and joins it: one bucket, which REINDEX -- would split CREATE TABLE lion_sm_empty (u int, v text); CREATE INDEX lion_sm_empty_auto ON lion_sm_empty USING lion (u) WITH (summaries = auto); CREATE INDEX lion_sm_empty_on ON lion_sm_empty USING lion (u, v) WITH (summaries = on, summary_tids = 16); INSERT INTO lion_sm_empty SELECT i, 'v' || i FROM generate_series(1, 300) i; SELECT attno, summary_entries FROM lion_index_stats('lion_sm_empty_auto'); attno | summary_entries -------+----------------- 1 | 0 (1 row) SELECT attno, summary_entries > 5 AS many, summary_tids FROM lion_index_stats('lion_sm_empty_on'); attno | many | summary_tids -------+------+-------------- 1 | t | 300 2 | f | 300 (2 rows) SELECT lion_index_verify('lion_sm_empty_on', true); lion_index_verify ------------------- (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_empty WHERE u >= 20'); lion_sm ----------------------------- inside, summaries 17: (281) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_empty WHERE v < ''v5'''); lion_sm ---------------------------- inside, summaries 0: (245) (1 row) -- ---------- 9. a partitioned table, summaries in some partitions only ---------- CREATE TABLE lion_sm_p (u int NOT NULL, g int NOT NULL) PARTITION BY RANGE (u); CREATE TABLE lion_sm_p1 PARTITION OF lion_sm_p FOR VALUES FROM (0) TO (5000); CREATE TABLE lion_sm_p2 PARTITION OF lion_sm_p FOR VALUES FROM (5000) TO (10000); CREATE TABLE lion_sm_p3 PARTITION OF lion_sm_p FOR VALUES FROM (10000) TO (20000); INSERT INTO lion_sm_p SELECT i, i % 3 FROM generate_series(0, 19999) i; CREATE INDEX lion_sm_p1_i ON lion_sm_p1 USING lion (u, g) WITH (summaries = on, summary_tids = 32); CREATE INDEX lion_sm_p2_i ON lion_sm_p2 USING lion (u, g); CREATE INDEX lion_sm_p3_i ON lion_sm_p3 USING lion (u, g) WITH (summaries = on, summary_tids = 100); NOTICE: lion index "lion_sm_p3_i": column "u" has about one row per key VACUUM (FREEZE, ANALYZE) lion_sm_p; SELECT lion_sm('SELECT count(*) FROM lion_sm_p WHERE u >= 100'); lion_sm -------------------------------- inside, summaries 252: (19900) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_p WHERE u BETWEEN 3000 AND 17000 AND g = 1'); lion_sm ------------------------------------------------ inside 2, full domain 1, summaries 132: (4667) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_p WHERE u < 12000 AND g = 2'); lion_sm ------------------------------------------------ inside 2, full domain 1, summaries 177: (4000) (1 row) -- ---------- 10. a unique timestamp, the shape summaries are for ---------- CREATE TABLE lion_sm_ts (ts timestamptz NOT NULL, c int NOT NULL); INSERT INTO lion_sm_ts SELECT '2025-01-01 00:00:00+00'::timestamptz + i * interval '1 minute', i % 50 FROM generate_series(1, 30000) i; CREATE INDEX lion_sm_ts_i ON lion_sm_ts USING lion (ts, c) WITH (summaries = auto); NOTICE: lion index "lion_sm_ts_i": column "ts" has about one row per key VACUUM (FREEZE, ANALYZE) lion_sm_ts; SELECT attno, summary_entries > 0 AS has FROM lion_index_stats('lion_sm_ts_i'); attno | has -------+----- 1 | t 2 | f (2 rows) SELECT lion_sm('SELECT count(*) FROM lion_sm_ts WHERE ts >= ''2025-01-02 00:00:00+00'''); lion_sm ------------------------------ inside, summaries 7: (28561) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_ts WHERE ts >= ''2025-01-02 00:00:00+00'' AND c = 7'); lion_sm -------------------------------- complement, summaries 0: (571) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_ts WHERE ts BETWEEN ''2025-01-05'' AND ''2025-01-12'' AND c = 7'); lion_sm -------------------------------- complement, summaries 5: (202) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_ts WHERE ts < ''2025-01-03 00:00:00+00'' AND c = 9'); lion_sm ------------------------------- complement, summaries 7: (58) (1 row) SELECT lion_index_verify('lion_sm_ts_i', true); lion_index_verify ------------------- (1 row) -- ---------- 11. a count of every row driven by a summarized column ---------- -- With nothing that selects rows the count is the sum over every entry of the -- column with the fewest (DESIGN.md §35) - k here, NULL in every tenth row. -- Its walk hands out summaries, which hold no NULL row, so k's NULL entry is -- counted beside them, unless k's own `IS NOT NULL` is what drops it; the -- same counts over a plain index on k, and over partitions that have -- summaries or not CREATE TABLE lion_sm_all (k int, g int); INSERT INTO lion_sm_all SELECT CASE WHEN i % 10 = 0 THEN NULL ELSE (i * 7) % 300 END, CASE WHEN i % 4 = 1 THEN NULL ELSE i % 1009 END FROM generate_series(1, 30000) i; CREATE INDEX lion_sm_all_k ON lion_sm_all USING lion (k) WITH (summaries = on, summary_tids = 64); CREATE INDEX lion_sm_all_g ON lion_sm_all USING lion (g); VACUUM (FREEZE, ANALYZE) lion_sm_all; SET enable_seqscan = off; EXPLAIN (COSTS OFF) SELECT count(*) FROM lion_sm_all WHERE g <> 7; QUERY PLAN ------------------------------------------------------------------ Custom Scan (LionCount) Lion Indexes: lion_sm_all_k (all rows), lion_sm_all_g (g <> 7) (2 rows) RESET enable_seqscan; SELECT lion_sm('SELECT count(*) FROM lion_sm_all'); lion_sm ---------------------------------- no range, summaries 270: (30000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE g IS NOT NULL'); lion_sm ---------------------------------- no range, summaries 270: (22500) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE g <> 7'); lion_sm ---------------------------------- no range, summaries 270: (22477) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE k IS NOT NULL'); lion_sm ---------------------------------- no range, summaries 270: (27000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE k <> 3'); lion_sm ---------------------------------- no range, summaries 270: (26900) (1 row) SELECT lion_sm('SELECT count(*), count(*) FILTER (WHERE k IS NOT NULL), count(*) FILTER (WHERE g <> 7 OR k <> 3) FROM lion_sm_all'); lion_sm ---------------------------------------------- no range, summaries 810: (30000,27000,29897) (1 row) DROP INDEX lion_sm_all_k; CREATE INDEX lion_sm_all_k ON lion_sm_all USING lion (k); VACUUM ANALYZE lion_sm_all; SELECT lion_sm('SELECT count(*) FROM lion_sm_all'); lion_sm -------------------------------- no range, summaries 0: (30000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE g IS NOT NULL'); lion_sm -------------------------------- no range, summaries 0: (22500) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE g <> 7'); lion_sm -------------------------------- no range, summaries 0: (22477) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_all WHERE k IS NOT NULL'); lion_sm -------------------------------- no range, summaries 0: (27000) (1 row) CREATE TABLE lion_sm_allp (k int, g int) PARTITION BY RANGE (g); CREATE TABLE lion_sm_allp1 PARTITION OF lion_sm_allp FOR VALUES FROM (MINVALUE) TO (500); CREATE TABLE lion_sm_allp2 PARTITION OF lion_sm_allp FOR VALUES FROM (500) TO (MAXVALUE); CREATE TABLE lion_sm_allp0 PARTITION OF lion_sm_allp DEFAULT; INSERT INTO lion_sm_allp SELECT k, g FROM lion_sm_all; CREATE INDEX lion_sm_allp1_k ON lion_sm_allp1 USING lion (k) WITH (summaries = on, summary_tids = 64); CREATE INDEX lion_sm_allp2_k ON lion_sm_allp2 USING lion (k); CREATE INDEX lion_sm_allp0_k ON lion_sm_allp0 USING lion (k) WITH (summaries = on, summary_tids = 64); CREATE INDEX lion_sm_allp_g ON lion_sm_allp USING lion (g); VACUUM (FREEZE, ANALYZE) lion_sm_allp; SELECT lion_sm('SELECT count(*) FROM lion_sm_allp'); lion_sm ---------------------------------- no range, summaries 173: (30000) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_allp WHERE g IS NOT NULL'); lion_sm ---------------------------------- no range, summaries 173: (22500) (1 row) SELECT lion_sm('SELECT count(*) FROM lion_sm_allp WHERE g <> 7'); lion_sm ---------------------------------- no range, summaries 173: (22477) (1 row) DROP TABLE lion_sm, lion_sm_old, lion_sm_auto, lion_sm_empty, lion_sm_p, lion_sm_ts, lion_sm_all, lion_sm_allp; DROP FUNCTION lion_sm(text); DROP FUNCTION lion_sm_bitmap(text);