-- The sorted key directory (DESIGN.md §21).
--
-- Everything here is about the entry directory being a B-tree keyed by the
-- index key instead of a fixed set of hash buckets: that it grows by
-- splitting (at every level, root splits included), that an ordered opclass
-- makes the entry scan - and therefore a GROUP BY - come out in key order,
-- that an opclass whose comparison is coarser than byte equality still keeps
-- one entry per equality class, and that a sorted IN list costs one pass over
-- the leaves its values live on.
\set VERBOSITY terse
SET client_min_messages = warning;
LOAD 'pg_lion';
SET synchronous_commit = on;

CREATE EXTENSION IF NOT EXISTS pg_lion;

-- ---------------------------------------------------------------------
-- 1. An index created on an EMPTY table and grown by inserts.
--
-- This is the case the hash directory could not answer: it kept the 64
-- buckets it was built with for ever and every lookup walked a chain of a
-- dozen pages.  The tree splits instead, so the height grows and the lookups
-- stay logarithmic.
-- ---------------------------------------------------------------------

CREATE TABLE lion_dir (id int, k text NOT NULL);
CREATE INDEX lion_dir_k ON lion_dir USING lion (k);

-- An empty index is one leaf, which is also the root.
SELECT directory_height, leaf_pages, internal_pages, ordered, entries
	FROM lion_index_stats('lion_dir_k');

INSERT INTO lion_dir SELECT i, 'key' || lpad(i::text, 8, '0')
	FROM generate_series(1, 50000) i;
SELECT lion_index_verify('lion_dir_k');
SELECT directory_height > 0 AS has_internal_pages,
	   internal_pages > 0 AS internal_pages_exist,
	   entries = 50000 AS all_keys
	FROM lion_index_stats('lion_dir_k');

INSERT INTO lion_dir SELECT i, 'key' || lpad(i::text, 8, '0')
	FROM generate_series(50001, 100000) i;
SELECT lion_index_verify('lion_dir_k');

-- Descending keys as well, so that splits happen on the LEFT of the tree and
-- not only by appending to the rightmost page.
INSERT INTO lion_dir SELECT i, 'key' || lpad(i::text, 8, '0')
	FROM generate_series(150000, 100001, -1) i;
SELECT lion_index_verify('lion_dir_k');

-- ... and in random order, which is what really exercises the split point.
INSERT INTO lion_dir SELECT i, 'key' || lpad(i::text, 8, '0')
	FROM generate_series(150001, 200000) i ORDER BY hashint4(i);
SELECT lion_index_verify('lion_dir_k', true);

SELECT entries = 200000 AS all_keys,
	   directory_height >= 2 AS root_split_happened,
	   leaf_pages > 100 AS many_leaves,
	   internal_pages > 1 AS many_internal_pages
	FROM lion_index_stats('lion_dir_k');

-- Every key is findable, the first and the last included.
SELECT count(*) FROM lion_dir WHERE k = 'key00000001';
SELECT count(*) FROM lion_dir WHERE k = 'key00200000';
SELECT count(*) FROM lion_dir WHERE k = 'key00123456';
SELECT count(*) FROM lion_dir WHERE k = 'nosuchkey';

-- A REINDEX builds the same index from the same rows: same answers, and the
-- bulk-built tree is shallower than the one grown by inserts.
SELECT count(*) AS grown_rows FROM lion_dir;
REINDEX INDEX lion_dir_k;
SELECT lion_index_verify('lion_dir_k', true);
SELECT entries = 200000 AS all_keys FROM lion_index_stats('lion_dir_k');
SELECT count(*) FROM lion_dir WHERE k = 'key00123456';

DROP TABLE lion_dir;

-- ---------------------------------------------------------------------
-- 2. Ordered output: a GROUP BY driven by the index needs no Sort.
-- ---------------------------------------------------------------------

CREATE TABLE lion_ord (k int NOT NULL, nk int, v int);
INSERT INTO lion_ord
	SELECT i % 200, CASE WHEN i % 13 = 0 THEN NULL ELSE i % 200 END, i
	FROM generate_series(1, 100000) i;
CREATE INDEX lion_ord_k ON lion_ord USING lion (k);
CREATE INDEX lion_ord_nk ON lion_ord USING lion (nk);
VACUUM (FREEZE, ANALYZE) lion_ord;

SELECT ordered FROM lion_index_stats('lion_ord_k');

-- No Sort above the node: the groups already come out in key order.
EXPLAIN (COSTS OFF) SELECT k, count(*) FROM lion_ord GROUP BY k ORDER BY k;
SELECT k, count(*) FROM lion_ord GROUP BY k ORDER BY k LIMIT 3;

/*
 * ... and the node's own output really is in key order, with nothing above it
 * asking for one.  The check runs the query through EXECUTE so that it is
 * planned exactly as it is written - a GROUP BY buried in a subquery is
 * flattened into a HashAggregate over the heap, which would prove nothing at
 * all about the directory.
 */
CREATE FUNCTION lion_groups_monotonic(q text, rising bool) RETURNS boolean
	LANGUAGE plpgsql AS $$
DECLARE
	r record;
	prev bigint := NULL;
BEGIN
	FOR r IN EXECUTE q LOOP
		IF prev IS NOT NULL THEN
			IF rising AND r.k <= prev THEN
				RETURN false;
			END IF;
			IF NOT rising AND r.k >= prev THEN
				RETURN false;
			END IF;
		END IF;
		prev := r.k;
	END LOOP;
	RETURN true;
END $$;

EXPLAIN (COSTS OFF) SELECT k, count(*) FROM lion_ord GROUP BY k;
SELECT lion_groups_monotonic('SELECT k, count(*) FROM lion_ord GROUP BY k',
							 true) AS groups_in_key_order;

-- A NULLABLE group column keeps its Sort: the reserved NULL entry sorts
-- FIRST and `ORDER BY nk` means NULLS LAST.
EXPLAIN (COSTS OFF) SELECT nk, count(*) FROM lion_ord GROUP BY nk ORDER BY nk;

-- DESC needs a Sort too.
EXPLAIN (COSTS OFF) SELECT k, count(*) FROM lion_ord GROUP BY k ORDER BY k DESC;

DROP TABLE lion_ord;

-- ---------------------------------------------------------------------
-- 3. A type with no btree opclass at all: xid.  The directory is ordered by
-- (hash, stored bytes), which is a complete order but not the type's, so
-- ordered = false and nothing may claim the output is sorted.
-- ---------------------------------------------------------------------

CREATE TABLE lion_unord (x xid NOT NULL, v int);
INSERT INTO lion_unord SELECT (i % 50)::text::xid, i
	FROM generate_series(1, 20000) i;
CREATE INDEX lion_unord_x ON lion_unord USING lion (x);
VACUUM (FREEZE, ANALYZE) lion_unord;

SELECT ordered FROM lion_index_stats('lion_unord_x');
SELECT lion_index_verify('lion_unord_x', true);

-- The counts are right whatever the order.
SELECT count(*) FROM lion_unord WHERE x = '7'::xid;
SELECT sum(c) AS total, count(*) AS groups
	FROM (SELECT x, count(*) AS c FROM lion_unord GROUP BY x) g;

