-- The build (DESIGN.md §24, "Build"): every row's code appended to its key's
-- entry in memory, spilled in sorted runs when maintenance_work_mem runs out,
-- merged back in directory order, and on PostgreSQL 17 and later scanned by
-- parallel workers too.  Whatever the route, the index is the same one, page
-- for page, so this builds each index every way and compares the relation
-- files byte for byte.
--
-- The tables are UNLOGGED because a logged build's pages carry the LSN of the
-- WAL record that logged them; an unlogged one's are written as they are.
--
-- There are two expected files: build.out for 17 and later, build_1.out for
-- 16, where only btree indexes are built in parallel and the DEBUG lines say
-- so.
\set VERBOSITY terse
SET client_min_messages = warning;
CREATE EXTENSION IF NOT EXISTS pg_lion;
CREATE EXTENSION IF NOT EXISTS pageinspect;
-- The build's phases, as pg_stat_progress_create_index names them (DESIGN.md
-- §24, "Progress").  What a build reports in them is left alone, as core's
-- tests leave theirs: another session would see it only by a race.
SELECT n, pg_indexam_progress_phasename(a.oid, n) AS phase
  FROM pg_am a, generate_series(1, 6) n
 WHERE a.amname = 'lion' ORDER BY n;
 n |           phase           
---+---------------------------
 1 | initializing
 2 | scanning table
 3 | merging runs (workers)
 4 | writing columns
 5 | copying columns (workers)
 6 | 
(6 rows)

SELECT setseed(0.31);
 setseed 
---------
 
(1 row)

CREATE FUNCTION lion_build_digest(idx regclass) RETURNS text
	LANGUAGE sql AS $$ SELECT md5(pg_read_binary_file(pg_relation_filepath(idx))) $$;
-- REINDEX under the given memory and worker settings, and digest the result
CREATE FUNCTION lion_build_as(idx regclass, mem text, workers int)
	RETURNS text LANGUAGE plpgsql AS $$
BEGIN
	PERFORM set_config('maintenance_work_mem', mem, true);
	PERFORM set_config('max_parallel_maintenance_workers', workers::text, true);
	EXECUTE format('REINDEX INDEX %s', idx);
	RETURN lion_build_digest(idx);
END $$;
-- ---------------------------------------------------------------------
-- 1. Every kind of key: enum, bool, int, text, timestamptz, NULLs, arrays
--    with empty arrays and NULL elements, tsvectors with no lexemes.
--    parallel_workers fixes the worker count whatever the table's size or
--    maintenance_work_mem (plan_create_index_workers()).
-- ---------------------------------------------------------------------
CREATE TYPE lion_build_mood AS ENUM ('sad', 'ok', 'happy', 'ecstatic');
CREATE UNLOGGED TABLE lion_build (
	id int, mood lion_build_mood, flag bool, n int, t text, ts timestamptz,
	ia int[], ta text[], tv tsvector, u int8, pad text)
	WITH (fillfactor = 60, parallel_workers = 2);
INSERT INTO lion_build
SELECT g,
	   CASE WHEN g % 13 = 0 THEN NULL
			ELSE (ARRAY['sad','ok','happy','ecstatic']::lion_build_mood[])[1 + g % 4] END,
	   CASE WHEN g % 17 = 0 THEN NULL ELSE g % 3 = 0 END,
	   CASE WHEN g % 19 = 0 THEN NULL ELSE (g * 7919) % 500 END,
	   CASE WHEN g % 23 = 0 THEN NULL ELSE 'text ' || ((g * 48271) % 2000) END,
	   '2025-01-01'::timestamptz + ((g::int8 * 104729) % 5000) * interval '1 minute',
	   CASE WHEN g % 10 = 0 THEN NULL
			WHEN g % 10 = 1 THEN '{}'::int4[]
			WHEN g % 10 = 2 THEN ARRAY[NULL, g % 5]::int4[]
			ELSE ARRAY[g % 5, g % 50, g % 300, g % 5] END,
	   CASE WHEN g % 9 = 0 THEN NULL
			WHEN g % 9 = 1 THEN '{}'::text[]
			ELSE ARRAY['tag' || (g % 30), 'tag' || (g % 7), 'u' || g] END,
	   CASE WHEN g % 8 = 0 THEN NULL
			WHEN g % 8 = 1 THEN ''::tsvector
			ELSE to_tsvector('simple', 'word' || (g % 40) || ' other' || (g % 400)) END,
	   g::int8 * 1000003,
	   repeat('p', 20)
  FROM generate_series(1, 40000) g;
