Fix GIN pending cleanup race

Hi!
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.

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);
}

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.

The following deterministic repro uses 0002 from attached

reshke=# SELECT count(*) FROM w WHERE d @@ 'common & !updated'::tsquery;
count
-------
1
(1 row)

reshke=#
-- session 2 (the cleaner, pauses before each key insert):
SELECT injection_points_attach('gin-pending-cleanup-key','wait');
SELECT gin_clean_pending_list('w_gin');
injection_points_attach
-------------------------

(1 row)

reshke=#
-- session 1: let the wave insert just the first key ('common'):
SELECT injection_points_wakeup('gin-pending-cleanup-key');
injection_points_wakeup
-------------------------

(1 row)

reshke=# SELECT count(*) FROM w WHERE d @@ 'common & !updated'::tsquery;
count
-------
2
(1 row)

reshke=# explain SELECT count(*) FROM w WHERE d @@ 'common &
!updated'::tsquery;
QUERY PLAN
---------------------------------------------------------------------------
Aggregate (cost=26.75..26.76 rows=1 width=8)
-> Bitmap Heap Scan on w (cost=17.26..26.73 rows=6 width=0)
Recheck Cond: (d @@ '''common'' & !''updated'''::tsquery)
-> Bitmap Index Scan on w_gin (cost=0.00..17.26 rows=6 width=0)
Index Cond: (d @@ '''common'' & !''updated'''::tsquery)
(5 rows)

With use of [1] patches for GIN pageinspect we can see

reshke=# select * from gin_entrypage_items(get_raw_page('w_gin', 1),
'w_gin'::regclass);
itemoffset | downlink | tids | keys
------------+----------------+-------------------+----------
1 | (2147483664,2) | {"(0,1)","(0,2)"} | d=common
(1 row)

after one more injection_points_wakeup('gin-pending-cleanup-key'):

reshke=# select * from gin_entrypage_items(get_raw_page('w_gin', 1),
'w_gin'::regclass);
itemoffset | downlink | tids | keys
------------+----------------+-------------------+-----------
1 | (2147483664,2) | {"(0,1)","(0,2)"} | d=common
2 | (2147483664,1) | {"(0,2)"} | d=updated
(2 rows)

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

[0] https://www.postgresql.org/message-id/5d366878-2007-4d31-861e-19294b7a583b%40gmail.com
[1] https://www.postgresql.org/message-id/SY7PR01MB10921891275CC615D3282326EB6B72@SY7PR01MB10921.ausprd01.prod.outlook.com

--
Best regards,
Kirill Reshke