From: Andrey Borodin <x4mmm@yandex-team.ru>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_691C4BED-FD70-4652-A391-F1F617729CE5"
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3864.300.41.1.7\))
Subject: amcheck: add index-all-keys-match verification for B-Tree
Message-Id: <432626F9-65DF-4F0D-B345-26CFC3E2CFAC@yandex-team.ru>
Date: Tue, 17 Feb 2026 14:19:29 +0500
To: pgsql-hackers <pgsql-hackers@postgresql.org>
Archived-At: <https://www.postgresql.org/message-id/432626F9-65DF-4F0D-B345-26CFC3E2CFAC%40yandex-team.ru>
Precedence: bulk


--Apple-Mail=_691C4BED-FD70-4652-A391-F1F617729CE5
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

Hi hackers,

Attached patch adds a new "indexallkeysmatch" option to bt_index_check()
and bt_index_parent_check() that verifies each index tuple points to a
heap tuple with the same key - the reverse of "heapallindexed".

I need the tool to investigate corruption, possibly inflicted by us
ourselves. But the tool might be useful for the community too.
We hit B-tree corruptions where index entries stored different keys than
their heap tuples (e.g. "foobar" in index vs "foo-bar" in heap).
This happened with UTF-8 Russian locales around hyphens/spaces. The
index structure stayed valid so existing checks didn't catch it.

The implementation uses a Bloom filter to avoid excessive random heap
I/O. A sequential heap scan fingerprints visible (key, tid) pairs
first. During the index traversal, each leaf tuple is probed against
the filter; only when the filter says "missing" do we fetch the heap
tuple and compare keys. Posting list entries are expanded and checked
individually.

When both heapallindexed and indexallkeysmatch are enabled, the heap
is scanned twice. Combining them into one pass would complicate the
code and possibly introduce some errors.

There's also a TAP test that detects corruption via expression function =
swap.
Someone might consider not using bug (corrupting indexes by changing =
expression)
in tests, but it's already used, so I reused this bug too.

WDYT? Would you like to see it on CF, or do we have enough amcheck =
patches
there already and it's better to postpone it to v20?


Best regards, Andrey Borodin.

--Apple-Mail=_691C4BED-FD70-4652-A391-F1F617729CE5
Content-Disposition: attachment;
	filename=v1-0001-amcheck-add-indexallkeysmatch-verification-for-B-.patch
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="v1-0001-amcheck-add-indexallkeysmatch-verification-for-B-.patch"
Content-Transfer-Encoding: quoted-printable

