Thread: Amcheck verification of GiST and GIN

Hello world!

Few years ago we had a thread with $subj [0]. A year ago Heikki put a lot of effort in improving GIN checks [1] while
huntinga GIN bug. 
And in view of some releases with a recommendation to reindex anything that fails or lacks amcheck verification, I
decidedthat I want to review the thread. 

PFA $subj incorporating all Heikki's improvements and restored GiST checks. Also I've added heapallindexed verification
forGiST. I'm sure that we must add it for GIN too. Yet I do not know how to implement it. Maybe just check that every
entrygenerated from heap present in entry tree? Or that every tids is present in the index? 

GiST verification does parent check despite taking only AccessShareLock. It's possible because when the key discrepancy
isfound we acquire parent tuple with lock coupling. I'm sure that this is correct to check keys this way. And I'm
almostsure it will not deadlock, because split is doing the same locking. 

What do you think?

Best regards, Andrey Borodin.

[0] https://www.postgresql.org/message-id/flat/CAF3eApa07-BajjG8%2BRYx-Dr_cq28ZA0GsZmUQrGu5b2ayRhB5A%40mail.gmail.com
[1]
https://www.postgresql.org/message-id/flat/9fdbb584-1e10-6a55-ecc2-9ba8b5dca1cf%40iki.fi#fec2751faf1ca52495b0a61acc0f5532

> 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
enhancedcomments 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.

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
usefulfor 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

On Fri, Jan 13, 2023 at 7:35 PM Jose Arthur Benetasso Villanova
<jose.arthur@gmail.com> wrote:
>
> Hello again. I see the change. Thanks
>

Thanks! I also found out that there was a CI complaint about amcheck.h
not including some necessary stuff. Here's a version with a fix for
that.

Best regards, Andrey Borodin.

Hi Andrey,

> Thanks! I also found out that there was a CI complaint about amcheck.h
> not including some necessary stuff. Here's a version with a fix for
> that.

Thanks for the updated patchset.

One little nitpick I have is that the tests cover only cases when all
the checks pass successfully. The tests don't show that the checks
will fail if the indexes are corrupted. Usually we check this as well,
see bd807be6 and other amcheck replated patches and commits.

-- 
Best regards,
Aleksander Alekseev

On Fri, Jan 13, 2023 at 8:15 PM Andrey Borodin <amborodin86@gmail.com> wrote:
> (v21 of patch series)

I can see why the refactoring patch is necessary overall, but I have
some concerns about the details. More specifically:

* PageGetItemIdCareful() doesn't seem like it needs to be moved to
amcheck.c and generalized to work with GIN and GiST.

It seems better to just allow some redundancy, by having static/local
versions of PageGetItemIdCareful() for both GIN and GiST. There are
numerous reasons why that seems better to me. For one thing it's
simpler. For another, the requirements are already a bit different,
and may become more different in the future. I have seriously
considered adding a new PageGetItemCareful() routine to nbtree in the
past (which would work along similar lines when we access
IndexTuples), which would have to be quite different across each index
AM. Maybe this idea of adding a PageGetItemCareful() would totally
supersede the existing PageGetItemIdCareful() function.

But even now, without any of that, the rules for
PageGetItemIdCareful() are already different. For example, with GIN
you cannot have LP_DEAD bits set, so ISTM that you should be checking
for that in its own custom version of PageGetItemIdCareful().

You can just have comments that refer the reader to the original
nbtree version of PageGetItemIdCareful() for a high level overview.

* You have distinct versions of the current btree_index_checkable()
function for both GIN and GiST, which doesn't seem necessary to me --
so this is kind of the opposite of the situation with
PageGetItemIdCareful() IMV.

The only reason to have separate versions of these is to detect when
the wrong index AM is used -- the other 2 checks are 100% common to
all index AMs. Why not just move that one non-generic check out of the
function, to each respective index AM .c file, while keeping the other
2 generic checks in amcheck.c?

Once things are structured this way, it would then make sense to add a
can't-be-LP_DEAD check to the GIN specific version of
PageGetItemIdCareful().

I also have some questions about the verification functionality itself:

* Why haven't you done something like palloc_btree_page() for both
GiST and GIN, and use that for everything?

Obviously this may not be possible in100% of all cases -- even
verify_nbtree.c doesn't manage that. But I see no reason for that
here. Though, in general, it's not exactly clear what's going on with
buffer lock coupling in general.

* Why does gin_refind_parent() buffer lock the parent while the child
buffer lock remains held?

In any case this doesn't really need to have any buffer lock coupling.
Since you're both of the new verification functions you're adding are
"parent" variants, that acquire a ShareLock to block concurrent
modifications and concurrent VACUUM?

* Oh wait, they don't use a ShareLock at all -- they use an
AccessShareLock. This means that there are significant inconsistencies
with the verify_nbtree.c scheme.

I now realize that gist_index_parent_check() and
gin_index_parent_check() are actually much closer to bt_index_check()
than to bt_index_parent_check(). I think that you should stick with
the convention of using the word "parent" whenever we'll need a
ShareLock, and omitting "parent" whenever we will only require an
AccessShareLock. I'm not sure if that means that you should change the
lock strength or change the name of the functions. I am sure that you
should follow the general convention that we have already.

I feel rather pessimistic about our ability to get all the details
right with GIN. Frankly I have serious doubts that GIN itself gets
everything right, which makes our task just about impossible. The GIN
README did gain a "Concurrency" section in 2019, at my behest, but in
general the locking protocols are still chronically under-documented,
and have been revised in various ways as a response to bugs. So at
least in the case of GIN, we really need amcheck coverage, but should
take a very conservative approach.

With GIN I think that we need to make the most modest possible
assumptions about concurrency, by using a ShareLock. Without that, I
think that we can have very little confidence in the verification
checks -- the concurrency rules are just too complicated right now.
Maybe it will be possible in the future, but right now I'd rather not
try that. I find it very difficult to figure out the GIN locking
protocol, even for things that seem like they should be quite
straightforward. This situation would be totally unthinkable in
nbtree, and perhaps with GiST.

