-- Wide bitmaps: NARROWs of width 3 and 4, and BITSETs (DESIGN.md §3, §38).
--
-- A dense set of scattered rows is a bitmap: a NARROW of the narrowest width
-- that holds its blocks' offsets, k words of each block (k = 1 .. 5 at 8K),
-- or a BITSET, 8 words of each.  The set algebra, the readers, VACUUM and
-- the inserts take a bitmap's width as it comes, and have code compiled for
-- each width up to 4 and for a BITSET's.  narrow.sql has the format at every
-- width; this file has the paths of the set algebra, each section running
-- its queries on three tables of the same columns and values:
--
--	lion_bs		136 rows to a page: its dense sets are NARROWs of width 3
--	lion_bs4	226 rows to a page: NARROWs of width 4
--	lion_bs6	226 rows to a page, its indexes built before its rows: the
--				inserts write the NARROWs of width 4 a build writes
--
-- No index holds a BITSET: a NARROW is smaller than one for any heap's rows
-- at 8K, and every write optimizes what it writes.  The BITSETs here are the
-- set algebra's own, the unions it makes of bitmaps and other kinds.
--
-- lion_bs also has two columns, and a row number, the others do not have
-- room for.  lion_index_stats() shows each index's containers by kind.
-- Every answer is checked against a sequential scan, as a multiset in both
-- directions.  range_cost.sql §2 has the union of a range collected on such
-- rows, where a widening is refused.
\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;
SET max_parallel_workers_per_gather = 0;

/*
 * lbs_check() runs q with one kind of scan - 'bitmap', 'plain' (an Index
 * Scan) or 'count' (the LionCount pushdown, every other scan of the table
 * disabled and the pushdown taken at any price) - and again as a sequential
 * scan with the pushdown off, and compares the two as multisets.  It says
 * whether the scan asked for was really used, and the answer: its rows when
 * there are four or fewer, else how many.
 */
CREATE FUNCTION lbs_check(q text, how text) RETURNS text
LANGUAGE plpgsql AS $$
DECLARE
	ln text;
	used boolean := false;
	want text;
	nrows bigint;
	ndiff bigint;
	answer text;
BEGIN
	PERFORM set_config('enable_seqscan', 'off', true);
	PERFORM set_config('enable_bitmapscan', (how = 'bitmap')::text, true);
	PERFORM set_config('enable_indexscan', (how <> 'bitmap')::text, true);
	PERFORM set_config('enable_indexonlyscan', (how <> 'bitmap')::text, true);
	PERFORM set_config('pg_lion.enable_plain_scan', (how = 'plain')::text, true);
	PERFORM set_config('pg_lion.pushdown_margin',
					   CASE how WHEN 'count' THEN '1000' ELSE '1' END, true);
	PERFORM set_config('pg_lion.enable_count_pushdown', (how = 'count')::text, true);
	want := CASE how WHEN 'bitmap' THEN 'Bitmap Index Scan'
					 WHEN 'plain' THEN 'Index (Only )?Scan using'
					 ELSE 'Custom Scan \(LionCount\)' END;
	FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP
		IF ln ~ want THEN
			used := true;
		END IF;
	END LOOP;
	EXECUTE format('CREATE TEMP TABLE lbs_on AS SELECT s::text AS r FROM (%s) s', q);

	PERFORM set_config('enable_seqscan', 'on', true);
	PERFORM set_config('enable_bitmapscan', 'off', true);
	PERFORM set_config('enable_indexscan', 'off', true);
	PERFORM set_config('enable_indexonlyscan', 'off', true);
	PERFORM set_config('pg_lion.enable_count_pushdown', 'off', true);
	EXECUTE format('CREATE TEMP TABLE lbs_off AS SELECT s::text AS r FROM (%s) s', q);
	PERFORM set_config('enable_bitmapscan', 'on', true);
	PERFORM set_config('enable_indexscan', 'on', true);
	PERFORM set_config('enable_indexonlyscan', 'on', true);
	PERFORM set_config('pg_lion.enable_plain_scan', 'on', true);
	PERFORM set_config('pg_lion.pushdown_margin', '1', true);
	PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true);

	EXECUTE 'SELECT count(*), string_agg(r, '' '' ORDER BY r) FROM lbs_on'
		INTO nrows, answer;
	EXECUTE 'SELECT (SELECT count(*) FROM (SELECT * FROM lbs_on EXCEPT ALL SELECT * FROM lbs_off) a)'
			' + (SELECT count(*) FROM (SELECT * FROM lbs_off EXCEPT ALL SELECT * FROM lbs_on) b)'
		INTO ndiff;
	EXECUTE 'DROP TABLE lbs_on, lbs_off';
	IF ndiff <> 0 THEN
		RETURN format('MISMATCH: %s rows differ', ndiff);
	END IF;
	RETURN format('%s%s: %s', CASE WHEN used THEN '' ELSE 'no ' END, how,
				  CASE WHEN nrows <= 4 THEN answer ELSE nrows || ' rows' END);