-- 2. HOT chains, made while the table has no index: a heap-only tuple is
--    reported under its chain's root offset, so the codes of one heap page
--    reach the build out of order.
UPDATE lion_build SET pad = pad || 'q' WHERE id % 5 = 0;
UPDATE lion_build SET pad = pad || 'r' WHERE id % 7 = 0;
UPDATE lion_build SET pad = pad || 's' WHERE id % 5 = 0;
SELECT count(*) > 1000 AS has_heap_only_tuples
  FROM generate_series(0, pg_relation_size('lion_build') /
					   current_setting('block_size')::int - 1) b,
	   heap_page_items(get_raw_page('lion_build', b::int))
 WHERE (t_infomask2 & 32768) <> 0;		-- HEAP_ONLY_TUPLE
 has_heap_only_tuples 
----------------------
 t
(1 row)

-- Without positions (positions.sql builds them): the shape check of section 5
-- counts a tsvector column's lexemes, and positions add a row-length key.
CREATE INDEX lion_build_all ON lion_build
	USING lion (mood, flag, n, t, ts, ia, ta, tv, u) WITH (store_positions = off);
CREATE INDEX lion_build_tv ON lion_build USING lion (tv) WITH (store_positions = off);
CREATE INDEX lion_build_part ON lion_build USING lion (n, t) WHERE flag;
CREATE INDEX lion_build_expr ON lion_build USING lion ((n % 10), lower(t));
-- 3. An unordered class whose hash collides all the time, so that the
--    distinct keys of one hash meet in memory, in one run and across runs;
--    and one whose equality is coarser than the bytes, so that which
--    spelling an entry stores depends on which row came first.
CREATE FUNCTION lion_build_xid_hash(xid) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT (($1::text)::int8 % 3)::int4 $$;
CREATE OPERATOR CLASS lion_build_xid_ops FOR TYPE xid USING lion AS
	OPERATOR 1 = (xid, xid),
	FUNCTION 1 lion_build_xid_hash(xid);
CREATE FUNCTION lion_build_lower_eq(text, text) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT lower($1) = lower($2) $$;
CREATE OPERATOR ==== (LEFTARG = text, RIGHTARG = text,
					  FUNCTION = lion_build_lower_eq, COMMUTATOR = ====);
CREATE FUNCTION lion_build_lower_hash(text) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT hashtext(lower($1)) $$;
CREATE OPERATOR CLASS lion_build_lower_ops FOR TYPE text USING lion AS
	OPERATOR 1 ==== (text, text),
	FUNCTION 1 lion_build_lower_hash(text);
CREATE UNLOGGED TABLE lion_build_coll (x xid, s text, pad text)
	WITH (fillfactor = 60, parallel_workers = 2);
INSERT INTO lion_build_coll
SELECT CASE WHEN g % 29 = 0 THEN NULL ELSE ((g * 7) % 12 + 1)::text::xid END,
	   CASE (g * 31) % 4 WHEN 0 THEN 'Key' WHEN 1 THEN 'kEY' WHEN 2 THEN 'KEY'
			ELSE 'key' END || (g % 50),
	   'p'
  FROM generate_series(1, 30000) g;
-- ... and HOT chains again, so that the first row of a spelling moves
UPDATE lion_build_coll SET pad = pad || 'q' WHERE x::text::int % 5 = 0;
CREATE INDEX lion_build_coll_x ON lion_build_coll
	USING lion (x lion_build_xid_ops, s lion_build_lower_ops);
CREATE INDEX lion_build_coll_s ON lion_build_coll USING lion (s lion_build_lower_ops);
-- ---------------------------------------------------------------------
-- 4. The same index every way: in memory, spilled (at the least
--    maintenance_work_mem there is), in parallel, and in parallel with every
--    participant spilling.
-- ---------------------------------------------------------------------
-- The least maintenance_work_mem there is: 64kB, and 1MB before 17.  These
-- tables fit in 1MB, so on 16 the "spilled" builds are in-memory builds and
-- only the comparison is exercised (build_1.out); 16 builds serially anyway.
SELECT CASE WHEN current_setting('server_version_num')::int >= 170000
			THEN '64kB' ELSE '1MB' END AS lion_build_least_mem \gset
