-- What a count over two ranges is priced at, and the union a range taken as
-- a source is collected into (DESIGN.md §28, "The cost of a summed range";
-- §32, "The collected union, dense" and "What collecting a range costs").
--
-- `count(*) WHERE <range on a> AND <range on b>` sums one range and collects
-- the other as a source.  A collected range holds no pin, so it cannot drive
-- the count of the other sources that the complement of the summed range
-- needs, and the executor walks the inside however wide it is.  The planner
-- priced the complement all the same - any positive source would do - and
-- took two ranges over nearly every row for a tenth of what their inside
-- walk costs: the node, 2.5 s, over a sequential scan of 0.33 s (2M rows).
--
-- The union a collected range builds was folded one container at a time
-- into a key's union once that was a RUN - which a dense union of scattered
-- rows is, and every union of a column in heap order - a bitset image per
-- container, 12.7 s for a range of 1.9 million scattered rows.  It is
-- widened into a bitset and ORed into in place now, and the model prices a
-- union in heap order at a fold or two a union key rather than one a
-- container.  Every answer is checked against the pushdown turned off; the
-- plan choices are the planner's own, nothing disabled.
\set VERBOSITY terse
SET client_min_messages = warning;
LOAD 'pg_lion';
CREATE EXTENSION IF NOT EXISTS pg_lion;
RESET client_min_messages;
-- VACUUM can only set all-visible once the commit record is on disk
SET synchronous_commit = on;
-- a sample of every row: the statistics, and the plans, do not depend on it
SET default_statistics_target = 1000;
SET max_parallel_workers_per_gather = 0;

-- 100,000 rows, 45 to a heap page, 35 container keys.  lo has four values;
-- w1 is the row number modulo 1000 and w2 a permutation of 20,000 keys of
-- five rows each, both spread over the whole heap; o has four rows a key, in
-- the heap's order; m has four rows a key too, its keys up to 12,500 in the
-- heap's order in the second half of the heap and the others a permutation
-- over the first half.
CREATE TABLE rcost (id int, lo int, w1 int, w2 int, o int, m int, pad text);
INSERT INTO rcost
SELECT g, g % 4, g % 1000, ((g::bigint * 7919) % 20000)::int, g / 4,
	   CASE WHEN g > 50000 THEN (g - 50001) / 4
			ELSE 12500 + ((g::bigint * 7919) % 50000)::int / 4 END,
	   repeat('x', 120)
  FROM generate_series(1, 100000) g;
CREATE INDEX rcost_lo ON rcost USING lion (lo);
CREATE INDEX rcost_w1 ON rcost USING lion (w1);
CREATE INDEX rcost_w2 ON rcost USING lion (w2);
CREATE INDEX rcost_o ON rcost USING lion (o);
CREATE INDEX rcost_m ON rcost USING lion (m);
VACUUM (FREEZE, ANALYZE) rcost;

/*
 * rc_check() runs q with the pushdown forced (every other scan disabled) and
 * again with the pushdown off and the planner left alone, and compares the
 * answers.  It reports how the node took its ranges: how many it collected,
 * walked and spilled, and how it evaluated the range it summed.
 */