END $$;

-- lbs_check() of q on each of the three tables, its %s the table's name.
CREATE FUNCTION lbs_all(q text, how text)
RETURNS TABLE (tbl text, result text)
LANGUAGE sql AS $$
	SELECT t, lbs_check(format(q, t), how)
	  FROM unnest(ARRAY['lion_bs', 'lion_bs4', 'lion_bs6']) WITH ORDINALITY u(t, n)
	 ORDER BY n
$$;

-- An index's containers by kind, per key column.
CREATE FUNCTION lbs_mix(idx regclass)
RETURNS TABLE (attno int2, arrays int8, bitsets int8, runs int8, narrows int8)
LANGUAGE sql AS $$
	SELECT attno, array_containers, bitset_containers, run_containers,
		   narrow_containers
	  FROM lion_index_stats(idx)
$$;

-- The kinds of the containers of a column on each table, and the bytes they
-- take: NARROWs of width 3 are 1544 each and of width 4 2056.
CREATE FUNCTION lbs_mix_all(col text)
RETURNS TABLE (tbl text, arrays int8, bitsets int8, runs int8, narrows int8,
			   container_bytes int8)
LANGUAGE sql AS $$
	SELECT t, array_containers, bitset_containers, run_containers,
		   narrow_containers, container_bytes
	  FROM unnest(ARRAY['lion_bs', 'lion_bs4', 'lion_bs6']) WITH ORDINALITY u(t, n),
		   lion_index_stats((t || '_' || col)::regclass)
	 ORDER BY n
$$;

-- ---------- 1. the tables ----------
/*
 * 60,000 rows (30,000 in lion_bs6) with the same values in each table: a is
 * every other row and b every third, bitmaps at every key.  r is runs of 40
 * rows, four values: RUNs.  z is 0 in 150 rows of every 160, in runs that
 * fill a block's offsets, and one of five other values in the rest: 0 a RUN,
 * the others ARRAYs.  lion_bs, of seven int columns, also has the row
 * number id, s with 23 values, some 440 members a key, ARRAYs, and u with
 * 5000 values of twelve rows, a member or two at a key: sparse segments,
 * whose members an AND looks up one at a time.  lion_bs has seven container
 * keys and lion_bs4 five; lion_bs6 has three, and its indexes, made before
 * its rows, have the NARROWs a build makes: an insert writes the smallest
 * container that holds its members.
 */
CREATE TABLE lion_bs (id int NOT NULL, a int NOT NULL, b int NOT NULL,
					  r int NOT NULL, s int NOT NULL, u int NOT NULL,
					  z int NOT NULL)
	WITH (autovacuum_enabled = off);