-- ... but the plan keeps its Sort, because the entry order is not xid's.
EXPLAIN (COSTS OFF)
	SELECT x, count(*) FROM lion_unord GROUP BY x ORDER BY x::text;

DROP TABLE lion_unord;

-- ---------------------------------------------------------------------
-- 4. An IN list of 1000 sorted values costs one pass over the leaves.
--
-- "Directory Pages Read" is the leaves and internal pages the node read.  A
-- thousand values located in one left-to-right walk may read each leaf they
-- live on once, plus the descents it takes to get there; a thousand separate
-- descents would be several times that.
-- ---------------------------------------------------------------------

CREATE TABLE lion_in (k int NOT NULL, v int);
INSERT INTO lion_in SELECT i % 20000, i FROM generate_series(1, 200000) i;
CREATE INDEX lion_in_k ON lion_in USING lion (k);
VACUUM (FREEZE, ANALYZE) lion_in;

CREATE FUNCTION lion_dirpages(q text) RETURNS bigint LANGUAGE plpgsql AS $$
DECLARE
	j json;
BEGIN
	EXECUTE 'EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF, BUFFERS OFF, FORMAT JSON) '
		|| q INTO j;
	RETURN (j -> 0 -> 'Plan' ->> 'Directory Pages Read')::bigint;
END $$;

SELECT count(*) FROM lion_in WHERE k = ANY (ARRAY(SELECT generate_series(0, 999)));

SELECT lion_dirpages('SELECT count(*) FROM lion_in WHERE k = ANY (ARRAY(SELECT generate_series(0, 999)))')
	   <= (SELECT leaf_pages + directory_height + 2
		   FROM lion_index_stats('lion_in_k'))
	AS sorted_list_is_one_pass;

-- A single key is one descent: the root, its internal pages and the leaf.
SELECT lion_dirpages('SELECT count(*) FROM lion_in WHERE k = 1234')
	   <= (SELECT directory_height + 1 FROM lion_index_stats('lion_in_k'))
	AS single_key_is_one_descent;

DROP FUNCTION lion_dirpages(text);
DROP TABLE lion_in;

-- ---------------------------------------------------------------------
-- 5. fillfactor: 10 packs the leaves a tenth full, 100 completely.
-- ---------------------------------------------------------------------

CREATE TABLE lion_ff (k int NOT NULL);
INSERT INTO lion_ff SELECT i FROM generate_series(1, 50000) i;
CREATE INDEX lion_ff_10 ON lion_ff USING lion (k) WITH (fillfactor = 10);
CREATE INDEX lion_ff_100 ON lion_ff USING lion (k) WITH (fillfactor = 100);
SELECT lion_index_verify('lion_ff_10', true);
SELECT lion_index_verify('lion_ff_100', true);
SELECT (SELECT leaf_pages FROM lion_index_stats('lion_ff_10')) >
	   4 * (SELECT leaf_pages FROM lion_index_stats('lion_ff_100'))
	AS fillfactor_10_is_much_bigger;
SELECT count(*) FROM lion_ff WHERE k = 31337;
DROP TABLE lion_ff;

-- ---------------------------------------------------------------------
-- 7. The INTERNAL levels are packed independently of `fillfactor`.
--
-- fillfactor is about leaving room on the LEAVES for later inserts.  Applied
-- to an internal page it can leave one downlink on it, which makes every
-- level as large as the one below and the bottom-up build never reaches a
-- root at all (it ran until the statement timeout).  An internal page always
-- takes at least two downlinks, whatever the fill target says.
-- ---------------------------------------------------------------------

CREATE TABLE lion_ffi (k text NOT NULL);
INSERT INTO lion_ffi SELECT repeat('k', 500) || lpad(i::text, 6, '0')
	FROM generate_series(1, 3000) i;
CREATE INDEX lion_ffi_k ON lion_ffi USING lion (k) WITH (fillfactor = 10);
SELECT lion_index_verify('lion_ffi_k', true);
SELECT directory_height > 0 AS has_internal_levels,
	   internal_pages < leaf_pages AS levels_shrink,
	   entries = 3000 AS all_keys
	FROM lion_index_stats('lion_ffi_k');
SELECT count(*) FROM lion_ffi WHERE k = repeat('k', 500) || '001234';
DROP TABLE lion_ffi;

-- ---------------------------------------------------------------------
-- 8. A key much larger than the ones already on the page.
--
-- The high key a page is closed with is the first key of the page to its
-- right, and a LION_MAX_KEY_SIZE one arriving behind a page full of short
-- keys does not fit next to them.  nbtree's rule is that the item which
-- becomes the first of the next page supplies the high key, so trailing items
-- move right until the key fits; reserving for the incoming key alone
-- overflowed the page and the build failed outright.
-- ---------------------------------------------------------------------

CREATE TABLE lion_bigkey (k text NOT NULL);
INSERT INTO lion_bigkey SELECT 'k' || lpad(i::text, 7, '0')
	FROM generate_series(1, 12000) i;
-- one long key right behind a short one, at every distance from a page
-- boundary: the gaps between them are 1, 2, 3, ... keys
INSERT INTO lion_bigkey
	SELECT 'k' || lpad(i::text, 7, '0') || repeat('x', 2035)
	FROM generate_series(1, 150) t, LATERAL (SELECT (t * (t + 1) / 2) AS i) s;
CREATE INDEX lion_bigkey_k ON lion_bigkey USING lion (k);
SELECT lion_index_verify('lion_bigkey_k', true);
CREATE INDEX lion_bigkey_k100 ON lion_bigkey USING lion (k)
	WITH (fillfactor = 100);
SELECT lion_index_verify('lion_bigkey_k100', true);
SELECT count(*) FROM lion_bigkey WHERE k = 'k0000105' || repeat('x', 2035);
DROP TABLE lion_bigkey;

-- ---------------------------------------------------------------------
-- 9. An opclass whose equality is COARSER than the key type's.
--
-- Such a class holds one entry per equality class - 'A' and 'a' share one -
-- and the key type's own comparison separates the two spellings, so borrowing
-- it would put the entry where only one of them looks for it.  An opclass
-- without support proc 4 is therefore UNORDERED unless its equality IS the
-- key type's default btree equality, in which case borrowing is provably
-- consistent.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_dir_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_dir_lower_eq, COMMUTATOR = ====);
CREATE FUNCTION lion_dir_lower_hash(text) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT hashtext(lower($1)) $$;
CREATE OPERATOR CLASS lion_dir_lower_ops FOR TYPE text USING lion AS
	OPERATOR 1 ==== (text, text),
	FUNCTION 1 lion_dir_lower_hash(text);

CREATE TABLE lion_coarse (v text NOT NULL);
INSERT INTO lion_coarse SELECT 'A' FROM generate_series(1, 1000);
INSERT INTO lion_coarse SELECT 'a' FROM generate_series(1, 1000);
INSERT INTO lion_coarse SELECT 'B' || i FROM generate_series(1, 1000) i;
CREATE INDEX lion_coarse_v ON lion_coarse USING lion (v lion_dir_lower_ops);
-- one entry for the two spellings, and no ordering claimed for the class
SELECT ordered, entries = 1001 AS one_entry_per_class
	FROM lion_index_stats('lion_coarse_v');
