-- Every transition of a LionOrdered scan (DESIGN.md §30.4), forced and
-- named: EXPLAIN ANALYZE says why a lazy set was built, how the switch to
-- fetch-and-sort sorted, and when the early stop ended a walk - at every
-- work_mem, the walk's record of the members it met spilling with the set
-- past hash_mem.  Each run's rows are compared, in order, with the same
-- query with the node off.
--
-- Not forced here: building a lazy set because the switch could be due by
-- the set's recorded member count: ordered.sql forces that (case 15).
\set VERBOSITY terse
SET client_min_messages = warning;
CREATE EXTENSION IF NOT EXISTS pg_lion;
RESET client_min_messages;
SET synchronous_commit = on;
SET max_parallel_workers_per_gather = 0;
-- a: 7 values in heap order's period, b: 10 by hash; k: a permutation of
-- the ids with a btree, in no heap order; the primary key in heap order
CREATE TABLE otr (id int PRIMARY KEY, k int, a int, b int, pad text)
	WITH (autovacuum_enabled = off);
INSERT INTO otr SELECT i, (i::bigint * 7919 % 200003)::int, i % 7,
	   (hashint4(i) & 1023) % 10, repeat('x', 40)
  FROM generate_series(1, 200000) i;
CREATE INDEX otr_l ON otr USING lion (a, b);
CREATE INDEX otr_k ON otr (k, id);
-- the heap in eight interleaved sweeps: a walk of one meets a new container
-- key every 700 entries or so, where one in heap order meets one every 5,500
CREATE INDEX otr_m ON otr ((id % 8), id);
VACUUM (FREEZE, ANALYZE) otr;
-- the node's counters for q, which must be a LionOrdered plan
CREATE FUNCTION otr_run(q text) RETURNS SETOF text LANGUAGE plpgsql AS $$
DECLARE ln text; used bool := false;
BEGIN
	FOR ln IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF) ' || q LOOP
		IF ln ~ 'Custom Scan \(LionOrdered\)' THEN
			used := true;
		ELSIF ln ~ '(Index Entries Walked|Lion Set:|Switched|Fetch and Sort (Method|Space Type)|Stopped Early)' THEN
			-- one external sort or another, as the major's tuplesort runs it
			RETURN NEXT btrim(regexp_replace(ln, 'external (sort|merge)', 'external'));
		END IF;
	END LOOP;
	IF NOT used THEN
		RETURN NEXT 'not LionOrdered';
	END IF;
END $$;
-- q's rows in order against the same query with the node off and sorting on
-- (a hash of the hash so far and the row: 100,000 rows in a string grown a
-- row at a time would be copied 100,000 times)
CREATE FUNCTION otr_rows(q text) RETURNS text LANGUAGE plpgsql AS $$
DECLARE r record; acc text := '';
BEGIN
	FOR r IN EXECUTE q LOOP
		acc := md5(acc || r::text);
	END LOOP;
	RETURN acc;
END $$;
CREATE FUNCTION otr_same(q text, ordinary text) RETURNS text
LANGUAGE plpgsql AS $$
DECLARE a text := otr_rows(q); b text;
BEGIN
	SET LOCAL pg_lion.enable_ordered_scan = off;
	SET LOCAL enable_sort = on;
	SET LOCAL enable_seqscan = on;
	b := otr_rows(ordinary);
	RETURN CASE WHEN a = b THEN 'same' ELSE 'differ' END;
END $$;
-- only the node's plans, made at the default work_mem: generic plans keep
-- them when work_mem is lowered below.  A LionOrdered set starts lazily only
-- where the planner expects the walk to stop short (DESIGN.md §30.4): those
-- below whose walks go far bound the walked column by parameters, whose
-- default estimate (0.5% of the rows) has the planner expect a short walk,
-- and are run over the whole table
SET enable_sort = off;
SET enable_seqscan = off;
SET enable_bitmapscan = off;
SET pg_lion.enable_plain_scan = off;
SET pg_lion.pushdown_margin = 1000;
SET plan_cache_mode = force_generic_plan;
PREPARE otr_k(int) AS
	SELECT id, k FROM otr WHERE a = $1 AND b = 4 ORDER BY k, id LIMIT 5;
PREPARE otr_id(int, int, int) AS
	SELECT id FROM otr WHERE a = $1 AND b = 4 AND id % 8 BETWEEN $2 AND $3
	 ORDER BY id % 8, id LIMIT 3000;
PREPARE otr_all(int, int, int) AS
	SELECT id FROM otr WHERE a = $1 AND b = 4 AND id BETWEEN $2 AND $3
	 ORDER BY id;
PREPARE otr_pad(int, int, int) AS
	SELECT id, k, pad FROM otr WHERE a = $1 AND b = 4 AND k BETWEEN $2 AND $3
	 ORDER BY k, id;