INSERT INTO lion_bs
SELECT i, i % 2, i % 3, (i / 40) % 4, i % 23, i % 5000,
	   CASE WHEN i % 160 < 150 THEN 0 ELSE 1 + i % 5 END
  FROM generate_series(1, 60000) i;
CREATE INDEX lion_bs_a ON lion_bs USING lion (a);
CREATE INDEX lion_bs_b ON lion_bs USING lion (b);
CREATE INDEX lion_bs_r ON lion_bs USING lion (r);
CREATE INDEX lion_bs_s ON lion_bs USING lion (s);
CREATE INDEX lion_bs_u ON lion_bs USING lion (u);
CREATE INDEX lion_bs_z ON lion_bs USING lion (z);
CREATE TABLE lion_bs4 (a int2 NOT NULL, b int2 NOT NULL, r int2 NOT NULL,
					   z int2 NOT NULL)
	WITH (autovacuum_enabled = off);
INSERT INTO lion_bs4
SELECT i % 2, i % 3, (i / 40) % 4, CASE WHEN i % 160 < 150 THEN 0 ELSE 1 + i % 5 END
  FROM generate_series(1, 60000) i;
CREATE INDEX lion_bs4_a ON lion_bs4 USING lion (a);
CREATE INDEX lion_bs4_b ON lion_bs4 USING lion (b);
CREATE INDEX lion_bs4_r ON lion_bs4 USING lion (r);
CREATE INDEX lion_bs4_z ON lion_bs4 USING lion (z);
CREATE TABLE lion_bs6 (LIKE lion_bs4) WITH (autovacuum_enabled = off);
CREATE INDEX lion_bs6_a ON lion_bs6 USING lion (a);
CREATE INDEX lion_bs6_b ON lion_bs6 USING lion (b);
CREATE INDEX lion_bs6_r ON lion_bs6 USING lion (r);
CREATE INDEX lion_bs6_z ON lion_bs6 USING lion (z);
INSERT INTO lion_bs6
SELECT i % 2, i % 3, (i / 40) % 4, CASE WHEN i % 160 < 150 THEN 0 ELSE 1 + i % 5 END
  FROM generate_series(1, 30000) i;
VACUUM (FREEZE, ANALYZE) lion_bs, lion_bs4, lion_bs6;
SELECT t AS tbl, count(*) FILTER (WHERE (ctid::text::point)[0] = 0) AS rows_on_page_0,
	   max((ctid::text::point)[0]) + 1 AS pages
  FROM (SELECT 'lion_bs' AS t, ctid FROM lion_bs UNION ALL
		SELECT 'lion_bs4', ctid FROM lion_bs4 UNION ALL
		SELECT 'lion_bs6', ctid FROM lion_bs6) x
 GROUP BY t ORDER BY t;
SELECT 'a' AS col, * FROM lbs_mix_all('a') UNION ALL
SELECT 'b', * FROM lbs_mix_all('b') UNION ALL
SELECT 'r', * FROM lbs_mix_all('r') UNION ALL
SELECT 'z', * FROM lbs_mix_all('z');
SELECT 's' AS col, * FROM lbs_mix('lion_bs_s') UNION ALL
SELECT 'u', * FROM lbs_mix('lion_bs_u');

-- ---------- 2. the count: ANDs ----------
-- two bitmaps, in one kernel pass; a RUN and a bitmap, both ways round, the
-- RUN's gaps cleared from the bitmap's image; an ARRAY tested against a
-- bitmap; a member or two looked up in one; and chains of them
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 1 AND b = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 0 AND r = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE r = 1 AND b = 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 0 AND b = 1 AND z = 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z = 3 AND a = 1', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z = 4 AND a = 0 AND b = 1 AND r = 3', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE s = 5 AND a = 1', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE u = 77 AND b = 1', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE s = 5 AND a = 1 AND b = 1 AND r = 3', 'count');