-- BOTH spellings find that entry; the stored one used to be the only one that did
SELECT lion_index_count('lion_coarse_v', 'A'::text) AS stored_spelling,
	   lion_index_count('lion_coarse_v', 'a'::text) AS other_spelling;
SELECT lion_index_count_any('lion_coarse_v', ARRAY['a','A']::text[]) AS in_list;
SELECT count(*) FROM lion_coarse WHERE v ==== 'a';
SELECT lion_index_verify('lion_coarse_v', true);
DROP TABLE lion_coarse;

-- The same class WITHOUT the coarse equality: its strategy 1 is text's own
-- default btree equality, so borrowing bttextcmp is consistent and the index
-- is ordered even though the class names no support proc 4.
CREATE OPERATOR CLASS lion_dir_plain_ops FOR TYPE text USING lion AS
	OPERATOR 1 = (text, text),
	FUNCTION 1 hashtext(text);
CREATE TABLE lion_borrowed (v text NOT NULL);
INSERT INTO lion_borrowed SELECT 'v' || lpad(i::text, 6, '0')
	FROM generate_series(1, 2000) i;
CREATE INDEX lion_borrowed_v ON lion_borrowed
	USING lion (v lion_dir_plain_ops);
SELECT ordered, entries FROM lion_index_stats('lion_borrowed_v');
SELECT lion_index_verify('lion_borrowed_v', true);
DROP TABLE lion_borrowed;
DROP OPERATOR CLASS lion_dir_plain_ops USING lion;
DROP OPERATOR CLASS lion_dir_lower_ops USING lion;
DROP OPERATOR ==== (text, text);
DROP FUNCTION lion_dir_lower_eq(text, text);
DROP FUNCTION lion_dir_lower_hash(text);

-- ---------------------------------------------------------------------
-- 10. An opclass with a comparison of its OWN (support proc 4).
--
-- The build sorts with an OPERATOR and the directory descends with a
-- FUNCTION, and §21 needs them to be the same order exactly.  The operator is
-- therefore the `<` of the btree family that uses the very same comparison
-- support function, and not the key type's default `<`: sorting one way and
-- searching the other leaves every key where no search looks for it.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_rev_cmp(int4, int4) RETURNS int4
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT btint4cmp($2, $1) $$;
CREATE FUNCTION lion_rev_lt(int4, int4) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT $1 > $2 $$;
CREATE FUNCTION lion_rev_le(int4, int4) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT $1 >= $2 $$;
CREATE FUNCTION lion_rev_eq(int4, int4) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT $1 = $2 $$;
CREATE FUNCTION lion_rev_ge(int4, int4) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT $1 <= $2 $$;
CREATE FUNCTION lion_rev_gt(int4, int4) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT $1 < $2 $$;
CREATE OPERATOR <# (LEFTARG = int4, RIGHTARG = int4, FUNCTION = lion_rev_lt,
					COMMUTATOR = >#, NEGATOR = >=#);
CREATE OPERATOR <=# (LEFTARG = int4, RIGHTARG = int4, FUNCTION = lion_rev_le,
					 COMMUTATOR = >=#, NEGATOR = >#);
CREATE OPERATOR =# (LEFTARG = int4, RIGHTARG = int4, FUNCTION = lion_rev_eq,
					COMMUTATOR = =#);
CREATE OPERATOR >=# (LEFTARG = int4, RIGHTARG = int4, FUNCTION = lion_rev_ge,
					 COMMUTATOR = <=#, NEGATOR = <#);
CREATE OPERATOR ># (LEFTARG = int4, RIGHTARG = int4, FUNCTION = lion_rev_gt,
					COMMUTATOR = <#, NEGATOR = <=#);
CREATE OPERATOR CLASS lion_rev_btree FOR TYPE int4 USING btree AS
	OPERATOR 1 <#, OPERATOR 2 <=#, OPERATOR 3 =#, OPERATOR 4 >=#, OPERATOR 5 >#,
	FUNCTION 1 lion_rev_cmp(int4, int4);
CREATE OPERATOR CLASS lion_rev_ops FOR TYPE int4 USING lion AS
	OPERATOR 1 = (int4, int4),
	FUNCTION 1 hashint4(int4),
	FUNCTION 4 lion_rev_cmp(int4, int4);

CREATE TABLE lion_rev (k int NOT NULL);
INSERT INTO lion_rev SELECT i % 500 FROM generate_series(1, 5000) i;
CREATE INDEX lion_rev_k ON lion_rev USING lion (k lion_rev_ops);
VACUUM (FREEZE, ANALYZE) lion_rev;
SELECT ordered, entries FROM lion_index_stats('lion_rev_k');
-- build order == search order: every key is where the descent looks for it
SELECT lion_index_verify('lion_rev_k', true);
SELECT count(*) AS keys_not_found FROM generate_series(0, 499) g
	WHERE lion_index_count('lion_rev_k', g) <> 10;
-- the groups come out in the OPCLASS's order, which is descending (the node
-- is forced: 500 groups of 10 rows each are a sequential scan's to win, and
-- this opclass's SQL comparison makes every entry of the walk dearer still)
SET enable_seqscan = off;
EXPLAIN (COSTS OFF) SELECT k, count(*) FROM lion_rev GROUP BY k;
SELECT k, count(*) FROM lion_rev GROUP BY k LIMIT 3;
SELECT lion_groups_monotonic('SELECT k, count(*) FROM lion_rev GROUP BY k',
							 false) AS groups_in_opclass_order;
-- ... and that is not int4's own order, so an ORDER BY keeps its Sort
EXPLAIN (COSTS OFF) SELECT k, count(*) FROM lion_rev GROUP BY k ORDER BY k;
RESET enable_seqscan;
DROP TABLE lion_rev;

-- A comparison that belongs to no btree family at all cannot drive a
-- tuplesort, and an ordering the build cannot reproduce is no ordering: the
-- index is unordered instead, which is still correct.
CREATE FUNCTION lion_odd_cmp(int4, int4) RETURNS int4
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT btint4cmp($2, $1) $$;
CREATE OPERATOR CLASS lion_odd_ops FOR TYPE int4 USING lion AS
	OPERATOR 1 = (int4, int4),
	FUNCTION 1 hashint4(int4),
	FUNCTION 4 lion_odd_cmp(int4, int4);
CREATE TABLE lion_odd (k int NOT NULL);
INSERT INTO lion_odd SELECT i % 500 FROM generate_series(1, 5000) i;
CREATE INDEX lion_odd_k ON lion_odd USING lion (k lion_odd_ops);
SELECT ordered, entries FROM lion_index_stats('lion_odd_k');
SELECT lion_index_verify('lion_odd_k', true);
SELECT count(*) AS keys_not_found FROM generate_series(0, 499) g
	WHERE lion_index_count('lion_odd_k', g) <> 10;