* Why does the GIN patch change a comment in contrib/amcheck/amcheck.c?

* There is no pg_amcheck patch here, but I think that there should be,
since that is now the preferred and recommended way to run amcheck in
general.

We could probably do something very similar to what is already there
for nbtree. Maybe it would make sense to change --heapallindexed and
--parent-check so that they call your parent check functions for GiST
and GIN -- though the locking/naming situation must be resolved before
we decide what to do here, for pg_amcheck.

-- 
Peter Geoghegan

On Thu, Feb 2, 2023 at 11:51 AM Peter Geoghegan <pg@bowt.ie> wrote:
> I also have some questions about the verification functionality itself:

I forgot to include another big concern here:

* Why are there only WARNINGs, never ERRORs here?

It's far more likely that you'll run into problems when running
amcheck this way. I understand that the heapam checks can do that, but
that is both more useful, and less risky. With heapam we're not
traversing a tree structure in logical/keyspace order. I'm not
claiming that this approach is impossible; just that it doesn't seem
even remotely worth it. Indexes are never supposed to be corrupt, but
if they are corrupt the solution always involves a REINDEX. You never
try to recover the data from an index, since it's redundant and less
authoritative, almost by definition (at least in Postgres).

By far the most important piece of information is that an index has
some non-zero amount of corruption. Any amount of corruption is
supposed to be extremely surprising. It's kind of like if you see one
cockroach in your home. The problem is not that you have one cockroach
in your home; the problem is that you simply have cockroaches. We can
all agree that in some abstract sense, fewer cockroaches is better.
But that doesn't seem to have any practical relevance -- it's a purely
theoretical point. It doesn't really affect what you do about the
problem at that point.

Admittedly there is some value in seeing multiple WARNINGs to true
experts that are performing some kind of forensic analysis, but that
doesn't seem worth it to me -- I'm an expert, and I don't think that
I'd do it this way for any reason other than it being more convenient
as a way to get information about a system that I don't have access
to. Even then, I think that I'd probably have serious doubts about
most of the extra information that I'd get, since it might very well
be a downstream consequence of the same basic problem.

-- 
Peter Geoghegan

On Thu, Feb 2, 2023 at 12:31 PM Nikolay Samokhvalov
<samokhvalov@gmail.com> wrote:
> I understand your thoughts (I think) and agree with them, but at least one
> scenario where I do want to see *all* errors is corruption prevention – running
> amcheck in lower environments, not in production, to predict and prevent issues.
> For example, not long ago, Ubuntu 16.04 became EOL (in phases), and people
> needed to upgrade, with glibc version change. It was quite good to use amcheck
> on production clones (running on a new OS/glibc) to identify all indexes that
> need to be rebuilt. Being able to see only one of them would be very
> inconvenient. Rebuilding all indexes didn't seem a good idea in the case of
> large databases.

I agree that this matters at the level of whole indexes. That is, if
you want to check every index in the database, it is unhelpful if the
whole process stops just because one individual index has corruption.
Any extra information about the index that is corrupt may not be all
that valuable, but information about other indexes remains almost as
valuable.

I think that that problem should be solved at a higher level, in the
program that runs amcheck. Note that pg_amcheck will already do this
for B-Tree indexes. While verify_nbtree.c won't try to limp on with an
index that is known to be corrupt, pg_amcheck will continue with other
indexes.

We should add a "Tip" to the amcheck documentation on 14+ about this.
We should clearly advise users that they should probably just use
pg_amcheck. Using the SQL interface directly should now mostly be
something that only a tiny minority of experts need to do -- and even
the experts won't do it that way unless they have a good reason to.

--
Peter Geoghegan

On Thu, Feb 2, 2023 at 12:56 PM Nikolay Samokhvalov
<samokhvalov@gmail.com> wrote:
> I already realized my mistake – indeed, having multiple errors for 1 index
> doesn't seem to be super practically helpful.

I wouldn't mind supporting it if the cost wasn't too high. But I
believe that it's not a good trade-off.

>> I think that that problem should be solved at a higher level, in the
>> program that runs amcheck. Note that pg_amcheck will already do this
>> for B-Tree indexes.
>
>
> That's a great tool, and it's great it supports parallelization, very useful
> on large machines.

Another big advantage of just using pg_amcheck is that running each
index verification in a standalone query avoids needlessly holding the
same MVCC snapshot across all indexes verified (compared to running
one big SQL query that verifies multiple indexes). As simple as
pg_amcheck's approach is (it's doing nothing that you couldn't
replicate in a shell script), in practice that its standardized
approach probably makes things a lot smoother, especially in terms of
how VACUUM is impacted.

--
Peter Geoghegan

On Thu, Feb 2, 2023 at 12:15 PM Peter Geoghegan <pg@bowt.ie> wrote:
> * Why are there only WARNINGs, never ERRORs here?

Attached revision v22 switches all of the WARNINGs over to ERRORs. It
has also been re-indented, and now uses a non-generic version of
PageGetItemIdCareful() in both verify_gin.c and verify_gist.c.
Obviously this isn't a big set of revisions, but I thought that Andrey
would appreciate it if I posted this much now. I haven't thought much
more about the locking stuff, which is my main concern for now.

Who are the authors of the patch, in full? At some point we'll need to
get the attribution right if this is going to be committed.

I think that it would be good to add some comments explaining the high
level control flow. Is the verification process driven by a
breadth-first search, or a depth-first search, or something else?

I think that we should focus on getting the GiST patch into shape for
commit first, since that seems easier.

-- 
Peter Geoghegan

Thank for working on this, Peter!

On Fri, Feb 3, 2023 at 6:50 PM Peter Geoghegan <pg@bowt.ie> wrote:
>
> I think that we should focus on getting the GiST patch into shape for
> commit first, since that seems easier.
>

