Amcheck verification of GiST and GIN

On 30 May 2022, at 12:40, Andrey Borodin <x4mmm@yandex-team.ru> wrote:

What do you think?

Hi Andrey!

Here's a version with better tests. I've made sure that GiST tests actually trigger page reuse after deletion. And enhanced comments in both GiST and GIN test scripts. I hope you'll like it.

GIN heapallindexed is still a no-op check. Looking forward to hear any ideas on what it could be.

Best regards, Andrey Borodin.

On Wed, Jun 22, 2022 at 11:35 AM Andrey Borodin <x4mmm@yandex-team.ru>
wrote:

On 30 May 2022, at 12:40, Andrey Borodin <x4mmm@yandex-team.ru> wrote:

What do you think?

Hi Andrey!

Hi Andrey!

Since you're talking to yourself, just wanted to support you – this is an
important thing, definitely should be very useful for many projects; I hope
to find time to test it in the next few days.

Thanks for working on it.

Hi,

I think having amcheck for more indexes is great.

On 2022-06-22 20:40:56 +0300, Andrey Borodin wrote:

diff --git a/contrib/amcheck/amcheck.c b/contrib/amcheck/amcheck.c

new file mode 100644
index 0000000000..7a222719dd
--- /dev/null
+++ b/contrib/amcheck/amcheck.c
@@ -0,0 +1,187 @@
+/*-------------------------------------------------------------------------
+ *
+ * amcheck.c
+ *		Utility functions common to all access methods.

This'd likely be easier to read if the reorganization were split into its own
commit.

I'd also split gin / gist support. It's a large enough patch that that imo
makes reviewing easier.

+void amcheck_lock_relation_and_check(Oid indrelid, IndexCheckableCallback checkable,
+												IndexDoCheckCallback check, LOCKMODE lockmode, void *state)

Might be worth pgindenting - the void for function definitions (but not for
declarations) is typically on its own line in PG code.

+static GistCheckState
+gist_init_heapallindexed(Relation rel)
+{
+	int64		total_pages;
+	int64		total_elems;
+	uint64		seed;
+	GistCheckState result;
+
+	/*
+	* Size Bloom filter based on estimated number of tuples in index
+	*/
+	total_pages = RelationGetNumberOfBlocks(rel);
+	total_elems = Max(total_pages * (MaxOffsetNumber / 5),
+						(int64) rel->rd_rel->reltuples);
+	/* Generate a random seed to avoid repetition */
+	seed = pg_prng_uint64(&pg_global_prng_state);
+	/* Create Bloom filter to fingerprint index */
+	result.filter = bloom_create(total_elems, maintenance_work_mem, seed);
+
+	/*
+	 * Register our own snapshot
+	 */
+	result.snapshot = RegisterSnapshot(GetTransactionSnapshot());

FWIW, comments like this, that just restate exactly what the code does, are
imo not helpful. Also, there's a trailing space :)

Greetings,

Andres Freund

On 23 Jun 2022, at 00:27, Nikolay Samokhvalov <samokhvalov@gmail.com> wrote:

Since you're talking to yourself, just wanted to support you – this is an important thing, definitely should be very useful for many projects; I hope to find time to test it in the next few days.

Thanks Nikolay!

On 23 Jun 2022, at 04:29, Andres Freund <andres@anarazel.de> wrote:

Thanks for looking into the patch, Andres!

On 2022-06-22 20:40:56 +0300, Andrey Borodin wrote:

diff --git a/contrib/amcheck/amcheck.c b/contrib/amcheck/amcheck.c