DROP TABLE lion_odd;
DROP OPERATOR CLASS lion_odd_ops USING lion;
DROP FUNCTION lion_odd_cmp(int4, int4);
-- (lion_rev_btree and its comparison are used again by §14.)

-- ---------------------------------------------------------------------
-- 11. Hash collisions under an UNORDERED opclass.
--
-- Without an ordering the entries of one hash are ordered by their stored
-- BYTES, and the sort only brings the hash together: the several distinct
-- keys inside one hash arrive interleaved and used to be written out in the
-- order their first TID happened to turn up.  The reserved NULL entry hashes
-- to 0 and shares its run with any key that hashes there, which used to split
-- it into several entries.
--
-- `xid` has no btree opclass at all, so a class over it is unordered whatever
-- its equality is; the hash here is deliberately coarse so that every value
-- collides with a great many others.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_coarse_xid_hash(xid) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT (($1::text)::int8 % 7)::int4 $$;
CREATE OPERATOR CLASS lion_coarse_xid_ops FOR TYPE xid USING lion AS
	OPERATOR 1 = (xid, xid),
	FUNCTION 1 lion_coarse_xid_hash(xid);

CREATE TABLE lion_coll (x xid, v int);
INSERT INTO lion_coll
	SELECT CASE WHEN i % 11 = 0 THEN NULL ELSE (i % 300 + 1)::text::xid END, i
	FROM generate_series(1, 6000) i;
CREATE INDEX lion_coll_x ON lion_coll USING lion (x lion_coarse_xid_ops);
VACUUM (ANALYZE) lion_coll;
-- 300 keys and ONE reserved NULL entry, in the order the directory wants
SELECT ordered, entries FROM lion_index_stats('lion_coll_x');
SELECT lion_index_verify('lion_coll_x', true);
-- every key's posting set holds exactly the rows the heap has for it
SET pg_lion.enable_count_pushdown = off;
CREATE TEMP TABLE lion_coll_exp AS
	SELECT x, count(*) AS c FROM lion_coll WHERE x IS NOT NULL GROUP BY x;
RESET pg_lion.enable_count_pushdown;
SELECT count(*) AS keys, count(*) FILTER (
		WHERE lion_index_count('lion_coll_x', e.x) <> e.c) AS keys_wrong
	FROM lion_coll_exp e;
DROP TABLE lion_coll_exp;
-- the pushdown answers exactly what the heap does
SELECT count(*) FROM lion_coll WHERE x IS NULL;
SELECT count(*) FROM lion_coll WHERE x IS NOT NULL;
SELECT sum(c) AS total, count(*) AS groups
	FROM (SELECT x, count(*) AS c FROM lion_coll GROUP BY x) g;
SET pg_lion.enable_count_pushdown = off;
SELECT sum(c) AS total, count(*) AS groups
	FROM (SELECT x, count(*) AS c FROM lion_coll GROUP BY x) g;
RESET pg_lion.enable_count_pushdown;
DROP TABLE lion_coll;

-- The INSERT path places colliding keys by the same order.
CREATE TABLE lion_colli (x xid, v int);
CREATE INDEX lion_colli_x ON lion_colli USING lion (x lion_coarse_xid_ops);
INSERT INTO lion_colli
	SELECT CASE WHEN i % 11 = 0 THEN NULL ELSE (i % 300 + 1)::text::xid END, i
	FROM generate_series(1, 6000) i;
SELECT ordered, entries FROM lion_index_stats('lion_colli_x');
SELECT lion_index_verify('lion_colli_x', true);
SET pg_lion.enable_count_pushdown = off;
CREATE TEMP TABLE lion_colli_exp AS
	SELECT x, count(*) AS c FROM lion_colli WHERE x IS NOT NULL GROUP BY x;
RESET pg_lion.enable_count_pushdown;
SELECT count(*) AS keys, count(*) FILTER (
		WHERE lion_index_count('lion_colli_x', e.x) <> e.c) AS keys_wrong
	FROM lion_colli_exp e;
DROP TABLE lion_colli_exp;
SELECT count(*) FROM lion_colli WHERE x IS NULL;
DROP TABLE lion_colli;
DROP OPERATOR CLASS lion_coarse_xid_ops USING lion;
DROP FUNCTION lion_coarse_xid_hash(xid);

-- ---------------------------------------------------------------------
-- 12. Cross-type values on an ORDERED index.
--
-- A value of another type can be descended for when the family offers the
-- cross-type ordering (support proc 4), or when it casts to the key type;
-- otherwise the leaves are walked with the cross-type equality instead.  The
-- single and the batched lookup must make that decision the same way - the
-- batched one used to descend a key-ordered tree in HASH order and come back
-- with nothing.
-- ---------------------------------------------------------------------

-- The shipped integer family has the cross-type ordering.
CREATE TABLE lion_xt (k int NOT NULL, v int);
INSERT INTO lion_xt SELECT i % 2000, i FROM generate_series(1, 40000) i;
CREATE INDEX lion_xt_k ON lion_xt USING lion (k);
VACUUM (ANALYZE) lion_xt;
SELECT lion_index_count('lion_xt_k', 7::int8) AS one_int8,
	   lion_index_count('lion_xt_k', 7::int2) AS one_int2;
SELECT lion_index_count_any('lion_xt_k',
							ARRAY(SELECT (i * 7)::int8 FROM generate_series(1, 200) i)) AS many_int8,
	   lion_index_count_any('lion_xt_k',
							ARRAY(SELECT (i * 7)::int2 FROM generate_series(1, 200) i)) AS many_int2;
SELECT count(*) FROM lion_xt
	WHERE k = ANY (ARRAY(SELECT (i * 7)::int8 FROM generate_series(1, 200) i));
DROP TABLE lion_xt;

-- A family with cross-type equality and hash but NO cross-type ordering.
CREATE OPERATOR FAMILY lion_noxcmp_ops USING lion;
CREATE OPERATOR CLASS lion_noxcmp_int4_ops FOR TYPE int4 USING lion
	FAMILY lion_noxcmp_ops AS
	OPERATOR 1 = (int4, int4),
	FUNCTION 1 hashint4(int4),
	FUNCTION 4 btint4cmp(int4, int4);
ALTER OPERATOR FAMILY lion_noxcmp_ops USING lion ADD
	OPERATOR 1 = (int4, int8),
	OPERATOR 1 = (int4, int2),
	FUNCTION 1 (int8, int8) hashint8(int8),
	FUNCTION 1 (int2, int2) hashint2(int2);

CREATE TABLE lion_noxcmp (k int NOT NULL, v int);
INSERT INTO lion_noxcmp SELECT i % 2000, i FROM generate_series(1, 40000) i;
CREATE INDEX lion_noxcmp_k ON lion_noxcmp
	USING lion (k lion_noxcmp_int4_ops);
VACUUM (ANALYZE) lion_noxcmp;
SELECT ordered FROM lion_index_stats('lion_noxcmp_k');
-- one value at a time: the leaf walk of §21
SELECT lion_index_count('lion_noxcmp_k', 7::int8) AS one_int8,
	   lion_index_count('lion_noxcmp_k', 7::int2) AS one_int2;