Here's the next version. I've focused on GiST part in this revision.
Changes:
1. Refactored index_chackable so that is shared between all AMs.
2. Renamed gist_index_parent_check -> gist_index_check
3. Gathered reviewers (in no particular order). I hope I didn't forget
anyone. GIN patch is based on work by Grigory Kryachko, but
essentially rewritten by Heikki. Somewhat cosmetically whacked by me.
4. Extended comments for GistScanItem,
gist_check_parent_keys_consistency() and gist_refind_parent().

I tried adding support of GiST in pg_amcheck, but it is largely
assuming the relation is either heap or B-tree. I hope to do that part
tomorrow or in nearest future.

Here's the current version. Thank you!


Best regards, Andrey Borodin.

On Sat, Feb 4, 2023 at 1:37 PM Andrey Borodin <amborodin86@gmail.com> wrote:
>
> I tried adding support of GiST in pg_amcheck, but it is largely
> assuming the relation is either heap or B-tree. I hope to do that part
> tomorrow or in nearest future.
>

Here's v24 == (v23 + a step for pg_amcheck). There's a lot of
shotgun-style changes, but I hope next index types will be easy to add
now.

Adding Mark to cc, just in case.

Thanks!


Best regards, Andrey Borodin.

Hi,

On Thu, Feb 02, 2023 at 12:56:47PM -0800, Nikolay Samokhvalov wrote:
> On Thu, Feb 2, 2023 at 12:43 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > I think that that problem should be solved at a higher level, in the
> > program that runs amcheck. Note that pg_amcheck will already do this
> > for B-Tree indexes.
> 
> That's a great tool, and it's great it supports parallelization, very useful
> on large machines.

Right, but unfortunately not an option on managed services. It's clear
that this restriction should not be a general guideline for Postgres
development, but it makes the amcheck extension (that is now shipped
everywhere due to being in-code I believe) somewhat less useful for
use-case of checking your whole database for corruption.


Michael

On Sun, Feb 5, 2023 at 4:45 PM Andrey Borodin <amborodin86@gmail.com> wrote:
> Here's v24 == (v23 + a step for pg_amcheck). There's a lot of
> shotgun-style changes, but I hope next index types will be easy to add
> now.

Some feedback on the GiST patch:

* You forgot to initialize GistCheckState.heaptuplespresent to 0.

It might be better to allocate GistCheckState dynamically, using
palloc0(). That's future proof. "Simple and obvious" is usually the
most important goal for managing memory in amcheck code. It can be a
little inefficient if that makes it simpler.

* ISTM that gist_index_check() should allow the caller to omit a
"heapallindexed" argument by specifying "DEFAULT FALSE", for
consistency with bt_index_check().

(Actually there are two versions of bt_index_check(), with
overloading, but that's just because of the way that the extension
evolved over time).

* What's the point in having a custom memory context that is never reset?

I believe that gistgetadjusted() will leak memory here, so there is a
need for some kind of high level strategy for managing memory. The
strategy within verify_nbtree.c is to call MemoryContextReset() right
after every loop iteration within bt_check_level_from_leftmost() --
which is pretty much once every call to bt_target_page_check(). That
kind of approach is obviously not going to suffer any memory leaks.

Again, "simple and obvious" is good for memory management in amcheck.

* ISTM that it would be clearer if the per-page code within
gist_check_parent_keys_consistency() was broken out into its own
function -- a little like bt_target_page_check()..

That way the control flow would be easier to understand when looking
at the code at a high level.

* ISTM that gist_refind_parent() should throw an error about
corruption in the event of a parent page somehow becoming a leaf page.

Obviously this is never supposed to happen, and likely never will
happen, even with corruption. But it seems like a good idea to make
the most conservative possible assumption by throwing an error. If it
never happens anyway, then the fact that we handle it with an error
won't matter -- so the error is harmless. If it does happen then we'll
want to hear about it as soon as possible -- so the error is useful.

* I suggest using c99 style variable declarations in loops.

Especially for things like "for (OffsetNumber offset =
FirstOffsetNumber; ... ; ... )".

--
Peter Geoghegan

On Thu, Mar 16, 2023 at 4:48 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Some feedback on the GiST patch:

I see that the Bloom filter that's used to implement heapallindexed
verification fingerprints index tuples that are formed via calls to
gistFormTuple(), without any attempt to normalize-away differences in
TOAST input state. In other words, there is nothing like
verify_nbtree.c's bt_normalize_tuple() function involved in the
fingerprinting process. Why is that safe, though? See the "toast_bug"
test case within contrib/amcheck/sql/check_btree.sql for an example of
how inconsistent TOAST input state confused verify_nbtree.c's
heapallindexed verification (before bugfix commit eba775345d). I'm
concerned about GiST heapallindexed verification being buggy in
exactly the same way, or in some way that is roughly analogous.

I do have some concerns about there being analogous problems that are
unique to GiST, since GiST is an AM that gives opclass authors many
more choices than B-Tree opclass authors have. In particular, I wonder
if heapallindexed verification needs to account for how GiST
compression might end up breaking heapallindexed. I refer to the
"compression" implemented by GiST support routine 3 of GiST opclasses.
The existence of GiST support routine 7, the "same" routine, also
makes me feel a bit squeamish about heapallindexed verification -- the
existence of a "same" routine hints at some confusion about "equality
versus equivalence" issues.

In more general terms: heapallindexed verification works by
fingerprinting index tuples during the index verification stage, and
then performing Bloom filter probes in a separate CREATE INDEX style
heap-matches-index stage (obviously). There must be some justification
for our assumption that there can be no false positive corruption
reports due only to a GiST opclass (either extant or theoretical) that
follows the GiST contract, and yet allows an inconsistency to arise
that isn't really index corruption. This justification won't be easy
to come up with, since the GiST contract was not really designed with
these requirements in mind. But...we should try to come up with
something.

