Skip to content

Commit 4e82a95

Browse files
tglsfdctglsfdc
committed
Replace "amgetmulti" AM functions with "amgetbitmap", in which the whole
indexscan always occurs in one call, and the results are returned in a TIDBitmap instead of a limited-size array of TIDs. This should improve speed a little by reducing AM entry/exit overhead, and it is necessary infrastructure if we are ever to support bitmap indexes. In an only slightly related change, add support for TIDBitmaps to preserve (somewhat lossily) the knowledge that particular TIDs reported by an index need to have their quals rechecked when the heap is visited. This facility is not really used yet; we'll need to extend the forced-recheck feature to plain indexscans before it's useful, and that hasn't been coded yet. The intent is to use it to clean up 8.3's horrid @@@ kluge for text search with weighted queries. There might be other uses in future, but that one alone is sufficient reason. Heikki Linnakangas, with some adjustments by me.
1 parent f260edb commit 4e82a95

30 files changed

+420
-269
lines changed

‎doc/src/sgml/catalogs.sgml

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
<!-- $PostgreSQL: pgsql/doc/src/sgml/catalogs.sgml,v 2.163 2008/03/10 12:55:13 mha Exp $ -->
1+
<!-- $PostgreSQL: pgsql/doc/src/sgml/catalogs.sgml,v 2.164 2008/04/10 22:25:25 tgl Exp $ -->
22
<!--
33
Documentation of the system catalogs, directed toward PostgreSQL developers
44
-->
@@ -473,10 +473,10 @@
473473
</row>
474474

475475
<row>
476-
<entry><structfield>amgetmulti</structfield></entry>
476+
<entry><structfield>amgetbitmap</structfield></entry>
477477
<entry><type>regproc</type></entry>
478478
<entry><literal><link linkend="catalog-pg-proc"><structname>pg_proc</structname></link>.oid</literal></entry>
479-
<entry><quote>Fetch multiple tuples</quote> function</entry>
479+
<entry><quote>Fetch all valid tuples</quote> function</entry>
480480
</row>
481481

482482
<row>

‎doc/src/sgml/indexam.sgml

Lines changed: 19 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
<!-- $PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.23 2007/04/06 22:33:41 tgl Exp $ -->
1+
<!-- $PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.24 2008/04/10 22:25:25 tgl Exp $ -->
22