new file mode 100644
index 0000000000..7a222719dd
--- /dev/null
+++ b/contrib/amcheck/amcheck.c
@@ -0,0 +1,187 @@
+/*-------------------------------------------------------------------------
+ *
+ * amcheck.c
+ *		Utility functions common to all access methods.

This'd likely be easier to read if the reorganization were split into its own
commit.

I'd also split gin / gist support. It's a large enough patch that that imo
makes reviewing easier.

I will split the patch in 3 steps:
1. extract generic functions to amcheck.c
2. add gist functions
3. add gin functions
But each this step is just adding few independent files + some lines to Makefile.

I'll fix other notes too in the next version.

Thanks!

Best regards, Andrey Borodin.

On 26 Jun 2022, at 00:10, Andrey Borodin <x4mmm@yandex-team.ru> wrote:

I will split the patch in 3 steps:
1. extract generic functions to amcheck.c
2. add gist functions
3. add gin functions

I'll fix other notes too in the next version.

Done. PFA attached patchset.

Thanks!

Best regards, Andrey Borodin.

On 23 Jul 2022, at 14:40, Andrey Borodin <x4mmm@yandex-team.ru> wrote:

Done. PFA attached patchset.

Best regards, Andrey Borodin.
<v12-0001-Refactor-amcheck-to-extract-common-locking-routi.patch><v12-0002-Add-gist_index_parent_check-function-to-verify-G.patch><v12-0003-Add-gin_index_parent_check-to-verify-GIN-index.patch>

Here's v13. Changes:
1. Fixed passing through downlink in GIN index
2. Fixed GIN tests (one test case was not working)

Thanks to Vitaliy Kukharik for trying this patches.

Best regards, Andrey Borodin.

Hi,

On 2022-08-17 17:28:02 +0500, Andrey Borodin wrote:

Here's v13. Changes:
1. Fixed passing through downlink in GIN index
2. Fixed GIN tests (one test case was not working)

Thanks to Vitaliy Kukharik for trying this patches.

Due to the merge of the meson based build, this patch needs to be
adjusted. See
https://cirrus-ci.com/build/6637154947301376

The changes should be fairly simple, just mirroring the Makefile ones.

Greetings,

Andres Freund

Hi,

On 2022-09-22 08:19:09 -0700, Andres Freund wrote:

Hi,

On 2022-08-17 17:28:02 +0500, Andrey Borodin wrote:

Here's v13. Changes:
1. Fixed passing through downlink in GIN index
2. Fixed GIN tests (one test case was not working)

Thanks to Vitaliy Kukharik for trying this patches.

Due to the merge of the meson based build, this patch needs to be
adjusted. See
https://cirrus-ci.com/build/6637154947301376

The changes should be fairly simple, just mirroring the Makefile ones.

Here's an updated patch adding meson compat.

I didn't fix the following warnings:

[25/28 3 89%] Compiling C object contrib/amcheck/amcheck.dll.p/amcheck.c.obj
../../home/andres/src/postgresql/contrib/amcheck/amcheck.c: In function ‘amcheck_lock_relation_and_check’:
../../home/andres/src/postgresql/contrib/amcheck/amcheck.c:81:20: warning: implicit declaration of function ‘NewGUCNestLevel’ [-Wimplicit-function-declaration]
81 | save_nestlevel = NewGUCNestLevel();
| ^~~~~~~~~~~~~~~
../../home/andres/src/postgresql/contrib/amcheck/amcheck.c:124:2: warning: implicit declaration of function ‘AtEOXact_GUC’; did you mean ‘AtEOXact_SMgr’? [-Wimplicit-function-declaration]
124 | AtEOXact_GUC(false, save_nestlevel);
| ^~~~~~~~~~~~
| AtEOXact_SMgr
[26/28 2 92%] Compiling C object contrib/amcheck/amcheck.dll.p/verify_gin.c.obj
../../home/andres/src/postgresql/contrib/amcheck/verify_gin.c: In function ‘gin_check_parent_keys_consistency’:
../../home/andres/src/postgresql/contrib/amcheck/verify_gin.c:423:8: warning: unused variable ‘heapallindexed’ [-Wunused-variable]
423 | bool heapallindexed = *((bool*)callback_state);
| ^~~~~~~~~~~~~~
[28/28 1 100%] Linking target contrib/amcheck/amcheck.dll

Greetings,

Andres Freund

On Sun, Oct 2, 2022 at 12:12 AM Andres Freund <andres@anarazel.de> wrote:

Here's an updated patch adding meson compat.

Thank you, Andres! Here's one more rebase (something was adjusted in
amcheck build).
Also I've fixed new warnings except warning about absent
heapallindexed for GIN. It's a TODO.

Thanks!

Best regards, Andrey Borodin.

Hello.

I reviewed this patch and I would like to share some comments.

It compiled with those 2 warnings:

verify_gin.c: In function 'gin_check_parent_keys_consistency':
verify_gin.c:481:38: warning: declaration of 'maxoff' shadows a previous
local [-Wshadow=compatible-local]
481 | OffsetNumber maxoff =
PageGetMaxOffsetNumber(page);
| ^~~~~~
verify_gin.c:453:41: note: shadowed declaration is here
453 | maxoff;
| ^~~~~~
verify_gin.c:423:25: warning: unused variable 'heapallindexed'
[-Wunused-variable]
423 | bool heapallindexed = *((bool*)callback_state);
| ^~~~~~~~~~~~~~

Also, I'm not sure about postgres' headers conventions, inside amcheck.h,
there is "miscadmin.h" included, and inside verify_gin.c, verify_gist.h
and verify_nbtree.c both amcheck.h and miscadmin.h are included.

About the documentation, the bt_index_parent_check has comments about the
ShareLock and "SET client_min_messages = DEBUG1;", and both
gist_index_parent_check and gin_index_parent_check lack it. verify_gin
uses DEBUG3, I'm not sure if it is on purpose, but it would be nice to
document it or put DEBUG1 to be consistent.

I lack enough context to do a deep review on the code, so in this area
this patch needs more eyes.

I did the following test:

postgres=# create table teste (t text, tv tsvector);
CREATE TABLE
postgres=# insert into teste values ('hello', 'hello'::tsvector);
INSERT 0 1
postgres=# create index teste_tv on teste using gist(tv);
CREATE INDEX
postgres=# select pg_relation_filepath('teste_tv');
pg_relation_filepath
----------------------
base/5/16441
(1 row)

postgres=#
\q
$ bin/pg_ctl -D data -l log
waiting for server to shut down.... done
server stopped
$ okteta base/5/16441 # I couldn't figure out the dd syntax to change the
1FE9 to '0'
$ bin/pg_ctl -D data -l log
waiting for server to start.... done
server started
$ bin/psql -U ze postgres
psql (16devel)
Type "help" for help.

postgres=# SET client_min_messages = DEBUG3;
SET
postgres=# select gist_index_parent_check('teste_tv'::regclass, true);
DEBUG: verifying that tuples from index "teste_tv" are present in "teste"
ERROR: heap tuple (0,1) from table "teste" lacks matching index tuple
within index "teste_tv"
postgres=#

A simple index corruption in gin:

postgres=# CREATE TABLE "gin_check"("Column1" int[]);
CREATE TABLE
postgres=# insert into gin_check values (ARRAY[1]),(ARRAY[2]);
INSERT 0 2
postgres=# CREATE INDEX gin_check_idx on "gin_check" USING GIN("Column1");
CREATE INDEX
postgres=# select pg_relation_filepath('gin_check_idx');
pg_relation_filepath
----------------------
base/5/16453
(1 row)

postgres=#
\q
$ bin/pg_ctl -D data -l logfile stop
waiting for server to shut down.... done
server stopped
$ okteta data/base/5/16453 # edited some bits near 3FCC
$ bin/pg_ctl -D data -l logfile start
waiting for server to start.... done
server started
$ bin/psql -U ze postgres
psql (16devel)
Type "help" for help.

postgres=# SET client_min_messages = DEBUG3;
SET
postgres=# SELECT gin_index_parent_check('gin_check_idx', true);
ERROR: number of items mismatch in GIN entry tuple, 49 in tuple header, 1
decoded
postgres=#

There are more code paths to follow to check the entire code, and I had a
hard time to corrupt the indices. Is there any automated code to corrupt
index to test such code?

--
Jose Arthur Benetasso Villanova

Hello!

Thank you for the review!

On Thu, Nov 24, 2022 at 6:04 PM Jose Arthur Benetasso Villanova
<jose.arthur@gmail.com> wrote:

It compiled with those 2 warnings:

verify_gin.c: In function 'gin_check_parent_keys_consistency':
verify_gin.c:481:38: warning: declaration of 'maxoff' shadows a previous
local [-Wshadow=compatible-local]
481 | OffsetNumber maxoff =
PageGetMaxOffsetNumber(page);
| ^~~~~~
verify_gin.c:453:41: note: shadowed declaration is here
453 | maxoff;
| ^~~~~~
verify_gin.c:423:25: warning: unused variable 'heapallindexed'
[-Wunused-variable]

Fixed.

423 | bool heapallindexed = *((bool*)callback_state);
| ^~~~~~~~~~~~~~

This one is in progress yet, heapallindexed check is not implemented yet...

Also, I'm not sure about postgres' headers conventions, inside amcheck.h,
there is "miscadmin.h" included, and inside verify_gin.c, verify_gist.h
and verify_nbtree.c both amcheck.h and miscadmin.h are included.

Fixed.

About the documentation, the bt_index_parent_check has comments about the
ShareLock and "SET client_min_messages = DEBUG1;", and both
gist_index_parent_check and gin_index_parent_check lack it. verify_gin
uses DEBUG3, I'm not sure if it is on purpose, but it would be nice to
document it or put DEBUG1 to be consistent.

GiST and GIN verifications do not take ShareLock for parent checks.
B-tree check cannot verify cross-level invariants between levels when
the index is changing.

GiST verification checks only one invariant that can be verified if
page locks acquired the same way as page split does.
GIN does not require ShareLock because it does not check cross-level invariants.

Reporting progress with DEBUG1 is a good idea, I did not know that
this feature exists. I'll implement something similar in following
versions.

I did the following test:

Cool! Thank you!

There are more code paths to follow to check the entire code, and I had a
hard time to corrupt the indices. Is there any automated code to corrupt
index to test such code?

Heapam tests do this in an automated way, look into this file
t/001_verify_heapam.pl.
Surely we can write these tests. At least automate what you have just
done in the review. However, committing similar checks is a very
tedious work: something will inevitably turn buildfarm red as a
watermelon.

I hope I'll post a version with DEBUG1 reporting and heapallindexed soon.
PFA current state.
Thank you for looking into this!

Best regards, Andrey Borodin.

On Sun, Nov 27, 2022 at 1:29 PM Andrey Borodin <amborodin86@gmail.com> wrote:

GiST verification checks only one invariant that can be verified if
page locks acquired the same way as page split does.
GIN does not require ShareLock because it does not check cross-level invariants.

I was wrong. GIN check does similar gin_refind_parent() to lock pages
in bottom-up manner and truly verify downlink-child_page invariant.

Here's v17. The only difference is that I added progress reporting to
GiST verification.
I still did not implement heapallindexed for GIN. Existence of pending
lists makes this just too difficult for a weekend coding project :(

Thank you!

Best regards, Andrey Borodin.

On Sun, 27 Nov 2022, Andrey Borodin wrote:

On Sun, Nov 27, 2022 at 1:29 PM Andrey Borodin <amborodin86@gmail.com> wrote:

I was wrong. GIN check does similar gin_refind_parent() to lock pages
in bottom-up manner and truly verify downlink-child_page invariant.

Does this mean that we need the adjustment in docs?

Here's v17. The only difference is that I added progress reporting to
GiST verification.
I still did not implement heapallindexed for GIN. Existence of pending
lists makes this just too difficult for a weekend coding project :(

Thank you!

Best regards, Andrey Borodin.

I'm a bit lost here. I tried your patch again and indeed the
heapallindexed inside gin_check_parent_keys_consistency has a TODO
comment, but it's unclear to me if you are going to implement it or if the
patch "needs review". Right now it's "Waiting on Author".

--
Jose Arthur Benetasso Villanova

On Wed, Dec 14, 2022 at 7:19 AM Jose Arthur Benetasso Villanova
<jose.arthur@gmail.com> wrote:

I'm a bit lost here. I tried your patch again and indeed the
heapallindexed inside gin_check_parent_keys_consistency has a TODO
comment, but it's unclear to me if you are going to implement it or if the
patch "needs review". Right now it's "Waiting on Author".

FWIW, I don't think there's a hard requirement that every index AM
needs to support the same set of amcheck options. Where it makes sense
and can be done in a reasonably straightforward manner, we should. But
sometimes that may not be the case, and that seems fine, too.

--
Robert Haas
EDB: http://www.enterprisedb.com

Hi Jose, thank you for review and sorry for so long delay to answer.

On Wed, Dec 14, 2022 at 4:19 AM Jose Arthur Benetasso Villanova
<jose.arthur@gmail.com> wrote:

On Sun, 27 Nov 2022, Andrey Borodin wrote:

On Sun, Nov 27, 2022 at 1:29 PM Andrey Borodin <amborodin86@gmail.com> wrote:

I was wrong. GIN check does similar gin_refind_parent() to lock pages
in bottom-up manner and truly verify downlink-child_page invariant.

Does this mean that we need the adjustment in docs?

It seems to me that gin_index_parent_check() docs are correct.

Here's v17. The only difference is that I added progress reporting to
GiST verification.
I still did not implement heapallindexed for GIN. Existence of pending
lists makes this just too difficult for a weekend coding project :(

Thank you!

Best regards, Andrey Borodin.

I'm a bit lost here. I tried your patch again and indeed the
heapallindexed inside gin_check_parent_keys_consistency has a TODO
comment, but it's unclear to me if you are going to implement it or if the
patch "needs review". Right now it's "Waiting on Author".

Please find the attached new version. In this patchset heapallindexed
flag is removed from GIN checks.

Thank you!

Best regards, Andrey Borodin.

On Sun, Jan 8, 2023 at 8:05 PM Andrey Borodin <amborodin86@gmail.com> wrote:

Please find the attached new version. In this patchset heapallindexed
flag is removed from GIN checks.

Uh... sorry, git-formatted wrong branch.
Here's the correct version. Double checked.

Best regards, Andrey Borodin.

On Sun, 8 Jan 2023, Andrey Borodin wrote:

On Sun, Jan 8, 2023 at 8:05 PM Andrey Borodin <amborodin86@gmail.com> wrote:

Please find the attached new version. In this patchset heapallindexed
flag is removed from GIN checks.

Uh... sorry, git-formatted wrong branch.
Here's the correct version. Double checked.

Hello again.

I applied the patch without errors / warnings and did the same tests. All
working as expected.

The only thing that I found is the gin_index_parent_check function in docs
still references the "gin_index_parent_check(index regclass,
heapallindexed boolean) returns void"

--
Jose Arthur Benetasso Villanova

On Fri, Jan 13, 2023 at 3:46 AM Jose Arthur Benetasso Villanova
<jose.arthur@gmail.com> wrote:

The only thing that I found is the gin_index_parent_check function in docs
still references the "gin_index_parent_check(index regclass,
heapallindexed boolean) returns void"

Correct! Please find the attached fixed version.

Thank you!

Best regards, Andrey Borodin.

On Fri, 13 Jan 2023, Andrey Borodin wrote:

On Fri, Jan 13, 2023 at 3:46 AM Jose Arthur Benetasso Villanova
<jose.arthur@gmail.com> wrote:

The only thing that I found is the gin_index_parent_check function in docs
still references the "gin_index_parent_check(index regclass,
heapallindexed boolean) returns void"

Correct! Please find the attached fixed version.

Thank you!

Best regards, Andrey Borodin.

Hello again. I see the change. Thanks

--
Jose Arthur Benetasso Villanova