PREPARE otr_or(int, int, int) AS
	SELECT id FROM otr WHERE (b = $1 OR a = 2) AND id % 8 BETWEEN $2 AND $3
	 ORDER BY id % 8, id LIMIT 90000;
PREPARE otr_far(int) AS
	SELECT id FROM otr WHERE a = $1 AND b = 4 ORDER BY id;
EXPLAIN (COSTS OFF) EXECUTE otr_k(3);
                QUERY PLAN                 
-------------------------------------------
 Limit
   ->  Custom Scan (LionOrdered) on otr
         Ordered By: otr_k (index only)
         Lion Cond: ((a = $1) AND (b = 4))
         Lion Indexes: otr_l
(5 rows)

EXPLAIN (COSTS OFF) EXECUTE otr_id(3, 0, 7);
                         QUERY PLAN                          
-------------------------------------------------------------
 Limit
   ->  Custom Scan (LionOrdered) on otr
         Ordered By: otr_m (index only)
         Index Cond: (((id % 8) >= $2) AND ((id % 8) <= $3))
         Lion Cond: ((a = $1) AND (b = 4))
         Lion Indexes: otr_l
(6 rows)

EXPLAIN (COSTS OFF) EXECUTE otr_all(3, 1, 200000);
                QUERY PLAN                 
-------------------------------------------
 Custom Scan (LionOrdered) on otr
   Ordered By: otr_pkey (index only)
   Index Cond: ((id >= $2) AND (id <= $3))
   Lion Cond: ((a = $1) AND (b = 4))
   Lion Indexes: otr_l
(5 rows)

EXPLAIN (COSTS OFF) EXECUTE otr_pad(3, 0, 200003);
               QUERY PLAN                
-----------------------------------------
 Custom Scan (LionOrdered) on otr
   Ordered By: otr_k
   Index Cond: ((k >= $2) AND (k <= $3))
   Lion Cond: ((a = $1) AND (b = 4))
   Lion Indexes: otr_l
(5 rows)

EXPLAIN (COSTS OFF) EXECUTE otr_or(1, 0, 7);
                         QUERY PLAN                          
-------------------------------------------------------------
 Limit
   ->  Custom Scan (LionOrdered) on otr
         Ordered By: otr_m (index only)
         Index Cond: (((id % 8) >= $2) AND ((id % 8) <= $3))
         Lion Cond: ((b = $1) OR (a = 2))
         Lion Indexes: otr_l
(6 rows)

-- 1. The lazy set built because its probes cost what the build would: the
--    walk in k's order starts its streams again at nearly every key
SELECT * FROM otr_run('EXECUTE otr_k(3)');
                               otr_run                               
---------------------------------------------------------------------
 Index Entries Walked: 372
 Lion Set: 36 containers, exact, after 16 keys probed (probe budget)
(2 rows)

SELECT otr_same('EXECUTE otr_k(3)',
	'SELECT id, k FROM otr WHERE a = 3 AND b = 4 ORDER BY k, id LIMIT 5');
 otr_same 
----------
 same
(1 row)

-- 2. ... because the walk has met 10,000 entries, at least eight for each
--    unit of the probe budget, in heap order and with the switch kept away;
--    the early stop then ends the walk at the last member
SET pg_lion.ordered_switch_ratio = 1000000;
SELECT * FROM otr_run('EXECUTE otr_all(3, 1, 200000)');
                             otr_run                             
-----------------------------------------------------------------
 Index Entries Walked: 199881
 Lion Set: 36 containers, exact, after 2 keys probed (long walk)
 Scans Stopped Early: 1
(3 rows)

SELECT otr_same('EXECUTE otr_all(3, 1, 200000)',
	'SELECT id FROM otr WHERE a = 3 AND b = 4 ORDER BY id');
 otr_same 
----------
 same
(1 row)

RESET pg_lion.ordered_switch_ratio;
-- 3. ... because the memo, a member bitmap per key met, outgrew half of
--    hash_mem; built in 64kB, the set takes over what the memo met, a bit a
--    member, and the walk goes on counting: the early stop ends it at the
--    last member
SET work_mem = '64kB';
SET hash_mem_multiplier = 1;
SELECT * FROM otr_run('EXECUTE otr_id(3, 0, 7)');
                             otr_run                             
-----------------------------------------------------------------
 Index Entries Walked: 199938
 Lion Set: 36 containers, exact, after 8 keys probed (memo size)
 Scans Stopped Early: 1
(3 rows)

SELECT otr_same('EXECUTE otr_id(3, 0, 7)',
	'SELECT id FROM otr WHERE a = 3 AND b = 4 ORDER BY id % 8, id LIMIT 3000');
 otr_same 
----------
 same
(1 row)

