-- Lion-filtered walks of a covering B-tree, index-only (DESIGN.md §40). -- -- SELECT FROM t WHERE -- [AND ] [ORDER BY ]: the node walks -- the btree, tests each TID against lion's set, and returns the members' -- values from the INDEX TUPLES, reading the heap only for pages the -- visibility map does not call all-visible. With an ORDER BY it is the -- LionOrdered of ordered.sql in its index-only mode; without one it is a -- LionBtreeScan. Every query below is run through the node (every core scan -- disabled) and through the ordinary plan (the node off), and the answers are -- compared: in order where the query orders them, as multisets otherwise. \set VERBOSITY terse SET client_min_messages = warning; LOAD 'pg_lion'; CREATE EXTENSION IF NOT EXISTS pg_lion; RESET client_min_messages; SET synchronous_commit = on; SET max_parallel_workers_per_gather = 0; SET default_statistics_target = 1000; SET work_mem = '64MB'; CREATE TABLE bs ( id int PRIMARY KEY, k int NOT NULL, -- a permutation of the ids grp int, -- 100 groups x int, -- what the aggregates sum c200 int, c20 int, -- lion-filtered tags text[], flag bool, nm name, -- a btree stores a name as a cstring note text, -- indexed by nothing: updating it is HOT payload text -- in no btree, so a query reading it is heap mode; -- wide, so the heap is six times the covering btrees ) WITH (autovacuum_enabled = off); INSERT INTO bs SELECT i, (i::bigint * 7919 % 100003)::int, i % 100, i % 1000, ((hashint8extended(i::bigint, 33) & 9223372036854775807) % 200)::int, ((hashint8extended(i::bigint, 22) & 9223372036854775807) % 20)::int, ARRAY['t' || (i % 10), 'u' || (i % 37)], i % 3 = 0, ('n' || (i % 50))::name, 'n', repeat(md5(i::text), 8) FROM generate_series(1, 100000) i; -- the covering btrees CREATE INDEX bs_k ON bs (k) INCLUDE (id, grp, x, c200, c20, nm); CREATE INDEX bs_grp ON bs (grp) INCLUDE (x, tags); CREATE INDEX bs_part ON bs (k) INCLUDE (id, x, c200, flag) WHERE flag; CREATE INDEX bs_part_nf ON bs (x) INCLUDE (id, c200) WHERE flag; CREATE INDEX bs_expr ON bs ((k % 1000), id) INCLUDE (c200); -- the filter side: lion CREATE INDEX bs_c200 ON bs USING lion (c200); CREATE INDEX bs_c20 ON bs USING lion (c20); CREATE INDEX bs_tags ON bs USING lion (tags); VACUUM (FREEZE, ANALYZE) bs; /* * lion_bs() runs q through the node - every core scan disabled, so that a * LionOrdered or a LionBtreeScan is the only path left that is not - and * through the ordinary plan (both of the node's settings off, every core scan * on), compares the two answers - in order when `ordered`, as multisets * otherwise - and names the node the first plan used, and whether it was * index-only. A prepared statement's cached plan does not change with the * settings, so for one the ordinary answer comes from the query it stands * for, given as `ordinary`. */ CREATE FUNCTION lion_bs(q text, ordered boolean DEFAULT false, ordinary text DEFAULT NULL) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; r record; node text := 'no node'; mode text := ''; a text[] := '{}'; b 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.pushdown_margin', '1000', true); PERFORM set_config('enable_tidscan', 'off', true); FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP IF ln ~ 'Custom Scan \(Lion(Ordered|BtreeScan)\)' THEN node := substring(ln from 'Custom Scan \((Lion\w+)\)'); ELSIF ln ~ '^\s*(Ordered By|Index): .*index only' THEN mode := ' index only'; END IF; END LOOP; FOR r IN EXECUTE q LOOP a := a || r::text; END LOOP; PERFORM set_config('enable_seqscan', 'on', true); PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('pg_lion.enable_plain_scan', 'on', true); PERFORM set_config('pg_lion.pushdown_margin', '1', true); PERFORM set_config('enable_tidscan', 'on', true); PERFORM set_config('pg_lion.enable_ordered_scan', 'off', true); PERFORM set_config('pg_lion.enable_btree_scan', 'off', true); FOR r IN EXECUTE coalesce(ordinary, q) LOOP b := b || r::text; END LOOP; PERFORM set_config('pg_lion.enable_ordered_scan', 'on', true); PERFORM set_config('pg_lion.enable_btree_scan', 'on', true); IF NOT ordered THEN SELECT coalesce(array_agg(e ORDER BY e), '{}') INTO a FROM unnest(a) e; SELECT coalesce(array_agg(e ORDER BY e), '{}') INTO b FROM unnest(b) e; END IF; IF a IS DISTINCT FROM b THEN RETURN format('MISMATCH: %s rows through the node, %s ordinary; first %s / %s', coalesce(array_length(a, 1), 0), coalesce(array_length(b, 1), 0), a[1], b[1]); END IF; RETURN format('%s%s, %s rows', node, mode, coalesce(array_length(a, 1), 0)); END $$; /* * lion_bs_plan() prints the plan's NODES with nothing disabled (the plan * choice is the test), one per line, without the lines whose contents vary * between majors. */ CREATE FUNCTION lion_bs_plan(q text) RETURNS SETOF text LANGUAGE plpgsql AS $$ DECLARE ln text; BEGIN FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP IF ln !~ '^\s*(Index Searches|Disabled|Storage|Planning|Execution|Buffers)' THEN RETURN NEXT ln; END IF; END LOOP; END $$; /* * lion_bs_run() runs q through the node under EXPLAIN ANALYZE and prints the * node's name, its index and mode, and its counters. */ CREATE FUNCTION lion_bs_run(q text) RETURNS SETOF text LANGUAGE plpgsql AS $$ DECLARE ln 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.pushdown_margin', '1000', true); FOR ln IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF) ' || q LOOP IF ln ~ '(LionOrdered|LionBtreeScan|Ordered By:|Index:|Index Entries Walked|Lion Set|Heap Fetches|Rows Removed by|Switched)' THEN RETURN NEXT btrim(regexp_replace(ln, '\s*\(actual.*\)', '')); END IF; END LOOP; PERFORM set_config('enable_seqscan', 'on', true); PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('pg_lion.enable_plain_scan', 'on', true); PERFORM set_config('pg_lion.pushdown_margin', '1', true); END $$; /* * lion_bs_set() runs q through the node under EXPLAIN ANALYZE and prints * the node's mode, the set's kind, and whether the heap was read, rows were * removed by the recheck and the walk switched to fetch and sort - without * the numbers, which vary with the memory the set is given. */ CREATE FUNCTION lion_bs_set(q text) RETURNS SETOF text LANGUAGE plpgsql AS $$ DECLARE ln text; switched boolean := false; 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.pushdown_margin', '1000', true); FOR ln IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF) ' || q LOOP IF ln ~ '(Ordered By|Index):' THEN RETURN NEXT btrim(ln); ELSIF ln ~ 'Lion Set:' THEN RETURN NEXT 'Lion Set: ' || substring(ln from '(exact|rechecked)'); ELSIF ln ~ '(Heap Fetches|Rows Removed by Lion Recheck)' THEN RETURN NEXT substring(ln from '(Heap Fetches|Rows Removed by Lion Recheck)') || CASE WHEN ln ~ ': 0$' THEN ': 0' ELSE ': > 0' END; ELSIF ln ~ 'Switched to Fetch and Sort' THEN switched := true; END IF; END LOOP; RETURN NEXT CASE WHEN switched THEN 'Switched to Fetch and Sort' ELSE 'no switch' END; PERFORM set_config('enable_seqscan', 'on', true); PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('pg_lion.enable_plain_scan', 'on', true); PERFORM set_config('pg_lion.pushdown_margin', '1', true); END $$; /* * lion_bs_node() names the node the plan uses with nothing disabled, if any. */ CREATE FUNCTION lion_bs_node(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; BEGIN FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP IF ln ~ 'Custom Scan \(Lion' THEN RETURN substring(ln from 'Custom Scan \((Lion\w+)\)'); END IF; END LOOP; RETURN 'no Lion node'; END $$; -- 1. The plans, as EXPLAIN shows them: a covered btree qual with a lion -- filter, returning INCLUDE columns, with and without an ORDER BY; the -- same query reading a column the btree lacks walks in heap mode. SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) SELECT id, k, grp, x FROM bs WHERE k BETWEEN 1000 AND 3000 AND c200 = 17; QUERY PLAN --------------------------------------------- Custom Scan (LionBtreeScan) on bs Index: bs_k (index only) Index Cond: ((k >= 1000) AND (k <= 3000)) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) EXPLAIN (COSTS OFF) SELECT id, k, grp, x FROM bs WHERE k BETWEEN 1000 AND 3000 AND c200 = 17 ORDER BY k; QUERY PLAN --------------------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Cond: ((k >= 1000) AND (k <= 3000)) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) EXPLAIN (COSTS OFF) SELECT id, k, grp, x FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k DESC LIMIT 10; QUERY PLAN ------------------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (backward, index only) Lion Cond: ((c200 = 17) AND (c20 = 3)) Lion Indexes: bs_c200, bs_c20 (5 rows) EXPLAIN (COSTS OFF) SELECT id, k, grp, x, payload FROM bs WHERE k BETWEEN 1000 AND 3000 AND c200 = 17 ORDER BY k; QUERY PLAN --------------------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k Index Cond: ((k >= 1000) AND (k <= 3000)) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) EXPLAIN (COSTS OFF) SELECT sum(x), max(x) FROM bs WHERE tags @> ARRAY['t3']; QUERY PLAN --------------------------------------------- Aggregate -> Custom Scan (LionBtreeScan) on bs Index: bs_grp (index only) Lion Cond: (tags @> '{t3}'::text[]) Lion Indexes: bs_tags (5 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; -- 2. The answers against the ordinary plan: a covered `=` and ranges with a -- lion filter, IN lists on either side, a name column (a cstring in the -- btree), DESC with a LIMIT, OFFSET, an empty answer, a LIMIT beyond. SELECT lion_bs('SELECT id, k, grp, x FROM bs WHERE k BETWEEN 1000 AND 3000 AND c200 = 17'); lion_bs ---------------------------------- LionBtreeScan index only, 3 rows (1 row) SELECT lion_bs('SELECT id, k, grp, x FROM bs WHERE k BETWEEN 1000 AND 3000 AND c200 = 17 ORDER BY k', true); lion_bs -------------------------------- LionOrdered index only, 3 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE k = 4711 AND c20 = 7'); lion_bs ---------------------------------- LionBtreeScan index only, 0 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE k = 4711 AND c20 = (SELECT c20 FROM bs WHERE k = 4711)'); lion_bs ---------------------------------- LionBtreeScan index only, 1 rows (1 row) SELECT lion_bs('SELECT id, k, x, c200 FROM bs WHERE k = ANY (ARRAY[5, 50, 500, 5000, 50000, 99999]) AND c20 IN (3, 4, 5)'); lion_bs ---------------------------------- LionBtreeScan index only, 2 rows (1 row) SELECT lion_bs('SELECT id, k, c200, c20 FROM bs WHERE c200 IN (17, 18, 250) AND c20 = 3'); lion_bs ----------------------------------- LionBtreeScan index only, 54 rows (1 row) SELECT lion_bs('SELECT id, k, c200, c20 FROM bs WHERE c200 IN (17, 18, 250) AND c20 = 3 ORDER BY k', true); lion_bs --------------------------------- LionOrdered index only, 54 rows (1 row) SELECT lion_bs('SELECT id, k, nm FROM bs WHERE c200 = 17 AND nm = ''n17'' ORDER BY k', true); lion_bs -------------------------------- LionOrdered index only, 6 rows (1 row) SELECT lion_bs('SELECT id, k, nm FROM bs WHERE c200 = 17 AND nm > ''n4'' ORDER BY k DESC LIMIT 20', true); lion_bs --------------------------------- LionOrdered index only, 20 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k DESC LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT lion_bs('SELECT id, k FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10 OFFSET 20', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT lion_bs('SELECT id, k FROM bs WHERE c200 = -1 ORDER BY k LIMIT 10', true); lion_bs -------------------------------- LionOrdered index only, 0 rows (1 row) SELECT lion_bs('SELECT id, k FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k LIMIT 100000', true); lion_bs --------------------------------- LionOrdered index only, 26 rows (1 row) SELECT lion_bs('SELECT id, k FROM bs WHERE c200 = 17 AND c20 = 3 AND k > 90000'); lion_bs ---------------------------------- LionBtreeScan index only, 2 rows (1 row) -- 3. The aggregate shape: a full walk of the covering btree with no btree -- qual, only a lion filter - a scalar one and a multi-key one, exact -- both (DESIGN.md §29.6) - under a GROUP BY and under a plain aggregate. SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] GROUP BY grp'); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3'', ''u5''] GROUP BY grp ORDER BY grp', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT lion_bs('SELECT sum(x), max(x) FROM bs WHERE tags @> ARRAY[''t3'']'); lion_bs ---------------------------------- LionBtreeScan index only, 1 rows (1 row) SELECT lion_bs('SELECT grp, x FROM bs WHERE tags && ARRAY[''u5'', ''u6'']'); lion_bs ------------------------------------- LionBtreeScan index only, 5406 rows (1 row) SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] AND grp BETWEEN 10 AND 19 GROUP BY grp ORDER BY grp', true); lion_bs -------------------------------- LionOrdered index only, 1 rows (1 row) -- 4. The counters: on a table VACUUM has left all-visible nothing is read -- from the heap, under a scalar filter and under a multi-key one alike. SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10'); lion_bs_run --------------------------------------------------------------------- -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 3025 Lion Set Hits: 10 Heap Fetches: 0 Lion Set: 83 containers, exact, after 28 keys probed (probe budget) (6 rows) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k DESC'); lion_bs_run ----------------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k (backward, index only) Index Entries Walked: 86577 Lion Set Hits: 26 Heap Fetches: 0 Lion Set: 22 containers, exact (6 rows) SELECT * FROM lion_bs_run('SELECT grp, x FROM bs WHERE tags @> ARRAY[''t3'', ''u5'']'); lion_bs_run ----------------------------------- Custom Scan (LionBtreeScan) on bs Index: bs_grp (index only) Index Entries Walked: 93971 Lion Set Hits: 270 Heap Fetches: 0 Lion Set: 82 containers, exact (6 rows) SELECT * FROM lion_bs_run('SELECT sum(x) FROM bs WHERE tags @> ARRAY[''t3'']'); lion_bs_run --------------------------------------- -> Custom Scan (LionBtreeScan) on bs Index: bs_grp (index only) Index Entries Walked: 94000 Lion Set Hits: 10000 Heap Fetches: 0 Lion Set: 83 containers, exact (6 rows) -- 5. Pages not all-visible: rows inserted in this transaction are visited in -- the heap for their visibility (and counted), and so are updated and -- deleted rows' pages until VACUUM; after it nothing is. BEGIN; INSERT INTO bs SELECT 100000 + i, 100003 + i, i % 100, i, 17, 3, ARRAY['t3'], true, 'n0', 'n', 'x' FROM generate_series(1, 40) i; SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 AND k > 100000 ORDER BY k', true); lion_bs --------------------------------- LionOrdered index only, 40 rows (1 row) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE c200 = 17 AND k > 100000 ORDER BY k'); lion_bs_run -------------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 42 Lion Set Hits: 40 Heap Fetches: 40 Lion Set: lazy, 3 keys probed, exact (6 rows) COMMIT; UPDATE bs SET note = 'm' WHERE c200 = 17 AND id % 3 = 0; -- HOT UPDATE bs SET x = x + 1 WHERE c200 = 17 AND id % 5 = 0; -- an INCLUDE column: not HOT UPDATE bs SET c200 = 16 WHERE c200 = 17 AND id % 7 = 0; -- a lion column: not HOT DELETE FROM bs WHERE c200 = 17 AND id % 11 = 0; SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k', true); lion_bs ---------------------------------- LionOrdered index only, 423 rows (1 row) SELECT lion_bs('SELECT id, k, x, c200 FROM bs WHERE c200 IN (16, 17) AND k < 50000'); lion_bs ------------------------------------ LionBtreeScan index only, 480 rows (1 row) SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] GROUP BY grp ORDER BY grp', true); lion_bs --------------------------------- LionOrdered index only, 43 rows (1 row) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE c200 = 17 AND k > 100000 ORDER BY k'); lion_bs_run -------------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 39 Lion Set Hits: 31 Heap Fetches: 31 Lion Set: lazy, 4 keys probed, exact (6 rows) VACUUM (FREEZE) bs; SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k', true); lion_bs ---------------------------------- LionOrdered index only, 423 rows (1 row) SELECT lion_bs('SELECT id, k, x, c200 FROM bs WHERE c200 IN (16, 17) AND k < 50000'); lion_bs ------------------------------------ LionBtreeScan index only, 480 rows (1 row) SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] GROUP BY grp ORDER BY grp', true); lion_bs --------------------------------- LionOrdered index only, 43 rows (1 row) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE c200 = 17 AND k > 100000 ORDER BY k'); lion_bs_run -------------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 39 Lion Set Hits: 31 Heap Fetches: 0 Lion Set: lazy, 4 keys probed, exact (6 rows) ANALYZE bs; -- 6. Row locks: a row mark needs the row's ctid, which no index returns, so -- the walk is heap mode and EvalPlanQual rechecks a heap tuple. SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 5 FOR UPDATE; QUERY PLAN --------------------------------------------- Limit -> LockRows -> Custom Scan (LionOrdered) on bs Ordered By: bs_k Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (6 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 5 FOR UPDATE', true); lion_bs --------------------- LionOrdered, 5 rows (1 row) -- 7. Cursors, fetched in pieces, in both modes. SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) DECLARE bs_c CURSOR FOR SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 8; QUERY PLAN --------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) EXPLAIN (COSTS OFF) DECLARE bs_h CURSOR FOR SELECT id, k, left(payload, 8) FROM bs WHERE c200 = 17 ORDER BY k LIMIT 8; QUERY PLAN --------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_k Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) BEGIN; DECLARE bs_c CURSOR FOR SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 8; DECLARE bs_h CURSOR FOR SELECT id, k, left(payload, 8) FROM bs WHERE c200 = 17 ORDER BY k LIMIT 8; FETCH 3 FROM bs_c; id | k | x -------+-----+----- 51157 | 130 | 157 54794 | 669 | 794 10772 | 909 | 772 (3 rows) FETCH 3 FROM bs_h; id | k | left -------+-----+---------- 51157 | 130 | 9c33495b 54794 | 669 | 3e0f7533 10772 | 909 | 51ca7239 (3 rows) FETCH 2 FROM bs_c; id | k | x -------+------+----- 62472 | 927 | 472 32657 | 3025 | 657 (2 rows) FETCH ALL FROM bs_c; id | k | x -------+------+----- 84496 | 3751 | 496 41560 | 3767 | 561 39590 | 3805 | 591 (3 rows) FETCH ALL FROM bs_h; id | k | left -------+------+---------- 62472 | 927 | 8feb2aa4 32657 | 3025 | 6a46fc9c 84496 | 3751 | 3211c34e 41560 | 3767 | 298cb17c 39590 | 3805 | 3d1327c1 (5 rows) COMMIT; RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; -- 8. Params: a generic plan; a LATERAL subquery rescanned with the outer -- row's value in the lion filter (the set is rebuilt per outer row) and -- in the btree's quals (it is not); a correlated subquery without an -- ORDER BY, rescanned the same way. SET plan_cache_mode = force_generic_plan; PREPARE bs_p(int, int) AS SELECT id, k, x FROM bs WHERE c200 = $1 AND k > $2 ORDER BY k LIMIT 5; SELECT lion_bs('EXECUTE bs_p(17, 50000)', true, 'SELECT id, k, x FROM bs WHERE c200 = 17 AND k > 50000 ORDER BY k LIMIT 5'); lion_bs -------------------------------- LionOrdered index only, 5 rows (1 row) SELECT lion_bs('EXECUTE bs_p(18, 0)', true, 'SELECT id, k, x FROM bs WHERE c200 = 18 AND k > 0 ORDER BY k LIMIT 5'); lion_bs -------------------------------- LionOrdered index only, 5 rows (1 row) DEALLOCATE bs_p; RESET plan_cache_mode; SELECT lion_bs('SELECT o.v, x.id, x.k FROM (VALUES (17), (18), (250), (3)) o(v), LATERAL (SELECT id, k FROM bs WHERE c200 = o.v ORDER BY k LIMIT 3) x', true); lion_bs -------------------------------- LionOrdered index only, 9 rows (1 row) SELECT lion_bs('SELECT o.v, x.id, x.k FROM (VALUES (100), (50000), (99990)) o(v), LATERAL (SELECT id, k FROM bs WHERE c200 = 17 AND k > o.v ORDER BY k LIMIT 3) x', true); lion_bs -------------------------------- LionOrdered index only, 9 rows (1 row) SELECT lion_bs('SELECT o.v, (SELECT sum(x) FROM bs WHERE c200 = o.v AND k < 20000) FROM (VALUES (17), (18), (250)) o(v)'); lion_bs ---------------------------------- LionBtreeScan index only, 3 rows (1 row) SELECT * FROM lion_bs_run('SELECT o.v, x.id FROM (VALUES (17), (18), (250), (3)) o(v), LATERAL (SELECT id FROM bs WHERE c200 = o.v ORDER BY k LIMIT 3) x'); lion_bs_run ---------------------------------------------------------------------------------- -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 2038 Lion Set Hits: 9 Heap Fetches: 0 Lion Set: 82 containers, exact, 3 builds, after 82 keys probed (probe budget x3) (6 rows) SELECT * FROM lion_bs_run('SELECT o.v, x.id FROM (VALUES (100), (50000), (99990)) o(v), LATERAL (SELECT id FROM bs WHERE c200 = 17 AND k > o.v ORDER BY k LIMIT 3) x'); lion_bs_run --------------------------------------------------------------------- -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 1754 Lion Set Hits: 9 Heap Fetches: 0 Lion Set: 78 containers, exact, after 26 keys probed (probe budget) (6 rows) -- A LATERAL subquery pulled up from under an outer join, whose x.ov the -- scan of bs computes (a PlaceHolderVar, NULL where no row matches): every -- path of bs is parameterized by o, and the node's are not, so it offers -- none - the btree path it built for its ordered side named no outer -- relation, and core's assertion that it named o aborted the backend. SELECT lion_bs('SELECT o.v, x.id, x.ov FROM (VALUES (17), (18)) o(v) LEFT JOIN LATERAL (SELECT id, o.v AS ov FROM bs WHERE c200 = 17) x ON true'); lion_bs ------------------- no node, 846 rows (1 row) -- 9. A partial btree: its predicate's clause stays in the filter, so the -- predicate column must be covered too - it is in bs_part and not in -- bs_part_nf, whose walk is heap mode. SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) SELECT id, k, x FROM bs WHERE flag AND c200 = 17 ORDER BY k LIMIT 10; QUERY PLAN ------------------------------------------ Limit -> Custom Scan (LionOrdered) on bs Filter: flag Ordered By: bs_part (index only) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (6 rows) EXPLAIN (COSTS OFF) SELECT id, x FROM bs WHERE flag AND c200 = 17 ORDER BY x LIMIT 10; QUERY PLAN --------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Filter: flag Ordered By: bs_part_nf Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (6 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; SELECT lion_bs('SELECT id, k, x FROM bs WHERE flag AND c200 = 17 ORDER BY k LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT lion_bs('SELECT id, x FROM bs WHERE flag AND c200 = 17 ORDER BY x LIMIT 10', true); lion_bs ---------------------- LionOrdered, 10 rows (1 row) SELECT lion_bs('SELECT id, x FROM bs WHERE flag AND c200 = 17 AND x < 100'); lion_bs ----------------------------------- LionBtreeScan index only, 39 rows (1 row) -- 10. An expression btree gives the order and no value: heap mode. SELECT lion_bs('SELECT id, k % 1000 FROM bs WHERE c200 = 17 ORDER BY k % 1000, id LIMIT 10', true); lion_bs ---------------------- LionOrdered, 10 rows (1 row) -- 11. The settings: without index-only scans there is no index-only mode -- and no unordered walk; pg_lion.enable_btree_scan gates the unordered -- walks alone, pg_lion.enable_ordered_scan the claimed orders alone. SET enable_indexonlyscan = off; SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10', true); lion_bs ---------------------- LionOrdered, 10 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE k BETWEEN 1000 AND 9000 AND c200 = 17'); lion_bs ------------------ no node, 21 rows (1 row) RESET enable_indexonlyscan; SET pg_lion.enable_btree_scan = off; SELECT lion_bs('SELECT id, k, x FROM bs WHERE k BETWEEN 1000 AND 9000 AND c200 = 17'); lion_bs ------------------ no node, 21 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) RESET pg_lion.enable_btree_scan; SET pg_lion.enable_ordered_scan = off; SELECT lion_bs('SELECT id, k, x FROM bs WHERE k BETWEEN 1000 AND 9000 AND c200 = 17'); lion_bs ----------------------------------- LionBtreeScan index only, 21 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10', true); lion_bs ----------------------------------- LionBtreeScan index only, 10 rows (1 row) SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] GROUP BY grp'); lion_bs ----------------------------------- LionBtreeScan index only, 43 rows (1 row) RESET pg_lion.enable_ordered_scan; -- 12. The plan choice, with nothing disabled: the index-only node for a lion -- filter under ORDER BY a btree column LIMIT 10 when the btree lacks the -- filter's column; when it holds it, core's own Index Only Scan with the -- filter walks the same entries for one cpu_operator_cost each where the -- node's probe costs two cpu_tuple_costs more (DESIGN.md §40.3), and is -- chosen - the two run in the same time here; the heap-mode node when a -- column is not covered; the bitmap scan and Sort when the filter is so -- selective that the walk to a tenth member is long; the aggregate shape -- through core's filtered Index Only Scan when the btree holds the -- filter column, and otherwise through the bitmap scan or the lion -- index's own scan - on a heap of 4,350 pages the probes of a full -- covering walk cost more than the heap pages it saves; a covered btree -- qual with a lion filter the same way. SELECT * FROM lion_bs_plan('SELECT grp, x FROM bs WHERE c200 = 17 ORDER BY grp LIMIT 10'); lion_bs_plan ----------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_grp (index only) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) SELECT * FROM lion_bs_plan('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10'); lion_bs_plan ---------------------------------------- Limit -> Index Only Scan using bs_k on bs Filter: (c200 = 17) (3 rows) SELECT * FROM lion_bs_plan('SELECT id, k, x, payload FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10'); lion_bs_plan --------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_k Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) SELECT * FROM lion_bs_plan('SELECT id, k, x FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k LIMIT 10'); lion_bs_plan --------------------------------------------------------- Limit -> Sort Sort Key: k -> Bitmap Heap Scan on bs Recheck Cond: ((c200 = 17) AND (c20 = 3)) -> BitmapAnd -> Bitmap Index Scan on bs_c200 Index Cond: (c200 = 17) -> Bitmap Index Scan on bs_c20 Index Cond: (c20 = 3) (10 rows) SELECT * FROM lion_bs_plan('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] GROUP BY grp'); lion_bs_plan ------------------------------------------ GroupAggregate Group Key: grp -> Index Only Scan using bs_grp on bs Filter: (tags @> '{t3}'::text[]) (4 rows) SELECT * FROM lion_bs_plan('SELECT sum(x) FROM bs WHERE tags @> ARRAY[''t3'']'); lion_bs_plan ------------------------------------------ Aggregate -> Index Only Scan using bs_grp on bs Filter: (tags @> '{t3}'::text[]) (3 rows) SELECT * FROM lion_bs_plan('SELECT grp, sum(x) FROM bs WHERE c20 = 3 GROUP BY grp'); lion_bs_plan ------------------------------------- HashAggregate Group Key: grp -> Index Scan using bs_c20 on bs Index Cond: (c20 = 3) (4 rows) SELECT * FROM lion_bs_plan('SELECT sum(x) FROM bs WHERE c20 IN (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)'); lion_bs_plan ----------------------------------------------------------------------------- Aggregate -> Bitmap Heap Scan on bs Recheck Cond: (c20 = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[])) -> Bitmap Index Scan on bs_c20 Index Cond: (c20 = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[])) (5 rows) SELECT * FROM lion_bs_plan('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3'', ''u5''] GROUP BY grp'); lion_bs_plan ------------------------------------------------- HashAggregate Group Key: grp -> Index Scan using bs_tags on bs Index Cond: (tags @> '{t3,u5}'::text[]) (4 rows) SELECT * FROM lion_bs_plan('SELECT id, k, x FROM bs WHERE k BETWEEN 1000 AND 9000 AND c200 = 17'); lion_bs_plan --------------------------------------------- Index Only Scan using bs_k on bs Index Cond: ((k >= 1000) AND (k <= 9000)) Filter: (c200 = 17) (3 rows) -- 13. A btree that lacks the lion filter's columns covers the query all the -- same (DESIGN.md §40.1): an exact set - a multi-key AND or OR of whole -- keys included (§29.6) - needs no recheck, and a set that turns out -- inexact at run time is rechecked on the heap tuple, -- fetched for that alone and counted. Lion marks no clause lossy at -- plan time, so a tsquery prefix or NOT - a superset, rechecked on every -- member - walks index-only too, reading the heap for each member as -- heap mode would. SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) SELECT grp, x FROM bs WHERE c200 = 17 ORDER BY grp LIMIT 10; QUERY PLAN ----------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_grp (index only) Lion Cond: (c200 = 17) Lion Indexes: bs_c200 (5 rows) EXPLAIN (COSTS OFF) SELECT id, k, x FROM bs WHERE tags @> ARRAY['t3'] ORDER BY k LIMIT 10; QUERY PLAN --------------------------------------------- Limit -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Lion Cond: (tags @> '{t3}'::text[]) Lion Indexes: bs_tags (5 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; -- an exact set: the heap is not read SELECT lion_bs('SELECT grp, x FROM bs WHERE c200 = 17 ORDER BY grp LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT * FROM lion_bs_run('SELECT grp, x FROM bs WHERE c200 = 17 ORDER BY grp LIMIT 10'); lion_bs_run --------------------------------------------------------------------- -> Custom Scan (LionOrdered) on bs Ordered By: bs_grp (index only) Index Entries Walked: 1939 Lion Set Hits: 10 Heap Fetches: 0 Lion Set: 78 containers, exact, after 77 keys probed (probe budget) (6 rows) SELECT lion_bs('SELECT grp, sum(x) FROM bs WHERE c20 = 3 GROUP BY grp ORDER BY grp', true); lion_bs ---------------------------------- LionOrdered index only, 100 rows (1 row) SELECT * FROM lion_bs_run('SELECT grp, sum(x) FROM bs WHERE c20 = 3 GROUP BY grp ORDER BY grp'); lion_bs_run ------------------------------------- -> Custom Scan (LionOrdered) on bs Ordered By: bs_grp (index only) Index Entries Walked: 99979 Lion Set Hits: 4987 Heap Fetches: 0 Lion Set: 83 containers, exact (6 rows) -- a multi-key filter over a btree without its column: exact as well, and -- the heap is not read either SELECT lion_bs('SELECT id, k, x FROM bs WHERE tags @> ARRAY[''t3''] ORDER BY k LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE tags @> ARRAY[''t3''] ORDER BY k LIMIT 10'); lion_bs_run ------------------------------------- -> Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 96 Lion Set Hits: 10 Heap Fetches: 0 Lion Set: 83 containers, exact (6 rows) SELECT lion_bs('SELECT id, k, x FROM bs WHERE tags @> ARRAY[''t3'', ''u5''] AND k > 50000'); lion_bs ------------------------------------ LionBtreeScan index only, 134 rows (1 row) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE tags @> ARRAY[''t3'', ''u5''] AND k > 50000'); lion_bs_run ----------------------------------- Custom Scan (LionBtreeScan) on bs Index: bs_k (index only) Index Entries Walked: 50022 Lion Set Hits: 134 Heap Fetches: 0 Lion Set: 83 containers, exact (6 rows) -- rows not all-visible: fetched for their visibility, nothing to recheck BEGIN; INSERT INTO bs SELECT 200000 + i, 200003 + i, i % 100, i, 17, 3, ARRAY['t3', 'u5'], true, 'n0', 'n', 'x' FROM generate_series(1, 20) i; SELECT lion_bs('SELECT id, k, x FROM bs WHERE tags @> ARRAY[''t3'', ''u5''] AND k > 200000 ORDER BY k', true); lion_bs --------------------------------- LionOrdered index only, 20 rows (1 row) SELECT * FROM lion_bs_run('SELECT id, k, x FROM bs WHERE tags @> ARRAY[''t3'', ''u5''] AND k > 200000 ORDER BY k'); lion_bs_run --------------------------------- Custom Scan (LionOrdered) on bs Ordered By: bs_k (index only) Index Entries Walked: 20 Lion Set Hits: 20 Heap Fetches: 20 Lion Set: 83 containers, exact (6 rows) ROLLBACK; -- the rolled-back rows landed one to a page: a VACUUM that skips the indexes -- (few pages with dead items) would leave their dead items, and those pages -- not all-visible, so the index cleanup is forced VACUUM (FREEZE, INDEX_CLEANUP ON) bs; -- a set that outgrows hash_mem at run time spills and stays exact: nothing -- is rechecked, and the heap is not read (ordered.sql, section 10: the -- table that does, its plan made at 64MB and kept, run at 64kB) CREATE TABLE bsd (id int PRIMARY KEY, k int, c2 int, pad text) WITH (autovacuum_enabled = off); INSERT INTO bsd SELECT i, (i::bigint * 7919 % 400009)::int, ((hashint8extended(i::bigint, 11) & 9223372036854775807) % 2)::int, repeat('x', 80) FROM generate_series(1, 400000) i; CREATE INDEX bsd_k ON bsd (k) INCLUDE (id); CREATE INDEX bsd_c2 ON bsd USING lion (c2); VACUUM (FREEZE, ANALYZE) bsd; PREPARE bs_deg AS SELECT id, k FROM bsd WHERE c2 = 1 ORDER BY k LIMIT 20; SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) EXECUTE bs_deg; QUERY PLAN ---------------------------------------- Limit -> Custom Scan (LionOrdered) on bsd Ordered By: bsd_k (index only) Lion Cond: (c2 = 1) Lion Indexes: bsd_c2 (5 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; SET work_mem = '64kB'; SET hash_mem_multiplier = 1; SET pg_lion.enable_lazy_set = off; SELECT * FROM lion_bs_set('EXECUTE bs_deg'); lion_bs_set -------------------------------- Ordered By: bsd_k (index only) Heap Fetches: 0 Lion Set: exact no switch (4 rows) SELECT lion_bs('EXECUTE bs_deg', true, 'SELECT id, k FROM bsd WHERE c2 = 1 ORDER BY k LIMIT 20'); lion_bs --------------------------------- LionOrdered index only, 20 rows (1 row) RESET pg_lion.enable_lazy_set; RESET hash_mem_multiplier; RESET work_mem; DEALLOCATE bs_deg; DROP TABLE bsd; -- a tsquery: an AND of lexemes is exact; a prefix or a NOT widens the set to -- a superset, and every member is rechecked on its heap tuple CREATE TABLE bst (id int PRIMARY KEY, k int NOT NULL, tsv tsvector) WITH (autovacuum_enabled = off); INSERT INTO bst SELECT i, (i * 7919) % 20011, to_tsvector('simple', 'w' || (i % 50) || ' x' || (i % 7) || ' y' || (i % 3)) FROM generate_series(1, 20000) i; CREATE INDEX bst_k ON bst (k) INCLUDE (id); CREATE INDEX bst_tsv ON bst USING lion (tsv); VACUUM (FREEZE, ANALYZE) bst; SELECT lion_bs($$SELECT id, k FROM bst WHERE tsv @@ 'w3 & x5'::tsquery ORDER BY k LIMIT 5$$, true); lion_bs -------------------------------- LionOrdered index only, 5 rows (1 row) SELECT * FROM lion_bs_run($$SELECT id, k FROM bst WHERE tsv @@ 'w3 & x5'::tsquery ORDER BY k LIMIT 5$$); lion_bs_run -------------------------------------- -> Custom Scan (LionOrdered) on bst Ordered By: bst_k (index only) Index Entries Walked: 1023 Lion Set Hits: 5 Heap Fetches: 0 Lion Set: 3 containers, exact (6 rows) SELECT lion_bs($$SELECT id, k FROM bst WHERE tsv @@ 'w3:*'::tsquery ORDER BY k LIMIT 5$$, true); lion_bs -------------------------------- LionOrdered index only, 5 rows (1 row) SELECT * FROM lion_bs_run($$SELECT id, k FROM bst WHERE tsv @@ 'w3:*'::tsquery ORDER BY k LIMIT 5$$); lion_bs_run -------------------------------------- -> Custom Scan (LionOrdered) on bst Ordered By: bst_k (index only) Index Entries Walked: 19 Lion Set Hits: 5 Heap Fetches: 0 Lion Set: 3 containers, exact (6 rows) SELECT lion_bs($$SELECT id, k FROM bst WHERE tsv @@ '!w3'::tsquery ORDER BY k LIMIT 5$$, true); lion_bs -------------------------------- LionOrdered index only, 5 rows (1 row) SELECT * FROM lion_bs_run($$SELECT id, k FROM bst WHERE tsv @@ '!w3'::tsquery ORDER BY k LIMIT 5$$); lion_bs_run -------------------------------------- -> Custom Scan (LionOrdered) on bst Ordered By: bst_k (index only) Index Entries Walked: 5 Lion Set Hits: 5 Heap Fetches: 5 Rows Removed by Lion Recheck: 0 Lion Set: 3 containers, rechecked (7 rows) -- rows not all-visible on an inexact set: fetched once, for their visibility -- and for the recheck both BEGIN; INSERT INTO bst SELECT 20000 + i, 30000 + i, to_tsvector('simple', 'w3 x' || (i % 7) || ' y0') FROM generate_series(1, 20) i; SELECT lion_bs($$SELECT id, k FROM bst WHERE tsv @@ 'w3:*'::tsquery AND k > 30000 ORDER BY k$$, true); lion_bs --------------------------------- LionOrdered index only, 20 rows (1 row) SELECT * FROM lion_bs_run($$SELECT id, k FROM bst WHERE tsv @@ 'w3:*'::tsquery AND k > 30000 ORDER BY k$$); lion_bs_run ---------------------------------- Custom Scan (LionOrdered) on bst Ordered By: bst_k (index only) Index Entries Walked: 20 Lion Set Hits: 20 Heap Fetches: 20 Lion Set: 3 containers, exact (6 rows) ROLLBACK; DROP TABLE bst; -- 14. The fetch-and-sort switch in index-only mode (DESIGN.md §40.4): a -- filter whose members all sit at the far end of the order switches, -- after pg_lion.ordered_switch_ratio entries per member, and reads the -- heap for them; a large ratio keeps it walking; a uniform filter's walk -- to its end never switches and reads nothing from the heap, where in -- heap mode (a system column in the target) it switches as before. CREATE TABLE bsh (id int PRIMARY KEY, k int NOT NULL, c int, x int) WITH (autovacuum_enabled = off); INSERT INTO bsh SELECT i, i, CASE WHEN i > 98000 THEN 1 ELSE 0 END, i % 100 FROM generate_series(1, 100000) i; CREATE INDEX bsh_k ON bsh (k) INCLUDE (id, x); CREATE INDEX bsh_c ON bsh USING lion (c); VACUUM (FREEZE, ANALYZE) bsh; SELECT lion_bs('SELECT id, x FROM bsh WHERE c = 1 ORDER BY k LIMIT 10', true); lion_bs --------------------------------- LionOrdered index only, 10 rows (1 row) SELECT * FROM lion_bs_set('SELECT id, x FROM bsh WHERE c = 1 ORDER BY k LIMIT 10'); lion_bs_set -------------------------------- Ordered By: bsh_k (index only) Heap Fetches: > 0 Lion Set: exact Switched to Fetch and Sort (4 rows) SET pg_lion.ordered_switch_ratio = 1000000; SELECT * FROM lion_bs_set('SELECT id, x FROM bsh WHERE c = 1 ORDER BY k LIMIT 10'); lion_bs_set -------------------------------- Ordered By: bsh_k (index only) Heap Fetches: 0 Lion Set: exact no switch (4 rows) RESET pg_lion.ordered_switch_ratio; SELECT * FROM lion_bs_set('SELECT grp, sum(x) FROM bs WHERE tags @> ARRAY[''t3''] GROUP BY grp ORDER BY grp'); lion_bs_set --------------------------------- Ordered By: bs_grp (index only) Heap Fetches: 0 Lion Set: exact no switch (4 rows) SELECT * FROM lion_bs_set('SELECT id, k, x FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k DESC'); lion_bs_set ----------------------------------------- Ordered By: bs_k (backward, index only) Heap Fetches: 0 Lion Set: exact no switch (4 rows) SELECT * FROM lion_bs_set('SELECT id, k, x, ctid FROM bs WHERE c200 = 17 AND c20 = 3 ORDER BY k DESC'); lion_bs_set ----------------------------- Ordered By: bs_k (backward) Heap Fetches: > 0 Lion Set: exact Switched to Fetch and Sort (4 rows) DROP TABLE bsh; -- 15. NULLs in the columns returned, a NULL name among them; a btree column -- DESC NULLS FIRST, walked both ways; a dropped column, so that the -- mapping's attnos have a gap. CREATE TABLE bsn (id int PRIMARY KEY, grp int, dropme text, x int, nm name, c int) WITH (autovacuum_enabled = off); INSERT INTO bsn SELECT i, CASE WHEN i % 7 = 0 THEN NULL ELSE i % 5 END, 'd', CASE WHEN i % 11 = 0 THEN NULL ELSE i END, CASE WHEN i % 13 = 0 THEN NULL ELSE ('n' || i % 3)::name END, i % 4 FROM generate_series(1, 3000) i; ALTER TABLE bsn DROP COLUMN dropme; CREATE INDEX bsn_grp ON bsn (grp DESC NULLS FIRST, id) INCLUDE (x, nm); CREATE INDEX bsn_c ON bsn USING lion (c); VACUUM (FREEZE, ANALYZE) bsn; SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) SELECT grp, x, nm FROM bsn WHERE c = 1 ORDER BY grp DESC NULLS FIRST, id LIMIT 12; QUERY PLAN ------------------------------------------ Limit -> Custom Scan (LionOrdered) on bsn Ordered By: bsn_grp (index only) Lion Cond: (c = 1) Lion Indexes: bsn_c (5 rows) SELECT grp, x, nm FROM bsn WHERE c = 1 ORDER BY grp DESC NULLS FIRST, id LIMIT 6; grp | x | nm -----+-----+---- | 21 | n0 | 49 | n1 | | n2 | 105 | n0 | 133 | n1 | 161 | n2 (6 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; SELECT lion_bs('SELECT grp, x, nm FROM bsn WHERE c = 1 ORDER BY grp DESC NULLS FIRST, id LIMIT 12', true); lion_bs --------------------------------- LionOrdered index only, 12 rows (1 row) SELECT lion_bs('SELECT grp, x, nm FROM bsn WHERE c = 1 ORDER BY grp NULLS LAST, id DESC LIMIT 12', true); lion_bs --------------------------------- LionOrdered index only, 12 rows (1 row) SELECT lion_bs('SELECT id, x, nm FROM bsn WHERE c = 1 AND grp IS NULL'); lion_bs ------------------------------------ LionBtreeScan index only, 107 rows (1 row) SELECT lion_bs('SELECT id, grp FROM bsn WHERE c = 1 AND nm IS NULL ORDER BY grp DESC NULLS FIRST, id LIMIT 5', true); lion_bs -------------------------------- LionOrdered index only, 5 rows (1 row) SELECT lion_bs('SELECT id, grp, x FROM bsn WHERE c = 1 AND x IS NULL ORDER BY grp DESC NULLS FIRST, id', true); lion_bs --------------------------------- LionOrdered index only, 68 rows (1 row) SELECT lion_bs('SELECT grp, count(*), count(x), count(nm) FROM bsn WHERE c IN (1, 2) GROUP BY grp ORDER BY grp DESC NULLS FIRST', true); lion_bs -------------------------------- LionOrdered index only, 6 rows (1 row) DROP TABLE bsn; -- 16. A system column or a whole-row Var in the target is heap mode; with -- both settings off there is no node; a SCROLL cursor fetched backward -- over the index-only node (core's Material above it). SELECT lion_bs('SELECT ctid, id, k FROM bs WHERE c200 = 17 ORDER BY k LIMIT 5', true); lion_bs --------------------- LionOrdered, 5 rows (1 row) SELECT lion_bs('SELECT tableoid::regclass, id FROM bs WHERE c200 = 17 ORDER BY k LIMIT 5', true); lion_bs --------------------- LionOrdered, 5 rows (1 row) SELECT lion_bs('SELECT bs FROM bs WHERE c200 = 17 ORDER BY k LIMIT 5', true); lion_bs --------------------- LionOrdered, 5 rows (1 row) SET pg_lion.enable_ordered_scan = off; SET pg_lion.enable_btree_scan = off; SELECT lion_bs('SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 10', true); lion_bs ------------------ no node, 10 rows (1 row) SELECT lion_bs('SELECT id, k, x FROM bs WHERE k BETWEEN 1000 AND 9000 AND c200 = 17'); lion_bs ------------------ no node, 21 rows (1 row) RESET pg_lion.enable_ordered_scan; RESET pg_lion.enable_btree_scan; BEGIN; SET LOCAL enable_seqscan = off; SET LOCAL enable_bitmapscan = off; SET LOCAL pg_lion.enable_plain_scan = off; SET LOCAL pg_lion.pushdown_margin = 1000; DECLARE bs_s SCROLL CURSOR FOR SELECT id, k, x FROM bs WHERE c200 = 17 ORDER BY k LIMIT 8; FETCH 5 FROM bs_s; id | k | x -------+------+----- 51157 | 130 | 157 54794 | 669 | 794 10772 | 909 | 772 62472 | 927 | 472 32657 | 3025 | 657 (5 rows) FETCH BACKWARD 3 FROM bs_s; id | k | x -------+-----+----- 62472 | 927 | 472 10772 | 909 | 772 54794 | 669 | 794 (3 rows) FETCH ALL FROM bs_s; id | k | x -------+------+----- 10772 | 909 | 772 62472 | 927 | 472 32657 | 3025 | 657 84496 | 3751 | 496 41560 | 3767 | 561 39590 | 3805 | 591 (6 rows) COMMIT; -- 17. The pairs that add nothing (DESIGN.md §40.2): a lion index clause the -- btree's own clauses spell already - an OR of equalities included, -- which 18 and later match to each index as a `k = ANY` of its own - is -- not offered, with core's scans enabled or disabled (the plan's text -- varies between majors, so only the node's presence is printed); a -- partial lion index walked whole, with no clauses of its own, adds its -- predicate's selectivity and is offered. Before 18 the OR is no clause -- of the btree's, so the lion index's restricts the walk and the pair is -- offered, and forced where lion's paths are. CREATE TABLE bso (id int, k int, c int, flag bool) WITH (autovacuum_enabled = off); INSERT INTO bso SELECT i, i % 1000, i % 10, i % 3 = 0 FROM generate_series(1, 30000) i; CREATE INDEX bso_k ON bso (k) INCLUDE (id, c); CREATE INDEX bso_k_lion ON bso USING lion (k); CREATE INDEX bso_c_part ON bso USING lion (c) WHERE flag; VACUUM (FREEZE, ANALYZE) bso; SELECT lion_bs_node('SELECT id, k FROM bso WHERE k = 1 OR k = 7'); lion_bs_node -------------- no Lion node (1 row) SELECT lion_bs_node('SELECT id, k FROM bso WHERE k IN (1, 7)'); lion_bs_node -------------- no Lion node (1 row) SELECT lion_bs_node('SELECT id, k FROM bso WHERE k BETWEEN 10 AND 20'); lion_bs_node -------------- no Lion node (1 row) SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; SELECT lion_bs_node('SELECT id, k FROM bso WHERE k = 1 OR k = 7') = CASE WHEN current_setting('server_version_num')::int >= 180000 THEN 'no Lion node' ELSE 'LionBtreeScan' END AS or_as_the_major_matches_it; or_as_the_major_matches_it ---------------------------- t (1 row) SELECT lion_bs_node('SELECT id, k FROM bso WHERE k IN (1, 7)'); lion_bs_node -------------- no Lion node (1 row) SELECT lion_bs_node('SELECT id, k FROM bso WHERE flag AND k BETWEEN 10 AND 500'); lion_bs_node --------------- LionBtreeScan (1 row) EXPLAIN (COSTS OFF) SELECT id, k FROM bso WHERE flag AND k BETWEEN 10 AND 500; QUERY PLAN ------------------------------------------ Custom Scan (LionBtreeScan) on bso Index: bso_k (index only) Index Cond: ((k >= 10) AND (k <= 500)) Lion Cond: flag Lion Indexes: bso_c_part (5 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; SELECT lion_bs('SELECT id, k FROM bso WHERE k = 1 OR k = 7') = CASE WHEN current_setting('server_version_num')::int >= 180000 THEN 'no node, 60 rows' ELSE 'LionBtreeScan index only, 60 rows' END AS or_as_the_major_matches_it; or_as_the_major_matches_it ---------------------------- t (1 row) SELECT lion_bs('SELECT id, k FROM bso WHERE flag AND k BETWEEN 10 AND 500'); lion_bs ------------------------------------- LionBtreeScan index only, 4910 rows (1 row) DROP TABLE bso; -- 18. A clause core's AND leaves out (DESIGN.md §40.2): beside -- `c20 IN (1, 2)`, `c3 IN (0, 1)` keeps two thirds of the rows, and core -- leaves it out of its BitmapAnd for the bitmap heap scan's Filter to -- test on the heap tuple; a walk of `(k) INCLUDE (id)`, which lacks c3, -- would have to fetch every member's tuple to test it. So the AND of -- both lion accesses is offered too, and the walk is index only - with -- nothing disabled for the aggregate, over the heap scan, and ordered, a -- btree filter beside it, an OR spelling the IN list, a `<>` that keeps -- nearly every row. The price decides: for the first 50 in order, the -- walk over core's smaller set, fetching the few members' tuples, is the -- cheaper. A walk that reads the heap anyway - a column the btree lacks -- in the target - keeps core's access, and a clause no lion access -- answers is the Filter's whatever the set. CREATE TABLE bsc (id int, k int, c3 int, c20 int, payload text) WITH (autovacuum_enabled = off); INSERT INTO bsc SELECT i, (i * 7919) % 60011, (hashint4(i) & 1023) % 3, (hashint4(i + 1) & 1023) % 20, repeat('p', 400) FROM generate_series(1, 60000) i; CREATE INDEX bsc_k ON bsc (k) INCLUDE (id); CREATE INDEX bsc_c3 ON bsc USING lion (c3); CREATE INDEX bsc_c20 ON bsc USING lion (c20); VACUUM (FREEZE, ANALYZE) bsc; SELECT * FROM lion_bs_plan('SELECT sum(id) FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1)'); lion_bs_plan ------------------------------------------------------------------------------------------- Aggregate -> Custom Scan (LionBtreeScan) on bsc Index: bsc_k (index only) Lion Cond: ((c20 = ANY ('{1,2}'::integer[])) AND (c3 = ANY ('{0,1}'::integer[]))) Lion Indexes: bsc_c20, bsc_c3 (5 rows) SELECT * FROM lion_bs_run('SELECT sum(id) FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1)'); lion_bs_run ---------------------------------------- -> Custom Scan (LionBtreeScan) on bsc Index: bsc_k (index only) Index Entries Walked: 59999 Lion Set Hits: 4051 Heap Fetches: 0 Lion Set: 53 containers, exact (6 rows) SELECT lion_bs('SELECT id FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1)'); lion_bs ------------------------------------- LionBtreeScan index only, 4051 rows (1 row) SELECT lion_bs('SELECT sum(id), count(*) FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1)'); lion_bs ---------------------------------- LionBtreeScan index only, 1 rows (1 row) SELECT lion_bs('SELECT id, k FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1) ORDER BY k LIMIT 50', true); lion_bs ---------------------- LionOrdered, 50 rows (1 row) SELECT lion_bs('SELECT id, k FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1) ORDER BY k DESC', true); lion_bs ----------------------------------- LionOrdered index only, 4051 rows (1 row) SELECT lion_bs('SELECT id FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1) AND k % 7 = 1'); lion_bs ------------------------------------ LionBtreeScan index only, 579 rows (1 row) SELECT lion_bs('SELECT id, k FROM bsc WHERE c20 IN (1, 2) AND (c3 = 0 OR c3 = 1) ORDER BY k', true); lion_bs ----------------------------------- LionOrdered index only, 4051 rows (1 row) SELECT lion_bs('SELECT id FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1) AND c20 <> 9'); lion_bs ------------------------------------- LionBtreeScan index only, 4051 rows (1 row) SET enable_seqscan = off; SET enable_bitmapscan = off; SET pg_lion.enable_plain_scan = off; SET pg_lion.pushdown_margin = 1000; EXPLAIN (COSTS OFF) SELECT id, k, c3 FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1) ORDER BY k; QUERY PLAN ----------------------------------------------- Custom Scan (LionOrdered) on bsc Filter: (c3 = ANY ('{0,1}'::integer[])) Ordered By: bsc_k Lion Cond: (c20 = ANY ('{1,2}'::integer[])) Lion Indexes: bsc_c20 (5 rows) EXPLAIN (COSTS OFF) SELECT id, k FROM bsc WHERE c20 IN (1, 2) AND c3 + 0 = 1 ORDER BY k; QUERY PLAN ----------------------------------------------- Custom Scan (LionOrdered) on bsc Filter: ((c3 + 0) = 1) Ordered By: bsc_k Lion Cond: (c20 = ANY ('{1,2}'::integer[])) Lion Indexes: bsc_c20 (5 rows) RESET enable_seqscan; RESET enable_bitmapscan; RESET pg_lion.enable_plain_scan; RESET pg_lion.pushdown_margin; SELECT lion_bs('SELECT id, k, c3 FROM bsc WHERE c20 IN (1, 2) AND c3 IN (0, 1) ORDER BY k', true); lion_bs ------------------------ LionOrdered, 4051 rows (1 row) SELECT lion_bs('SELECT id, k FROM bsc WHERE c20 IN (1, 2) AND c3 + 0 = 1 ORDER BY k', true); lion_bs ------------------------ LionOrdered, 2007 rows (1 row) DROP TABLE bsc; DROP TABLE bs; DROP FUNCTION lion_bs(text, boolean, text); DROP FUNCTION lion_bs_plan(text); DROP FUNCTION lion_bs_run(text); DROP FUNCTION lion_bs_set(text); DROP FUNCTION lion_bs_node(text);