What are the assumptions underlying heapallindexed verification for
GiST? It doesn't have to be provably correct or anything, but it
should at least be empirically falsifiable. Basically, something that
says: "Here are our assumptions, if we were wrong in making these
assumptions then you could tell that we made a mistake because of X,
Y, Z". It's not always clear when something is corrupt. Admittedly I
have much less experience with GiST than other people, which likely
includes you (Andrey). I am likely missing some context around the
evolution of GiST. Possibly I'm making a big deal out of something
without it being unhelpful. Unsure.

Here is an example of the basic definition of correctness being
unclear, in a bad way: Is a HOT chain corrupt when its root
LP_REDIRECT points to an LP_DEAD item, or does that not count as
corruption? I'm pretty sure that the answer is ambiguous even today,
or was ambiguous until recently, at least. Hopefully the
verify_heapam.c HOT chain verification patch will be committed,
providing us with a clear *definition* of HOT chain corruption -- the
definition itself may not be the easy part.

On a totally unrelated note: I wonder if we should be checking that
internal page tuples have 0xffff as their offset number? Seems like
it'd be a cheap enough cross-check.

--
Peter Geoghegan

Hi Peter,

Thanks for the feedback! I'll work on it during the weekend.

On Thu, Mar 16, 2023 at 6:23 PM Peter Geoghegan <pg@bowt.ie> wrote:
>
> existence of a "same" routine hints at some confusion about "equality
> versus equivalence" issues.

Hmm...yes, actually, GiST deals with floats routinely. And there might
be some sorts of NaNs and Infs that are equal, but not binary
equivalent.
I'll think more about it.

gist_get_adjusted() calls "same" routine, which for type point will
use FPeq(double A, double B). And this might be kind of a corruption
out of the box. Because it's an epsilon-comparison, ε=1.0E-06.
GiST might miss newly inserted data, because the "adjusted" tuple was
"same" if data is in proximity of 0.000001 of any previously indexed
point, but out of known MBRs.
I'll try to reproduce this tomorrow, so far no luck.


Best regards, Andrey Borodin.

On Fri, Mar 17, 2023 at 8:40 PM Andrey Borodin <amborodin86@gmail.com> wrote:
>
> On Thu, Mar 16, 2023 at 6:23 PM Peter Geoghegan <pg@bowt.ie> wrote:
> >
> > existence of a "same" routine hints at some confusion about "equality
> > versus equivalence" issues.
>
> Hmm...yes, actually, GiST deals with floats routinely. And there might
> be some sorts of NaNs and Infs that are equal, but not binary
> equivalent.
> I'll think more about it.
>
> gist_get_adjusted() calls "same" routine, which for type point will
> use FPeq(double A, double B). And this might be kind of a corruption
> out of the box. Because it's an epsilon-comparison, ε=1.0E-06.
> GiST might miss newly inserted data, because the "adjusted" tuple was
> "same" if data is in proximity of 0.000001 of any previously indexed
> point, but out of known MBRs.
> I'll try to reproduce this tomorrow, so far no luck.
>
After several attempts to corrupt GiST with this 0.000001 epsilon
adjustment tolerance I think GiST indexing of points is valid.
Because intersection for search purposes is determined with the same epsilon!
So it's kind of odd
postgres=# select point(0.0000001,0)~=point(0,0);
?column?
----------
 t
(1 row)
, yet the index works correctly.



On Thu, Mar 16, 2023 at 4:48 PM Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Sun, Feb 5, 2023 at 4:45 PM Andrey Borodin <amborodin86@gmail.com> wrote:
> > Here's v24 == (v23 + a step for pg_amcheck). There's a lot of
> > shotgun-style changes, but I hope next index types will be easy to add
> > now.
>
> Some feedback on the GiST patch:
>
> * You forgot to initialize GistCheckState.heaptuplespresent to 0.
>
> It might be better to allocate GistCheckState dynamically, using
> palloc0(). That's future proof. "Simple and obvious" is usually the
> most important goal for managing memory in amcheck code. It can be a
> little inefficient if that makes it simpler.
Done.

> * ISTM that gist_index_check() should allow the caller to omit a
> "heapallindexed" argument by specifying "DEFAULT FALSE", for
> consistency with bt_index_check().
Done.

> * What's the point in having a custom memory context that is never reset?
The problem is we traverse index with depth-first scan and must retain
internal tuples for a whole time of the scan.
And gistgetadjusted() will allocate memory only in case of suspicion
of corruption. So, it's kind of an infrequent case.

The context is there only as an overall leak protection mechanism.
Actual memory management is done via pfree() calls.

> Again, "simple and obvious" is good for memory management in amcheck.
Yes, that would be great to come up with some "unit of work" contexts.
Yet, now palloced tuples and scan items have very different lifespans.


> * ISTM that it would be clearer if the per-page code within
> gist_check_parent_keys_consistency() was broken out into its own
> function -- a little like bt_target_page_check()..

I've refactored page logic into gist_check_page().

> * ISTM that gist_refind_parent() should throw an error about
> corruption in the event of a parent page somehow becoming a leaf page.
Done.

> * I suggest using c99 style variable declarations in loops.
Done.


On Thu, Mar 16, 2023 at 6:23 PM Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Thu, Mar 16, 2023 at 4:48 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > Some feedback on the GiST patch:
>
> I see that the Bloom filter that's used to implement heapallindexed
> verification fingerprints index tuples that are formed via calls to
> gistFormTuple(), without any attempt to normalize-away differences in
> TOAST input state. In other words, there is nothing like
> verify_nbtree.c's bt_normalize_tuple() function involved in the
> fingerprinting process. Why is that safe, though? See the "toast_bug"
> test case within contrib/amcheck/sql/check_btree.sql for an example of
> how inconsistent TOAST input state confused verify_nbtree.c's
> heapallindexed verification (before bugfix commit eba775345d). I'm
> concerned about GiST heapallindexed verification being buggy in
> exactly the same way, or in some way that is roughly analogous.
FWIW contrib opclasses, AFAIK, always detoast possibly long datums,
see gbt_var_compress()
https://github.com/postgres/postgres/blob/master/contrib/btree_gist/btree_utils_var.c#L281
But there might be opclasses that do not do so...
Also, there are INCLUDEd attributes. Right now we just put them as-is
to the bloom filter. Does this constitute a TOAST bug as in B-tree?
If so, I think we should use a version of tuple formatting that omits
included attributes...
What do you think?

