Re: Fix GIN pending cleanup race

Hi Kirill!

> I was reviewing [0] and benchmarking/checking the correctness of GIN
> indexes and did find something that is a server bug in master (and
> affects all versions 8.4+). The bug is racy and doesn't hit in a
> single session run.
>
> A repro would be this data
>
>
> CREATE EXTENSION injection_points;
> CREATE TABLE w(id int, d tsvector);
> CREATE INDEX w_gin ON w USING gin(d) WITH (fastupdate=on);
> INSERT INTO w SELECT g, to_tsvector('simple','common x')
> FROM generate_series(1,1) g; -- ok
> INSERT INTO w SELECT g, to_tsvector('simple','common updated')
> FROM generate_series(2,2) g; -- not ok
>
> and this query
>
> SELECT count(*) FROM w WHERE d @@ 'common & !updated'::tsquery;
> -- racy result: 2
> -- seqscan: 1
>
> Shortly, rootcause is lack of rechecking main tree index entries for
> recently-transferred-entries from fastupdate list.

It's surprising that hasn't been reported earlier. I'm assuming that's
because it's tsvector specific; or at least it cannot happen with
pg_trgm. I'm not sure about other operator classes.
> So, a GIN index with fast update list transfers entries from pending
> list to main tree deliberately without holding any lock, see this code
> listing at ginfast.c:
>
> /*
> * Moving collected data into regular structure can take
> * significant amount of time - so, run it without locking pending
> * list.
> */
> ginBeginBAScan(&accum);
> while ((list = ginGetBAEntry(&accum, &attnum, &key, &category, &nlist)) != NULL)
> {
> ginEntryInsert(ginstate, attnum, key, category, list, nlist, NULL);
> vacuum_delay_point(false);
> }

Locking the pending list during flush would be another way to fix it,
would it? But then all readers would be blocked for the duration of the
flush.

> So, for some rows, it can happen that some entries for this row are
> already in the main GIN index while some are not. In the example,
> imagine that cleanup insert the key 'common' but not yet 'updated'.
> keyGetItem() passes entryRes['updated'] = GIN_FALSE ("certainly
> absent") to the
> consistent function, which after negation makes the query true and
> passese without a recheck.
> So, index scan returns the wrong row.

Now it seems obvious but it's somewhat tricky, especially because it
cannot happen with pg_trgm.
> So, to fix this, I can see two alternatives. First one is to somehow
> force tsvector opclass to set a recheck flag for such cases. But
> opclass know little about GIN internals so looks like this would
> force to recheck query almost every time, so performance regression.

Agreed. We shouldn't hardwire GIN index internals into the opclass.

> 0001 attached takes different approach: we remember all
> possibly-in-doubt keys in sorted array (during pending list
> traversal), dedup this and force recheck for them in main tree
> traversal.

- The number of seen rows is bounded by the size of the pending list.
Why not use that as maximum?
- Why use a sorted list and binary search instead of a simplehash.h hash
map? Hashing should be much cheaper.
- Why do you enable rechecking for seen rows instead of just skipping
them when reading the main index? They should have been processed
already.
- Could we alternatively mark rows that are not transferred fully yet as
incomplete in the main index to save the seen array?
- The seen check is performed for any operator class, regardless of if
it can cause that problem or not. Ideally, we only do the check for
specific operator classes. We could provide means for the operator
class to inform the GIN index if it should do the check or not. But
we can also first look at the overhead. Maybe it's low enough to not
matter.

--
David Geier