-- a whole list: the same answers, which is the point
SELECT lion_index_count_any('lion_noxcmp_k', ARRAY[1,2,3,4,5]::int8[]) AS five_int8,
	   lion_index_count_any('lion_noxcmp_k', ARRAY[1,2,3,4,5]::int2[]) AS five_int2;
SELECT lion_index_count_any('lion_noxcmp_k',
							ARRAY(SELECT (i * 7)::int8 FROM generate_series(1, 200) i)) AS many_int8;
SELECT count(*) FROM lion_noxcmp
	WHERE k = ANY (ARRAY(SELECT (i * 7)::int8 FROM generate_series(1, 200) i));
SET pg_lion.enable_count_pushdown = off;
SELECT count(*) FROM lion_noxcmp
	WHERE k = ANY (ARRAY(SELECT (i * 7)::int8 FROM generate_series(1, 200) i));
RESET pg_lion.enable_count_pushdown;
DROP TABLE lion_noxcmp;
DROP OPERATOR FAMILY lion_noxcmp_ops USING lion CASCADE;

-- ---------------------------------------------------------------------
-- 13. verify() treats two entries of ONE equality class as corruption.
--
-- The directory holds exactly one entry per equality class, and a lookup
-- returns the first entry of the class it meets - so a second one holds rows
-- that no lookup ever finds.  Two concurrent writers creating the same key
-- used to be able to make one (test/isolation/dir_insert_race.spec); verify()
-- must say so whenever it happens.  The class here has an equality that a
-- setting switches, which is how the test manufactures the two shapes a
-- duplicate can take: byte-identical twins, and two different spellings of
-- one class (the citext shape), which the per-page ordering check alone
-- cannot see.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_dup_eq(text, text) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$
	SELECT CASE current_setting('lion_test.eq_mode', true)
		WHEN 'never' THEN false
		WHEN 'fold' THEN lower($1) = lower($2)
		ELSE $1 = $2 END $$;
CREATE FUNCTION lion_dup_hash(text) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT hashtext(lower($1)) $$;
CREATE OPERATOR ##= (LEFTARG = text, RIGHTARG = text,
					 FUNCTION = lion_dup_eq, COMMUTATOR = ##=);
CREATE OPERATOR CLASS lion_dup_ops FOR TYPE text USING lion AS
	OPERATOR 1 ##= (text, text),
	FUNCTION 1 lion_dup_hash(text);

-- 'A' and 'a' are two keys while the equality is exact ...
CREATE TABLE lion_dup (v text NOT NULL);
INSERT INTO lion_dup SELECT 'A' FROM generate_series(1, 10);
INSERT INTO lion_dup SELECT 'a' FROM generate_series(1, 10);
INSERT INTO lion_dup SELECT 'k' || i FROM generate_series(1, 500) i;
CREATE INDEX lion_dup_v ON lion_dup USING lion (v lion_dup_ops);
SELECT ordered, entries FROM lion_index_stats('lion_dup_v');
SELECT lion_index_verify('lion_dup_v');
-- ... and one class, held in two entries, once it folds case
SET lion_test.eq_mode = 'fold';
SELECT lion_index_verify('lion_dup_v');
RESET lion_test.eq_mode;
-- an equality that never matches makes every insert a new entry: byte-identical twins
SET lion_test.eq_mode = 'never';
INSERT INTO lion_dup VALUES ('k7');
RESET lion_test.eq_mode;
SELECT entries FROM lion_index_stats('lion_dup_v');
SELECT lion_index_verify('lion_dup_v');
DROP TABLE lion_dup;
DROP OPERATOR CLASS lion_dup_ops USING lion;
DROP OPERATOR ##= (text, text);
DROP FUNCTION lion_dup_eq(text, text);
DROP FUNCTION lion_dup_hash(text);

-- ---------------------------------------------------------------------
-- 14. A cross-type IN list on a directory that is NOT in the value type's
-- order.
--
-- A batched lookup sorts its values into the directory order and then walks
-- the leaves left to right, only ever stepping right.  The values are of
-- another type, so the directory's own comparison cannot sort them; sorting
-- them with the VALUE type's default order (what the code used to do) is the
-- directory order only when the opclass happens to sort that way too.  Here
-- it sorts in reverse: every value after the first one was looked for to the
-- right of where it lives, and the list came back with almost nothing.
--
-- The family's cross-type comparison is what descends for a value of the
-- other type.  A list of them is sorted with the family's OWN comparison of
-- the value type when there is one, and otherwise not walked at all: each
-- value descends on its own.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_rev_cmp48(int4, int8) RETURNS int4
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT btint84cmp($2, $1) $$;
CREATE FUNCTION lion_rev_cmp88(int8, int8) RETURNS int4
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT btint8cmp($2, $1) $$;
CREATE OPERATOR FAMILY lion_revx_ops USING lion;
CREATE OPERATOR CLASS lion_revx_int4_ops FOR TYPE int4 USING lion
	FAMILY lion_revx_ops AS
	OPERATOR 1 = (int4, int4),
	FUNCTION 1 hashint4(int4),
	FUNCTION 4 lion_rev_cmp(int4, int4);
ALTER OPERATOR FAMILY lion_revx_ops USING lion ADD
	OPERATOR 1 = (int4, int8),
	FUNCTION 1 (int8, int8) hashint8(int8),
	FUNCTION 4 (int4, int8) lion_rev_cmp48(int4, int8);

CREATE TABLE lion_revx (k int NOT NULL, v int);
INSERT INTO lion_revx SELECT i % 5000, i FROM generate_series(1, 50000) i;
CREATE INDEX lion_revx_k ON lion_revx USING lion (k lion_revx_int4_ops);
VACUUM (ANALYZE) lion_revx;
SELECT ordered, leaf_pages > 20 AS many_leaves FROM lion_index_stats('lion_revx_k');
SELECT lion_index_verify('lion_revx_k', true);

-- The values arrive in no order and live all over the directory.
CREATE TEMP TABLE lion_revx_vals AS
	SELECT ((i * 37) % 5000)::int8 AS v FROM generate_series(1, 400) i;
INSERT INTO lion_revx_vals VALUES (4999), (0), (2500), (7), (7);
SET pg_lion.enable_count_pushdown = off;
SET enable_bitmapscan = off;
SET enable_indexscan = off;
SELECT count(*) AS expected FROM lion_revx
	WHERE k = ANY (ARRAY(SELECT v FROM lion_revx_vals));
SELECT count(*) AS expected_in FROM lion_revx
	WHERE k IN (4999::int8, 10::int8, 2500::int8, 7::int8, 3333::int8, 4000::int8);
RESET enable_bitmapscan;
RESET enable_indexscan;
-- the bitmap path, one value at a time
SET enable_seqscan = off;
SELECT count(*) AS bitmap_scan FROM lion_revx
	WHERE k = ANY (ARRAY(SELECT v FROM lion_revx_vals));
RESET enable_seqscan;
RESET pg_lion.enable_count_pushdown;
-- no comparison of int8 against int8 in the family: every value descends alone
SELECT lion_index_count_any('lion_revx_k', ARRAY(SELECT v FROM lion_revx_vals))
	AS count_any;