33
<chapter id="indexam">
44
<title>Index Access Method Interface Definition</title>
@@ -320,23 +320,16 @@ amgettuple (IndexScanDesc scan,
320320

321321
<para>
322322
<programlisting>
323-
boolean
324-
amgetmulti (IndexScanDesc scan,
325-
ItemPointer tids,
326-
int32 max_tids,
327-
int32 *returned_tids);
323+
int64
324+
amgetbitmap (IndexScanDesc scan,
325+
TIDBitmap *tbm);
328326
</programlisting>
329-
Fetch multiple tuples in the given scan. Returns TRUE if the scan should
330-
continue, FALSE if no matching tuples remain. <literal>tids</> points to
331-
a caller-supplied array of <literal>max_tids</>
332-
<structname>ItemPointerData</> records, which the call fills with TIDs of
333-
matching tuples. <literal>*returned_tids</> is set to the number of TIDs
334-
actually returned. This can be less than <literal>max_tids</>, or even
335-
zero, even when the return value is TRUE. (This provision allows the
336-
access method to choose the most efficient stopping points in its scan,
337-
for example index page boundaries.) <function>amgetmulti</> and
327+
Fetch all tuples in the given scan and add them to the caller-supplied
328+
TIDBitmap (that is, OR the set of tuple IDs into whatever set is already
329+
in the bitmap). The number of tuples fetched is returned.
330+
<function>amgetbitmap</> and
338331
<function>amgettuple</> cannot be used in the same index scan; there
339-
are other restrictions too when using <function>amgetmulti</>, as explained
332+
are other restrictions too when using <function>amgetbitmap</>, as explained
340333
in <xref linkend="index-scanning">.
341334
</para>
342335

@@ -491,20 +484,17 @@ amrestrpos (IndexScanDesc scan);
491484

492485
<para>
493486
Instead of using <function>amgettuple</>, an index scan can be done with
494-
<function>amgetmulti</> to fetch multiple tuples per call. This can be
487+
<function>amgetbitmap</> to fetch all tuples in one call. This can be
495488
noticeably more efficient than <function>amgettuple</> because it allows
496489
avoiding lock/unlock cycles within the access method. In principle
497-
<function>amgetmulti</> should have the same effects as repeated
490+
<function>amgetbitmap</> should have the same effects as repeated
498491
<function>amgettuple</> calls, but we impose several restrictions to
499-
simplify matters. In the first place, <function>amgetmulti</> does not
500-
take a <literal>direction</> argument, and therefore it does not support
501-
backwards scan nor intrascan reversal of direction. The access method
502-
need not support marking or restoring scan positions during an
503-
<function>amgetmulti</> scan, either. (These restrictions cost little
504-
since it would be difficult to use these features in an
505-
<function>amgetmulti</> scan anyway: adjusting the caller's buffered
506-
list of TIDs would be complex.) Finally, <function>amgetmulti</> does
507-
not guarantee any locking of the returned tuples, with implications
492+
simplify matters. First of all, <function>amgetbitmap</> returns all
493+
tuples at once and marking or restoring scan positions isn't
494+
supported. Secondly, the tuples are returned in a bitmap which doesn't
495+
have any specific ordering, which is why <function>amgetbitmap</> doesn't
496+
take a <literal>direction</> argument. Finally, <function>amgetbitmap</>
497+
does not guarantee any locking of the returned tuples, with implications
508498
spelled out in <xref linkend="index-locking">.
509499
</para>
510500

@@ -605,9 +595,8 @@ amrestrpos (IndexScanDesc scan);
605595
</para>
606596

607597
<para>
608-
In an <function>amgetmulti</> index scan, the access method need not
609-
guarantee to keep an index pin on any of the returned tuples. (It would be
610-
impractical to pin more than the last one anyway.) Therefore
598+
In an <function>amgetbitmap</> index scan, the access method does not
599+
keep an index pin on any of the returned tuples. Therefore
611600
it is only safe to use such scans with MVCC-compliant snapshots.
612601
</para>
613602

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

Lines changed: 19 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -8,13 +8,15 @@
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.10 2008/01/01 19:45:46 momjian Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/gin/ginget.c,v 1.11 2008/04/10 22:25:25 tgl Exp $
1212
*-------------------------------------------------------------------------
1313
*/
1414

1515
#include "postgres.h"
16+
1617
#include "access/gin.h"
1718
#include "catalog/index.h"
19+
#include "miscadmin.h"
1820
#include "utils/memutils.h"
1921

2022
static bool
@@ -476,34 +478,37 @@ scanGetItem(IndexScanDesc scan, ItemPointerData *item)
476478
#define GinIsVoidRes(s) ( ((GinScanOpaque) scan->opaque)->isVoidRes == true )
477479

478480
Datum
479-
gingetmulti(PG_FUNCTION_ARGS)
481+
gingetbitmap(PG_FUNCTION_ARGS)
480482
{
481483
IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
482-
ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
483-
int32 max_tids = PG_GETARG_INT32(2);
484-
int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3);
484+
TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
485+
int64 ntids;
485486

486487
if (GinIsNewKey(scan))
487488
newScanKey(scan);
488489

489-
*returned_tids = 0;
490-
491490
if (GinIsVoidRes(scan))
492-
PG_RETURN_BOOL(false);
491+
PG_RETURN_INT64(0);
493492

494493
startScan(scan);
495494

496-
do
495+
ntids = 0;
496+
for (;;)
497497
{
498-
if (scanGetItem(scan, tids + *returned_tids))
499-
(*returned_tids)++;
500-
else
498+
ItemPointerData iptr;
499+
500+
CHECK_FOR_INTERRUPTS();
501+
502+
if (!scanGetItem(scan, &iptr))
501503
break;
502-
} while (*returned_tids < max_tids);
504+
505+
tbm_add_tuples(tbm, &iptr, 1, false);
506+
ntids++;
507+
}
503508

504509
stopScan(scan);
505510

506-
PG_RETURN_BOOL(*returned_tids == max_tids);
511+
PG_RETURN_INT64(ntids);
507512
}
508513

509514
Datum

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

Lines changed: 32 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -8,21 +8,24 @@
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.69 2008/01/01 19:45:46 momjian Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/gist/gistget.c,v 1.70 2008/04/10 22:25:25 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
1515
#include "postgres.h"
1616

1717
#include "access/gist_private.h"
1818
#include "executor/execdebug.h"
19+
#include "miscadmin.h"
1920
#include "pgstat.h"
2021
#include "utils/memutils.h"
2122

2223