-- 4. ... and the set built then spills past hash_mem, exact still, the
--    walk's bits with it
SELECT * FROM otr_run('EXECUTE otr_or(1, 0, 7)');
                                     otr_run                                     
---------------------------------------------------------------------------------
 Index Entries Walked: 200000
 Lion Set: 36 containers, exact, spilled 130 kB, after 7 keys probed (memo size)
 Scans Stopped Early: 1
(3 rows)

SELECT otr_same('EXECUTE otr_or(1, 0, 7)',
	'SELECT id FROM otr WHERE (b = 1 OR a = 2) ORDER BY id % 8, id LIMIT 90000');
 otr_same 
----------
 same
(1 row)

-- 5. Built from the start, in 64kB: the walk counts the members it meets
--    in a bit each, and the early stop ends it at the last
SET pg_lion.enable_lazy_set = off;
SELECT * FROM otr_run('EXECUTE otr_id(3, 0, 7)');
            otr_run             
--------------------------------
 Index Entries Walked: 199938
 Lion Set: 36 containers, exact
 Scans Stopped Early: 1
(3 rows)

SELECT otr_same('EXECUTE otr_id(3, 0, 7)',
	'SELECT id FROM otr WHERE a = 3 AND b = 4 ORDER BY id % 8, id LIMIT 3000');
 otr_same 
----------
 same
(1 row)

RESET pg_lion.enable_lazy_set;
RESET hash_mem_multiplier;
RESET work_mem;
-- 6. The switch to fetch and sort: with the ratio at 1 it comes at the
--    first chance, 10,000 entries in
SET pg_lion.ordered_switch_ratio = 1;
SELECT * FROM otr_run('EXECUTE otr_pad(3, 0, 200003)');
                               otr_run                               
---------------------------------------------------------------------
 Index Entries Walked: 10000
 Lion Set: 36 containers, exact, after 16 keys probed (probe budget)
 Switched to Fetch and Sort: 1 of 1 scans, 2738 members fetched
 Fetch and Sort Method: quicksort
 Fetch and Sort Space Type: Memory
(5 rows)

SELECT otr_same('EXECUTE otr_pad(3, 0, 200003)',
	'SELECT id, k, pad FROM otr WHERE a = 3 AND b = 4 ORDER BY k, id');
 otr_same 
----------
 same
(1 row)

-- 7. ... and when the members' rows do not fit in work_mem, its sort goes
--    to disk, as a Sort node's does, and the switch comes at the same
--    entry: 2,738 rows of some 100 bytes in 64kB and in 256kB, none of
--    them left to the walk's remaining 190,000 entries
SET work_mem = '64kB';
SET hash_mem_multiplier = 1;
SELECT * FROM otr_run('EXECUTE otr_pad(3, 0, 200003)');
                               otr_run                               
---------------------------------------------------------------------
 Index Entries Walked: 10000
 Lion Set: 36 containers, exact, after 16 keys probed (probe budget)
 Switched to Fetch and Sort: 1 of 1 scans, 2738 members fetched
 Fetch and Sort Method: external
 Fetch and Sort Space Type: Disk
(5 rows)

SELECT otr_same('EXECUTE otr_pad(3, 0, 200003)',
	'SELECT id, k, pad FROM otr WHERE a = 3 AND b = 4 ORDER BY k, id');
 otr_same 
----------
 same
(1 row)

SET work_mem = '256kB';
SELECT * FROM otr_run('EXECUTE otr_pad(3, 0, 200003)');
                               otr_run                               
---------------------------------------------------------------------
 Index Entries Walked: 10000
 Lion Set: 36 containers, exact, after 16 keys probed (probe budget)
 Switched to Fetch and Sort: 1 of 1 scans, 2738 members fetched
 Fetch and Sort Method: external
 Fetch and Sort Space Type: Disk
(5 rows)

SELECT otr_same('EXECUTE otr_pad(3, 0, 200003)',
	'SELECT id, k, pad FROM otr WHERE a = 3 AND b = 4 ORDER BY k, id');
 otr_same 
----------
 same
(1 row)

RESET hash_mem_multiplier;
RESET work_mem;
RESET pg_lion.ordered_switch_ratio;
-- 8. A walk the planner expects to go far, with no LIMIT: the set built at
--    the start, never lazily
SELECT * FROM otr_run('EXECUTE otr_far(3)');
            otr_run             
--------------------------------
 Index Entries Walked: 199881
 Lion Set: 36 containers, exact
 Scans Stopped Early: 1
(3 rows)

SELECT otr_same('EXECUTE otr_far(3)',
	'SELECT id FROM otr WHERE a = 3 AND b = 4 ORDER BY id');
 otr_same 
----------
 same
(1 row)