>
> I do have some concerns about there being analogous problems that are
> unique to GiST, since GiST is an AM that gives opclass authors many
> more choices than B-Tree opclass authors have. In particular, I wonder
> if heapallindexed verification needs to account for how GiST
> compression might end up breaking heapallindexed. I refer to the
> "compression" implemented by GiST support routine 3 of GiST opclasses.
> The existence of GiST support routine 7, the "same" routine, also
> makes me feel a bit squeamish about heapallindexed verification -- the
> existence of a "same" routine hints at some confusion about "equality
> versus equivalence" issues.
>
> In more general terms: heapallindexed verification works by
> fingerprinting index tuples during the index verification stage, and
> then performing Bloom filter probes in a separate CREATE INDEX style
> heap-matches-index stage (obviously). There must be some justification
> for our assumption that there can be no false positive corruption
> reports due only to a GiST opclass (either extant or theoretical) that
> follows the GiST contract, and yet allows an inconsistency to arise
> that isn't really index corruption. This justification won't be easy
> to come up with, since the GiST contract was not really designed with
> these requirements in mind. But...we should try to come up with
> something.
>
> What are the assumptions underlying heapallindexed verification for
> GiST? It doesn't have to be provably correct or anything, but it
> should at least be empirically falsifiable. Basically, something that
> says: "Here are our assumptions, if we were wrong in making these
> assumptions then you could tell that we made a mistake because of X,
> Y, Z". It's not always clear when something is corrupt. Admittedly I
> have much less experience with GiST than other people, which likely
> includes you (Andrey). I am likely missing some context around the
> evolution of GiST. Possibly I'm making a big deal out of something
> without it being unhelpful. Unsure.
>
> Here is an example of the basic definition of correctness being
> unclear, in a bad way: Is a HOT chain corrupt when its root
> LP_REDIRECT points to an LP_DEAD item, or does that not count as
> corruption? I'm pretty sure that the answer is ambiguous even today,
> or was ambiguous until recently, at least. Hopefully the
> verify_heapam.c HOT chain verification patch will be committed,
> providing us with a clear *definition* of HOT chain corruption -- the
> definition itself may not be the easy part.

Rules for compression methods are not described anyware. And I suspect
that it's intentional, to provide more flexibility.
To make heapallindexed check work we need that opclass always returns
the same compression result for the same input datum.
All known to me opclasses (built-in and PostGIS) comply with this requirement.

Yet another behavior might be reasonable. Consider we have a
compression which learns on data. It will observe that some datums are
more frequent and start using shorter version of them.

Compression function actually is not about compression, but kind of a
conversion from heap format to indexable. Many opclasses do not have a
compression function at all.
We can require that the checked opclass would not have a compression
function at all. But GiST is mainly used for PostGIS, and in PostGIS
they use compression to convert complex geometry into a bounding box.

Method "same" is used only for a business of internal tuples, but not
for leaf tuples that we fingerprint in the bloom filter.

We can put requirements for heapallindexed in another way: "the
opclass compression method must be a pure function". It's also a very
strict requirement, disallowing all kinds of detoasting, dictionary
compression etc. And btree_gist opclasses does not comply :) But they
seem to me safe for heapallindexed.

> On a totally unrelated note: I wonder if we should be checking that
> internal page tuples have 0xffff as their offset number? Seems like
> it'd be a cheap enough cross-check.
>

Done.

Thank you!

Best regards, Andrey Borodin.

On Sun, Mar 19, 2023 at 4:00 PM Andrey Borodin <amborodin86@gmail.com> wrote:
>
> Also, there are INCLUDEd attributes. Right now we just put them as-is
> to the bloom filter. Does this constitute a TOAST bug as in B-tree?
> If so, I think we should use a version of tuple formatting that omits
> included attributes...
> What do you think?
I've ported the B-tree TOAST test to GiST, and, as expected, it fails.
Finds non-indexed tuple for a fresh valid index.
I've implemented normalization, plz see gistFormNormalizedTuple().
But there are two problems:
1. I could not come up with a proper way to pfree() compressed value
after decompressing. See TODO in gistFormNormalizedTuple().
2. In the index tuples seem to be normalized somewhere. They do not
have to be deformed and normalized. It's not clear to me how this
happened.

Thanks!

Best regards, Andrey Borodin.

On Sun, Mar 19, 2023 at 4:00 PM Andrey Borodin <amborodin86@gmail.com> wrote:
> After several attempts to corrupt GiST with this 0.000001 epsilon
> adjustment tolerance I think GiST indexing of points is valid.
> Because intersection for search purposes is determined with the same epsilon!
> So it's kind of odd
> postgres=# select point(0.0000001,0)~=point(0,0);
> ?column?
> ----------
>  t
> (1 row)
> , yet the index works correctly.

I think that it's okay, provided that we can assume deterministic
behavior in the code that forms new index tuples. Within nbtree,
operator classes like numeric_ops are supported by heapallindexed
verification, without any requirement for special normalization code
to make it work correctly as a special case. This is true even though
operator classes such as numeric_ops have similar "equality is not
equivalence" issues, which comes up in other areas (e.g., nbtree
deduplication, which must call support routine 4 during a CREATE INDEX
[1]).

The important principle is that amcheck must always be able to produce
a consistent fingerprintable binary output given the same input (the
same heap tuple/Datum array). This must work across all operator
classes that play by the rules for GiST operator classes. We *can*
tolerate some variation here. Well, we really *have* to tolerate a
little of this kind of variation in order to deal with the TOAST input
state thing...but I hope that that's the only complicating factor
here, for GiST (as it is for nbtree). Note that we already rely on the
fact that index_form_tuple() uses palloc0() (not plain palloc) in
verify_nbtree.c, for the obvious reason.

