Skip to content

Commit 24558da

Browse files
tglsfdctglsfdc
committed
Phase 2 of project to make index operator lossiness be determined at runtime
instead of plan time. Extend the amgettuple API so that the index AM returns a boolean indicating whether the indexquals need to be rechecked, and make that rechecking happen in nodeIndexscan.c (currently the only place where it's expected to be needed; other callers of index_getnext are just erroring out for now). For the moment, GIN and GIST have stub logic that just always sets the recheck flag to TRUE --- I'm hoping to get Teodor to handle pushing that control down to the opclass consistent() functions. The planner no longer pays any attention to amopreqcheck, and that catalog column will go away in due course.
1 parent c22ed3d commit 24558da

File tree

11 files changed

+141
-127
lines changed

11 files changed

+141
-127
lines changed

‎doc/src/sgml/indexam.sgml

Lines changed: 18 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
<!-- $PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.24 2008/04/10 22:25:25 tgl Exp $ -->
1+
<!-- $PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.25 2008/04/13 19:18:13 tgl Exp $ -->
22

33
<chapter id="indexam">
44
<title>Index Access Method Interface Definition</title>
@@ -315,7 +315,15 @@ amgettuple (IndexScanDesc scan,
315315
TID is stored into the <literal>scan</> structure. Note that
316316
<quote>success</> means only that the index contains an entry that matches
317317
the scan keys, not that the tuple necessarily still exists in the heap or
318-
will pass the caller's snapshot test.
318+
will pass the caller's snapshot test. On success, <function>amgettuple</>
319+
must also set <literal>scan-&gt;xs_recheck</> to TRUE or FALSE.
320+
FALSE means it is certain that the index entry matches the scan keys.
321+
TRUE means this is not certain, and the conditions represented by the
322+
scan keys must be rechecked against the heap tuple after fetching it.
323+
This provision supports <quote>lossy</> index operators.
324+
Note that rechecking will extend only to the scan conditions; a partial
325+
index predicate (if any) is never rechecked by <function>amgettuple</>
326+
callers.
319327
</para>
320328

321329
<para>
@@ -327,6 +335,14 @@ amgetbitmap (IndexScanDesc scan,
327335
Fetch all tuples in the given scan and add them to the caller-supplied
328336
TIDBitmap (that is, OR the set of tuple IDs into whatever set is already
329337
in the bitmap). The number of tuples fetched is returned.
338+
While inserting tuple IDs into the bitmap, <function>amgetbitmap</> can
339+
indicate that rechecking of the scan conditions is required for specific
340+
tuple IDs. This is analogous to the <literal>xs_recheck</> output parameter
341+
of <function>amgettuple</>. Note: in the current implementation, support
342+
for this feature is conflated with support for lossy storage of the bitmap
343+
itself, and therefore callers recheck both the scan conditions and the
344+
partial index predicate (if any) for recheckable tuples. That might not
345+
always be true, however.
330346
<function>amgetbitmap</> and
331347
<function>amgettuple</> cannot be used in the same index scan; there
332348
are other restrictions too when using <function>amgetbitmap</>, as explained

‎src/backend/access/gin/ginget.c

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/gin/ginget.c,v 1.11 2008/04/10 22:25:25 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/gin/ginget.c,v 1.12 2008/04/13 19:18:13 tgl Exp $
1212
*-------------------------------------------------------------------------
1313
*/
1414

@@ -428,11 +428,14 @@ keyGetItem(Relation index, GinState *ginstate, MemoryContext tempCtx, GinScanKey
428428
* returns true if found
429429
*/
430430
static bool
431-
scanGetItem(IndexScanDesc scan, ItemPointerData *item)
431+
scanGetItem(IndexScanDesc scan, ItemPointerData *item, bool *recheck)
432432
{
433433
uint32 i;
434434
GinScanOpaque so = (GinScanOpaque) scan->opaque;
435435

436+
/* XXX for the moment, treat all GIN operators as lossy */
437+
*recheck = true;
438+
436439
ItemPointerSetMin(item);
437440
for (i = 0; i < so->nkeys; i++)
438441
{
@@ -496,13 +499,14 @@ gingetbitmap(PG_FUNCTION_ARGS)
496499
for (;;)
497500
{
498501
ItemPointerData iptr;
502+
bool recheck;
499503

500504
CHECK_FOR_INTERRUPTS();
501505

502-
if (!scanGetItem(scan, &iptr))
506+
if (!scanGetItem(scan, &iptr, &recheck))
503507
break;
504508

505-
tbm_add_tuples(tbm, &iptr, 1, false);
509+
tbm_add_tuples(tbm, &iptr, 1, recheck);
506510
ntids++;
507511
}
508512

@@ -528,7 +532,7 @@ gingettuple(PG_FUNCTION_ARGS)
528532
PG_RETURN_BOOL(false);
529533

530534
startScan(scan);
531-
res = scanGetItem(scan, &scan->xs_ctup.t_self);
535+
res = scanGetItem(scan, &scan->xs_ctup.t_self, &scan->xs_recheck);
532536
stopScan(scan);
533537

534538
PG_RETURN_BOOL(res);

‎src/backend/access/gist/gistget.c

Lines changed: 22 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.70 2008/04/10 22:25:25 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.71 2008/04/13 19:18:14 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -23,9 +23,7 @@
2323

2424
static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n,
2525
ScanDirection dir);
26-
static int64 gistnext(IndexScanDesc scan, ScanDirection dir,
27-
ItemPointer tid, TIDBitmap *tbm,
28-
bool ignore_killed_tuples);
26+
static int64 gistnext(IndexScanDesc scan, ScanDirection dir, TIDBitmap *tbm);
2927
static bool gistindex_keytest(IndexTuple tuple, IndexScanDesc scan,
3028
OffsetNumber offset);
3129

@@ -100,7 +98,6 @@ gistgettuple(PG_FUNCTION_ARGS)
10098
IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
10199
ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1);
102100
GISTScanOpaque so;
103-
ItemPointerData tid;
104101
bool res;
105102

106103
so = (GISTScanOpaque) scan->opaque;
@@ -113,11 +110,9 @@ gistgettuple(PG_FUNCTION_ARGS)
113110
killtuple(scan->indexRelation, so, &(so->curpos));
114111

115112
/*
116-
* Get the next tuple that matches the search key. If asked to skip killed
117-
* tuples, continue looping until we find a non-killed tuple that matches
118-
* the search key.
113+
* Get the next tuple that matches the search key.
119114
*/
120-
res = (gistnext(scan, dir, &tid, NULL, scan->ignore_killed_tuples) > 0) ? true : false;
115+
res = (gistnext(scan, dir, NULL) > 0);
121116

122117
PG_RETURN_BOOL(res);
123118
}
@@ -129,7 +124,7 @@ gistgetbitmap(PG_FUNCTION_ARGS)
129124
TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
130125
int64 ntids;
131126

132-
ntids = gistnext(scan, ForwardScanDirection, NULL, tbm, false);
127+
ntids = gistnext(scan, ForwardScanDirection, tbm);
133128

134129
PG_RETURN_INT64(ntids);
135130
}
@@ -140,20 +135,23 @@ gistgetbitmap(PG_FUNCTION_ARGS)
140135
*
141136
* This function is used by both gistgettuple and gistgetbitmap. When
142137
* invoked from gistgettuple, tbm is null and the next matching tuple
143-
* is returned in *tid. When invoked from getbitmap, tid is null and
144-
* all matching tuples are added to tbm. In both cases, the function
145-
* result is the number of returned tuples.
138+
* is returned in scan->xs_ctup.t_self. When invoked from getbitmap,
139+
* tbm is non-null and all matching tuples are added to tbm before
140+
* returning. In both cases, the function result is the number of
141+
* returned tuples.
142+
*
143+
* If scan specifies to skip killed tuples, continue looping until we find a
144+
* non-killed tuple that matches the search key.
146145
*/
147146
static int64
148-
gistnext(IndexScanDesc scan, ScanDirection dir,
149-
ItemPointer tid, TIDBitmap *tbm,
150-
bool ignore_killed_tuples)
147+
gistnext(IndexScanDesc scan, ScanDirection dir, TIDBitmap *tbm)
151148
{
152149
Page p;
153150
OffsetNumber n;
154151
GISTScanOpaque so;
155152
GISTSearchStack *stk;
156153
IndexTuple it;
154+
bool recheck;
157155
GISTPageOpaque opaque;
158156
bool resetoffset = false;
159157
int64 ntids = 0;
@@ -194,7 +192,7 @@ gistnext(IndexScanDesc scan, ScanDirection dir,
194192

195193
if (XLogRecPtrIsInvalid(so->stack->lsn) || !XLByteEQ(so->stack->lsn, PageGetLSN(p)))
196194
{
197-
/* page changed from last visit or visit first time , reset offset */
195+
/* first visit or page changed from last visit, reset offset */
198196
so->stack->lsn = PageGetLSN(p);
199197
resetoffset = true;
200198

@@ -259,6 +257,8 @@ gistnext(IndexScanDesc scan, ScanDirection dir,
259257
for (;;)
260258
{
261259
n = gistfindnext(scan, n, dir);
260+
/* XXX for the moment, treat all GIST operators as lossy */
261+
recheck = true;
262262

263263
if (!OffsetNumberIsValid(n))
264264
{
@@ -298,15 +298,17 @@ gistnext(IndexScanDesc scan, ScanDirection dir,
298298
ItemPointerSet(&(so->curpos),
299299
BufferGetBlockNumber(so->curbuf), n);
300300

301-
if (!(ignore_killed_tuples && ItemIdIsDead(PageGetItemId(p, n))))
301+
if (!(scan->ignore_killed_tuples &&
302+
ItemIdIsDead(PageGetItemId(p, n))))
302303
{
303304
it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
304305
ntids++;
305306
if (tbm != NULL)
306-
tbm_add_tuples(tbm, &it->t_tid, 1, false);
307+
tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
307308
else
308309
{
309-
*tid = scan->xs_ctup.t_self = it->t_tid;
310+
scan->xs_ctup.t_self = it->t_tid;
311+
scan->xs_recheck = recheck;
310312

311313
LockBuffer(so->curbuf, GIST_UNLOCK);
312314
return ntids; /* always 1 */

‎src/backend/access/hash/hash.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/hash/hash.c,v 1.101 2008/04/10 22:25:25 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/hash/hash.c,v 1.102 2008/04/13 19:18:14 tgl Exp $
1212
*
1313
* NOTES
1414
* This file contains only the public interface routines.
@@ -210,6 +210,9 @@ hashgettuple(PG_FUNCTION_ARGS)
210210
OffsetNumber offnum;
211211
bool res;
212212

213+
/* Hash indexes are never lossy (at the moment anyway) */
214+
scan->xs_recheck = false;
215+
213216
/*
214217
* We hold pin but not lock on current buffer while outside the hash AM.
215218
* Reacquire the read lock here.

‎src/backend/access/index/genam.c

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/index/genam.c,v 1.67 2008/04/12 23:14:21 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/index/genam.c,v 1.68 2008/04/13 19:18:14 tgl Exp $
1212
*
1313
* NOTES
1414
* many of the old access method routines have been turned into
@@ -96,9 +96,9 @@ RelationGetIndexScan(Relation indexRelation,
9696
ItemPointerSetInvalid(&scan->xs_ctup.t_self);
9797
scan->xs_ctup.t_data = NULL;
9898
scan->xs_cbuf = InvalidBuffer;
99-
scan->xs_prev_xmax = InvalidTransactionId;
100-
scan->xs_next_hot = InvalidOffsetNumber;
10199
scan->xs_hot_dead = false;
100+
scan->xs_next_hot = InvalidOffsetNumber;
101+
scan->xs_prev_xmax = InvalidTransactionId;
102102

103103
/*
104104
* Let the AM fill in the key and any opaque data it wants.
@@ -233,7 +233,18 @@ systable_getnext(SysScanDesc sysscan)
233233
HeapTuple htup;
234234

235235
if (sysscan->irel)
236+
{
236237
htup = index_getnext(sysscan->iscan, ForwardScanDirection);
238+
/*
239+
* We currently don't need to support lossy index operators for
240+
* any system catalog scan. It could be done here, using the
241+
* scan keys to drive the operator calls, if we arranged to save
242+
* the heap attnums during systable_beginscan(); this is practical
243+
* because we still wouldn't need to support indexes on expressions.
244+
*/
245+
if (htup && sysscan->iscan->xs_recheck)
246+
elog(ERROR, "system catalog scans with lossy index conditions are not implemented");
247+
}
237248
else
238249
htup = heap_getnext(sysscan->scan, ForwardScanDirection);
239250

@@ -328,6 +339,9 @@ systable_getnext_ordered(SysScanDesc sysscan, ScanDirection direction)
328339

329340
Assert(sysscan->irel);
330341
htup = index_getnext(sysscan->iscan, direction);
342+
/* See notes in systable_getnext */
343+
if (htup && sysscan->iscan->xs_recheck)
344+
elog(ERROR, "system catalog scans with lossy index conditions are not implemented");
331345

332346
return htup;
333347
}

‎src/backend/access/index/indexam.c

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.106 2008/04/12 23:14:21 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.107 2008/04/13 19:18:14 tgl Exp $
1212
*
1313
* INTERFACE ROUTINES
1414
* index_open - open an index relation by relation OID
@@ -402,6 +402,10 @@ index_restrpos(IndexScanDesc scan)
402402
* snapshot, or NULL if no more matching tuples exist. On success,
403403
* the buffer containing the heap tuple is pinned (the pin will be dropped
404404
* at the next index_getnext or index_endscan).
405+
*
406+
* Note: caller must check scan->xs_recheck, and perform rechecking of the
407+
* scan keys if required. We do not do that here because we don't have
408+
* enough information to do it efficiently in the general case.
405409
* ----------------
406410
*/
407411
HeapTuple
@@ -455,6 +459,8 @@ index_getnext(IndexScanDesc scan, ScanDirection direction)
455459
/*
456460
* The AM's gettuple proc finds the next index entry matching the
457461
* scan keys, and puts the TID in xs_ctup.t_self (ie, *tid).
462+
* It should also set scan->xs_recheck, though we pay no
463+
* attention to that here.
458464
*/
459465
found = DatumGetBool(FunctionCall2(procedure,
460466
PointerGetDatum(scan),

‎src/backend/access/nbtree/nbtree.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
* Portions Copyright (c) 1994, Regents of the University of California
1313
*
1414
* IDENTIFICATION
15-
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtree.c,v 1.157 2008/04/10 22:25:25 tgl Exp $
15+
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtree.c,v 1.158 2008/04/13 19:18:14 tgl Exp $
1616
*
1717
*-------------------------------------------------------------------------
1818
*/
@@ -240,6 +240,9 @@ btgettuple(PG_FUNCTION_ARGS)
240240
BTScanOpaque so = (BTScanOpaque) scan->opaque;
241241
bool res;
242242

243+
/* btree indexes are never lossy */
244+
scan->xs_recheck = false;
245+
243246
/*
244247
* If we've already initialized this scan, we can just advance it in the
245248
* appropriate direction. If we haven't done so yet, we call a routine to

‎src/backend/commands/cluster.c

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
*
1212
*
1313
* IDENTIFICATION
14-
* $PostgreSQL: pgsql/src/backend/commands/cluster.c,v 1.172 2008/03/26 21:10:37 alvherre Exp $
14+
* $PostgreSQL: pgsql/src/backend/commands/cluster.c,v 1.173 2008/04/13 19:18:14 tgl Exp $
1515
*
1616
*-------------------------------------------------------------------------
1717
*/
@@ -776,6 +776,10 @@ copy_heap_data(Oid OIDNewHeap, Oid OIDOldHeap, Oid OIDOldIndex)
776776

777777
CHECK_FOR_INTERRUPTS();
778778

779+
/* Since we used no scan keys, should never need to recheck */
780+
if (scan->xs_recheck)
781+
elog(ERROR, "CLUSTER does not support lossy index conditions");
782+
779783
LockBuffer(scan->xs_cbuf, BUFFER_LOCK_SHARE);
780784

781785
switch (HeapTupleSatisfiesVacuum(tuple->t_data, OldestXmin,

‎src/backend/executor/nodeIndexscan.c

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/executor/nodeIndexscan.c,v 1.126 2008/03/18 03:54:52 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/executor/nodeIndexscan.c,v 1.127 2008/04/13 19:18:14 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -106,7 +106,7 @@ IndexNext(IndexScanState *node)
106106
/*
107107
* ok, now that we have what we need, fetch the next tuple.
108108
*/
109-
if ((tuple = index_getnext(scandesc, direction)) != NULL)
109+
while ((tuple = index_getnext(scandesc, direction)) != NULL)
110110
{
111111
/*
112112
* Store the scanned tuple in the scan tuple slot of the scan state.
@@ -118,6 +118,18 @@ IndexNext(IndexScanState *node)
118118
scandesc->xs_cbuf, /* buffer containing tuple */
119119
false); /* don't pfree */
120120

121+
/*
122+
* If the index was lossy, we have to recheck the index quals using
123+
* the real tuple.
124+
*/
125+
if (scandesc->xs_recheck)
126+
{
127+
econtext->ecxt_scantuple = slot;
128+
ResetExprContext(econtext);
129+
if (!ExecQual(node->indexqualorig, econtext, false))
130+
continue; /* nope, so ask index for another one */
131+
}
132+
121133
return slot;
122134
}
123135

0 commit comments

Comments
 (0)