-- 9. A lazy set built because the walk does not go in heap order: of the
--    first 64 container keys it evaluates, one in four lies behind the one
--    before.  The walk must get that far within the probe budget, which
--    counts every leaf key's containers while a probe that finds the first
--    key's set empty there seeks no other: a's rows lie in 8 containers the
--    walk meets last, b's and c's in all 72 of a table of one row a page
--    (64 pages a container), so the budget is 152 and the 64 keys cost 128
--    (48 probes forward at 1, 16 behind at 5).  The walk: one row of each of
--    the first 64 containers in the order 1, 2, 3, 0, 5, 6, 7, 4, ..., then
--    every row in heap order.
CREATE TABLE otr_h (id int, o int, a int, b int, c int, pad text)
	WITH (fillfactor = 10, autovacuum_enabled = off);
INSERT INTO otr_h SELECT p,
	   CASE WHEN p % 64 = 0 AND p < 64 * 64
			THEN (p / 256) * 4 + CASE WHEN (p / 64) % 4 = 0 THEN 3 ELSE (p / 64) % 4 - 1 END
			ELSE 1000 + p END,
	   (p >= 64 * 64)::int, p % 2, (p / 2) % 2, repeat('x', 1000)
  FROM generate_series(0, 72 * 64 - 1) p;
CREATE INDEX otr_h_l ON otr_h USING lion (a, b, c);
CREATE INDEX otr_h_o ON otr_h (o, id);
VACUUM (FREEZE, ANALYZE) otr_h;
-- row p on page p
SELECT count(*) FROM otr_h WHERE ctid <> format('(%s,1)', id)::tid;
 count 
-------
     0
(1 row)

SELECT * FROM otr_run('SELECT id FROM otr_h WHERE a = 1 AND b = 1 AND c = 1 ORDER BY o, id LIMIT 10');
                             otr_run                              
------------------------------------------------------------------
 Index Entries Walked: 4136
 Lion Set: 8 containers, exact, after 64 keys probed (heap order)
(2 rows)

SELECT otr_same('SELECT id FROM otr_h WHERE a = 1 AND b = 1 AND c = 1 ORDER BY o, id LIMIT 10',
	'SELECT id FROM otr_h WHERE a = 1 AND b = 1 AND c = 1 ORDER BY o, id LIMIT 10');
 otr_same 
----------
 same
(1 row)

DROP TABLE otr_h;
-- 10. The walk's bits past hash_mem while the set is within it: g's members,
--     every other row, are dense enough for bitmaps, whose places are their
--     bits, as many bytes as the set; the bits that do not fit in 64kB spill
--     to the set's file, and the walk still counts every member it meets.
--     They come first in k's order, so the early stop ends the walk half way
--     through the index, as it does at the default work_mem
CREATE TABLE otr_v (id int, k int, g int, pad text)
	WITH (autovacuum_enabled = off);
INSERT INTO otr_v SELECT i, CASE WHEN i % 2 = 0 THEN i ELSE 1000000 + i END,
	   (i % 2 = 0)::int, repeat('x', 40)
  FROM generate_series(1, 200000) i;
CREATE INDEX otr_v_l ON otr_v USING lion (g);
CREATE INDEX otr_v_k ON otr_v (k);
VACUUM (FREEZE, ANALYZE) otr_v;
SET pg_lion.ordered_switch_ratio = 1000000;
SET pg_lion.enable_lazy_set = off;
SELECT * FROM otr_run('SELECT id FROM otr_v WHERE g = 1 ORDER BY k');
            otr_run             
--------------------------------
 Index Entries Walked: 100000
 Lion Set: 33 containers, exact
 Scans Stopped Early: 1
(3 rows)

SET work_mem = '64kB';
SET hash_mem_multiplier = 1;
SELECT * FROM otr_run('SELECT id FROM otr_v WHERE g = 1 ORDER BY k');
                   otr_run                    
----------------------------------------------
 Index Entries Walked: 100000
 Lion Set: 33 containers, exact, spilled 8 kB
 Scans Stopped Early: 1
(3 rows)

SELECT otr_same('SELECT id FROM otr_v WHERE g = 1 ORDER BY k',
	'SELECT id FROM otr_v WHERE g = 1 ORDER BY k');
 otr_same 
----------
 same
(1 row)

RESET hash_mem_multiplier;
RESET work_mem;
RESET pg_lion.enable_lazy_set;
RESET pg_lion.ordered_switch_ratio;
DROP TABLE otr_v;
RESET plan_cache_mode;
RESET enable_sort;
RESET enable_seqscan;
RESET enable_bitmapscan;
RESET pg_lion.enable_plain_scan;
RESET pg_lion.pushdown_margin;
DEALLOCATE ALL;
DROP FUNCTION otr_same(text, text);
DROP FUNCTION otr_rows(text);
DROP FUNCTION otr_run(text);
DROP TABLE otr;