I think that there is a decent chance that it just wouldn't make sense
for an operator class author to ever do something that we need to
worry about. I'm pretty sure that it's just the TOAST thing. But it's
worth thinking about carefully.

[1] https://www.postgresql.org/docs/devel/btree-support-funcs.html
--
Peter Geoghegan

Hi Andrey,

27.03.2023 01:17, Andrey Borodin wrote:
> I've ported the B-tree TOAST test to GiST, and, as expected, it fails.
> Finds non-indexed tuple for a fresh valid index.

I've tried to use this feature with the latest patch set and discovered that
modified pg_amcheck doesn't find any gist indexes when running without a
schema specification. For example:
CREATE TABLE tbl (id integer, p point);
INSERT INTO tbl VALUES (1, point(1, 1));
CREATE INDEX gist_tbl_idx ON tbl USING gist (p);
CREATE INDEX btree_tbl_idx ON tbl USING btree (id);

pg_amcheck -v -s public
prints:
pg_amcheck: checking index "regression.public.btree_tbl_idx"
pg_amcheck: checking heap table "regression.public.tbl"
pg_amcheck: checking index "regression.public.gist_tbl_idx"

but without "-s public" a message about checking of gist_tbl_idx is absent.

As I can see in the server.log, the queries, that generate relation lists in
these cases, differ in:
... AND ep.pattern_id IS NULL AND c.relam = 2 AND c.relkind IN ('r', 'S', 'm', 't') AND c.relnamespace != 99 ...

... AND ep.pattern_id IS NULL AND c.relam IN (2, 403, 783)AND c.relkind IN ('r', 'S', 'm', 't', 'i') AND ((c.relam = 2

AND c.relkind IN ('r', 'S', 'm', 't')) OR ((c.relam = 403 OR c.relam = 783) AND c.relkind = 'i')) ...

Best regards,
Alexander

On Mon, 27 Mar 2023 at 03:47, Andrey Borodin <amborodin86@gmail.com> wrote:
>
> On Sun, Mar 19, 2023 at 4:00 PM Andrey Borodin <amborodin86@gmail.com> wrote:
> >
> > Also, there are INCLUDEd attributes. Right now we just put them as-is
> > to the bloom filter. Does this constitute a TOAST bug as in B-tree?
> > If so, I think we should use a version of tuple formatting that omits
> > included attributes...
> > What do you think?
> I've ported the B-tree TOAST test to GiST, and, as expected, it fails.
> Finds non-indexed tuple for a fresh valid index.
> I've implemented normalization, plz see gistFormNormalizedTuple().
> But there are two problems:
> 1. I could not come up with a proper way to pfree() compressed value
> after decompressing. See TODO in gistFormNormalizedTuple().
> 2. In the index tuples seem to be normalized somewhere. They do not
> have to be deformed and normalized. It's not clear to me how this
> happened.

I have changed the status of the commitfest entry to "Waiting on
Author" as there was no follow-up on Alexander's queries. Feel free to
address them and change the commitfest entry accordingly.

Regards,
Vignesh

> On 20 Jan 2024, at 07:46, vignesh C <vignesh21@gmail.com> wrote:
>
> I have changed the status of the commitfest entry to "Waiting on
> Author" as there was no follow-up on Alexander's queries. Feel free to
> address them and change the commitfest entry accordingly.

Thanks Vignesh!

At the moment it’s obvious that this change will not be in 17, but I have plans to continue work on this. So I’ll move
thisitem to July CF. 


Best regards, Andrey Borodin.

> On 6 Apr 2023, at 09:00, Alexander Lakhin <exclusion@gmail.com> wrote:
>
> I've tried to use this feature with the latest patch set and discovered that
> modified pg_amcheck doesn't find any gist indexes when running without a
> schema specification.

Thanks, Alexander! I’ve fixed this problem and rebased on current HEAD.
There’s one more problem in pg_amcheck’s GiST verification. We must check that amcheck is 1.5+ and use GiST
verificationonly in that case… 


Best regards, Andrey Borodin.

> On 5 Jul 2024, at 17:27, Andrey M. Borodin <x4mmm@yandex-team.ru> wrote:
>
> There’s one more problem in pg_amcheck’s GiST verification. We must check that amcheck is 1.5+ and use GiST
verificationonly in that case… 

Done. I’ll set the status to “Needs review”.


Best regards, Andrey Borodin.

Hi,

On 7/9/24 08:36, Andrey M. Borodin wrote:
> 
> 
>> On 5 Jul 2024, at 17:27, Andrey M. Borodin <x4mmm@yandex-team.ru> wrote:
>>
>> There’s one more problem in pg_amcheck’s GiST verification. We must
>> check that amcheck is 1.5+ and use GiST verification only in that
>> case …
> 
> Done. I’ll set the status to “Needs review”.
> 

I realized amcheck GIN/GiST support would be useful for testing my
patches adding parallel builds for these index types, so I decided to
take a look at this and do an initial review today.

Attached is a patch series with a extra commits to keep the review
comments and patches adjusting the formatting by pgindent (the patch
seems far enough for this).

Let me quickly go through the review comments:

1) Not sure I like 'amcheck.c' very much, I'd probably go with something
like 'verify_common.c' to match naming of the other files. But it's just
nitpicking and I can live with it.

2) amcheck_lock_relation_and_check seems to be the most important
function, yet there's no comment explaining what it does :-(

3) amcheck_lock_relation_and_check still has a TODO to add the correct
name of the AM

4) Do we actually need amcheck_index_mainfork_expected as a separate
function, or could it be a part of index_checkable?

5) The comment for heaptuplespresent says "debug counter" but that does
not really explain what it's for. (I see verify_nbtree has the same
comment, but maybe let's improve that.)