SELECT count(*) AS pushdown FROM lion_revx
	WHERE k = ANY (ARRAY(SELECT v FROM lion_revx_vals));
SELECT count(*) AS pushdown_in FROM lion_revx
	WHERE k IN (4999::int8, 10::int8, 2500::int8, 7::int8, 3333::int8, 4000::int8);
-- with the family's own int8 order, the list is sorted by it and walked
ALTER OPERATOR FAMILY lion_revx_ops USING lion ADD
	FUNCTION 4 (int8, int8) lion_rev_cmp88(int8, int8);
SELECT lion_index_count_any('lion_revx_k', ARRAY(SELECT v FROM lion_revx_vals))
	AS count_any_walked;
SELECT count(*) AS pushdown_walked FROM lion_revx
	WHERE k = ANY (ARRAY(SELECT v FROM lion_revx_vals));
DROP TABLE lion_revx_vals;
DROP TABLE lion_revx;
DROP OPERATOR FAMILY lion_revx_ops USING lion CASCADE;
DROP FUNCTION lion_rev_cmp48(int4, int8);
DROP FUNCTION lion_rev_cmp88(int8, int8);

-- ---------------------------------------------------------------------
-- 15. A cross-type ordering on an UNORDERED directory is not used.
--
-- The same reverse comparison, but in no btree family, so the build cannot
-- sort by it and the directory is ordered by (hash, bytes) instead (§21 rule
-- 3).  A cross-type proc 4 in the family must then be ignored: descending a
-- hash-ordered tree in value order finds nothing.  The bitmap scan used to
-- resolve its own comparison without asking whether the column was ordered;
-- it now shares the count path's resolution.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_odd2_cmp(int4, int4) RETURNS int4
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT btint4cmp($2, $1) $$;
CREATE FUNCTION lion_odd2_cmp48(int4, int8) RETURNS int4
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE AS $$ SELECT btint84cmp($2, $1) $$;
CREATE OPERATOR FAMILY lion_oddx_ops USING lion;
CREATE OPERATOR CLASS lion_oddx_int4_ops FOR TYPE int4 USING lion
	FAMILY lion_oddx_ops AS
	OPERATOR 1 = (int4, int4),
	FUNCTION 1 hashint4(int4),
	FUNCTION 4 lion_odd2_cmp(int4, int4);
ALTER OPERATOR FAMILY lion_oddx_ops USING lion ADD
	OPERATOR 1 = (int4, int8),
	FUNCTION 1 (int8, int8) hashint8(int8),
	FUNCTION 4 (int4, int8) lion_odd2_cmp48(int4, int8);
CREATE TABLE lion_oddx (k int NOT NULL, v int);
INSERT INTO lion_oddx SELECT i % 5000, i FROM generate_series(1, 50000) i;
CREATE INDEX lion_oddx_k ON lion_oddx USING lion (k lion_oddx_int4_ops);
VACUUM (FREEZE, ANALYZE) lion_oddx;
SELECT ordered FROM lion_index_stats('lion_oddx_k');
SET pg_lion.enable_count_pushdown = off;
SET enable_seqscan = off;
SET enable_indexscan = off;
EXPLAIN (COSTS OFF) SELECT count(*) FROM lion_oddx WHERE k = 7::int8;
SELECT count(*) AS bitmap_one FROM lion_oddx WHERE k = 7::int8;
SELECT count(*) AS bitmap_many FROM lion_oddx
	WHERE k = ANY (ARRAY(SELECT ((i * 37) % 5000)::int8 FROM generate_series(1, 300) i));
RESET enable_seqscan;
SET enable_bitmapscan = off;
SELECT count(*) AS expected_many FROM lion_oddx
	WHERE k = ANY (ARRAY(SELECT ((i * 37) % 5000)::int8 FROM generate_series(1, 300) i));
RESET enable_bitmapscan;
RESET enable_indexscan;
RESET pg_lion.enable_count_pushdown;
SELECT lion_index_count('lion_oddx_k', 7::int8) AS count_one,
	   lion_index_count_any('lion_oddx_k',
			ARRAY(SELECT ((i * 37) % 5000)::int8 FROM generate_series(1, 300) i)) AS count_any;
DROP TABLE lion_oddx;
DROP OPERATOR FAMILY lion_oddx_ops USING lion CASCADE;
DROP FUNCTION lion_odd2_cmp(int4, int4);
DROP FUNCTION lion_odd2_cmp48(int4, int8);

-- ---------------------------------------------------------------------
-- 16. A cast is not a comparison: text probes of a `name` index.
--
-- A family with `name = text` equality but no cross-type ordering used to
-- have its text values CAST to name and then looked up as names - through an
-- implicit cast, which is not lossless: text -> name truncates to 63 bytes,
-- so a text that differs from a stored name only past byte 63 found it.  Only
-- a BINARY coercion (same bytes) is taken now; anything else walks the leaves
-- with the family's cross-type equality, exactly as the bitmap scan always
-- did.
-- ---------------------------------------------------------------------

CREATE OPERATOR FAMILY lion_namex_ops USING lion;
CREATE OPERATOR CLASS lion_namex_name_ops FOR TYPE name USING lion
	FAMILY lion_namex_ops AS
	OPERATOR 1 = (name, name),
	FUNCTION 1 hashname(name),
	FUNCTION 4 btnamecmp(name, name);
ALTER OPERATOR FAMILY lion_namex_ops USING lion ADD
	OPERATOR 1 = (name, text),
	FUNCTION 1 (text, text) hashtext(text);
CREATE TABLE lion_namex (n name NOT NULL, v int);
INSERT INTO lion_namex SELECT repeat('n', 60) || lpad((i % 100)::text, 3, '0'), i
	FROM generate_series(1, 2000) i;
CREATE INDEX lion_namex_n ON lion_namex USING lion (n lion_namex_name_ops);
VACUUM (ANALYZE) lion_namex;
SELECT ordered, entries FROM lion_index_stats('lion_namex_n');
-- 63 bytes of these texts are a stored name; the texts themselves are not
SELECT lion_index_count('lion_namex_n', (repeat('n', 60) || '007tail')::text) AS one_long,
	   lion_index_count_any('lion_namex_n',
			ARRAY[repeat('n', 60) || '007tail', repeat('n', 60) || '008xyz']) AS any_long;
SELECT count(*) AS pushdown_any FROM lion_namex
	WHERE n = ANY (ARRAY[repeat('n', 60) || '007tail', repeat('n', 60) || '008xyz']);
-- (an IN list of texts is resolved by the PARSER to `name = ANY (name[])`,
-- truncating the constants itself, so it matches here and in the heap alike)
SELECT count(*) AS pushdown_in FROM lion_namex
	WHERE n IN ((repeat('n', 60) || '007tail')::text, (repeat('n', 60) || '008xyz')::text);
-- ... while a text that IS a stored name still finds it
SELECT lion_index_count('lion_namex_n', (repeat('n', 60) || '007')::text) AS one_exact,
	   lion_index_count_any('lion_namex_n',
			ARRAY[repeat('n', 60) || '007', repeat('n', 60) || '008tail']) AS any_exact;