CREATE TEMP TABLE lion_build_ways AS
SELECT idx::text AS idx,
	   lion_build_as(idx, '64MB', 0) AS in_memory,
	   lion_build_as(idx, :'lion_build_least_mem', 0) AS spilled,
	   lion_build_as(idx, '64MB', 2) AS parallel,
	   lion_build_as(idx, :'lion_build_least_mem', 2) AS parallel_spilled
  FROM unnest(ARRAY['lion_build_all', 'lion_build_tv', 'lion_build_part',
					'lion_build_expr', 'lion_build_coll_x',
					'lion_build_coll_s']::regclass[]) idx;
SELECT idx, spilled = in_memory AS spilled_same,
	   parallel = in_memory AS parallel_same,
	   parallel_spilled = in_memory AS parallel_spilled_same
  FROM lion_build_ways ORDER BY idx;
        idx        | spilled_same | parallel_same | parallel_spilled_same 
-------------------+--------------+---------------+-----------------------
 lion_build_all    | t            | t             | t
 lion_build_coll_s | t            | t             | t
 lion_build_coll_x | t            | t             | t
 lion_build_expr   | t            | t             | t
 lion_build_part   | t            | t             | t
 lion_build_tv     | t            | t             | t
(6 rows)

-- REINDEX CONCURRENTLY builds from an MVCC snapshot, serially and in parallel,
-- into a new index that then takes the old one's name
RESET maintenance_work_mem;
SET max_parallel_maintenance_workers = 0;
REINDEX INDEX CONCURRENTLY lion_build_all;
SELECT lion_build_digest('lion_build_all') = in_memory AS concurrently_same
  FROM lion_build_ways WHERE idx = 'lion_build_all';
 concurrently_same 
-------------------
 t
(1 row)

SET max_parallel_maintenance_workers = 2;
SET maintenance_work_mem = :'lion_build_least_mem';
REINDEX INDEX CONCURRENTLY lion_build_all;
SELECT lion_build_digest('lion_build_all') = in_memory AS concurrently_parallel_same
  FROM lion_build_ways WHERE idx = 'lion_build_all';
 concurrently_parallel_same 
----------------------------
 t
(1 row)

RESET maintenance_work_mem;
RESET max_parallel_maintenance_workers;
-- Which way each build went.
SET max_parallel_maintenance_workers = 2;
SET client_min_messages = debug1;
REINDEX INDEX lion_build_tv;
DEBUG:  building index "lion_build_tv" on table "lion_build" serially
DEBUG:  lion index "lion_build_tv": 1 key columns, 332 entries, 35 blocks, 30 directory pages, height 1, fillfactor 90, built in memory
SET max_parallel_maintenance_workers = 0;
REINDEX INDEX lion_build_tv;
DEBUG:  building index "lion_build_tv" on table "lion_build" serially
DEBUG:  lion index "lion_build_tv": 1 key columns, 332 entries, 35 blocks, 30 directory pages, height 1, fillfactor 90, built in memory
SET maintenance_work_mem = :'lion_build_least_mem';
REINDEX INDEX lion_build_tv;
DEBUG:  building index "lion_build_tv" on table "lion_build" serially
DEBUG:  lion index "lion_build_tv": 1 key columns, 332 entries, 35 blocks, 30 directory pages, height 1, fillfactor 90, built in memory
SET client_min_messages = warning;
RESET maintenance_work_mem;
RESET max_parallel_maintenance_workers;
-- ---------------------------------------------------------------------
-- 5. And it is the right index: verify() finds every heap row under every
--    key, and each column holds exactly as many keys, TIDs, NULL rows and
--    key-less rows as the heap says - so nothing is missing and nothing is
--    extra.  A posting set holds a TID once, so the totals settle it.
-- ---------------------------------------------------------------------
SELECT idx, lion_index_verify(idx::regclass, true) AS verified
  FROM lion_build_ways ORDER BY idx;
        idx        | verified 