6) I'd suggest moving the GISTSTATE + blocknum fields to the beginning
of GistCheckState, it seems more natural to start with "generic" fields.

7) I'd adjust the gist_check_parent_keys_consistency comment a bit, to
explain what the function does first, and only then explain how.

8) We seem to be copying PageGetItemIdCareful() around, right? And the
copy in _gist.c still references nbtree - I guess that's not right.

9) Why is the GIN function called gin_index_parent_check() and not
simply gin_index_check() as for the other AMs?

10) The debug in gin_check_posting_tree_parent_keys_consistency triggers
assert when running with client_min_messages='debug5', it seems to be
accessing bogus item pointers.

11) Why does it add pg_amcheck support only for GiST and not GIN?


That's all for now. I'll add this to the stress-testing tests of my
index build patches, and if that triggers more issues I'll report those.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 7/10/24 18:01, Tomas Vondra wrote:
> ...
>
> That's all for now. I'll add this to the stress-testing tests of my
> index build patches, and if that triggers more issues I'll report those.
> 

As mentioned a couple days ago, I started using this patch to validate
the patches adding parallel builds to GIN and GiST indexes - I scripts
to stress-test the builds, and I added the new amcheck functions as
another validation step.

For GIN indexes it didn't find anything new (in either this or my
patches), aside from the assert crash I already reported.

But for GiST it turned out to be very valuable - it did actually find an
issue in my patches, or rather confirm my hypothesis that the way the
patch generates fake LSN may not be quite right.

In particular, I've observed these two issues:

  ERROR:  heap tuple (13315,38) from table "planet_osm_roads" lacks
          matching index tuple within index "roads_7_1_idx"

  ERROR:  index "roads_7_7_idx" has inconsistent records on page 23723
          offset 113

And those consistency issues are real - I've managed to reproduce issues
with incorrect query results (by comparing the results to an index built
without parallelism).

So that's nice - it shows the value of this patch, and I like it.

One thing I've been wondering about is that currently amcheck (in
general, not just these new GIN/GiST functions) errors out on the first
issue, because it does ereport(ERROR). Which is good enough to decide if
there is some corruption, but a bit inconvenient if you need to assess
how much corruption is there. For example when investigating the issue
in my patch it would have been great to know if there's just one broken
page, or if there are dozens/hundreds/thousands of them.

I'd imagine we could have a flag which says whether to fail on the first
issue, or keep looking at future pages. Essentially, whether to do
ereport(ERROR) or ereport(WARNING). But maybe that's a dead-end, and
once we find the first issue it's futile to inspect the rest of the
index, because it can be garbage. Not sure. In any case, it's not up to
this patch to invent that.

I don't have additional comments, the patch seems to be clean and likely
ready to go. There's a couple committers already involved in this
thread, I wonder if one of them already planned to take care of this?
Peter and Andres, either of you interested in this?

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

OK, one mere comment - it seems the 0001 patch has incorrect indentation
in bt_index_check_callback, triggering this:

----------------------------------------------------------------------
verify_nbtree.c: In function ‘bt_index_check_callback’:
verify_nbtree.c:331:25: warning: this ‘if’ clause does not guard...
[-Wmisleading-indentation]
  331 |                         if (indrel->rd_opfamily[i] ==
INTERVAL_BTREE_FAM_OID)
      |                         ^~
In file included from ../../src/include/postgres.h:46,
                 from verify_nbtree.c:24:
../../src/include/utils/elog.h:142:9: note: ...this statement, but the
latter is misleadingly indented as if it were guarded by the ‘if’
  142 |         do { \
      |         ^~
../../src/include/utils/elog.h:164:9: note: in expansion of macro
‘ereport_domain’
  164 |         ereport_domain(elevel, TEXTDOMAIN, __VA_ARGS__)
      |         ^~~~~~~~~~~~~~
verify_nbtree.c:333:33: note: in expansion of macro ‘ereport’
  333 |                                 ereport(ERROR,
      |                                 ^~~~~~~
----------------------------------------------------------------------

This seems to be because the ereport() happens to be indented as if it
was in the "if", but should have been at the "for" level.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

OK, one more issue report. I originally thought it's a bug in my patch
adding parallel builds for GIN indexes, but it turns out it happens even
with serial builds on master ...

If I build any GIN index, and then do gin_index_parent_check() on it, I
get this error:

create index jsonb_hash on messages using gin (msg_headers jsonb_path_ops);

select gin_index_parent_check('jsonb_hash');
ERROR:  index "jsonb_hash" has wrong tuple order, block 43932, offset 328

I did try investigating usinng pageinspect - the page seems to be the
right-most in the tree, judging by rightlink = InvalidBlockNumber:

test=# select gin_page_opaque_info(get_raw_page('jsonb_hash', 43932));
 gin_page_opaque_info
----------------------
 (4294967295,0,{})
(1 row)

But gin_leafpage_items() apparently only works with compressed leaf
pages, so I'm not sure what's in the page. In any case, the index seems
to be working fine, so it seems like a bug in this patch.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hi Tomas!

Thank you so much for your interest in the patchset.

> On 10 Jul 2024, at 19:01, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:
>
> I realized amcheck GIN/GiST support would be useful for testing my
> patches adding parallel builds for these index types, so I decided to
> take a look at this and do an initial review today.

Great! Thank you!

> Attached is a patch series with a extra commits to keep the review
> comments and patches adjusting the formatting by pgindent (the patch
> seems far enough for this).

I was hoping to address your review comments this weekend, but unfortunately I could not. I'll do this ASAP, but at
leastI decided to post answers on questions. 

>
> Let me quickly go through the review comments:
>
> 1) Not sure I like 'amcheck.c' very much, I'd probably go with something
> like 'verify_common.c' to match naming of the other files. But it's just
> nitpicking and I can live with it.

Any name works for me. We have tens of files ending with "common.c", so I think that's a good way to go.

> 2) amcheck_lock_relation_and_check seems to be the most important
> function, yet there's no comment explaining what it does :-(