2324
static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n,
2425
ScanDirection dir);
25-
static int gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, int maxtids, bool ignore_killed_tuples);
26+
static int64 gistnext(IndexScanDesc scan, ScanDirection dir,
27+
ItemPointer tid, TIDBitmap *tbm,
28+
bool ignore_killed_tuples);
2629
static bool gistindex_keytest(IndexTuple tuple, IndexScanDesc scan,
2730
OffsetNumber offset);
2831

@@ -114,32 +117,37 @@ gistgettuple(PG_FUNCTION_ARGS)
114117
* tuples, continue looping until we find a non-killed tuple that matches
115118
* the search key.
116119
*/
117-
res = (gistnext(scan, dir, &tid, 1, scan->ignore_killed_tuples)) ? true : false;
120+
res = (gistnext(scan, dir, &tid, NULL, scan->ignore_killed_tuples) > 0) ? true : false;
118121

119122
PG_RETURN_BOOL(res);
120123
}
121124

122125
Datum
123-
gistgetmulti(PG_FUNCTION_ARGS)
126+
gistgetbitmap(PG_FUNCTION_ARGS)
124127
{
125128
IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
126-
ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1);
127-
int32 max_tids = PG_GETARG_INT32(2);
128-
int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3);
129+
TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
130+
int64 ntids;
129131

130-
*returned_tids = gistnext(scan, ForwardScanDirection, tids, max_tids, false);
132+
ntids = gistnext(scan, ForwardScanDirection, NULL, tbm, false);
131133

132-
PG_RETURN_BOOL(*returned_tids == max_tids);
134+
PG_RETURN_INT64(ntids);
133135
}
134136

135137
/*
136-
* Fetch a tuples that matchs the search key; this can be invoked
137-
* either to fetch the first such tuple or subsequent matching
138-
* tuples. Returns true iff a matching tuple was found.
138+
* Fetch tuple(s) that match the search key; this can be invoked
139+
* either to fetch the first such tuple or subsequent matching tuples.
140+
*
141+
* This function is used by both gistgettuple and gistgetbitmap. When
142+
* 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.
139146
*/
140-
static int
141-
gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
142-
int maxtids, bool ignore_killed_tuples)
147+
static int64
148+
gistnext(IndexScanDesc scan, ScanDirection dir,
149+
ItemPointer tid, TIDBitmap *tbm,
150+
bool ignore_killed_tuples)
143151
{
144152
Page p;
145153
OffsetNumber n;
@@ -148,7 +156,7 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
148156
IndexTuple it;
149157
GISTPageOpaque opaque;
150158
bool resetoffset = false;
151-
int ntids = 0;
159+
int64 ntids = 0;
152160

153161
so = (GISTScanOpaque) scan->opaque;
154162

@@ -174,6 +182,8 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
174182

175183
for (;;)
176184
{
185+
CHECK_FOR_INTERRUPTS();
186+
177187
/* First of all, we need lock buffer */
178188
Assert(so->curbuf != InvalidBuffer);
179189
LockBuffer(so->curbuf, GIST_SHARE);
@@ -285,20 +295,21 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
285295
* return success. Note that we keep "curbuf" pinned so that
286296
* we can efficiently resume the index scan later.
287297
*/
288-
289298
ItemPointerSet(&(so->curpos),
290299
BufferGetBlockNumber(so->curbuf), n);
291300

292301
if (!(ignore_killed_tuples && ItemIdIsDead(PageGetItemId(p, n))))
293302
{
294303
it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
295-
tids[ntids] = scan->xs_ctup.t_self = it->t_tid;
296304
ntids++;
297-
298-
if (ntids == maxtids)
305+
if (tbm != NULL)
306+
tbm_add_tuples(tbm, &it->t_tid, 1, false);
307+
else
299308
{
309+
*tid = scan->xs_ctup.t_self = it->t_tid;
310+
300311
LockBuffer(so->curbuf, GIST_UNLOCK);
301-
return ntids;
312+
return ntids; /* always 1 */
302313
}
303314
}
304315
}
@@ -308,7 +319,6 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
308319
* We've found an entry in an internal node whose key is
309320
* consistent with the search key, so push it to stack
310321
*/
311-
312322
stk = (GISTSearchStack *) palloc(sizeof(GISTSearchStack));
313323

314324
it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
@@ -318,7 +328,6 @@ gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids,
318328

319329
stk->next = so->stack->next;
320330
so->stack->next = stk;
321-
322331
}
323332

324333
if (ScanDirectionIsBackward(dir))

0 commit comments

Comments
 (0)