-------------------+----------
 lion_build_all    | 
 lion_build_coll_s | 
 lion_build_coll_x | 
 lion_build_expr   | 
 lion_build_part   | 
 lion_build_tv     | 
(6 rows)

-- keys_sql gives each row's distinct non-NULL keys as text[], NULL for NULL
CREATE FUNCTION lion_build_shape(keys_sql text, OUT keys int8, OUT pairs int8,
								 OUT nulls int8, OUT empties int8)
	LANGUAGE plpgsql AS $$
BEGIN
	EXECUTE format($q$
		WITH r AS (SELECT (%s) AS a FROM lion_build)
		SELECT (SELECT count(DISTINCT e) FROM r, unnest(a) e),
			   (SELECT coalesce(sum(cardinality(a)), 0) FROM r),
			   (SELECT count(*) FROM r WHERE a IS NULL),
			   (SELECT count(*) FROM r WHERE a = '{}')$q$, keys_sql)
		INTO keys, pairs, nulls, empties;
END $$;
SELECT s.attno, s.entries, s.ntids, s.null_tids, s.empty_tids,
	   s.entries = h.keys + (h.nulls > 0)::int + (h.empties > 0)::int
	   AND s.ntids = h.pairs + h.nulls + h.empties
	   AND s.null_tids = h.nulls AND s.empty_tids = h.empties AS exact
  FROM lion_index_stats('lion_build_all') s
  JOIN (VALUES (1, 'CASE WHEN mood IS NULL THEN NULL ELSE ARRAY[mood::text] END'),
			   (2, 'CASE WHEN flag IS NULL THEN NULL ELSE ARRAY[flag::text] END'),
			   (3, 'CASE WHEN n IS NULL THEN NULL ELSE ARRAY[n::text] END'),
			   (4, 'CASE WHEN t IS NULL THEN NULL ELSE ARRAY[t] END'),
			   (5, 'CASE WHEN ts IS NULL THEN NULL ELSE ARRAY[ts::text] END'),
			   (6, 'CASE WHEN ia IS NULL THEN NULL ELSE ARRAY(SELECT DISTINCT e::text FROM unnest(ia) e WHERE e IS NOT NULL) END'),
			   (7, 'CASE WHEN ta IS NULL THEN NULL ELSE ARRAY(SELECT DISTINCT e FROM unnest(ta) e WHERE e IS NOT NULL) END'),
			   (8, 'CASE WHEN tv IS NULL THEN NULL ELSE tsvector_to_array(tv) END'),
			   (9, 'CASE WHEN u IS NULL THEN NULL ELSE ARRAY[u::text] END')) c(attno, keys_sql)
	ON c.attno = s.attno,
	   lion_build_shape(c.keys_sql) h
 ORDER BY s.attno;
 attno | entries | ntids  | null_tids | empty_tids | exact 
-------+---------+--------+-----------+------------+-------
     1 |       5 |  40000 |      3076 |          0 | t
     2 |       3 |  40000 |      2352 |          0 | t
     3 |     501 |  40000 |      2105 |          0 | t
     4 |    2001 |  40000 |      1739 |          0 | t
     5 |    5000 |  40000 |         0 |          0 | t
     6 |     215 |  89710 |      4000 |       4000 | t
     7 |   31143 | 101203 |      4444 |       4445 | t
     8 |     332 |  70000 |      5000 |       5000 | t
     9 |   40000 |  40000 |         0 |          0 | t
(9 rows)

-- one entry per spelling class, which counts every spelling
SELECT lion_index_count_any('lion_build_coll_s', ARRAY['KEY7', 'key7']::text[]) =
	   (SELECT count(*) FROM lion_build_coll WHERE lower(s) = 'key7') AS class_count;
 class_count 
-------------
 t
(1 row)

SELECT entries FROM lion_index_stats('lion_build_coll_s');
 entries 
---------
      50
(1 row)

-- ---------------------------------------------------------------------
-- 6. Parallel only where the index expressions can run in a worker: a
--    parallel-unsafe expression makes it a serial build.  (PL/pgSQL, because
--    a SQL function this simple would be inlined, and the inlined expression
--    is safe.)
-- ---------------------------------------------------------------------
CREATE FUNCTION lion_build_unsafe(int) RETURNS int
	LANGUAGE plpgsql IMMUTABLE PARALLEL UNSAFE AS $$ BEGIN RETURN $1 % 10; END $$;