Makes sense.

> 3) amcheck_lock_relation_and_check still has a TODO to add the correct
> name of the AM

Yes, I've discovered it during rebase and added TODO.

> 4) Do we actually need amcheck_index_mainfork_expected as a separate
> function, or could it be a part of index_checkable?

It was separate function before refactoring...

> 5) The comment for heaptuplespresent says "debug counter" but that does
> not really explain what it's for. (I see verify_nbtree has the same
> comment, but maybe let's improve that.)

It's there for a DEBUG1 message
ereport(DEBUG1,
                (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset
%.2f%%set", 
But the message is gone for GiST. Perhaps, let's restore this message?

>
> 6) I'd suggest moving the GISTSTATE + blocknum fields to the beginning
> of GistCheckState, it seems more natural to start with "generic" fields.

Makes sense.

> 7) I'd adjust the gist_check_parent_keys_consistency comment a bit, to
> explain what the function does first, and only then explain how.

Makes sense.

> 8) We seem to be copying PageGetItemIdCareful() around, right? And the
> copy in _gist.c still references nbtree - I guess that's not right.

Version differ in two aspects:
1. Size of opaque data may be different. But we can pass it as a parameter.
2. GIN's line pointer verification is slightly more strict.

>
> 9) Why is the GIN function called gin_index_parent_check() and not
> simply gin_index_check() as for the other AMs?

AFAIR function should be called _parent_ if it takes ShareLock. gin_index_parent_check() does not, so I think we should
renameit. 

> 10) The debug in gin_check_posting_tree_parent_keys_consistency triggers
> assert when running with client_min_messages='debug5', it seems to be
> accessing bogus item pointers.
>
> 11) Why does it add pg_amcheck support only for GiST and not GIN?

GiST part is by far more polished. When we were discussing current implementation with Peter G, we decided that we
couldfinish work on GiST, and then proceed to GIN. Main concern is about GIN's locking model. 




> On 12 Jul 2024, at 15:16, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:
>
> On 7/10/24 18:01, Tomas Vondra wrote:
>> ...
>>
>> That's all for now. I'll add this to the stress-testing tests of my
>> index build patches, and if that triggers more issues I'll report those.
>>
>
> As mentioned a couple days ago, I started using this patch to validate
> the patches adding parallel builds to GIN and GiST indexes - I scripts
> to stress-test the builds, and I added the new amcheck functions as
> another validation step.
>
> For GIN indexes it didn't find anything new (in either this or my
> patches), aside from the assert crash I already reported.
>
> But for GiST it turned out to be very valuable - it did actually find an
> issue in my patches, or rather confirm my hypothesis that the way the
> patch generates fake LSN may not be quite right.
>
> In particular, I've observed these two issues:
>
>  ERROR:  heap tuple (13315,38) from table "planet_osm_roads" lacks
>          matching index tuple within index "roads_7_1_idx"
>
>  ERROR:  index "roads_7_7_idx" has inconsistent records on page 23723
>          offset 113
>
> And those consistency issues are real - I've managed to reproduce issues
> with incorrect query results (by comparing the results to an index built
> without parallelism).
>
> So that's nice - it shows the value of this patch, and I like it.

That's great!

> One thing I've been wondering about is that currently amcheck (in
> general, not just these new GIN/GiST functions) errors out on the first
> issue, because it does ereport(ERROR). Which is good enough to decide if
> there is some corruption, but a bit inconvenient if you need to assess
> how much corruption is there. For example when investigating the issue
> in my patch it would have been great to know if there's just one broken
> page, or if there are dozens/hundreds/thousands of them.
>
> I'd imagine we could have a flag which says whether to fail on the first
> issue, or keep looking at future pages. Essentially, whether to do
> ereport(ERROR) or ereport(WARNING). But maybe that's a dead-end, and
> once we find the first issue it's futile to inspect the rest of the
> index, because it can be garbage. Not sure. In any case, it's not up to
> this patch to invent that.

The thing is amcheck tries hard to to do a core dump. It's still possible to crash it with garbage. But if we continue
checkafter encountering first corruption - increase in SegFaults is inevitable. 


Thank you! I hope I can get back to code ASAP.


Best regards, Andrey Borodin.

Hi,

I've spent a bit more time looking at the GiST part as part of my
"parallel GiST build" patch nearby, and I think there's some sort of
memory leak.

Consider this:

  create table t (a text);

  insert into t select md5(i::text)
    from generate_series(1,25000000) s(i);

  create index on t using gist (a gist_trgm_ops);

  select gist_index_check('t_a_idx', true);

This creates a ~4GB GiST trigram index, and then checks it. But that
gets killed, because of OOM killer. On my test machine it consumes
~6.5GB of memory before OOM intervenes.

The memory context stats look like this:

  TopPortalContext: 8192 total in 1 blocks; 7680 free (0 chunks); 512 used
    PortalContext: 1024 total in 1 blocks; 616 free (0 chunks); 408
used: <unnamed>
      ExecutorState: 8192 total in 1 blocks; 4024 free (4 chunks); 4168 used
        printtup: 8192 total in 1 blocks; 7952 free (0 chunks); 240 used
        ExprContext: 8192 total in 1 blocks; 7224 free (10 chunks); 968 used
          amcheck context: 3128950872 total in 376 blocks; 219392 free
(1044 chunks); 3128731480 used
            ExecutorState: 8192 total in 1 blocks; 7200 free (0 chunks);
992 used
              ExprContext: 8192 total in 1 blocks; 7952 free (0 chunks);
240 used
            GiST scan context: 22248 total in 2 blocks; 7808 free (8
chunks); 14440 used

This is from before the OOM kill, but it shows there's ~3GB of memory is
the amcheck context.

Seems like a memory leak to me - I didn't look at which place leaks.



regards

-- 
Tomas Vondra