CREATE FUNCTION rc_check(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 := 'collected ' || coalesce(node ->> 'Range Sources Collected', '0') ||
			', walked ' || coalesce(node ->> 'Range Sources Walked', '0') ||
			', spilled ' || coalesce(node ->> 'Range Sources Spilled', '0');
		IF node ->> 'Range Evaluation' IS NOT NULL THEN
			how := how || ', ' || (node ->> 'Range Evaluation');
		END IF;
	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 $$;

-- ---------- 1. The complement of a summed range, and what drives it ----------

-- Two ranges over nearly every row: the widest is summed and the other
-- collected, which cannot drive the complement, so the node would walk the
-- 19,989 keys inside.  The sequential scan is the cheaper plan, and taken.
EXPLAIN (COSTS OFF) SELECT count(*) FROM rcost WHERE w1 > 10 AND w2 > 10;
EXPLAIN (COSTS OFF)
SELECT count(*) FROM rcost WHERE w1 BETWEEN 10 AND 900 AND w2 BETWEEN 10 AND 19000;
-- ... and the node, forced, walks the inside
SELECT rc_check('SELECT count(*) FROM rcost WHERE w1 > 10 AND w2 > 10');
SELECT rc_check('SELECT count(*) FROM rcost WHERE w1 BETWEEN 10 AND 900 AND w2 BETWEEN 10 AND 19000');

-- An equality beside the range drives the complement: the eleven keys
-- outside it are walked, and the node is still the plan.  A second range
-- beside them, w1's, is walked at the one count rather than collected
-- (DESIGN.md §32, "Walked at every count").
EXPLAIN (COSTS OFF) SELECT count(*) FROM rcost WHERE lo = 1 AND w2 > 10;
SELECT rc_check('SELECT count(*) FROM rcost WHERE lo = 1 AND w2 > 10');
SELECT rc_check('SELECT count(*) FROM rcost WHERE lo = 1 AND w1 > 10 AND w2 > 10');

-- ---------- 2. A range collected as a source, its union a RUN ----------

-- In the heap's order every key's union is a RUN, and each container after
-- its first used to be priced - and made - a fold into it: half the keys of
-- o went to an index scan and a sort.  They are a fold or two a union key
-- now, and the node is the plan.  Four groups, or a count(DISTINCT)'s four
-- existence tests, walk the range at each count instead, which is cheaper
-- than collecting it (DESIGN.md §32, "Walked at every count"); an OR's leaf
-- is never walked, and is collected.
EXPLAIN (COSTS OFF) SELECT count(DISTINCT lo) FROM rcost WHERE o BETWEEN 10 AND 12500;
SELECT rc_check('SELECT count(DISTINCT lo) FROM rcost WHERE o BETWEEN 10 AND 12500');
SELECT rc_check('SELECT lo, count(*) FROM rcost WHERE o BETWEEN 10 AND 24000 GROUP BY lo');
SELECT rc_check('SELECT lo, count(*) FROM rcost WHERE (o BETWEEN 10 AND 24000 OR w2 = -1) GROUP BY lo');

-- Nearly all of w1's rows: the union of every container key is dense, a
-- RUN - the case that folded every container - and widened into a bitset.
SELECT rc_check('SELECT lo, count(*) FROM rcost WHERE w1 BETWEEN 10 AND 990 GROUP BY lo');
SELECT rc_check('SELECT lo, count(*) FROM rcost WHERE (w1 BETWEEN 10 AND 990 OR w2 = -1) GROUP BY lo');
SELECT rc_check('SELECT count(DISTINCT lo) FROM rcost WHERE w2 BETWEEN 10 AND 19000');
SELECT rc_check('SELECT lo, count(*) FROM rcost WHERE w2 BETWEEN 5000 AND 12000 GROUP BY lo');
-- half in the heap's order, half scattered
SELECT rc_check('SELECT lo, count(*) FROM rcost WHERE m BETWEEN 0 AND 18750 GROUP BY lo');
SELECT rc_check('SELECT count(*) FROM rcost WHERE lo = 2 AND o > 100 AND m BETWEEN 10 AND 24000');

-- With 64 kB for the ranges, unions of rcost's 35 container keys all fit:
-- on its rows, 45 to a page, a union past an ARRAY's 256 members is a
-- NARROW of width 1, half a kilobyte (DESIGN.md §38).  rcostw has rcost's
-- rows in rcost's order, some 25 to a page and 63 container keys, and there
-- the widened unions do not all fit, and are optimized back - compacted - to
-- make room: for the next widening, and before the collection would give
-- up.  The unions optimized fit, and the range is still collected - as an
-- OR's leaf, o's, which four groups walk otherwise; w2's - keys of five
-- scattered rows, whose unions are ARRAYs with members pending until they
-- are folded - does not, and is walked.  A widening that finds no
-- room even then is refused, and folds as before: rcostn below.
CREATE TABLE rcostw AS SELECT id, lo, w1, w2, o, m, repeat('x', 260) AS pad
  FROM rcost ORDER BY id;
CREATE INDEX rcostw_lo ON rcostw USING lion (lo);
CREATE INDEX rcostw_w2 ON rcostw USING lion (w2);
CREATE INDEX rcostw_o ON rcostw USING lion (o);
CREATE INDEX rcostw_m ON rcostw USING lion (m);
VACUUM (FREEZE, ANALYZE) rcostw;
SET work_mem = '64kB';
SET hash_mem_multiplier = 1.0;
SELECT rc_check('SELECT count(DISTINCT lo) FROM rcost WHERE w2 BETWEEN 10 AND 19000');
SELECT rc_check('SELECT lo, count(*) FROM rcostw WHERE o BETWEEN 10 AND 24000 GROUP BY lo');
SELECT rc_check('SELECT lo, count(*) FROM rcostw WHERE (o BETWEEN 10 AND 24000 OR w2 = -1) GROUP BY lo');
SELECT rc_check('SELECT lo, count(*) FROM rcostw WHERE m BETWEEN 0 AND 18750 GROUP BY lo');
SELECT rc_check('SELECT count(DISTINCT lo) FROM rcostw WHERE w2 BETWEEN 10 AND 19000');
-- an OR's leaves, which cannot be walked: the second has what the first
-- leaves of the memory, and is collected a window of container keys at a
-- time past it, each window widening and compacting its own unions
SELECT rc_check('SELECT count(*) FROM rcostw WHERE lo = 1 AND (w2 BETWEEN 10 AND 3000 OR m BETWEEN 6000 AND 16000)');
SELECT rc_check('SELECT count(*) FROM rcostw WHERE lo = 1 AND (w2 BETWEEN 10 AND 4000 OR m BETWEEN 0 AND 18750)');
SELECT rc_check('SELECT count(*) FROM rcostw WHERE lo = 3 AND (w2 BETWEEN 10 AND 19000 OR o < 5)');
RESET work_mem;
RESET hash_mem_multiplier;
DROP TABLE rcostw;

-- v is 0 in every other row of rcostn's first 39 container keys, and
-- 100,000, outside the range, in the others: its rows are 185 to a page,
-- and v = 0 is a NARROW of width 3 (DESIGN.md §38), 1.5 kB at each of them
-- that nothing optimizes smaller, some 62 kB of the 64.  v's other values
-- lie in the heap's order on the two keys after them, 20 rows each, and each
-- of those keys' unions is a RUN that the sets after its first would widen:
-- every widening is refused, the union folds, and the range is still
-- collected.  With the memory, they are widened and ORed into in place.
CREATE TABLE rcostn (g int NOT NULL, v int NOT NULL, pad text NOT NULL);
INSERT INTO rcostn
SELECT i % 5, CASE WHEN i > 39 * 64 * 185 THEN 1 + (i - 39 * 64 * 185 - 1) / 20
				   WHEN i % 2 = 1 THEN 0 ELSE 100000 END, ''
  FROM generate_series(1, 41 * 64 * 185) i;
CREATE INDEX rcostn_g ON rcostn USING lion (g);
CREATE INDEX rcostn_v ON rcostn USING lion (v);
VACUUM (FREEZE, ANALYZE) rcostn;
SELECT count(*) AS rows_on_page_0, count(*) FILTER (WHERE v = 0) AS v0
  FROM rcostn WHERE (ctid::text::point)[0] = 0;
SELECT bitset_containers, run_containers, narrow_containers
  FROM lion_index_stats('rcostn_v');
SET work_mem = '64kB';
SET hash_mem_multiplier = 1.0;
SELECT rc_check('SELECT g, count(*) FROM rcostn WHERE v BETWEEN 0 AND 99999 GROUP BY g');
RESET work_mem;
RESET hash_mem_multiplier;
SELECT rc_check('SELECT g, count(*) FROM rcostn WHERE v BETWEEN 0 AND 99999 GROUP BY g');
DROP TABLE rcostn;

DROP FUNCTION rc_check(text);
DROP TABLE rcost;