CREATE INDEX lion_build_unsafe_i ON lion_build USING lion (lion_build_unsafe(n));
SET max_parallel_maintenance_workers = 2;
SET client_min_messages = debug1;
REINDEX INDEX lion_build_unsafe_i;
DEBUG:  building index "lion_build_unsafe_i" on table "lion_build" serially
DEBUG:  lion index "lion_build_unsafe_i": 1 key columns, 11 entries, 23 blocks, 1 directory pages, height 0, fillfactor 90, built in memory
SET client_min_messages = warning;
RESET max_parallel_maintenance_workers;
SELECT lion_index_verify('lion_build_unsafe_i', true);
 lion_index_verify 
-------------------
 
(1 row)

-- ---------------------------------------------------------------------
-- 7. The write split by column (DESIGN.md §24, "Parallel build"): the
--    workers write the columns after the first to files of their own,
--    numbering the blocks themselves, and the leader renumbers them as it
--    writes them.  So the columns after the first hold every kind of block
--    reference there is - posting trees with internal pages, position
--    trees, summaries and NARROW items - and the index has to come out the
--    serial build's, page for page.  The first column, a key a row, keeps
--    the leader busy while the workers take the next two.
-- ---------------------------------------------------------------------
CREATE UNLOGGED TABLE lion_build_split (id int, k int, s int, tv tsvector,
										pad text)
	WITH (fillfactor = 20, parallel_workers = 2);
INSERT INTO lion_build_split
SELECT g, g % 2, g / 50,
	   to_tsvector('simple', format('every w%s every', g % 3)),
	   repeat('p', 100)
  FROM generate_series(1, 30000) g;
CREATE INDEX lion_build_split_i ON lion_build_split USING lion (id, k, s, tv)
	WITH (posting_fillfactor = 10, summaries = on, store_positions = on);
SELECT lion_build_as('lion_build_split_i', '64MB', 0) AS lion_build_split_serial
\gset
SELECT lion_build_as('lion_build_split_i', '64MB', 2) =
	   :'lion_build_split_serial' AS parallel_same,
	   lion_build_as('lion_build_split_i', :'lion_build_least_mem', 2) =
	   :'lion_build_split_serial' AS parallel_spilled_same;
 parallel_same | parallel_spilled_same 
---------------+-----------------------
 t             | t
(1 row)

RESET maintenance_work_mem;
RESET max_parallel_maintenance_workers;
SELECT lion_index_verify('lion_build_split_i', true);
 lion_index_verify 
-------------------
 
(1 row)

SELECT attno, max_posting_height > 0 AS posting_trees,
	   summary_entries > 0 AS summaries, narrow_containers > 0 AS narrow
  FROM lion_index_stats('lion_build_split_i') ORDER BY attno;
 attno | posting_trees | summaries | narrow 
-------+---------------+-----------+--------
     1 | t             | t         | f
     2 | t             | t         | t
     3 | t             | t         | f
     4 | t             | f         | f
(4 rows)

-- 'every' is in every row twice, so its positions are a tree
SET enable_seqscan = off;
SELECT count(*) FILTER (WHERE tv @@ 'w1 <-> every'::tsquery) AS w1_every,
	   count(*) FILTER (WHERE tv @@ 'every <2> every'::tsquery) AS every_every
  FROM lion_build_split WHERE tv @@ 'every'::tsquery;
 w1_every | every_every 
----------+-------------
    10000 |       30000
(1 row)

RESET enable_seqscan;
DROP TABLE lion_build, lion_build_coll, lion_build_split;
DROP TYPE lion_build_mood;
DROP OPERATOR CLASS lion_build_xid_ops USING lion;
DROP OPERATOR CLASS lion_build_lower_ops USING lion;
DROP OPERATOR ==== (text, text);
DROP FUNCTION lion_build_xid_hash(xid), lion_build_lower_eq(text, text),
	lion_build_lower_hash(text), lion_build_unsafe(int),
	lion_build_shape(text),
	lion_build_digest(regclass), lion_build_as(regclass, text, int);