=46rom=20781576741691026b0e9d5ea7d3d1a44693d93efa=20Mon=20Sep=2017=20=
00:00:00=202001=0AFrom:=20Andrey=20Borodin=20<amborodin@acm.org>=0ADate:=20=
Tue,=2017=20Feb=202026=2012:05:51=20+0500=0ASubject:=20[PATCH=20v1]=20=
amcheck:=20add=20indexallkeysmatch=20verification=20for=20B-Tree=0A=20=
indexes=0A=0AAdd=20a=20new=20"indexallkeysmatch"=20option=20to=20=
bt_index_check()=20and=0Abt_index_parent_check()=20that=20verifies=20=
each=20index=20tuple=20points=20to=20a=0Aheap=20tuple=20with=20the=20=
same=20key.=20=20This=20is=20the=20reverse=20of=20the=20existing=0A=
"heapallindexed"=20check,=20which=20verifies=20every=20heap=20tuple=20is=20=
present=0Ain=20the=20index.=0A=0AThe=20implementation=20uses=20a=20Bloom=20=
filter=20to=20amortize=20random=20heap=0Alookups.=20=20A=20sequential=20=
heap=20scan=20first=20fingerprints=20all=20visible=0A(key,=20tid)=20=
pairs.=20=20During=20the=20index=20scan,=20each=20leaf=20tuple=20=
(including=0Aposting=20list=20entries)=20is=20probed=20against=20this=20=
filter.=20=20Only=20when=20the=0Afilter=20says=20"not=20present"=20do=20=
we=20perform=20an=20actual=20heap=20fetch=20and=0Akey=20comparison=20via=20=
FormIndexDatum,=20reporting=20corruption=20if=20the=20keys=0Adiffer.=0A=0A=
This=20check=20detects=20corruption=20where=20an=20index=20entry=20=
stores=20a=0Adifferent=20key=20than=20the=20heap=20tuple=20it=20points=20=
to=20--=20a=20scenario=20that=0Athe=20existing=20heapallindexed=20and=20=
structural=20checks=20cannot=20catch,=0Aparticularly=20when=20it=20=
manifests=20within=20posting=20lists=20before=20it=0Adevelops=20into=20a=20=
detectable=20ordering=20violation.=0A=0ABump=20amcheck=20extension=20=
version=20to=201.6.=0A---=0A=20contrib/amcheck/Makefile=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20|=20=20=204=20+-=0A=20=
contrib/amcheck/amcheck--1.5--1.6.sql=20=20=20=20=20=20=20=20=20|=20=20=
21=20++=0A=20contrib/amcheck/amcheck.control=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20|=20=20=202=20+-=0A=20=
contrib/amcheck/expected/check_btree.out=20=20=20=20=20=20|=20=2013=20+=0A=
=20contrib/amcheck/meson.build=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20|=20=20=202=20+=0A=20contrib/amcheck/sql/check_btree.sql=20=20=
=20=20=20=20=20=20=20=20=20|=20=20=204=20+=0A=20=
.../t/007_verify_nbtree_indexallkeysmatch.pl=20=20|=20111=20++++++=0A=20=
contrib/amcheck/verify_nbtree.c=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20|=20315=20++++++++++++++++--=0A=208=20files=20changed,=20432=20=
insertions(+),=2040=20deletions(-)=0A=20create=20mode=20100644=20=
contrib/amcheck/amcheck--1.5--1.6.sql=0A=20create=20mode=20100644=20=
contrib/amcheck/t/007_verify_nbtree_indexallkeysmatch.pl=0A=0Adiff=20=
--git=20a/contrib/amcheck/Makefile=20b/contrib/amcheck/Makefile=0Aindex=20=
1b7a63cbaa4..2c23109a200=20100644=0A---=20a/contrib/amcheck/Makefile=0A=
+++=20b/contrib/amcheck/Makefile=0A@@=20-10,12=20+10,12=20@@=20OBJS=20=3D=20=
\=0A=20=0A=20EXTENSION=20=3D=20amcheck=0A=20DATA=20=3D=20=
amcheck--1.2--1.3.sql=20amcheck--1.1--1.2.sql=20amcheck--1.0--1.1.sql=20=
amcheck--1.0.sql=20\=0A-=09=09amcheck--1.3--1.4.sql=20=
amcheck--1.4--1.5.sql=0A+=09=09amcheck--1.3--1.4.sql=20=
amcheck--1.4--1.5.sql=20amcheck--1.5--1.6.sql=0A=20PGFILEDESC=20=3D=20=
"amcheck=20-=20function=20for=20verifying=20relation=20integrity"=0A=20=0A=
=20REGRESS=20=3D=20check=20check_btree=20check_gin=20check_heap=0A=20=0A=
-EXTRA_INSTALL=20=3D=20contrib/pg_walinspect=0A+EXTRA_INSTALL=20=3D=20=
contrib/pg_walinspect=20contrib/pg_surgery=0A=20TAP_TESTS=20=3D=201=0A=20=
=0A=20ifdef=20USE_PGXS=0Adiff=20--git=20=
a/contrib/amcheck/amcheck--1.5--1.6.sql=20=
b/contrib/amcheck/amcheck--1.5--1.6.sql=0Anew=20file=20mode=20100644=0A=
index=2000000000000..ac01f429d7d=0A---=20/dev/null=0A+++=20=
b/contrib/amcheck/amcheck--1.5--1.6.sql=0A@@=20-0,0=20+1,21=20@@=0A+/*=20=
contrib/amcheck/amcheck--1.5--1.6.sql=20*/=0A+=0A+--=20complain=20if=20=
script=20is=20sourced=20in=20psql,=20rather=20than=20via=20CREATE=20=
EXTENSION=0A+\echo=20Use=20"ALTER=20EXTENSION=20amcheck=20UPDATE=20TO=20=
'1.6'"=20to=20load=20this=20file.=20\quit=0A+=0A+--=20Add=20=
indexallkeysmatch=20parameter=20to=20bt_index_check=20and=20=
bt_index_parent_check=0A+CREATE=20FUNCTION=20bt_index_check(index=20=
regclass,=0A+=20=20=20=20heapallindexed=20boolean,=20checkunique=20=
boolean,=20indexallkeysmatch=20boolean)=0A+RETURNS=20VOID=0A+AS=20=
'MODULE_PATHNAME',=20'bt_index_check'=0A+LANGUAGE=20C=20STRICT=20=
PARALLEL=20RESTRICTED;=0A+=0A+CREATE=20FUNCTION=20=
bt_index_parent_check(index=20regclass,=0A+=20=20=20=20heapallindexed=20=
boolean,=20rootdescend=20boolean,=20checkunique=20boolean,=0A+=20=20=20=20=
indexallkeysmatch=20boolean)=0A+RETURNS=20VOID=0A+AS=20=
'MODULE_PATHNAME',=20'bt_index_parent_check'=0A+LANGUAGE=20C=20STRICT=20=
PARALLEL=20RESTRICTED;=0A+=0A+REVOKE=20ALL=20ON=20FUNCTION=20=
bt_index_check(regclass,=20boolean,=20boolean,=20boolean)=20FROM=20=
PUBLIC;=0A+REVOKE=20ALL=20ON=20FUNCTION=20=
bt_index_parent_check(regclass,=20boolean,=20boolean,=20boolean,=20=
boolean)=20FROM=20PUBLIC;=0Adiff=20--git=20=
a/contrib/amcheck/amcheck.control=20b/contrib/amcheck/amcheck.control=0A=
index=20c8ba6d7c9bc..2f329ef2cf4=20100644=0A---=20=
a/contrib/amcheck/amcheck.control=0A+++=20=
b/contrib/amcheck/amcheck.control=0A@@=20-1,5=20+1,5=20@@=0A=20#=20=
amcheck=20extension=0A=20comment=20=3D=20'functions=20for=20verifying=20=
relation=20integrity'=0A-default_version=20=3D=20'1.5'=0A=
+default_version=20=3D=20'1.6'=0A=20module_pathname=20=3D=20=
'$libdir/amcheck'=0A=20relocatable=20=3D=20true=0Adiff=20--git=20=
a/contrib/amcheck/expected/check_btree.out=20=
b/contrib/amcheck/expected/check_btree.out=0Aindex=20=
6558f2c5a4f..3015a8d304f=20100644=0A---=20=
a/contrib/amcheck/expected/check_btree.out=0A+++=20=
b/contrib/amcheck/expected/check_btree.out=0A@@=20-232,6=20+232,19=20@@=20=
SELECT=20bt_index_parent_check('bttest_b_idx',=20heapallindexed=20=3D>=20=
true,=20rootdescend=0A=20=20=0A=20(1=20row)=0A=20=0A+--=20=
indexallkeysmatch:=20verify=20each=20index=20tuple=20points=20to=20heap=20=
tuple=20with=20same=20key=0A+SELECT=20bt_index_check('bttest_a_idx',=20=
heapallindexed=20=3D>=20false,=20checkunique=20=3D>=20false,=20=
indexallkeysmatch=20=3D>=20true);=0A+=20bt_index_check=20=0A=
+----------------=0A+=20=0A+(1=20row)=0A+=0A+SELECT=20=
bt_index_parent_check('bttest_a_idx',=20heapallindexed=20=3D>=20false,=20=
rootdescend=20=3D>=20false,=20checkunique=20=3D>=20false,=20=
indexallkeysmatch=20=3D>=20true);=0A+=20bt_index_parent_check=20=0A=
+-----------------------=0A+=20=0A+(1=20row)=0A+=0A=20--=20Check=20that=20=
null=20values=20in=20an=20unique=20index=20are=20not=20treated=20as=20=
equal=0A=20CREATE=20TABLE=20bttest_unique_nulls=20(a=20serial,=20b=20=
int,=20c=20int=20UNIQUE);=0A=20INSERT=20INTO=20bttest_unique_nulls=20=
VALUES=20(generate_series(1,=2010000),=202,=20default);=0Adiff=20--git=20=
a/contrib/amcheck/meson.build=20b/contrib/amcheck/meson.build=0Aindex=20=
d5137ef691d..220b1ce1d59=20100644=0A---=20a/contrib/amcheck/meson.build=0A=
+++=20b/contrib/amcheck/meson.build=0A@@=20-27,6=20+27,7=20@@=20=
install_data(=0A=20=20=20'amcheck--1.2--1.3.sql',=0A=20=20=20=
'amcheck--1.3--1.4.sql',=0A=20=20=20'amcheck--1.4--1.5.sql',=0A+=20=20=
'amcheck--1.5--1.6.sql',=0A=20=20=20kwargs:=20contrib_data_args,=0A=20)=0A=
=20=0A@@=20-50,6=20+51,7=20@@=20tests=20+=3D=20{=0A=20=20=20=20=20=20=20=
't/004_verify_nbtree_unique.pl',=0A=20=20=20=20=20=20=20't/005_pitr.pl',=0A=
=20=20=20=20=20=20=20't/006_verify_gin.pl',=0A+=20=20=20=20=20=20=
't/007_verify_nbtree_indexallkeysmatch.pl',=0A=20=20=20=20=20],=0A=20=20=20=
},=0A=20}=0Adiff=20--git=20a/contrib/amcheck/sql/check_btree.sql=20=
b/contrib/amcheck/sql/check_btree.sql=0Aindex=20171f7f691ec..e844aae3e6f=20=
100644=0A---=20a/contrib/amcheck/sql/check_btree.sql=0A+++=20=
b/contrib/amcheck/sql/check_btree.sql=0A@@=20-148,6=20+148,10=20@@=20=
SELECT=20bt_index_check('bttest_b_idx',=20heapallindexed=20=3D>=20false,=20=
checkunique=20=3D>=20tr=0A=20SELECT=20=
bt_index_parent_check('bttest_a_idx',=20heapallindexed=20=3D>=20true,=20=
rootdescend=20=3D>=20true,=20checkunique=20=3D>=20true);=0A=20SELECT=20=
bt_index_parent_check('bttest_b_idx',=20heapallindexed=20=3D>=20true,=20=
rootdescend=20=3D>=20false,=20checkunique=20=3D>=20true);=0A=20=0A+--=20=
indexallkeysmatch:=20verify=20each=20index=20tuple=20points=20to=20heap=20=
tuple=20with=20same=20key=0A+SELECT=20bt_index_check('bttest_a_idx',=20=
heapallindexed=20=3D>=20false,=20checkunique=20=3D>=20false,=20=
indexallkeysmatch=20=3D>=20true);=0A+SELECT=20=
bt_index_parent_check('bttest_a_idx',=20heapallindexed=20=3D>=20false,=20=
rootdescend=20=3D>=20false,=20checkunique=20=3D>=20false,=20=
indexallkeysmatch=20=3D>=20true);=0A+=0A=20--=20Check=20that=20null=20=
values=20in=20an=20unique=20index=20are=20not=20treated=20as=20equal=0A=20=
CREATE=20TABLE=20bttest_unique_nulls=20(a=20serial,=20b=20int,=20c=20int=20=
UNIQUE);=0A=20INSERT=20INTO=20bttest_unique_nulls=20VALUES=20=
(generate_series(1,=2010000),=202,=20default);=0Adiff=20--git=20=
a/contrib/amcheck/t/007_verify_nbtree_indexallkeysmatch.pl=20=
b/contrib/amcheck/t/007_verify_nbtree_indexallkeysmatch.pl=0Anew=20file=20=
mode=20100644=0Aindex=2000000000000..caf2cbd93e7=0A---=20/dev/null=0A+++=20=
b/contrib/amcheck/t/007_verify_nbtree_indexallkeysmatch.pl=0A@@=20-0,0=20=
+1,111=20@@=0A+=0A+#=20Copyright=20(c)=202026,=20PostgreSQL=20Global=20=
Development=20Group=0A+#=0A+#=20Test=20indexallkeysmatch=20verification:=20=
each=20index=20tuple=20must=20point=20to=20a=20heap=0A+#=20tuple=20with=20=
the=20same=20key.=0A+=0A+use=20strict;=0A+use=20warnings=20FATAL=20=3D>=20=
'all';=0A+=0A+use=20PostgreSQL::Test::Cluster;=0A+use=20=
PostgreSQL::Test::Utils;=0A+use=20Test::More;=0A+=0A+my=20$node=20=3D=20=
PostgreSQL::Test::Cluster->new('test');=0A+$node->init;=0A=
+$node->append_conf('postgresql.conf',=20'autovacuum=3Doff');=0A=
+$node->start;=0A+=0A+$node->safe_psql('postgres',=20q(CREATE=20=
EXTENSION=20amcheck));=0A+=0A+#=0A+#=20Test=201:=20indexallkeysmatch=20=
on=20uncorrupted=20table=20(plain=20column)=0A+#=0A=
+$node->safe_psql('postgres',=20q(=0A+=09CREATE=20TABLE=20idxall_plain=20=
(id=20int);=0A+=09INSERT=20INTO=20idxall_plain=20SELECT=20=
generate_series(1,=201000);=0A+=09CREATE=20INDEX=20idxall_plain_idx=20ON=20=
idxall_plain=20(id);=0A+));=0A+=0A+my=20$result=20=3D=20=
$node->safe_psql('postgres',=0A+=09q(SELECT=20=
bt_index_check('idxall_plain_idx',=20false,=20false,=20true)));=0A=
+is($result,=20'',=20'indexallkeysmatch=20passes=20on=20uncorrupted=20=
plain=20table');=0A+=0A+#=0A+#=20Test=202:=20indexallkeysmatch=20on=20=
uncorrupted=20table=20with=20deduplication=0A+#=0A=
+$node->safe_psql('postgres',=20q(=0A+=09CREATE=20TABLE=20idxall_dedup=20=
(id=20int);=0A+=09INSERT=20INTO=20idxall_dedup=20SELECT=20i=20%=2010=20=
FROM=20generate_series(1,=201000)=20i;=0A+=09CREATE=20INDEX=20=
idxall_dedup_idx=20ON=20idxall_dedup=20(id)=0A+=09=09WITH=20=
(deduplicate_items=20=3D=20on);=0A+));=0A+=0A+$result=20=3D=20=
$node->safe_psql('postgres',=0A+=09q(SELECT=20=
bt_index_check('idxall_dedup_idx',=20false,=20false,=20true)));=0A=
+is($result,=20'',=20'indexallkeysmatch=20passes=20on=20uncorrupted=20=
table=20with=20deduplication');=0A+=0A+#=0A+#=20Test=203:=20=
indexallkeysmatch=20on=20uncorrupted=20expression=20index=0A+#=0A=
+$node->safe_psql('postgres',=20q(=0A+=09CREATE=20FUNCTION=20=
idxall_func(int)=20RETURNS=20int=20LANGUAGE=20sql=20IMMUTABLE=20AS=0A+=09=
$$=20SELECT=20$1;=20$$;=0A+=0A+=09CREATE=20TABLE=20idxall_expr=20(id=20=
int);=0A+=09INSERT=20INTO=20idxall_expr=20SELECT=20generate_series(1,=20=
500);=0A+=09CREATE=20INDEX=20idxall_expr_idx=20ON=20idxall_expr=20=
(idxall_func(id));=0A+));=0A+=0A+$result=20=3D=20=
$node->safe_psql('postgres',=0A+=09q(SELECT=20=
bt_index_check('idxall_expr_idx',=20false,=20false,=20true)));=0A=
+is($result,=20'',=20'indexallkeysmatch=20passes=20on=20uncorrupted=20=
expression=20index');=0A+=0A+#=0A+#=20Test=204:=20Detect=20corruption=20=
--=20swap=20expression=20function=20so=20heap=20re-evaluation=0A+#=20=
produces=20different=20keys=20than=20what=20the=20index=20stores.=0A+#=0A=
+#=20The=20index=20was=20built=20with=20idxall_func(x)=20=3D=20x.=20=20=
Now=20change=20it=20to=20return=20x+1.=0A+#=20This=20simulates=20the=20=
corruption=20scenario:=20index=20says=20key=3D42=20for=20a=20TID,=20but=0A=
+#=20re-reading=20the=20heap=20and=20re-evaluating=20gives=20key=3D43.=0A=
+#=0A+$node->safe_psql('postgres',=20q(=0A+=09CREATE=20OR=20REPLACE=20=
FUNCTION=20idxall_func(int)=20RETURNS=20int=20LANGUAGE=20sql=20IMMUTABLE=20=
AS=0A+=09$$=20SELECT=20$1=20+=201;=20$$;=0A+));=0A+=0A+my=20($stdout,=20=
$stderr);=0A+($result,=20$stdout,=20$stderr)=20=3D=20=
$node->psql('postgres',=0A+=09q(SELECT=20=
bt_index_check('idxall_expr_idx',=20false,=20false,=20true)));=0A=
+like($stderr,=0A+=09qr/index=20tuple=20in=20index=20"idxall_expr_idx"=20=
does=20not=20match=20heap=20tuple/,=0A+=09'detected=20index-heap=20key=20=
mismatch=20via=20expression=20function=20swap');=0A+=0A+#=0A+#=20Test=20=
5:=20Restore=20function=20and=20verify=20no=20corruption=20reported=0A+#=0A=
+$node->safe_psql('postgres',=20q(=0A+=09CREATE=20OR=20REPLACE=20=
FUNCTION=20idxall_func(int)=20RETURNS=20int=20LANGUAGE=20sql=20IMMUTABLE=20=
AS=0A+=09$$=20SELECT=20$1;=20$$;=0A+));=0A+=0A+$result=20=3D=20=
$node->safe_psql('postgres',=0A+=09q(SELECT=20=
bt_index_check('idxall_expr_idx',=20false,=20false,=20true)));=0A=
+is($result,=20'',=20'indexallkeysmatch=20passes=20after=20restoring=20=
correct=20function');=0A+=0A+#=0A+#=20Test=206:=20indexallkeysmatch=20=
with=20bt_index_parent_check=0A+#=0A+$node->safe_psql('postgres',=20q(=0A=
+=09CREATE=20OR=20REPLACE=20FUNCTION=20idxall_func(int)=20RETURNS=20int=20=
LANGUAGE=20sql=20IMMUTABLE=20AS=0A+=09$$=20SELECT=20$1=20+=201;=20$$;=0A=
+));=0A+=0A+($result,=20$stdout,=20$stderr)=20=3D=20=
$node->psql('postgres',=0A+=09q(SELECT=20=
bt_index_parent_check('idxall_expr_idx',=20false,=20false,=20false,=20=
true)));=0A+like($stderr,=0A+=09qr/index=20tuple=20in=20index=20=
"idxall_expr_idx"=20does=20not=20match=20heap=20tuple/,=0A+=09=
'bt_index_parent_check=20also=20detects=20index-heap=20key=20mismatch');=0A=
+=0A+$node->stop;=0A+done_testing();=0Adiff=20--git=20=
a/contrib/amcheck/verify_nbtree.c=20b/contrib/amcheck/verify_nbtree.c=0A=
index=2034433e819d4..28f283b3a21=20100644=0A---=20=
a/contrib/amcheck/verify_nbtree.c=0A+++=20=
b/contrib/amcheck/verify_nbtree.c=0A@@=20-13,6=20+13,11=20@@=0A=20=20*=20=
verify=20its=20structure.=20=20A=20heap=20scan=20later=20uses=20Bloom=20=
filter=20probes=20to=20verify=0A=20=20*=20that=20every=20visible=20heap=20=
tuple=20has=20a=20matching=20index=20tuple.=0A=20=20*=0A+=20*=20When=20=
heap-to-index=20verification=20(indexallkeysmatch)=20is=20requested,=20a=20=
Bloom=0A+=20*=20filter=20fingerprints=20(key,tid)=20from=20a=20heap=20=
scan=20first.=20=20The=20index=20scan=20then=0A+=20*=20probes=20this=20=
filter;=20when=20the=20probe=20fails,=20a=20heap=20lookup=20verifies=20=
that=20the=0A+=20*=20index=20tuple=20points=20to=20a=20heap=20tuple=20=
with=20the=20same=20key.=0A+=20*=0A=20=20*=0A=20=20*=20Copyright=20(c)=20=
2017-2026,=20PostgreSQL=20Global=20Development=20Group=0A=20=20*=0A@@=20=
-30,8=20+35,9=20@@=0A=20#include=20"access/tableam.h"=0A=20#include=20=
"access/transam.h"=0A=20#include=20"access/xact.h"=0A-#include=20=
"verify_common.h"=0A=20#include=20"catalog/index.h"=0A+#include=20=
"executor/executor.h"=0A+#include=20"verify_common.h"=0A=20#include=20=
"catalog/pg_am.h"=0A=20#include=20"catalog/pg_opfamily_d.h"=0A=20=
#include=20"common/pg_prng.h"=0A@@=20-82,6=20+88,8=20@@=20typedef=20=
struct=20BtreeCheckState=0A=20=09bool=09=09readonly;=0A=20=09/*=20Also=20=
verifying=20heap=20has=20no=20unindexed=20tuples?=20*/=0A=20=09bool=09=09=
heapallindexed;=0A+=09/*=20Also=20verifying=20each=20index=20tuple=20=
points=20to=20heap=20tuple=20with=20same=20key?=20*/=0A+=09bool=09=09=
indexallkeysmatch;=0A=20=09/*=20Also=20making=20sure=20non-pivot=20=
tuples=20can=20be=20found=20by=20new=20search?=20*/=0A=20=09bool=09=09=
rootdescend;=0A=20=09/*=20Also=20check=20uniqueness=20constraint=20if=20=
index=20is=20unique=20*/=0A@@=20-132,6=20+140,15=20@@=20typedef=20struct=20=
BtreeCheckState=0A=20=09bloom_filter=20*filter;=0A=20=09/*=20Debug=20=
counter=20*/=0A=20=09int64=09=09heaptuplespresent;=0A+=0A+=09/*=0A+=09=20=
*=20Mutable=20state,=20for=20optional=20indexallkeysmatch=20=
verification:=0A+=09=20*/=0A+=0A+=09/*=20Bloom=20filter=20fingerprints=20=
heap=20(key,tid)=20pairs=20*/=0A+=09bloom_filter=20*heapfilter;=0A+=09/*=20=
Debug=20counter=20for=20index=20tuples=20verified=20*/=0A+=09int64=09=09=
indextuplesverified;=0A=20}=20BtreeCheckState;=0A=20=0A=20/*=0A@@=20=
-169,6=20+186,7=20@@=20typedef=20struct=20BTCallbackState=0A=20{=0A=20=09=
bool=09=09parentcheck;=0A=20=09bool=09=09heapallindexed;=0A+=09bool=09=09=
indexallkeysmatch;=0A=20=09bool=09=09rootdescend;=0A=20=09bool=09=09=
checkunique;=0A=20}=20BTCallbackState;=0A@@=20-180,7=20+198,7=20@@=20=
static=20void=20bt_index_check_callback(Relation=20indrel,=20Relation=20=
heaprel,=0A=20=09=09=09=09=09=09=09=09=09void=20*state,=20bool=20=
readonly);=0A=20static=20void=20bt_check_every_level(Relation=20rel,=20=
Relation=20heaprel,=0A=20=09=09=09=09=09=09=09=09=20bool=20heapkeyspace,=20=
bool=20readonly,=20bool=20heapallindexed,=0A-=09=09=09=09=09=09=09=09=20=
bool=20rootdescend,=20bool=20checkunique);=0A+=09=09=09=09=09=09=09=09=20=
bool=20indexallkeysmatch,=20bool=20rootdescend,=20bool=20checkunique);=0A=
=20static=20BtreeLevel=20bt_check_level_from_leftmost(BtreeCheckState=20=
*state,=0A=20=09=09=09=09=09=09=09=09=09=09=09=20=20=20BtreeLevel=20=
level);=0A=20static=20bool=20=
bt_leftmost_ignoring_half_dead(BtreeCheckState=20*state,=0A@@=20-212,6=20=
+230,13=20@@=20static=20void=20bt_downlink_missing_check(BtreeCheckState=20=
*state,=20bool=20rightsplit,=0A=20static=20void=20=
bt_tuple_present_callback(Relation=20index,=20ItemPointer=20tid,=0A=20=09=
=09=09=09=09=09=09=09=09=20=20Datum=20*values,=20bool=20*isnull,=0A=20=09=
=09=09=09=09=09=09=09=09=20=20bool=20tupleIsAlive,=20void=20=
*checkstate);=0A+static=20void=20bt_heap_fingerprint_callback(Relation=20=
index,=20ItemPointer=20tid,=0A+=09=09=09=09=09=09=09=09=09=09=20=20Datum=20=
*values,=20bool=20*isnull,=0A+=09=09=09=09=09=09=09=09=09=09=20=20bool=20=
tupleIsAlive,=20void=20*checkstate);=0A+static=20void=20=
bt_verify_index_tuple_points_to_heap(BtreeCheckState=20*state,=0A+=09=09=09=
=09=09=09=09=09=09=09=09=09=20=20IndexTuple=20itup,=0A+=09=09=09=09=09=09=
=09=09=09=09=09=09=20=20BlockNumber=20targetblock,=0A+=09=09=09=09=09=09=09=
=09=09=09=09=09=20=20OffsetNumber=20offset);=0A=20static=20IndexTuple=20=
bt_normalize_tuple(BtreeCheckState=20*state,=0A=20=09=09=09=09=09=09=09=09=
=09=20IndexTuple=20itup);=0A=20static=20inline=20IndexTuple=20=
bt_posting_plain_tuple(IndexTuple=20itup,=20int=20n);=0A@@=20-240,13=20=
+265,15=20@@=20static=20inline=20ItemPointer=20=
BTreeTupleGetHeapTIDCareful(BtreeCheckState=20*state,=0A=20static=20=
inline=20ItemPointer=20BTreeTupleGetPointsToTID(IndexTuple=20itup);=0A=20=
=0A=20/*=0A-=20*=20bt_index_check(index=20regclass,=20heapallindexed=20=
boolean,=20checkunique=20boolean)=0A+=20*=20bt_index_check(index=20=
regclass,=20heapallindexed=20boolean,=20checkunique=20boolean,=20=
indexallkeysmatch=20boolean)=0A=20=20*=0A=20=20*=20Verify=20integrity=20=
of=20B-Tree=20index.=0A=20=20*=0A=20=20*=20Acquires=20AccessShareLock=20=
on=20heap=20&=20index=20relations.=20=20Does=20not=20consider=0A=20=20*=20=
invariants=20that=20exist=20between=20parent/child=20pages.=20=20=
Optionally=20verifies=0A-=20*=20that=20heap=20does=20not=20contain=20any=20=
unindexed=20or=20incorrectly=20indexed=20tuples.=0A+=20*=20that=20heap=20=
does=20not=20contain=20any=20unindexed=20or=20incorrectly=20indexed=20=
tuples=0A+=20*=20(heapallindexed),=20or=20that=20each=20index=20tuple=20=
points=20to=20a=20heap=20tuple=20with=0A+=20*=20the=20same=20key=20=
(indexallkeysmatch).=0A=20=20*/=0A=20Datum=0A=20=
bt_index_check(PG_FUNCTION_ARGS)=0A@@=20-255,6=20+282,7=20@@=20=
bt_index_check(PG_FUNCTION_ARGS)=0A=20=09BTCallbackState=20args;=0A=20=0A=
=20=09args.heapallindexed=20=3D=20false;=0A+=09args.indexallkeysmatch=20=
=3D=20false;=0A=20=09args.rootdescend=20=3D=20false;=0A=20=09=
args.parentcheck=20=3D=20false;=0A=20=09args.checkunique=20=3D=20false;=0A=
@@=20-263,6=20+291,8=20@@=20bt_index_check(PG_FUNCTION_ARGS)=0A=20=09=09=
args.heapallindexed=20=3D=20PG_GETARG_BOOL(1);=0A=20=09if=20(PG_NARGS()=20=
>=3D=203)=0A=20=09=09args.checkunique=20=3D=20PG_GETARG_BOOL(2);=0A+=09=
if=20(PG_NARGS()=20>=3D=204)=0A+=09=09args.indexallkeysmatch=20=3D=20=
PG_GETARG_BOOL(3);=0A=20=0A=20=09=
amcheck_lock_relation_and_check(indrelid,=20BTREE_AM_OID,=0A=20=09=09=09=09=
=09=09=09=09=09bt_index_check_callback,=0A@@=20-272,13=20+302,15=20@@=20=
bt_index_check(PG_FUNCTION_ARGS)=0A=20}=0A=20=0A=20/*=0A-=20*=20=
bt_index_parent_check(index=20regclass,=20heapallindexed=20boolean,=20=
rootdescend=20boolean,=20checkunique=20boolean)=0A+=20*=20=
bt_index_parent_check(index=20regclass,=20heapallindexed=20boolean,=20=
rootdescend=20boolean,=20checkunique=20boolean,=20indexallkeysmatch=20=
boolean)=0A=20=20*=0A=20=20*=20Verify=20integrity=20of=20B-Tree=20index.=0A=
=20=20*=0A=20=20*=20Acquires=20ShareLock=20on=20heap=20&=20index=20=
relations.=20=20Verifies=20that=20downlinks=20in=0A=20=20*=20parent=20=
pages=20are=20valid=20lower=20bounds=20on=20child=20pages.=20=20=
Optionally=20verifies=0A-=20*=20that=20heap=20does=20not=20contain=20any=20=
unindexed=20or=20incorrectly=20indexed=20tuples.=0A+=20*=20that=20heap=20=
does=20not=20contain=20any=20unindexed=20or=20incorrectly=20indexed=20=
tuples=0A+=20*=20(heapallindexed),=20or=20that=20each=20index=20tuple=20=
points=20to=20a=20heap=20tuple=20with=0A+=20*=20the=20same=20key=20=
(indexallkeysmatch).=0A=20=20*/=0A=20Datum=0A=20=
bt_index_parent_check(PG_FUNCTION_ARGS)=0A@@=20-287,6=20+319,7=20@@=20=
bt_index_parent_check(PG_FUNCTION_ARGS)=0A=20=09BTCallbackState=20args;=0A=
=20=0A=20=09args.heapallindexed=20=3D=20false;=0A+=09=
args.indexallkeysmatch=20=3D=20false;=0A=20=09args.rootdescend=20=3D=20=
false;=0A=20=09args.parentcheck=20=3D=20true;=0A=20=09args.checkunique=20=
=3D=20false;=0A@@=20-297,6=20+330,8=20@@=20=
bt_index_parent_check(PG_FUNCTION_ARGS)=0A=20=09=09args.rootdescend=20=3D=20=
PG_GETARG_BOOL(2);=0A=20=09if=20(PG_NARGS()=20>=3D=204)=0A=20=09=09=
args.checkunique=20=3D=20PG_GETARG_BOOL(3);=0A+=09if=20(PG_NARGS()=20>=3D=20=
5)=0A+=09=09args.indexallkeysmatch=20=3D=20PG_GETARG_BOOL(4);=0A=20=0A=20=
=09amcheck_lock_relation_and_check(indrelid,=20BTREE_AM_OID,=0A=20=09=09=09=
=09=09=09=09=09=09bt_index_check_callback,=0A@@=20-348,7=20+383,8=20@@=20=
bt_index_check_callback(Relation=20indrel,=20Relation=20heaprel,=20void=20=
*state,=20bool=20rea=0A=20=0A=20=09/*=20Check=20index,=20possibly=20=
against=20table=20it=20is=20an=20index=20on=20*/=0A=20=09=
bt_check_every_level(indrel,=20heaprel,=20heapkeyspace,=20readonly,=0A-=09=
=09=09=09=09=09=20args->heapallindexed,=20args->rootdescend,=20=
args->checkunique);=0A+=09=09=09=09=09=09=20args->heapallindexed,=20=
args->indexallkeysmatch,=0A+=09=09=09=09=09=09=20args->rootdescend,=20=
args->checkunique);=0A=20}=0A=20=0A=20/*=0A@@=20-376,8=20+412,8=20@@=20=
bt_index_check_callback(Relation=20indrel,=20Relation=20heaprel,=20void=20=
*state,=20bool=20rea=0A=20=20*/=0A=20static=20void=0A=20=
bt_check_every_level(Relation=20rel,=20Relation=20heaprel,=20bool=20=
heapkeyspace,=0A-=09=09=09=09=09=20bool=20readonly,=20bool=20=
heapallindexed,=20bool=20rootdescend,=0A-=09=09=09=09=09=20bool=20=
checkunique)=0A+=09=09=09=09=09=20bool=20readonly,=20bool=20=
heapallindexed,=20bool=20indexallkeysmatch,=0A+=09=09=09=09=09=20bool=20=
rootdescend,=20bool=20checkunique)=0A=20{=0A=20=09BtreeCheckState=20=
*state;=0A=20=09Page=09=09metapage;=0A@@=20-407,38=20+443,17=20@@=20=
bt_check_every_level(Relation=20rel,=20Relation=20heaprel,=20bool=20=
heapkeyspace,=0A=20=09state->heapkeyspace=20=3D=20heapkeyspace;=0A=20=09=
state->readonly=20=3D=20readonly;=0A=20=09state->heapallindexed=20=3D=20=
heapallindexed;=0A+=09state->indexallkeysmatch=20=3D=20=
indexallkeysmatch;=0A=20=09state->rootdescend=20=3D=20rootdescend;=0A=20=09=
state->checkunique=20=3D=20checkunique;=0A=20=09state->snapshot=20=3D=20=
InvalidSnapshot;=0A=20=0A-=09if=20(state->heapallindexed)=0A+=09if=20=
(state->heapallindexed=20||=20state->indexallkeysmatch)=0A=20=09{=0A-=09=09=
int64=09=09total_pages;=0A-=09=09int64=09=09total_elems;=0A-=09=09uint64=09=
=09seed;=0A-=0A-=09=09/*=0A-=09=09=20*=20Size=20Bloom=20filter=20based=20=
on=20estimated=20number=20of=20tuples=20in=20index,=0A-=09=09=20*=20=
while=20conservatively=20assuming=20that=20each=20block=20must=20contain=20=
at=20least=0A-=09=09=20*=20MaxTIDsPerBTreePage=20/=203=20"plain"=20=
tuples=20--=20see=0A-=09=09=20*=20bt_posting_plain_tuple()=20for=20=
definition,=20and=20details=20of=20how=20posting=0A-=09=09=20*=20list=20=
tuples=20are=20handled.=0A-=09=09=20*/=0A-=09=09total_pages=20=3D=20=
RelationGetNumberOfBlocks(rel);=0A-=09=09total_elems=20=3D=20=
Max(total_pages=20*=20(MaxTIDsPerBTreePage=20/=203),=0A-=09=09=09=09=09=09=
=20=20(int64)=20state->rel->rd_rel->reltuples);=0A-=09=09/*=20Generate=20=
a=20random=20seed=20to=20avoid=20repetition=20*/=0A-=09=09seed=20=3D=20=
pg_prng_uint64(&pg_global_prng_state);=0A-=09=09/*=20Create=20Bloom=20=
filter=20to=20fingerprint=20index=20*/=0A-=09=09state->filter=20=3D=20=
bloom_create(total_elems,=20maintenance_work_mem,=20seed);=0A-=09=09=
state->heaptuplespresent=20=3D=200;=0A-=0A=20=09=09/*=0A-=09=09=20*=20=
Register=20our=20own=20snapshot=20for=20heapallindexed,=20rather=20than=20=
asking=0A-=09=09=20*=20table_index_build_scan()=20to=20do=20this=20for=20=
us=20later.=20=20This=20needs=20to=0A-=09=09=20*=20happen=20before=20=
index=20fingerprinting=20begins,=20so=20we=20can=20later=20be=0A-=09=09=20=
*=20certain=20that=20index=20fingerprinting=20should=20have=20reached=20=
all=20tuples=0A-=09=09=20*=20returned=20by=20table_index_build_scan().=0A=
+=09=09=20*=20Register=20our=20own=20snapshot=20for=20=
heapallindexed/indexallkeysmatch,=20rather=0A+=09=09=20*=20than=20asking=20=
table_index_build_scan()=20to=20do=20this=20for=20us=20later.=20=20This=0A=
+=09=09=20*=20needs=20to=20happen=20before=20fingerprinting=20begins.=0A=20=
=09=09=20*/=0A=20=09=09state->snapshot=20=3D=20=
RegisterSnapshot(GetTransactionSnapshot());=0A=20=0A@@=20-463,16=20=
+478,55=20@@=20bt_check_every_level(Relation=20rel,=20Relation=20=
heaprel,=20bool=20heapkeyspace,=0A=20=09=09=09=09=09=09=20=20=20=
RelationGetRelationName(rel)));=0A=20=09}=0A=20=0A+=09if=20=
(state->heapallindexed)=0A+=09{=0A+=09=09int64=09=09total_pages;=0A+=09=09=
int64=09=09total_elems;=0A+=09=09uint64=09=09seed;=0A+=0A+=09=09/*=0A+=09=
=09=20*=20Size=20Bloom=20filter=20based=20on=20estimated=20number=20of=20=
tuples=20in=20index,=0A+=09=09=20*=20while=20conservatively=20assuming=20=
that=20each=20block=20must=20contain=20at=20least=0A+=09=09=20*=20=
MaxTIDsPerBTreePage=20/=203=20"plain"=20tuples=20--=20see=0A+=09=09=20*=20=
bt_posting_plain_tuple()=20for=20definition,=20and=20details=20of=20how=20=
posting=0A+=09=09=20*=20list=20tuples=20are=20handled.=0A+=09=09=20*/=0A=
+=09=09total_pages=20=3D=20RelationGetNumberOfBlocks(rel);=0A+=09=09=
total_elems=20=3D=20Max(total_pages=20*=20(MaxTIDsPerBTreePage=20/=203),=0A=
+=09=09=09=09=09=09=20=20(int64)=20state->rel->rd_rel->reltuples);=0A+=09=
=09seed=20=3D=20pg_prng_uint64(&pg_global_prng_state);=0A+=09=09=
state->filter=20=3D=20bloom_create(total_elems,=20maintenance_work_mem,=20=
seed);=0A+=09=09state->heaptuplespresent=20=3D=200;=0A+=09}=0A+=0A+=09if=20=
(state->indexallkeysmatch)=0A+=09{=0A+=09=09int64=09=09total_pages;=0A+=09=
=09int64=09=09total_elems;=0A+=09=09uint64=09=09seed;=0A+=0A+=09=09/*=0A=
+=09=09=20*=20Size=20Bloom=20filter=20based=20on=20estimated=20number=20=
of=20heap=20tuples.=0A+=09=09=20*/=0A+=09=09total_pages=20=3D=20=
RelationGetNumberOfBlocks(heaprel);=0A+=09=09total_elems=20=3D=20=
Max(total_pages=20*=20MaxHeapTuplesPerPage,=0A+=09=09=09=09=09=09=20=20=
(int64)=20heaprel->rd_rel->reltuples);=0A+=09=09seed=20=3D=20=
pg_prng_uint64(&pg_global_prng_state);=0A+=09=09state->heapfilter=20=3D=20=
bloom_create(total_elems,=20maintenance_work_mem,=20seed);=0A+=09=09=
state->indextuplesverified=20=3D=200;=0A+=09}=0A+=0A=20=09/*=0A=20=09=20=
*=20We=20need=20a=20snapshot=20to=20check=20the=20uniqueness=20of=20the=20=
index.=20=20For=20better=0A=20=09=20*=20performance,=20take=20it=20once=20=
per=20index=20check.=20=20If=20one=20was=20already=20taken=0A=20=09=20*=20=
above,=20use=20that.=0A=20=09=20*/=0A-=09if=20(state->checkunique)=0A+=09=
if=20(state->checkunique=20||=20state->indexallkeysmatch)=0A=20=09{=0A=20=
=09=09state->indexinfo=20=3D=20BuildIndexInfo(state->rel);=0A=20=0A-=09=09=
if=20(state->indexinfo->ii_Unique=20&&=20state->snapshot=20=3D=3D=20=
InvalidSnapshot)=0A+=09=09if=20(state->checkunique=20&&=20=
state->indexinfo->ii_Unique=20&&=0A+=09=09=09state->snapshot=20=3D=3D=20=
InvalidSnapshot)=0A=20=09=09=09state->snapshot=20=3D=20=
RegisterSnapshot(GetTransactionSnapshot());=0A=20=09}=0A=20=0A@@=20=
-490,6=20+544,36=20@@=20bt_check_every_level(Relation=20rel,=20Relation=20=
heaprel,=20bool=20heapkeyspace,=0A=20=09=09=09=09=09=09=09=09=09=09=09=09=
=20ALLOCSET_DEFAULT_SIZES);=0A=20=09state->checkstrategy=20=3D=20=
GetAccessStrategy(BAS_BULKREAD);=0A=20=0A+=09/*=0A+=09=20*=20When=20=
indexallkeysmatch,=20fingerprint=20heap=20first=20so=20we=20can=20verify=20=
each=20index=0A+=09=20*=20tuple=20points=20to=20a=20heap=20tuple=20with=20=
the=20same=20key=20during=20the=20index=20scan.=0A+=09=20*/=0A+=09if=20=
(state->indexallkeysmatch)=0A+=09{=0A+=09=09IndexInfo=20=20*indexinfo=20=
=3D=20BuildIndexInfo(state->rel);=0A+=09=09TableScanDesc=20scan;=0A+=0A+=09=
=09scan=20=3D=20table_beginscan_strat(state->heaprel,=0A+=09=09=09=09=09=09=
=09=09=09=20state->snapshot,=0A+=09=09=09=09=09=09=09=09=09=200,=20NULL,=20=
true,=20true);=0A+=09=09indexinfo->ii_Concurrent=20=3D=20true;=0A+=09=09=
indexinfo->ii_Unique=20=3D=20false;=0A+=09=09indexinfo->ii_ExclusionOps=20=
=3D=20NULL;=0A+=09=09indexinfo->ii_ExclusionProcs=20=3D=20NULL;=0A+=09=09=
indexinfo->ii_ExclusionStrats=20=3D=20NULL;=0A+=0A+=09=09elog(DEBUG1,=20=
"fingerprinting=20heap=20\"%s\"=20for=20index=20\"%s\"=20verification",=0A=
+=09=09=09=20RelationGetRelationName(state->heaprel),=0A+=09=09=09=20=
RelationGetRelationName(state->rel));=0A+=0A+=09=09=
table_index_build_scan(state->heaprel,=20state->rel,=20indexinfo,=20=
true,=20false,=0A+=09=09=09=09=09=09=09=20=20=20=
bt_heap_fingerprint_callback,=20state,=20scan);=0A+=0A+=09=09=
ereport(DEBUG1,=0A+=09=09=09=09(errmsg_internal("finished=20heap=20=
fingerprint=20with=20bitset=20%.2f%%=20set",=0A+=09=09=09=09=09=09=09=09=
100.0=20*=20bloom_prop_bits_set(state->heapfilter))));=0A+=09}=0A+=0A=20=09=
/*=20Get=20true=20root=20block=20from=20meta-page=20*/=0A=20=09metapage=20=
=3D=20palloc_btree_page(state,=20BTREE_METAPAGE);=0A=20=09metad=20=3D=20=
BTPageGetMeta(metapage);=0A@@=20-596,6=20+680,14=20@@=20=
bt_check_every_level(Relation=20rel,=20Relation=20heaprel,=20bool=20=
heapkeyspace,=0A=20=09=09bloom_free(state->filter);=0A=20=09}=0A=20=0A+=09=
if=20(state->indexallkeysmatch)=0A+=09{=0A+=09=09ereport(DEBUG1,=0A+=09=09=
=09=09(errmsg_internal("finished=20verifying=20"=20INT64_FORMAT=20"=20=
index=20tuples=20point=20to=20matching=20heap=20tuples",=0A+=09=09=09=09=09=
=09=09=09=20state->indextuplesverified)));=0A+=09=09=
bloom_free(state->heapfilter);=0A+=09}=0A+=0A=20=09/*=20Be=20tidy:=20*/=0A=
=20=09if=20(state->snapshot=20!=3D=20InvalidSnapshot)=0A=20=09=09=
UnregisterSnapshot(state->snapshot);=0A@@=20-1516,6=20+1608,28=20@@=20=
bt_target_page_check(BtreeCheckState=20*state)=0A=20=09=09=09}=0A=20=09=09=
}=0A=20=0A+=09=09/*=20Verify=20each=20index=20tuple=20points=20to=20heap=20=
tuple=20with=20same=20key=20*/=0A+=09=09if=20(state->indexallkeysmatch=20=
&&=20P_ISLEAF(topaque)=20&&=20!ItemIdIsDead(itemid))=0A+=09=09{=0A+=09=09=
=09if=20(BTreeTupleIsPosting(itup))=0A+=09=09=09{=0A+=09=09=09=09for=20=
(int=20i=20=3D=200;=20i=20<=20BTreeTupleGetNPosting(itup);=20i++)=0A+=09=09=
=09=09{=0A+=09=09=09=09=09IndexTuple=09logtuple;=0A+=0A+=09=09=09=09=09=
logtuple=20=3D=20bt_posting_plain_tuple(itup,=20i);=0A+=09=09=09=09=09=
bt_verify_index_tuple_points_to_heap(state,=20logtuple,=0A+=09=09=09=09=09=
=09=09=09=09=09=09=09=09=09=20=20state->targetblock,=20offset);=0A+=09=09=
=09=09=09pfree(logtuple);=0A+=09=09=09=09}=0A+=09=09=09}=0A+=09=09=09=
else=0A+=09=09=09{=0A+=09=09=09=09=
bt_verify_index_tuple_points_to_heap(state,=20itup,=0A+=09=09=09=09=09=09=
=09=09=09=09=09=09=09=20state->targetblock,=20offset);=0A+=09=09=09}=0A+=09=
=09}=0A+=0A=20=09=09/*=0A=20=09=09=20*=20*=20High=20key=20check=20*=0A=20=
=09=09=20*=0A@@=20-2812,6=20+2926,133=20@@=20=
bt_tuple_present_callback(Relation=20index,=20ItemPointer=20tid,=20Datum=20=
*values,=0A=20=09=09pfree(norm);=0A=20}=0A=20=0A+/*=0A+=20*=20Per-tuple=20=
callback=20from=20table_index_build_scan=20for=20indexallkeysmatch.=20=20=
Add=0A+=20*=20each=20visible=20heap=20tuple's=20(key,=20tid)=20to=20the=20=
Bloom=20filter=20for=20later=20probe=0A+=20*=20during=20the=20index=20=
scan.=0A+=20*/=0A+static=20void=0A+bt_heap_fingerprint_callback(Relation=20=
index,=20ItemPointer=20tid,=20Datum=20*values,=0A+=09=09=09=09=09=09=09=20=
=20bool=20*isnull,=20bool=20tupleIsAlive,=20void=20*checkstate)=0A+{=0A+=09=
BtreeCheckState=20*state=20=3D=20(BtreeCheckState=20*)=20checkstate;=0A+=09=
IndexTuple=09itup,=0A+=09=09=09=09norm;=0A+=0A+=09=
Assert(state->indexallkeysmatch);=0A+=0A+=09itup=20=3D=20=
index_form_tuple(RelationGetDescr(index),=20values,=20isnull);=0A+=09=
itup->t_tid=20=3D=20*tid;=0A+=09norm=20=3D=20bt_normalize_tuple(state,=20=
itup);=0A+=09bloom_add_element(state->heapfilter,=20(unsigned=20char=20=
*)=20norm,=0A+=09=09=09=09=09=20=20IndexTupleSize(norm));=0A+=09=
pfree(itup);=0A+=09if=20(norm=20!=3D=20itup)=0A+=09=09pfree(norm);=0A+}=0A=
+=0A+/*=0A+=20*=20Verify=20that=20the=20index=20tuple=20points=20to=20a=20=
heap=20tuple=20with=20the=20same=20key.=0A+=20*=20When=20the=20Bloom=20=
filter=20lacks=20the=20(key,=20tid),=20perform=20a=20heap=20lookup=20to=20=
confirm.=0A+=20*=20Skip=20index=20tuples=20that=20point=20to=20dead=20=
heap=20tuples=20(not=20visible=20to=20snapshot).=0A+=20*/=0A+static=20=
void=0A+bt_verify_index_tuple_points_to_heap(BtreeCheckState=20*state,=20=
IndexTuple=20itup,=0A+=09=09=09=09=09=09=09=09=09BlockNumber=20=
targetblock,=20OffsetNumber=20offset)=0A+{=0A+=09ItemPointer=20tid=20=3D=20=
BTreeTupleGetHeapTID(itup);=0A+=09IndexTuple=09norm;=0A+=09bool=09=09=
in_filter;=0A+=0A+=09Assert(state->indexallkeysmatch);=0A+=0A+=09/*=20=
Only=20verify=20tuples=20pointing=20to=20visible=20heap=20rows=20*/=0A+=09=
if=20(!heap_entry_is_visible(state,=20tid))=0A+=09=09return;=0A+=0A+=09=
norm=20=3D=20bt_normalize_tuple(state,=20itup);=0A+=09in_filter=20=3D=20=
!bloom_lacks_element(state->heapfilter,=20(unsigned=20char=20*)=20norm,=0A=
+=09=09=09=09=09=09=09=09=09=20IndexTupleSize(norm));=0A+=09if=20(norm=20=
!=3D=20itup)=0A+=09=09pfree(norm);=0A+=0A+=09if=20(in_filter)=0A+=09{=0A=
+=09=09state->indextuplesverified++;=0A+=09=09return;=0A+=09}=0A+=0A+=09=
/*=0A+=09=20*=20Bloom=20filter=20says=20(key,=20tid)=20not=20in=20heap.=20=
=20Follow=20TID=20to=20verify;=20this=0A+=09=20*=20amortizes=20random=20=
heap=20lookups=20when=20the=20filter=20has=20false=20negatives,=20or=0A+=09=
=20*=20reports=20corruption=20when=20the=20index=20points=20to=20wrong=20=
heap=20tuple.=0A+=09=20*/=0A+=09{=0A+=09=09TupleTableSlot=20*slot;=0A+=09=
=09IndexTuple=09heap_itup;=0A+=09=09IndexTuple=09heap_norm;=0A+=09=09=
Datum=09=09values[INDEX_MAX_KEYS];=0A+=09=09bool=09=09=
isnull[INDEX_MAX_KEYS];=0A+=09=09IndexInfo=20=20*indexinfo;=0A+=09=09=
EState=09=20=20=20*estate;=0A+=09=09bool=09=09found;=0A+=0A+=09=09slot=20=
=3D=20table_slot_create(state->heaprel,=20NULL);=0A+=09=09found=20=3D=20=
table_tuple_fetch_row_version(state->heaprel,=20tid,=0A+=09=09=09=09=09=09=
=09=09=09=09=09=20=20state->snapshot,=20slot);=0A+=09=09if=20(!found)=0A=
+=09=09{=0A+=09=09=09ExecDropSingleTupleTableSlot(slot);=0A+=09=09=09=
ereport(ERROR,=0A+=09=09=09=09=09(errcode(ERRCODE_INDEX_CORRUPTED),=0A+=09=
=09=09=09=09=20errmsg("index=20tuple=20in=20index=20\"%s\"=20points=20to=20=
non-existent=20heap=20tuple",=0A+=09=09=09=09=09=09=09=
RelationGetRelationName(state->rel)),=0A+=09=09=09=09=09=20=
errdetail_internal("Index=20tid=3D(%u,%u)=20points=20to=20heap=20=
tid=3D(%u,%u).",=0A+=09=09=09=09=09=09=09=09=09=20=20=20targetblock,=20=
offset,=0A+=09=09=09=09=09=09=09=09=09=20=20=20=
ItemPointerGetBlockNumber(tid),=0A+=09=09=09=09=09=09=09=09=09=20=20=20=
ItemPointerGetOffsetNumber(tid))));=0A+=09=09}=0A+=0A+=09=09indexinfo=20=
=3D=20state->indexinfo;=0A+=09=09estate=20=3D=20CreateExecutorState();=0A=
+=09=09GetPerTupleExprContext(estate)->ecxt_scantuple=20=3D=20slot;=0A+=09=
=09FormIndexDatum(indexinfo,=20slot,=20estate,=20values,=20isnull);=0A+=09=
=09FreeExecutorState(estate);=0A+=0A+=09=09heap_itup=20=3D=20=
index_form_tuple(RelationGetDescr(state->rel),=20values,=20isnull);=0A+=09=
=09heap_itup->t_tid=20=3D=20*tid;=0A+=09=09heap_norm=20=3D=20=
bt_normalize_tuple(state,=20heap_itup);=0A+=0A+=09=09norm=20=3D=20=
bt_normalize_tuple(state,=20itup);=0A+=09=09if=20=
(IndexTupleSize(heap_norm)=20!=3D=20IndexTupleSize(norm)=20||=0A+=09=09=09=
memcmp(heap_norm,=20norm,=20IndexTupleSize(norm))=20!=3D=200)=0A+=09=09{=0A=
+=09=09=09ExecDropSingleTupleTableSlot(slot);=0A+=09=09=09=
pfree(heap_itup);=0A+=09=09=09if=20(heap_norm=20!=3D=20heap_itup)=0A+=09=09=
=09=09pfree(heap_norm);=0A+=09=09=09if=20(norm=20!=3D=20itup)=0A+=09=09=09=
=09pfree(norm);=0A+=09=09=09ereport(ERROR,=0A+=09=09=09=09=09=
(errcode(ERRCODE_INDEX_CORRUPTED),=0A+=09=09=09=09=09=20errmsg("index=20=
tuple=20in=20index=20\"%s\"=20does=20not=20match=20heap=20tuple",=0A+=09=09=
=09=09=09=09=09RelationGetRelationName(state->rel)),=0A+=09=09=09=09=09=20=
errdetail_internal("Index=20tid=3D(%u,%u)=20points=20to=20heap=20=
tid=3D(%u,%u)=20with=20different=20key.",=0A+=09=09=09=09=09=09=09=09=09=20=
=20=20targetblock,=20offset,=0A+=09=09=09=09=09=09=09=09=09=20=20=20=
ItemPointerGetBlockNumber(tid),=0A+=09=09=09=09=09=09=09=09=09=20=20=20=
ItemPointerGetOffsetNumber(tid))));=0A+=09=09}=0A+=0A+=09=09=
ExecDropSingleTupleTableSlot(slot);=0A+=09=09pfree(heap_itup);=0A+=09=09=
if=20(heap_norm=20!=3D=20heap_itup)=0A+=09=09=09pfree(heap_norm);=0A+=09=09=
if=20(norm=20!=3D=20itup)=0A+=09=09=09pfree(norm);=0A+=09=09=
state->indextuplesverified++;=0A+=09}=0A+}=0A+=0A=20/*=0A=20=20*=20=
Normalize=20an=20index=20tuple=20for=20fingerprinting.=0A=20=20*=0A--=20=0A=
2.51.2=0A=0A=

--Apple-Mail=_691C4BED-FD70-4652-A391-F1F617729CE5--