-- ---------- 3. the count: ORs ----------
-- IN lists of bitmaps and of RUNs, z = 0's runs set across whole words of
-- the image, and the arms of an OR, a bitmap's and a RUN's in either order
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE b IN (0, 2)', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE r IN (0, 3) AND a = 1', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z IN (0, 2) AND b = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE (z = 0 OR a = 1) AND b = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE (a = 1 OR r = 2) AND b = 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE (r = 2 OR a = 1) AND b = 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE (b = 1 OR r = 0) AND (a = 0 OR z = 3)', 'count');
-- an IN list or a nested OR beside an AND of bitmaps, which probes it for
-- the AND's members, or builds it; and bitmaps probed for the members of an
-- ARRAY and of a sparse segment
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 1 AND b = 0 AND z IN (1, 2, 3)', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 1 AND b = 0 AND (z = 1 OR (r = 2 AND z = 0))', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z = 5 AND b IN (0, 1)', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE (a = 1 OR r = 2) AND s = 4', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE a = 1 AND b = 0 AND r = 1 AND s IN (1, 2, 3)', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE s = 9 AND b IN (0, 1)', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE u = 4321 AND a IN (0, 1) AND b IN (1, 2)', 'count');

-- ---------- 4. the count: `<>` ----------
-- With nothing else to select rows, every row less z = 0's entry, a RUN
-- cleared from the image of b's union, or less a bitmap; an ARRAY, a RUN and
-- a bitmap less a bitmap; a bitmap less a RUN
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z <> 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE b <> 1', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z = 2 AND a <> 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE r = 1 AND a <> 1', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z = 0 AND a <> 1', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE b = 2 AND z <> 0', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a <> 1 AND r <> 0', 'count');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE s = 11 AND a <> 0', 'count');

-- ---------- 5. the count: GROUP BY ----------
-- groups of bitmaps, RUNs and ARRAYs, counted against a WHERE collected into
-- NARROWs - a copy is optimized, a BITSET's too - which they are tested
-- against through an image; two columns decoded against it; and
-- count(DISTINCT)
SELECT * FROM lbs_all('SELECT b, count(*) FROM %s WHERE a = 1 GROUP BY b', 'count');
SELECT * FROM lbs_all('SELECT r, count(*) FROM %s WHERE a = 0 AND b <> 2 GROUP BY r', 'count');
SELECT * FROM lbs_all('SELECT z, count(*) FROM %s WHERE b IN (0, 2) GROUP BY z', 'count');
SELECT * FROM lbs_all('SELECT b, r, count(*) FROM %s WHERE a = 1 GROUP BY b, r', 'count');
SELECT * FROM lbs_all('SELECT count(DISTINCT z) FROM %s WHERE a = 1 AND b = 0', 'count');
SELECT lbs_check('SELECT s, count(*) FROM lion_bs WHERE b IN (0, 2) GROUP BY s', 'count');
SELECT lbs_check('SELECT count(DISTINCT s) FROM lion_bs WHERE a = 1 AND b = 0', 'count');

-- ---------- 6. bitmap and plain scans ----------
-- a bitmap's members handed out; ANDs, ORs and `<>` of bitmaps and RUNs; an
-- IN list of RUNs, and of bitmaps, unioned for a plain scan
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE a = 1', 'bitmap');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE b = 2', 'plain');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE a = 0 AND b = 1', 'bitmap');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE a = 1 AND r = 3', 'bitmap');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE b IN (1, 2) AND z = 4', 'bitmap');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE a = 1 OR r = 1', 'bitmap');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE z <> 0', 'bitmap');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE b <> 0 AND a = 1', 'plain');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE r IN (1, 2)', 'plain');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE b IN (0, 2) AND z IN (0, 4)', 'plain');
SELECT lbs_check('SELECT id FROM lion_bs WHERE b IN (1, 2) AND s = 7', 'bitmap');
SELECT lbs_check('SELECT id FROM lion_bs WHERE s BETWEEN 3 AND 5 AND a = 1', 'bitmap');