SET pg_lion.enable_count_pushdown = off;
SET enable_bitmapscan = off;
SET enable_indexscan = off;
SELECT count(*) AS expected FROM lion_namex
	WHERE n = ANY (ARRAY[repeat('n', 60) || '007tail', repeat('n', 60) || '008xyz']);
SELECT count(*) AS expected_in FROM lion_namex
	WHERE n IN ((repeat('n', 60) || '007tail')::text, (repeat('n', 60) || '008xyz')::text);
RESET enable_bitmapscan;
RESET enable_indexscan;
RESET pg_lion.enable_count_pushdown;
DROP TABLE lion_namex;
DROP OPERATOR FAMILY lion_namex_ops USING lion CASCADE;

-- A BINARY coercion is still taken: a family whose cross-type equality
-- compares text with varchar descends for the varchar values as if they were
-- text (same bytes, so the same hash, equality and order), instead of walking
-- every leaf for each of them.
CREATE FUNCTION lion_text_eq_varchar(text, varchar) RETURNS boolean
	LANGUAGE internal IMMUTABLE STRICT PARALLEL SAFE AS 'texteq';
CREATE OPERATOR =~~= (LEFTARG = text, RIGHTARG = varchar,
					  FUNCTION = lion_text_eq_varchar);
CREATE OPERATOR FAMILY lion_textv_ops USING lion;
CREATE OPERATOR CLASS lion_textv_text_ops FOR TYPE text USING lion
	FAMILY lion_textv_ops AS
	OPERATOR 1 = (text, text),
	FUNCTION 1 hashtext(text),
	FUNCTION 4 bttextcmp(text, text);
ALTER OPERATOR FAMILY lion_textv_ops USING lion ADD
	OPERATOR 1 =~~= (text, varchar),
	FUNCTION 1 (varchar, varchar) hashtext(text);
CREATE TABLE lion_textv (k text NOT NULL);
INSERT INTO lion_textv SELECT 'v' || lpad((i % 20000)::text, 6, '0')
	FROM generate_series(1, 40000) i;
CREATE INDEX lion_textv_k ON lion_textv USING lion (k lion_textv_text_ops);
VACUUM (FREEZE, ANALYZE) lion_textv;
SELECT ordered, leaf_pages > 100 AS many_leaves FROM lion_index_stats('lion_textv_k');
SELECT lion_index_count_any('lion_textv_k',
		ARRAY['v000001', 'v019999', 'v010000', 'nope']::varchar[]) AS count_any;
SELECT count(*) AS pushdown FROM lion_textv
	WHERE k =~~= ANY (ARRAY['v000001', 'v019999', 'v010000', 'nope']::varchar[]);
CREATE FUNCTION lion_dirpages(q text) RETURNS bigint LANGUAGE plpgsql AS $$
DECLARE
	j json;
BEGIN
	EXECUTE 'EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF, BUFFERS OFF, FORMAT JSON) '
		|| q INTO j;
	RETURN (j -> 0 -> 'Plan' ->> 'Directory Pages Read')::bigint;
END $$;
SELECT lion_dirpages($q$SELECT count(*) FROM lion_textv
	WHERE k =~~= ANY (ARRAY['v000001', 'v019999', 'v010000', 'nope']::varchar[])$q$)
	   < (SELECT leaf_pages FROM lion_index_stats('lion_textv_k'))
	AS descended_not_walked;
DROP FUNCTION lion_dirpages(text);
DROP TABLE lion_textv;
DROP OPERATOR FAMILY lion_textv_ops USING lion CASCADE;
DROP OPERATOR =~~= (text, varchar);
DROP FUNCTION lion_text_eq_varchar(text, varchar);

-- ---------------------------------------------------------------------
-- 17. A list whose values share a hash run that spans several leaves.
--
-- The batched lookup keeps the leaf its last value was found on and only
-- steps right from there.  A value found on the SECOND leaf of a prefix run
-- left the walk standing to the right of where the run begins, and the next
-- value of the same run - sorted after it, but stored before it - was then
-- looked for from there and missed.  After a lookup that had to follow the
-- run across a page boundary the walk descends afresh.
-- ---------------------------------------------------------------------

CREATE FUNCTION lion_coarse_xid_hash(xid) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT (($1::text)::int8 % 7)::int4 $$;
CREATE FUNCTION lion_coarse_int4_hash(int4) RETURNS integer
	LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE
	AS $$ SELECT ($1::int8 % 7)::int4 $$;
CREATE OPERATOR FAMILY lion_coarsex_ops USING lion;
CREATE OPERATOR CLASS lion_coarsex_xid_ops FOR TYPE xid USING lion
	FAMILY lion_coarsex_ops AS
	OPERATOR 1 = (xid, xid),
	FUNCTION 1 lion_coarse_xid_hash(xid);
ALTER OPERATOR FAMILY lion_coarsex_ops USING lion ADD
	OPERATOR 1 = (xid, int4),
	FUNCTION 1 (int4, int4) lion_coarse_int4_hash(int4);
CREATE TABLE lion_cx (x xid NOT NULL, v int);
INSERT INTO lion_cx SELECT (i % 3000 + 1)::text::xid, i
	FROM generate_series(1, 30000) i;
CREATE INDEX lion_cx_x ON lion_cx USING lion (x lion_coarsex_xid_ops);
VACUUM (ANALYZE) lion_cx;
-- seven hash runs of ~430 entries each, every one of them several leaves long
SELECT ordered, leaf_pages > 20 AS many_leaves, entries
	FROM lion_index_stats('lion_cx_x');
-- every key, in descending order: xid values, and int4 values (cross-type)
SELECT lion_index_count_any('lion_cx_x',
		ARRAY(SELECT (3001 - i)::text::xid FROM generate_series(1, 3000) i)) AS xid_list,
	   lion_index_count_any('lion_cx_x',
		ARRAY(SELECT 3001 - i FROM generate_series(1, 3000) i)) AS int4_list;
SELECT count(*) AS pushdown FROM lion_cx
	WHERE x = ANY (ARRAY(SELECT 3001 - i FROM generate_series(1, 3000) i));
SET pg_lion.enable_count_pushdown = off;
SET enable_seqscan = off;
SELECT count(*) AS bitmap_scan FROM lion_cx
	WHERE x = ANY (ARRAY(SELECT 3001 - i FROM generate_series(1, 3000) i));
RESET enable_seqscan;
RESET pg_lion.enable_count_pushdown;
DROP TABLE lion_cx;
DROP OPERATOR FAMILY lion_coarsex_ops USING lion CASCADE;
DROP FUNCTION lion_coarse_xid_hash(xid);
DROP FUNCTION lion_coarse_int4_hash(int4);

-- ---------------------------------------------------------------------
-- 18. A binary coercion is not a licence to swap equalities.
--
-- text -> bpchar is a binary cast, so a text probe of a bpchar index could be
-- relabelled and compared with the key type's own equality.  That is only the
-- family's equality when the family says so: here `bpchar =~~= text` is
-- defined with TEXT semantics (trailing blanks significant), which differs
-- from bpchareq's.  The relabel shortcut would answer 100 for 'x '::text
-- where the family's equality - and the seqscan - answer 0.  The shortcut is
-- taken only when the family's cross-type strategy-1 operator is implemented
-- by the same function as the key type's own; otherwise the leaves are walked
-- with the family's equality (§21, "Cross-type searches").
-- ---------------------------------------------------------------------
CREATE FUNCTION lion_bpx_eq_text(bpchar, text) RETURNS boolean
	LANGUAGE sql IMMUTABLE STRICT AS $$ SELECT $1::text = $2 $$;
CREATE OPERATOR =~~= (LEFTARG = bpchar, RIGHTARG = text, FUNCTION = lion_bpx_eq_text);
CREATE OPERATOR FAMILY lion_bpx_fam USING lion;
CREATE OPERATOR CLASS lion_bpx_ops FOR TYPE bpchar USING lion FAMILY lion_bpx_fam AS
	OPERATOR 1 = (bpchar, bpchar),
	FUNCTION 1 hashbpchar(bpchar),
	FUNCTION 4 bpcharcmp(bpchar, bpchar);
-- hashtext agrees with hashbpchar on stored values without trailing blanks,
-- so the family is consistent for the values this test stores.
ALTER OPERATOR FAMILY lion_bpx_fam USING lion ADD
	OPERATOR 1 =~~= (bpchar, text),
	FUNCTION 1 (text, text) hashtext(text);
CREATE TABLE lion_bpx (k bpchar NOT NULL);
INSERT INTO lion_bpx SELECT 'x' FROM generate_series(1, 100);
INSERT INTO lion_bpx SELECT 'y' FROM generate_series(1, 50);
CREATE INDEX lion_bpx_k ON lion_bpx USING lion (k lion_bpx_ops);
VACUUM ANALYZE lion_bpx;
-- 'x '::text: the family says no match (text semantics); a relabel to bpchar
-- would say match.  Every index path must agree with the seqscan.
SELECT (SELECT count(*) FROM lion_bpx WHERE k =~~= 'x '::text) AS seq_truth,
	   lion_index_count('lion_bpx_k', 'x '::text) AS via_count,
	   lion_index_count_any('lion_bpx_k', ARRAY['x '::text, 'y '::text]) AS via_list;
SET pg_lion.enable_count_pushdown = on;
SELECT count(*) AS via_pushdown FROM lion_bpx WHERE k =~~= 'x '::text;
SET pg_lion.enable_count_pushdown = off;
SET enable_seqscan = off;
SELECT count(*) AS via_bitmap FROM lion_bpx WHERE k =~~= 'x '::text;
RESET enable_seqscan;
-- and the exact spelling still matches on every path
SELECT (SELECT count(*) FROM lion_bpx WHERE k =~~= 'x'::text) AS seq_truth,
	   lion_index_count('lion_bpx_k', 'x'::text) AS via_count,
	   lion_index_count_any('lion_bpx_k', ARRAY['x'::text, 'y'::text]) AS via_list;
RESET pg_lion.enable_count_pushdown;
DROP TABLE lion_bpx;
DROP OPERATOR FAMILY lion_bpx_fam USING lion CASCADE;
DROP OPERATOR =~~= (bpchar, text);
DROP FUNCTION lion_bpx_eq_text(bpchar, text);

-- ---------------------------------------------------------------------
-- 19. A long key whose posting set is just under inline_limit.
--
-- An entry is its header, its key and its INLINE payload, and must fit in
-- LION_MAX_ENTRY_SIZE.  With a 2047-byte key, a payload inside inline_limit
-- does not always fit next to it: the insert path spilled such a set onto a
-- container page, but ambuild kept it INLINE and then failed to make the
-- entry.  Any role that could INSERT could so make REINDEX, VACUUM FULL,
-- CLUSTER and a restore of the index fail for good.  The key below is the
-- largest a text key can be, and rows of it go in one at a time until the
-- insert path spills the set, which happens about 100 bytes short of
-- inline_limit.
-- ---------------------------------------------------------------------
-- Two rows a page, the key kept in the row as it is: compressed, hundreds
-- would share a page and the set would never grow this large, and at three a
-- page the build writes it in fewer bytes than the inserts did.
CREATE TABLE lion_bigset (id int NOT NULL, g int NOT NULL, k text NOT NULL)
	WITH (fillfactor = 60);
ALTER TABLE lion_bigset ALTER k SET STORAGE PLAIN;
CREATE INDEX lion_bigset_k ON lion_bigset USING lion (k);
CREATE INDEX lion_bigset_gk ON lion_bigset USING lion (g, k);
INSERT INTO lion_bigset SELECT i, 0, repeat('y', 2043)
	FROM generate_series(1, 1800) i;
DO $$
BEGIN
	FOR n IN 1801 .. 2400 LOOP
		INSERT INTO lion_bigset VALUES (n, 0, repeat('y', 2043));
		EXIT WHEN lion_index_posting_root('lion_bigset_k', repeat('y', 2043)) IS NOT NULL;
	END LOOP;
END $$;
-- the inserts spilled it ...
SELECT lion_index_posting_root('lion_bigset_k', repeat('y', 2043)) IS NOT NULL
	AS spilled_by_insert;
-- ... and every rebuild has to be able to write it again
REINDEX INDEX lion_bigset_k;
SELECT lion_index_verify('lion_bigset_k', true);
SELECT lion_index_posting_root('lion_bigset_k', repeat('y', 2043)) IS NOT NULL
	AS spilled_by_build;
REINDEX INDEX lion_bigset_gk;
SELECT lion_index_verify('lion_bigset_gk', true);
VACUUM FULL lion_bigset;
SELECT lion_index_verify('lion_bigset_k', true);
SELECT lion_index_verify('lion_bigset_gk', true);
SELECT lion_index_count('lion_bigset_k', repeat('y', 2043)) = count(*) AS n_exact
  FROM lion_bigset;
-- the sizes around the one above, each built from scratch
DO $$
BEGIN
	FOR n IN 3800 .. 4000 BY 2 LOOP
		EXECUTE format('CREATE INDEX lion_bigset_p ON lion_bigset USING lion (k) WHERE id <= %s', n);
		PERFORM lion_index_verify('lion_bigset_p', true);
		DROP INDEX lion_bigset_p;
	END LOOP;
END $$;
DROP TABLE lion_bigset;

DROP OPERATOR CLASS lion_rev_ops USING lion;
DROP OPERATOR CLASS lion_rev_btree USING btree;
DROP OPERATOR <# (int4, int4);
DROP OPERATOR <=# (int4, int4);
DROP OPERATOR =# (int4, int4);
DROP OPERATOR >=# (int4, int4);
DROP OPERATOR ># (int4, int4);
DROP FUNCTION lion_rev_cmp(int4, int4);
DROP FUNCTION lion_rev_lt(int4, int4);
DROP FUNCTION lion_rev_le(int4, int4);
DROP FUNCTION lion_rev_eq(int4, int4);
DROP FUNCTION lion_rev_ge(int4, int4);
DROP FUNCTION lion_rev_gt(int4, int4);

DROP FUNCTION lion_groups_monotonic(text, bool);