-- ---------- 7. inserts ----------
-- 10,000 rows more in each table.  The bitmaps of the last container key
-- take their members in place, and the ARRAYs the inserts take past a
-- NARROW's size become NARROWs: lion_bs's a and b at the key after its
-- last, and its s = 0, every other row; lion_bs4's b at its last key, which
-- the build left ARRAYs; and lion_bs6's at its last key, as everywhere else
-- in it.
INSERT INTO lion_bs
SELECT i, i % 2, i % 3, (i / 40) % 4, CASE WHEN i % 2 = 0 THEN 0 ELSE i % 23 END,
	   i % 5000, CASE WHEN i % 160 < 150 THEN 0 ELSE 1 + i % 5 END
  FROM generate_series(60001, 70000) i;
INSERT INTO lion_bs4
SELECT i % 2, i % 3, (i / 40) % 4, CASE WHEN i % 160 < 150 THEN 0 ELSE 1 + i % 5 END
  FROM generate_series(60001, 70000) i;
INSERT INTO lion_bs6
SELECT i % 2, i % 3, (i / 40) % 4, CASE WHEN i % 160 < 150 THEN 0 ELSE 1 + i % 5 END
  FROM generate_series(30001, 40000) i;
SELECT 'a' AS col, * FROM lbs_mix_all('a') UNION ALL
SELECT 'b', * FROM lbs_mix_all('b');
SELECT 's' AS col, * FROM lbs_mix('lion_bs_s');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 1 AND b = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE b = 0 AND z <> 0', 'count');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE a = 0 AND b = 1', 'bitmap');
SELECT lbs_check('SELECT count(*) FROM lion_bs WHERE s = 0 AND z <> 0', 'count');
SELECT lbs_check('SELECT id FROM lion_bs WHERE s = 0 AND a = 0', 'bitmap');

-- ---------- 8. a dirty heap, VACUUM and verify() ----------
-- The counts recheck the rows of the pages the map cannot vouch for.
-- VACUUM takes the dead rows out of the bitmaps, and re-optimizes each it
-- changed: a NARROW of the narrowest width, or an ARRAY again where that is
-- smaller.
UPDATE lion_bs SET z = 1 WHERE id % 7 = 0;
DELETE FROM lion_bs WHERE id % 10 IN (1, 3, 5, 7);
UPDATE lion_bs4 SET z = 1 WHERE (ctid::text::point)[1]::int % 7 = 0;
DELETE FROM lion_bs4 WHERE (ctid::text::point)[1]::int % 10 IN (1, 3, 5, 7);
UPDATE lion_bs6 SET z = 1 WHERE (ctid::text::point)[1]::int % 7 = 0;
DELETE FROM lion_bs6 WHERE (ctid::text::point)[1]::int % 10 IN (1, 3, 5, 7);
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 1 AND b = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z <> 0', 'count');
SELECT * FROM lbs_all('SELECT b, count(*) FROM %s WHERE a = 0 GROUP BY b', 'count');
VACUUM (FREEZE, ANALYZE) lion_bs, lion_bs4, lion_bs6;
SELECT 'a' AS col, * FROM lbs_mix_all('a') UNION ALL
SELECT 'b', * FROM lbs_mix_all('b');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE a = 1 AND b = 2', 'count');
SELECT * FROM lbs_all('SELECT count(*) FROM %s WHERE z <> 0', 'count');
SELECT * FROM lbs_all('SELECT ctid FROM %s WHERE a = 0 AND b = 1', 'bitmap');
SELECT lion_index_verify(t || '_' || c, true)
  FROM unnest(ARRAY['lion_bs', 'lion_bs4', 'lion_bs6']) t,
	   unnest(ARRAY['a', 'b', 'z']) c;

DROP TABLE lion_bs, lion_bs4, lion_bs6;
DROP FUNCTION lbs_check(text, text), lbs_all(text, text), lbs_mix(regclass),
	lbs_mix_all(text);