Bitmapscan changes - Mailing list pgsql-patches
| From | Heikki Linnakangas |
|---|---|
| Subject | Bitmapscan changes |
| Date | |
| Msg-id | 45F546AE.7020900@enterprisedb.com Whole thread Raw |
| Responses |
Re: Bitmapscan changes
(Tom Lane <tgl@sss.pgh.pa.us>)
Re: Bitmapscan changes (Gavin Sherry <swm@alcove.com.au>) |
| List | pgsql-patches |
Here's a patch to change the amgetmulti API so that it's called only once per scan, and the indexam adds *all* matching tuples at once to a caller-supplied TIDBitmap. Per Tom's proposal in July 2006: http://archives.postgresql.org/pgsql-hackers/2006-07/msg01233.php The patch also adds support for candidate matches. An index scan can indicate that the tuples it's returning are candidates, and the executor will recheck the original scan quals of any candidate matches when the tuple is fetched from heap. The candidate status is tracked in TIDBitmap on a per-page basis. No current indexams return candidate matches, but they can (and are with the patch) also be used when bitmap ANDing a lossy and non-lossy page: the result is a non-lossy candidate page, containing the bits of the non-lossy page. The motivation for adding the support for candidate matches is that GIT / clustered indexes need it. It's likely that we'll modify the API further to add support for the stream bitmaps when the bitmap indexam patch moves forward, but this is a step in the right direction and provides some immediate benefit. I added some regression tests to test bitmap AND and OR with a mixture of lossy and non-lossy pages, and to test the GIN getbitmap function which wasn't being exercised by any existing the regression tests. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com Index: doc/src/sgml/catalogs.sgml =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/doc/src/sgml/catalogs.sgml,v retrieving revision 2.145 diff -c -r2.145 catalogs.sgml *** doc/src/sgml/catalogs.sgml 14 Feb 2007 01:58:55 -0000 2.145 --- doc/src/sgml/catalogs.sgml 8 Mar 2007 21:39:15 -0000 *************** *** 436,445 **** </row> <row> ! <entry><structfield>amgetmulti</structfield></entry> <entry><type>regproc</type></entry> <entry><literal><link linkend="catalog-pg-proc"><structname>pg_proc</structname></link>.oid</literal></entry> ! <entry><quote>Fetch multiple tuples</quote> function</entry> </row> <row> --- 436,445 ---- </row> <row> ! <entry><structfield>amgetbitmap</structfield></entry> <entry><type>regproc</type></entry> <entry><literal><link linkend="catalog-pg-proc"><structname>pg_proc</structname></link>.oid</literal></entry> ! <entry><quote>Fetch all valid tuples</quote> function</entry> </row> <row> Index: doc/src/sgml/indexam.sgml =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/doc/src/sgml/indexam.sgml,v retrieving revision 2.22 diff -c -r2.22 indexam.sgml *** doc/src/sgml/indexam.sgml 22 Feb 2007 22:00:22 -0000 2.22 --- doc/src/sgml/indexam.sgml 8 Mar 2007 21:41:02 -0000 *************** *** 317,339 **** <para> <programlisting> ! boolean ! amgetmulti (IndexScanDesc scan, ! ItemPointer tids, ! int32 max_tids, ! int32 *returned_tids); </programlisting> ! Fetch multiple tuples in the given scan. Returns TRUE if the scan should ! continue, FALSE if no matching tuples remain. <literal>tids</> points to ! a caller-supplied array of <literal>max_tids</> ! <structname>ItemPointerData</> records, which the call fills with TIDs of ! matching tuples. <literal>*returned_tids</> is set to the number of TIDs ! actually returned. This can be less than <literal>max_tids</>, or even ! zero, even when the return value is TRUE. (This provision allows the ! access method to choose the most efficient stopping points in its scan, ! for example index page boundaries.) <function>amgetmulti</> and <function>amgettuple</> cannot be used in the same index scan; there ! are other restrictions too when using <function>amgetmulti</>, as explained in <xref linkend="index-scanning">. </para> --- 317,331 ---- <para> <programlisting> ! int32 ! amgetbitmap (IndexScanDesc scan, ! TIDBitmap *tbm); </programlisting> ! Fetch all tuples in the given scan and add them to the caller-supplied ! TIDBitmap. The number of tuples fetched is returned. ! <function>amgetbitmap</> and <function>amgettuple</> cannot be used in the same index scan; there ! are other restrictions too when using <function>amgetbitmap</>, as explained in <xref linkend="index-scanning">. </para> *************** *** 488,507 **** <para> Instead of using <function>amgettuple</>, an index scan can be done with ! <function>amgetmulti</> to fetch multiple tuples per call. This can be noticeably more efficient than <function>amgettuple</> because it allows avoiding lock/unlock cycles within the access method. In principle ! <function>amgetmulti</> should have the same effects as repeated <function>amgettuple</> calls, but we impose several restrictions to ! simplify matters. In the first place, <function>amgetmulti</> does not ! take a <literal>direction</> argument, and therefore it does not support ! backwards scan nor intrascan reversal of direction. The access method ! need not support marking or restoring scan positions during an ! <function>amgetmulti</> scan, either. (These restrictions cost little ! since it would be difficult to use these features in an ! <function>amgetmulti</> scan anyway: adjusting the caller's buffered ! list of TIDs would be complex.) Finally, <function>amgetmulti</> does ! not guarantee any locking of the returned tuples, with implications spelled out in <xref linkend="index-locking">. </para> --- 480,496 ---- <para> Instead of using <function>amgettuple</>, an index scan can be done with ! <function>amgetbitmap</> to fetch all tuples in one call. This can be noticeably more efficient than <function>amgettuple</> because it allows avoiding lock/unlock cycles within the access method. In principle ! <function>amgetbitmap</> should have the same effects as repeated <function>amgettuple</> calls, but we impose several restrictions to ! simplify matters. First of all, <function>amgetbitmap</> returns all ! tuples at once and marking or restoring scan positions isn't ! supported. Secondly, the tuples are returned in a bitmap which doesn't ! have any specific ordering, which is why <function>amgetbitmap</> doesn't ! take a <literal>direction</> argument. Finally, <function>amgetbitmap</> ! does not guarantee any locking of the returned tuples, with implications spelled out in <xref linkend="index-locking">. </para> *************** *** 602,608 **** </para> <para> ! In an <function>amgetmulti</> index scan, the access method need not guarantee to keep an index pin on any of the returned tuples. (It would be impractical to pin more than the last one anyway.) Therefore it is only safe to use such scans with MVCC-compliant snapshots. --- 591,597 ---- </para> <para> ! In an <function>amgetbitmap</> index scan, the access method need not guarantee to keep an index pin on any of the returned tuples. (It would be impractical to pin more than the last one anyway.) Therefore it is only safe to use such scans with MVCC-compliant snapshots. Index: src/backend/access/gin/ginget.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/access/gin/ginget.c,v retrieving revision 1.7 diff -c -r1.7 ginget.c *** src/backend/access/gin/ginget.c 1 Feb 2007 04:16:08 -0000 1.7 --- src/backend/access/gin/ginget.c 12 Mar 2007 11:18:29 -0000 *************** *** 423,456 **** #define GinIsVoidRes(s) ( ((GinScanOpaque) scan->opaque)->isVoidRes == true ) Datum ! gingetmulti(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1); ! int32 max_tids = PG_GETARG_INT32(2); ! int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3); if (GinIsNewKey(scan)) newScanKey(scan); - *returned_tids = 0; - if (GinIsVoidRes(scan)) ! PG_RETURN_BOOL(false); startScan(scan); ! do { ! if (scanGetItem(scan, tids + *returned_tids)) ! (*returned_tids)++; ! else break; ! } while (*returned_tids < max_tids); stopScan(scan); ! PG_RETURN_BOOL(*returned_tids == max_tids); } Datum --- 423,457 ---- #define GinIsVoidRes(s) ( ((GinScanOpaque) scan->opaque)->isVoidRes == true ) Datum ! gingetbitmap(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1); ! int32 ntids; if (GinIsNewKey(scan)) newScanKey(scan); if (GinIsVoidRes(scan)) ! PG_RETURN_INT32(0); startScan(scan); ! ntids = 0; ! for(;;) { ! ItemPointerData iptr; ! ! if (!scanGetItem(scan, &iptr)) break; ! ! ntids++; ! tbm_add_tuples(tbm, &iptr, 1, false); ! } stopScan(scan); ! PG_RETURN_INT32(ntids); } Datum Index: src/backend/access/gist/gistget.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/access/gist/gistget.c,v retrieving revision 1.64 diff -c -r1.64 gistget.c *** src/backend/access/gist/gistget.c 20 Jan 2007 18:43:35 -0000 1.64 --- src/backend/access/gist/gistget.c 12 Mar 2007 11:18:24 -0000 *************** *** 22,28 **** static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n, ScanDirection dir); ! static int gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, int maxtids, bool ignore_killed_tuples); static bool gistindex_keytest(IndexTuple tuple, IndexScanDesc scan, OffsetNumber offset); --- 22,30 ---- static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n, ScanDirection dir); ! static int gistnext(IndexScanDesc scan, ScanDirection dir, ! ItemPointer tid, TIDBitmap *tbm, ! bool ignore_killed_tuples); static bool gistindex_keytest(IndexTuple tuple, IndexScanDesc scan, OffsetNumber offset); *************** *** 114,145 **** * tuples, continue looping until we find a non-killed tuple that matches * the search key. */ ! res = (gistnext(scan, dir, &tid, 1, scan->ignore_killed_tuples)) ? true : false; PG_RETURN_BOOL(res); } Datum ! gistgetmulti(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1); ! int32 max_tids = PG_GETARG_INT32(2); ! int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3); ! *returned_tids = gistnext(scan, ForwardScanDirection, tids, max_tids, false); ! PG_RETURN_BOOL(*returned_tids == max_tids); } /* * Fetch a tuples that matchs the search key; this can be invoked * either to fetch the first such tuple or subsequent matching ! * tuples. Returns true iff a matching tuple was found. */ static int ! gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tids, ! int maxtids, bool ignore_killed_tuples) { Page p; OffsetNumber n; --- 116,152 ---- * tuples, continue looping until we find a non-killed tuple that matches * the search key. */ ! res = (gistnext(scan, dir, &tid, NULL, scan->ignore_killed_tuples)) ? true : false; PG_RETURN_BOOL(res); } Datum ! gistgetbitmap(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1); ! int32 ntids; ! ntids = gistnext(scan, ForwardScanDirection, NULL, tbm, false); ! PG_RETURN_INT32(ntids); } /* * Fetch a tuples that matchs the search key; this can be invoked * either to fetch the first such tuple or subsequent matching ! * tuples. ! * ! * This function is used by both gistgettuple and gistgetbitmap. When ! * invoked from gistgettuple, tbm is null and the next matching tuple ! * is returned in *tid. When invoked from getbitmap, tid is null and ! * all matching tuples are added to tbm and tid is null. In both cases, ! * the number of returned tuples is returned. */ static int ! gistnext(IndexScanDesc scan, ScanDirection dir, ItemPointer tid, ! TIDBitmap *tbm, bool ignore_killed_tuples) { Page p; OffsetNumber n; *************** *** 292,304 **** if (!(ignore_killed_tuples && ItemIdDeleted(PageGetItemId(p, n)))) { it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); ! tids[ntids] = scan->xs_ctup.t_self = it->t_tid; ! ntids++; ! ! if (ntids == maxtids) { LockBuffer(so->curbuf, GIST_UNLOCK); ! return ntids; } } } --- 299,313 ---- if (!(ignore_killed_tuples && ItemIdDeleted(PageGetItemId(p, n)))) { it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); ! if(tbm != NULL) ! tbm_add_tuples(tbm, &it->t_tid, 1, false); ! else { + *tid = scan->xs_ctup.t_self = it->t_tid; + ntids++; + LockBuffer(so->curbuf, GIST_UNLOCK); ! return ntids; /* always 1 */ } } } Index: src/backend/access/hash/hash.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/access/hash/hash.c,v retrieving revision 1.93 diff -c -r1.93 hash.c *** src/backend/access/hash/hash.c 20 Jan 2007 18:43:35 -0000 1.93 --- src/backend/access/hash/hash.c 12 Mar 2007 11:18:17 -0000 *************** *** 239,310 **** /* ! * hashgetmulti() -- get multiple tuples at once ! * ! * This is a somewhat generic implementation: it avoids lock reacquisition ! * overhead, but there's no smarts about picking especially good stopping ! * points such as index page boundaries. */ Datum ! hashgetmulti(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1); ! int32 max_tids = PG_GETARG_INT32(2); ! int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3); HashScanOpaque so = (HashScanOpaque) scan->opaque; - Relation rel = scan->indexRelation; bool res = true; int32 ntids = 0; ! /* ! * We hold pin but not lock on current buffer while outside the hash AM. ! * Reacquire the read lock here. ! */ ! if (BufferIsValid(so->hashso_curbuf)) ! _hash_chgbufaccess(rel, so->hashso_curbuf, HASH_NOLOCK, HASH_READ); ! while (ntids < max_tids) { ! /* ! * Start scan, or advance to next tuple. ! */ ! if (ItemPointerIsValid(&(so->hashso_curpos))) ! res = _hash_next(scan, ForwardScanDirection); ! else ! res = _hash_first(scan, ForwardScanDirection); ! /* * Skip killed tuples if asked to. */ if (scan->ignore_killed_tuples) { ! while (res) ! { ! Page page; ! OffsetNumber offnum; ! offnum = ItemPointerGetOffsetNumber(&(so->hashso_curpos)); ! page = BufferGetPage(so->hashso_curbuf); ! if (!ItemIdDeleted(PageGetItemId(page, offnum))) ! break; ! res = _hash_next(scan, ForwardScanDirection); ! } } - if (!res) - break; /* Save tuple ID, and continue scanning */ ! tids[ntids] = scan->xs_ctup.t_self; ! ntids++; ! } ! /* Release read lock on current buffer, but keep it pinned */ ! if (BufferIsValid(so->hashso_curbuf)) ! _hash_chgbufaccess(rel, so->hashso_curbuf, HASH_READ, HASH_NOLOCK); ! *returned_tids = ntids; ! PG_RETURN_BOOL(res); } --- 239,286 ---- /* ! * hashgetbitmap() -- get multiple tuples at once */ Datum ! hashgetbitmap(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1); HashScanOpaque so = (HashScanOpaque) scan->opaque; bool res = true; int32 ntids = 0; ! res = _hash_first(scan, ForwardScanDirection); ! while (res) { ! bool add_tuple; /* * Skip killed tuples if asked to. */ if (scan->ignore_killed_tuples) { ! Page page; ! OffsetNumber offnum; ! offnum = ItemPointerGetOffsetNumber(&(so->hashso_curpos)); ! page = BufferGetPage(so->hashso_curbuf); ! add_tuple = !ItemIdDeleted(PageGetItemId(page, offnum)); } + else + add_tuple = true; /* Save tuple ID, and continue scanning */ ! if (add_tuple) ! { ! tbm_add_tuples(tbm, &scan->xs_ctup.t_self, 1, false); ! ntids++; ! } ! res = _hash_next(scan, ForwardScanDirection); ! } ! PG_RETURN_INT32(ntids); } Index: src/backend/access/index/indexam.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/access/index/indexam.c,v retrieving revision 1.97 diff -c -r1.97 indexam.c *** src/backend/access/index/indexam.c 5 Jan 2007 22:19:23 -0000 1.97 --- src/backend/access/index/indexam.c 8 Mar 2007 22:17:39 -0000 *************** *** 21,27 **** * index_markpos - mark a scan position * index_restrpos - restore a scan position * index_getnext - get the next tuple from a scan ! * index_getmulti - get multiple tuples from a scan * index_bulk_delete - bulk deletion of index tuples * index_vacuum_cleanup - post-deletion cleanup of an index * index_getprocid - get a support procedure OID --- 21,27 ---- * index_markpos - mark a scan position * index_restrpos - restore a scan position * index_getnext - get the next tuple from a scan ! * index_getbitmap - get all tuples from a scan * index_bulk_delete - bulk deletion of index tuples * index_vacuum_cleanup - post-deletion cleanup of an index * index_getprocid - get a support procedure OID *************** *** 66,71 **** --- 66,72 ---- #include "access/heapam.h" #include "pgstat.h" #include "utils/relcache.h" + #include "nodes/tidbitmap.h" /* ---------------------------------------------------------------- *************** *** 510,551 **** /* ---------------- * index_getmulti - get multiple tuples from an index scan * ! * Collects the TIDs of multiple heap tuples satisfying the scan keys. * Since there's no interlock between the index scan and the eventual heap * access, this is only safe to use with MVCC-based snapshots: the heap * item slot could have been replaced by a newer tuple by the time we get * to it. * ! * A TRUE result indicates more calls should occur; a FALSE result says the ! * scan is done. *returned_tids could be zero or nonzero in either case. * ---------------- */ ! bool ! index_getmulti(IndexScanDesc scan, ! ItemPointer tids, int32 max_tids, ! int32 *returned_tids) { FmgrInfo *procedure; ! bool found; SCAN_CHECKS; ! GET_SCAN_PROCEDURE(amgetmulti); /* just make sure this is false... */ scan->kill_prior_tuple = false; /* ! * have the am's getmulti proc do all the work. */ ! found = DatumGetBool(FunctionCall4(procedure, ! PointerGetDatum(scan), ! PointerGetDatum(tids), ! Int32GetDatum(max_tids), ! PointerGetDatum(returned_tids))); ! pgstat_count_index_tuples(&scan->xs_pgstat_info, *returned_tids); ! return found; } /* ---------------- --- 511,547 ---- /* ---------------- * index_getmulti - get multiple tuples from an index scan * ! * Adds the TIDs of all heap tuples satisfying the scan keys to a bitmap. * Since there's no interlock between the index scan and the eventual heap * access, this is only safe to use with MVCC-based snapshots: the heap * item slot could have been replaced by a newer tuple by the time we get * to it. * ! * Returns the number of matching tuples found. * ---------------- */ ! int32 ! index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap) { FmgrInfo *procedure; ! int32 ntids; SCAN_CHECKS; ! GET_SCAN_PROCEDURE(amgetbitmap); /* just make sure this is false... */ scan->kill_prior_tuple = false; /* ! * have the am's getbitmap proc do all the work. */ ! ntids = DatumGetInt32(FunctionCall2(procedure, ! PointerGetDatum(scan), ! PointerGetDatum(bitmap))); ! pgstat_count_index_tuples(&scan->xs_pgstat_info, ntids); ! return ntids; } /* ---------------- Index: src/backend/access/nbtree/nbtree.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/access/nbtree/nbtree.c,v retrieving revision 1.154 diff -c -r1.154 nbtree.c *** src/backend/access/nbtree/nbtree.c 5 Jan 2007 22:19:23 -0000 1.154 --- src/backend/access/nbtree/nbtree.c 8 Mar 2007 20:02:28 -0000 *************** *** 278,302 **** } /* ! * btgetmulti() -- get multiple tuples at once ! * ! * In the current implementation there seems no strong reason to stop at ! * index page boundaries; we just press on until we fill the caller's buffer ! * or run out of matches. */ Datum ! btgetmulti(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1); ! int32 max_tids = PG_GETARG_INT32(2); ! int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3); BTScanOpaque so = (BTScanOpaque) scan->opaque; bool res = true; int32 ntids = 0; ! ! if (max_tids <= 0) /* behave correctly in boundary case */ ! PG_RETURN_BOOL(true); /* If we haven't started the scan yet, fetch the first page & tuple. */ if (!BTScanPosIsValid(so->currPos)) --- 278,294 ---- } /* ! * btgetbitmap() -- gets all matching tuples, and adds them to a bitmap */ Datum ! btgetbitmap(PG_FUNCTION_ARGS) { IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ! TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1); BTScanOpaque so = (BTScanOpaque) scan->opaque; bool res = true; int32 ntids = 0; ! ItemPointer heapTid; /* If we haven't started the scan yet, fetch the first page & tuple. */ if (!BTScanPosIsValid(so->currPos)) *************** *** 305,319 **** if (!res) { /* empty scan */ ! *returned_tids = ntids; ! PG_RETURN_BOOL(res); } /* Save tuple ID, and continue scanning */ ! tids[ntids] = scan->xs_ctup.t_self; ntids++; } ! while (ntids < max_tids) { /* * Advance to next tuple within page. This is the same as the easy --- 297,312 ---- if (!res) { /* empty scan */ ! PG_RETURN_INT32(0); } /* Save tuple ID, and continue scanning */ ! heapTid = &scan->xs_ctup.t_self; ! tbm_add_tuples(tbm, heapTid, 1, false); ! ntids++; } ! while (true) { /* * Advance to next tuple within page. This is the same as the easy *************** *** 328,339 **** } /* Save tuple ID, and continue scanning */ ! tids[ntids] = so->currPos.items[so->currPos.itemIndex].heapTid; ntids++; } ! *returned_tids = ntids; ! PG_RETURN_BOOL(res); } /* --- 321,333 ---- } /* Save tuple ID, and continue scanning */ ! heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid; ! tbm_add_tuples(tbm, heapTid, 1, false); ! ntids++; } ! PG_RETURN_INT32(ntids); } /* Index: src/backend/executor/nodeBitmapHeapscan.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/executor/nodeBitmapHeapscan.c,v retrieving revision 1.16 diff -c -r1.16 nodeBitmapHeapscan.c *** src/backend/executor/nodeBitmapHeapscan.c 5 Jan 2007 22:19:28 -0000 1.16 --- src/backend/executor/nodeBitmapHeapscan.c 7 Mar 2007 21:36:20 -0000 *************** *** 204,210 **** * If we are using lossy info, we have to recheck the qual conditions * at every tuple. */ ! if (tbmres->ntuples < 0) { econtext->ecxt_scantuple = slot; ResetExprContext(econtext); --- 204,210 ---- * If we are using lossy info, we have to recheck the qual conditions * at every tuple. */ ! if (tbmres->ntuples < 0 || tbmres->iscandidates) { econtext->ecxt_scantuple = slot; ResetExprContext(econtext); Index: src/backend/executor/nodeBitmapIndexscan.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/executor/nodeBitmapIndexscan.c,v retrieving revision 1.22 diff -c -r1.22 nodeBitmapIndexscan.c *** src/backend/executor/nodeBitmapIndexscan.c 5 Jan 2007 22:19:28 -0000 1.22 --- src/backend/executor/nodeBitmapIndexscan.c 7 Mar 2007 22:25:10 -0000 *************** *** 37,46 **** Node * MultiExecBitmapIndexScan(BitmapIndexScanState *node) { - #define MAX_TIDS 1024 TIDBitmap *tbm; IndexScanDesc scandesc; - ItemPointerData tids[MAX_TIDS]; int32 ntids; double nTuples = 0; bool doscan; --- 37,44 ---- *************** *** 91,113 **** */ while (doscan) { ! bool more = index_getmulti(scandesc, tids, MAX_TIDS, &ntids); ! if (ntids > 0) ! { ! tbm_add_tuples(tbm, tids, ntids); ! nTuples += ntids; ! } CHECK_FOR_INTERRUPTS(); ! if (!more) ! { ! doscan = ExecIndexAdvanceArrayKeys(node->biss_ArrayKeys, node->biss_NumArrayKeys); ! if (doscan) /* reset index scan */ ! index_rescan(node->biss_ScanDesc, node->biss_ScanKeys); ! } } /* must provide our own instrumentation support */ --- 89,104 ---- */ while (doscan) { ! ntids = index_getbitmap(scandesc, tbm); ! nTuples += ntids; CHECK_FOR_INTERRUPTS(); ! doscan = ExecIndexAdvanceArrayKeys(node->biss_ArrayKeys, node->biss_NumArrayKeys); ! if (doscan) /* reset index scan */ ! index_rescan(node->biss_ScanDesc, node->biss_ScanKeys); } /* must provide our own instrumentation support */ Index: src/backend/nodes/tidbitmap.c =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/backend/nodes/tidbitmap.c,v retrieving revision 1.11 diff -c -r1.11 tidbitmap.c *** src/backend/nodes/tidbitmap.c 5 Jan 2007 22:19:30 -0000 1.11 --- src/backend/nodes/tidbitmap.c 12 Mar 2007 12:04:25 -0000 *************** *** 10,16 **** * Also, since we wish to be able to store very large tuple sets in * memory with this data structure, we support "lossy" storage, in which * we no longer remember individual tuple offsets on a page but only the ! * fact that a particular page needs to be visited. * * The "lossy" storage uses one bit per disk page, so at the standard 8K * BLCKSZ, we can represent all pages in 64Gb of disk space in about 1Mb --- 10,21 ---- * Also, since we wish to be able to store very large tuple sets in * memory with this data structure, we support "lossy" storage, in which * we no longer remember individual tuple offsets on a page but only the ! * fact that a particular page needs to be visited. We also support the ! * notion of candidate matches, which are like non-lossy matches in that ! * the individual tuple offsets are remembered, but the offsets remembered ! * are a superset of the actual matches. Candidate matches need to be ! * rechecked in the executor to see which ones really match. They are ! * used when a lossy page is intersected with a non-lossy page. * * The "lossy" storage uses one bit per disk page, so at the standard 8K * BLCKSZ, we can represent all pages in 64Gb of disk space in about 1Mb *************** *** 87,92 **** --- 92,98 ---- { BlockNumber blockno; /* page number (hashtable key) */ bool ischunk; /* T = lossy storage, F = exact */ + bool iscandidate; /* should the results be rechecked? */ bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]; } PagetableEntry; *************** *** 145,150 **** --- 151,160 ---- static void tbm_lossify(TIDBitmap *tbm); static int tbm_comparator(const void *left, const void *right); + #ifdef TIDBITMAP_DEBUG + static void dump_pte(const PagetableEntry *e); + static void tbm_dump(TIDBitmap *tbm); + #endif /* * tbm_create - create an initially-empty bitmap *************** *** 247,253 **** * tbm_add_tuples - add some tuple IDs to a TIDBitmap */ void ! tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids) { int i; --- 257,263 ---- * tbm_add_tuples - add some tuple IDs to a TIDBitmap */ void ! tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool candidates) { int i; *************** *** 281,286 **** --- 291,297 ---- bitnum = BITNUM(off - 1); } page->words[wordnum] |= ((bitmapword) 1 << bitnum); + page->iscandidate = page->iscandidate || candidates; if (tbm->nentries > tbm->maxentries) tbm_lossify(tbm); *************** *** 361,366 **** --- 372,378 ---- /* Both pages are exact, merge at the bit level */ for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++) apage->words[wordnum] |= bpage->words[wordnum]; + apage->iscandidate = apage->iscandidate || bpage->iscandidate; } } *************** *** 472,493 **** else if (tbm_page_is_lossy(b, apage->blockno)) { /* ! * When the page is lossy in b, we have to mark it lossy in a too. We ! * know that no bits need be set in bitmap a, but we do not know which ! * ones should be cleared, and we have no API for "at most these ! * tuples need be checked". (Perhaps it's worth adding that?) */ ! tbm_mark_page_lossy(a, apage->blockno); - /* - * Note: tbm_mark_page_lossy will have removed apage from a, and may - * have inserted a new lossy chunk instead. We can continue the same - * seq_search scan at the caller level, because it does not matter - * whether we visit such a new chunk or not: it will have only the bit - * for apage->blockno set, which is correct. - * - * We must return false here since apage was already deleted. - */ return false; } else --- 484,496 ---- else if (tbm_page_is_lossy(b, apage->blockno)) { /* ! * Some of the tuples in 'a' might not satisfy the quals for 'b', ! * but because the page 'b' is lossy, we don't know which ones. ! * Therefore we mark 'a' as candidate to indicate that at most ! * those tuples set in 'a' are matches. */ ! apage->iscandidate = true; return false; } else *************** *** 505,511 **** --- 508,516 ---- if (apage->words[wordnum] != 0) candelete = false; } + apage->iscandidate = apage->iscandidate || bpage->iscandidate; } + return candelete; } } *************** *** 677,682 **** --- 682,688 ---- } output->blockno = page->blockno; output->ntuples = ntuples; + output->iscandidates = page->iscandidate; tbm->spageptr++; return output; } *************** *** 932,934 **** --- 938,990 ---- return 1; return 0; } + + + #ifdef TIDBITMAP_DEBUG + static void + dump_pte(const PagetableEntry *e) + { + int i; + int max; + char str[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK) * BITS_PER_BITMAPWORD + 1]; + + if(e->ischunk) + max = WORDS_PER_CHUNK * BITS_PER_BITMAPWORD; + else + max = WORDS_PER_PAGE * BITS_PER_BITMAPWORD; + + for(i=0; i < max; i++) + { + if(e->words[WORDNUM(i)] & (1<<(BITNUM(i)))) + str[i] = '1'; + else + str[i] = '0'; + } + str[max] = '\0'; + + + elog(LOG, "blockno %d%s%s: %s", e->blockno, + e->ischunk ? " (lossy)" : "", + e->iscandidate ? " (candidates)" : "", + str); + } + + + static void + tbm_dump(TIDBitmap *tbm) + { + int i; + + elog(LOG, "Bitmap, %d lossy and %d non-lossy pages", tbm->nchunks, tbm->npages); + + if(tbm->status == TBM_ONE_PAGE) + dump_pte(&tbm->entry1); + else + { + for(i = 0; i < tbm->nchunks; i++) + dump_pte(tbm->schunks[i]); + for(i = 0; i < tbm->npages; i++) + dump_pte(tbm->spages[i]); + } + } + #endif Index: src/include/access/genam.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/access/genam.h,v retrieving revision 1.66 diff -c -r1.66 genam.h *** src/include/access/genam.h 5 Jan 2007 22:19:50 -0000 1.66 --- src/include/access/genam.h 7 Mar 2007 22:06:31 -0000 *************** *** 17,22 **** --- 17,23 ---- #include "access/relscan.h" #include "access/sdir.h" #include "nodes/primnodes.h" + #include "nodes/tidbitmap.h" #include "storage/lock.h" /* *************** *** 108,116 **** extern HeapTuple index_getnext(IndexScanDesc scan, ScanDirection direction); extern bool index_getnext_indexitem(IndexScanDesc scan, ScanDirection direction); ! extern bool index_getmulti(IndexScanDesc scan, ! ItemPointer tids, int32 max_tids, ! int32 *returned_tids); extern IndexBulkDeleteResult *index_bulk_delete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, --- 109,115 ---- extern HeapTuple index_getnext(IndexScanDesc scan, ScanDirection direction); extern bool index_getnext_indexitem(IndexScanDesc scan, ScanDirection direction); ! extern int index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap); extern IndexBulkDeleteResult *index_bulk_delete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, Index: src/include/access/gin.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/access/gin.h,v retrieving revision 1.10 diff -c -r1.10 gin.h *** src/include/access/gin.h 31 Jan 2007 15:09:45 -0000 1.10 --- src/include/access/gin.h 8 Mar 2007 19:54:45 -0000 *************** *** 422,428 **** #define ItemPointerSetMin(p) ItemPointerSet( (p), (BlockNumber)0, (OffsetNumber)0) #define ItemPointerIsMin(p) ( ItemPointerGetBlockNumber(p) == (BlockNumber)0 && ItemPointerGetOffsetNumber(p) == (OffsetNumber)0) ! extern Datum gingetmulti(PG_FUNCTION_ARGS); extern Datum gingettuple(PG_FUNCTION_ARGS); /* ginvacuum.c */ --- 422,428 ---- #define ItemPointerSetMin(p) ItemPointerSet( (p), (BlockNumber)0, (OffsetNumber)0) #define ItemPointerIsMin(p) ( ItemPointerGetBlockNumber(p) == (BlockNumber)0 && ItemPointerGetOffsetNumber(p) == (OffsetNumber)0) ! extern Datum gingetbitmap(PG_FUNCTION_ARGS); extern Datum gingettuple(PG_FUNCTION_ARGS); /* ginvacuum.c */ Index: src/include/access/gist_private.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/access/gist_private.h,v retrieving revision 1.26 diff -c -r1.26 gist_private.h *** src/include/access/gist_private.h 20 Jan 2007 18:43:35 -0000 1.26 --- src/include/access/gist_private.h 8 Mar 2007 19:50:23 -0000 *************** *** 271,277 **** /* gistget.c */ extern Datum gistgettuple(PG_FUNCTION_ARGS); ! extern Datum gistgetmulti(PG_FUNCTION_ARGS); /* gistutil.c */ --- 271,277 ---- /* gistget.c */ extern Datum gistgettuple(PG_FUNCTION_ARGS); ! extern Datum gistgetbitmap(PG_FUNCTION_ARGS); /* gistutil.c */ Index: src/include/access/hash.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/access/hash.h,v retrieving revision 1.76 diff -c -r1.76 hash.h *** src/include/access/hash.h 30 Jan 2007 01:33:36 -0000 1.76 --- src/include/access/hash.h 8 Mar 2007 19:50:47 -0000 *************** *** 235,241 **** extern Datum hashinsert(PG_FUNCTION_ARGS); extern Datum hashbeginscan(PG_FUNCTION_ARGS); extern Datum hashgettuple(PG_FUNCTION_ARGS); ! extern Datum hashgetmulti(PG_FUNCTION_ARGS); extern Datum hashrescan(PG_FUNCTION_ARGS); extern Datum hashendscan(PG_FUNCTION_ARGS); extern Datum hashmarkpos(PG_FUNCTION_ARGS); --- 235,241 ---- extern Datum hashinsert(PG_FUNCTION_ARGS); extern Datum hashbeginscan(PG_FUNCTION_ARGS); extern Datum hashgettuple(PG_FUNCTION_ARGS); ! extern Datum hashgetbitmap(PG_FUNCTION_ARGS); extern Datum hashrescan(PG_FUNCTION_ARGS); extern Datum hashendscan(PG_FUNCTION_ARGS); extern Datum hashmarkpos(PG_FUNCTION_ARGS); Index: src/include/access/nbtree.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/access/nbtree.h,v retrieving revision 1.111 diff -c -r1.111 nbtree.h *** src/include/access/nbtree.h 8 Feb 2007 05:05:53 -0000 1.111 --- src/include/access/nbtree.h 7 Mar 2007 17:28:19 -0000 *************** *** 486,492 **** extern Datum btinsert(PG_FUNCTION_ARGS); extern Datum btbeginscan(PG_FUNCTION_ARGS); extern Datum btgettuple(PG_FUNCTION_ARGS); ! extern Datum btgetmulti(PG_FUNCTION_ARGS); extern Datum btrescan(PG_FUNCTION_ARGS); extern Datum btendscan(PG_FUNCTION_ARGS); extern Datum btmarkpos(PG_FUNCTION_ARGS); --- 486,492 ---- extern Datum btinsert(PG_FUNCTION_ARGS); extern Datum btbeginscan(PG_FUNCTION_ARGS); extern Datum btgettuple(PG_FUNCTION_ARGS); ! extern Datum btgetbitmap(PG_FUNCTION_ARGS); extern Datum btrescan(PG_FUNCTION_ARGS); extern Datum btendscan(PG_FUNCTION_ARGS); extern Datum btmarkpos(PG_FUNCTION_ARGS); Index: src/include/catalog/pg_am.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/catalog/pg_am.h,v retrieving revision 1.50 diff -c -r1.50 pg_am.h *** src/include/catalog/pg_am.h 20 Jan 2007 23:13:01 -0000 1.50 --- src/include/catalog/pg_am.h 8 Mar 2007 20:04:27 -0000 *************** *** 55,61 **** regproc aminsert; /* "insert this tuple" function */ regproc ambeginscan; /* "start new scan" function */ regproc amgettuple; /* "next valid tuple" function */ ! regproc amgetmulti; /* "fetch multiple tuples" function */ regproc amrescan; /* "restart this scan" function */ regproc amendscan; /* "end this scan" function */ regproc ammarkpos; /* "mark current scan position" function */ --- 55,61 ---- regproc aminsert; /* "insert this tuple" function */ regproc ambeginscan; /* "start new scan" function */ regproc amgettuple; /* "next valid tuple" function */ ! regproc amgetbitmap; /* "fetch multiple tuples" function */ regproc amrescan; /* "restart this scan" function */ regproc amendscan; /* "end this scan" function */ regproc ammarkpos; /* "mark current scan position" function */ *************** *** 92,98 **** #define Anum_pg_am_aminsert 11 #define Anum_pg_am_ambeginscan 12 #define Anum_pg_am_amgettuple 13 ! #define Anum_pg_am_amgetmulti 14 #define Anum_pg_am_amrescan 15 #define Anum_pg_am_amendscan 16 #define Anum_pg_am_ammarkpos 17 --- 92,98 ---- #define Anum_pg_am_aminsert 11 #define Anum_pg_am_ambeginscan 12 #define Anum_pg_am_amgettuple 13 ! #define Anum_pg_am_amgetbitmap 14 #define Anum_pg_am_amrescan 15 #define Anum_pg_am_amendscan 16 #define Anum_pg_am_ammarkpos 17 *************** *** 108,123 **** * ---------------- */ ! DATA(insert OID = 403 ( btree 5 1 t t t t t f t btinsert btbeginscan btgettuple btgetmulti btrescan btendscan btmarkposbtrestrpos btbuild btbulkdelete btvacuumcleanup btcostestimate btoptions )); DESCR("b-tree index access method"); #define BTREE_AM_OID 403 ! DATA(insert OID = 405 ( hash 1 1 f f f f f f f hashinsert hashbeginscan hashgettuple hashgetmulti hashrescan hashendscanhashmarkpos hashrestrpos hashbuild hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions )); DESCR("hash index access method"); #define HASH_AM_OID 405 ! DATA(insert OID = 783 ( gist 0 7 f f t t t t t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscangistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions )); DESCR("GiST index access method"); #define GIST_AM_OID 783 ! DATA(insert OID = 2742 ( gin 0 4 f f f f f t f gininsert ginbeginscan gingettuple gingetmulti ginrescan ginendscanginmarkpos ginrestrpos ginbuild ginbulkdelete ginvacuumcleanup gincostestimate ginoptions )); DESCR("GIN index access method"); #define GIN_AM_OID 2742 --- 108,123 ---- * ---------------- */ ! DATA(insert OID = 403 ( btree 5 1 t t t t t f t btinsert btbeginscan btgettuple btgetbitmap btrescan btendscan btmarkposbtrestrpos btbuild btbulkdelete btvacuumcleanup btcostestimate btoptions )); DESCR("b-tree index access method"); #define BTREE_AM_OID 403 ! DATA(insert OID = 405 ( hash 1 1 f f f f f f f hashinsert hashbeginscan hashgettuple hashgetbitmap hashrescan hashendscanhashmarkpos hashrestrpos hashbuild hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions )); DESCR("hash index access method"); #define HASH_AM_OID 405 ! DATA(insert OID = 783 ( gist 0 7 f f t t t t t gistinsert gistbeginscan gistgettuple gistgetbitmap gistrescan gistendscangistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions )); DESCR("GiST index access method"); #define GIST_AM_OID 783 ! DATA(insert OID = 2742 ( gin 0 4 f f f f f t f gininsert ginbeginscan gingettuple gingetbitmap ginrescan ginendscanginmarkpos ginrestrpos ginbuild ginbulkdelete ginvacuumcleanup gincostestimate ginoptions )); DESCR("GIN index access method"); #define GIN_AM_OID 2742 Index: src/include/catalog/pg_proc.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/catalog/pg_proc.h,v retrieving revision 1.447 diff -c -r1.447 pg_proc.h *** src/include/catalog/pg_proc.h 3 Mar 2007 19:52:46 -0000 1.447 --- src/include/catalog/pg_proc.h 8 Mar 2007 20:04:58 -0000 *************** *** 664,670 **** DATA(insert OID = 330 ( btgettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ btgettuple- _null_ )); DESCR("btree(internal)"); ! DATA(insert OID = 636 ( btgetmulti PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ btgetmulti - _null_ )); DESCR("btree(internal)"); DATA(insert OID = 331 ( btinsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null_ _null__null_ btinsert - _null_ )); DESCR("btree(internal)"); --- 664,670 ---- DATA(insert OID = 330 ( btgettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ btgettuple- _null_ )); DESCR("btree(internal)"); ! DATA(insert OID = 636 ( btgetbitmap PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ btgetbitmap - _null_ )); DESCR("btree(internal)"); DATA(insert OID = 331 ( btinsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null_ _null__null_ btinsert - _null_ )); DESCR("btree(internal)"); *************** *** 783,789 **** DATA(insert OID = 440 ( hashgettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ hashgettuple- _null_ )); DESCR("hash(internal)"); ! DATA(insert OID = 637 ( hashgetmulti PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ hashgetmulti - _null_ )); DESCR("hash(internal)"); DATA(insert OID = 441 ( hashinsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null__null_ _null_ hashinsert - _null_ )); DESCR("hash(internal)"); --- 783,789 ---- DATA(insert OID = 440 ( hashgettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ hashgettuple- _null_ )); DESCR("hash(internal)"); ! DATA(insert OID = 637 ( hashgetbitmap PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ hashgetbitmap - _null_ )); DESCR("hash(internal)"); DATA(insert OID = 441 ( hashinsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null__null_ _null_ hashinsert - _null_ )); DESCR("hash(internal)"); *************** *** 1051,1057 **** DATA(insert OID = 774 ( gistgettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ gistgettuple- _null_ )); DESCR("gist(internal)"); ! DATA(insert OID = 638 ( gistgetmulti PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ gistgetmulti - _null_ )); DESCR("gist(internal)"); DATA(insert OID = 775 ( gistinsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null__null_ _null_ gistinsert - _null_ )); DESCR("gist(internal)"); --- 1051,1057 ---- DATA(insert OID = 774 ( gistgettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ gistgettuple- _null_ )); DESCR("gist(internal)"); ! DATA(insert OID = 638 ( gistgetbitmap PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ gistgetbitmap - _null_ )); DESCR("gist(internal)"); DATA(insert OID = 775 ( gistinsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null__null_ _null_ gistinsert - _null_ )); DESCR("gist(internal)"); *************** *** 3967,3973 **** /* GIN */ DATA(insert OID = 2730 ( gingettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ gingettuple- _null_ )); DESCR("gin(internal)"); ! DATA(insert OID = 2731 ( gingetmulti PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ gingetmulti - _null_ )); DESCR("gin(internal)"); DATA(insert OID = 2732 ( gininsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null__null_ _null_ gininsert - _null_ )); DESCR("gin(internal)"); --- 3967,3973 ---- /* GIN */ DATA(insert OID = 2730 ( gingettuple PGNSP PGUID 12 1 0 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ gingettuple- _null_ )); DESCR("gin(internal)"); ! DATA(insert OID = 2731 ( gingetbitmap PGNSP PGUID 12 1 0 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ gingetbitmap - _null_ )); DESCR("gin(internal)"); DATA(insert OID = 2732 ( gininsert PGNSP PGUID 12 1 0 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null__null_ _null_ gininsert - _null_ )); DESCR("gin(internal)"); Index: src/include/nodes/tidbitmap.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/nodes/tidbitmap.h,v retrieving revision 1.5 diff -c -r1.5 tidbitmap.h *** src/include/nodes/tidbitmap.h 5 Jan 2007 22:19:56 -0000 1.5 --- src/include/nodes/tidbitmap.h 12 Mar 2007 12:07:03 -0000 *************** *** 36,41 **** --- 36,42 ---- { BlockNumber blockno; /* page number containing tuples */ int ntuples; /* -1 indicates lossy result */ + bool iscandidates; /* do the results need to be rechecked */ OffsetNumber offsets[1]; /* VARIABLE LENGTH ARRAY */ } TBMIterateResult; /* VARIABLE LENGTH STRUCT */ *************** *** 44,50 **** extern TIDBitmap *tbm_create(long maxbytes); extern void tbm_free(TIDBitmap *tbm); ! extern void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids); extern void tbm_union(TIDBitmap *a, const TIDBitmap *b); extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b); --- 45,51 ---- extern TIDBitmap *tbm_create(long maxbytes); extern void tbm_free(TIDBitmap *tbm); ! extern void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool candidates); extern void tbm_union(TIDBitmap *a, const TIDBitmap *b); extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b); Index: src/include/utils/rel.h =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/include/utils/rel.h,v retrieving revision 1.98 diff -c -r1.98 rel.h *** src/include/utils/rel.h 27 Feb 2007 23:48:10 -0000 1.98 --- src/include/utils/rel.h 7 Mar 2007 22:07:49 -0000 *************** *** 107,113 **** FmgrInfo aminsert; FmgrInfo ambeginscan; FmgrInfo amgettuple; ! FmgrInfo amgetmulti; FmgrInfo amrescan; FmgrInfo amendscan; FmgrInfo ammarkpos; --- 107,113 ---- FmgrInfo aminsert; FmgrInfo ambeginscan; FmgrInfo amgettuple; ! FmgrInfo amgetbitmap; FmgrInfo amrescan; FmgrInfo amendscan; FmgrInfo ammarkpos; Index: src/test/regress/parallel_schedule =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/test/regress/parallel_schedule,v retrieving revision 1.39 diff -c -r1.39 parallel_schedule *** src/test/regress/parallel_schedule 9 Feb 2007 03:35:35 -0000 1.39 --- src/test/regress/parallel_schedule 12 Mar 2007 11:04:17 -0000 *************** *** 61,67 **** # ---------- # The fourth group of parallel test # ---------- ! test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregatestransactions random portals arrays btree_index hash_index update namespace prepared_xacts delete test: privileges test: misc --- 61,67 ---- # ---------- # The fourth group of parallel test # ---------- ! test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregatesbitmapops transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete test: privileges test: misc Index: src/test/regress/serial_schedule =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/test/regress/serial_schedule,v retrieving revision 1.37 diff -c -r1.37 serial_schedule *** src/test/regress/serial_schedule 9 Feb 2007 03:35:35 -0000 1.37 --- src/test/regress/serial_schedule 12 Mar 2007 11:04:22 -0000 *************** *** 68,73 **** --- 68,74 ---- test: case test: join test: aggregates + test: bitmapops test: transactions ignore: random test: random Index: src/test/regress/expected/create_index.out =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/test/regress/expected/create_index.out,v retrieving revision 1.23 diff -c -r1.23 create_index.out *** src/test/regress/expected/create_index.out 9 Jan 2007 02:14:16 -0000 1.23 --- src/test/regress/expected/create_index.out 12 Mar 2007 11:11:08 -0000 *************** *** 315,320 **** --- 315,408 ---- 96 | {23,97,43} | {AAAAAAAAAA646,A87088} (1 row) + -- Repeat some of the above tests but make sure we exercise bitmapscans + SET enable_indexscan = OFF; + SELECT * FROM array_index_op_test WHERE i @> '{32}' ORDER BY seqno; + seqno | i | t + -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------ + 6 | {39,35,5,94,17,92,60,32} | {AAAAAAAAAAAAAAA35875,AAAAAAAAAAAAAAAA23657} + 74 | {32} | {AAAAAAAAAAAAAAAA1729,AAAAAAAAAAAAA22860,AAAAAA99807,AAAAA17383,AAAAAAAAAAAAAAA67062,AAAAAAAAAAA15165,AAAAAAAAAAA50956} + 77 | {97,15,32,17,55,59,18,37,50,39} | {AAAAAAAAAAAA67946,AAAAAA54032,AAAAAAAA81587,55847,AAAAAAAAAAAAAA28620,AAAAAAAAAAAAAAAAA43052,AAAAAA75463,AAAA49534,AAAAAAAA44066} + 89 | {40,32,17,6,30,88} | {AA44673,AAAAAAAAAAA6119,AAAAAAAAAAAAAAAA23657,AAAAAAAAAAAAAAAAAA47955,AAAAAAAAAAAAAAAA33598,AAAAAAAAAAA33576,AA44673} + 98 | {38,34,32,89} | {AAAAAAAAAAAAAAAAAA71621,AAAA8857,AAAAAAAAAAAAAAAAAAA65037,AAAAAAAAAAAAAAAA31334,AAAAAAAAAA48845} + 100 | {85,32,57,39,49,84,32,3,30} | {AAAAAAA80240,AAAAAAAAAAAAAAAA1729,AAAAA60038,AAAAAAAAAAA92631,AAAAAAAA9523} + (6 rows) + + SELECT * FROM array_index_op_test WHERE i && '{32}' ORDER BY seqno; + seqno | i | t + -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------ + 6 | {39,35,5,94,17,92,60,32} | {AAAAAAAAAAAAAAA35875,AAAAAAAAAAAAAAAA23657} + 74 | {32} | {AAAAAAAAAAAAAAAA1729,AAAAAAAAAAAAA22860,AAAAAA99807,AAAAA17383,AAAAAAAAAAAAAAA67062,AAAAAAAAAAA15165,AAAAAAAAAAA50956} + 77 | {97,15,32,17,55,59,18,37,50,39} | {AAAAAAAAAAAA67946,AAAAAA54032,AAAAAAAA81587,55847,AAAAAAAAAAAAAA28620,AAAAAAAAAAAAAAAAA43052,AAAAAA75463,AAAA49534,AAAAAAAA44066} + 89 | {40,32,17,6,30,88} | {AA44673,AAAAAAAAAAA6119,AAAAAAAAAAAAAAAA23657,AAAAAAAAAAAAAAAAAA47955,AAAAAAAAAAAAAAAA33598,AAAAAAAAAAA33576,AA44673} + 98 | {38,34,32,89} | {AAAAAAAAAAAAAAAAAA71621,AAAA8857,AAAAAAAAAAAAAAAAAAA65037,AAAAAAAAAAAAAAAA31334,AAAAAAAAAA48845} + 100 | {85,32,57,39,49,84,32,3,30} | {AAAAAAA80240,AAAAAAAAAAAAAAAA1729,AAAAA60038,AAAAAAAAAAA92631,AAAAAAAA9523} + (6 rows) + + SELECT * FROM array_index_op_test WHERE i @> '{17}' ORDER BY seqno; + seqno | i | t + -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------ + 6 | {39,35,5,94,17,92,60,32} | {AAAAAAAAAAAAAAA35875,AAAAAAAAAAAAAAAA23657} + 12 | {17,99,18,52,91,72,0,43,96,23} | {AAAAA33250,AAAAAAAAAAAAAAAAAAA85420,AAAAAAAAAAA33576} + 15 | {17,14,16,63,67} | {AA6416,AAAAAAAAAA646,AAAAA95309} + 19 | {52,82,17,74,23,46,69,51,75} | {AAAAAAAAAAAAA73084,AAAAA75968,AAAAAAAAAAAAAAAA14047,AAAAAAA80240,AAAAAAAAAAAAAAAAAAA1205,A68938} + 53 | {38,17} | {AAAAAAAAAAA21658} + 65 | {61,5,76,59,17} | {AAAAAA99807,AAAAA64741,AAAAAAAAAAA53908,AA21643,AAAAAAAAA10012} + 77 | {97,15,32,17,55,59,18,37,50,39} | {AAAAAAAAAAAA67946,AAAAAA54032,AAAAAAAA81587,55847,AAAAAAAAAAAAAA28620,AAAAAAAAAAAAAAAAA43052,AAAAAA75463,AAAA49534,AAAAAAAA44066} + 89 | {40,32,17,6,30,88} | {AA44673,AAAAAAAAAAA6119,AAAAAAAAAAAAAAAA23657,AAAAAAAAAAAAAAAAAA47955,AAAAAAAAAAAAAAAA33598,AAAAAAAAAAA33576,AA44673} + (8 rows) + + SELECT * FROM array_index_op_test WHERE i && '{17}' ORDER BY seqno; + seqno | i | t + -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------ + 6 | {39,35,5,94,17,92,60,32} | {AAAAAAAAAAAAAAA35875,AAAAAAAAAAAAAAAA23657} + 12 | {17,99,18,52,91,72,0,43,96,23} | {AAAAA33250,AAAAAAAAAAAAAAAAAAA85420,AAAAAAAAAAA33576} + 15 | {17,14,16,63,67} | {AA6416,AAAAAAAAAA646,AAAAA95309} + 19 | {52,82,17,74,23,46,69,51,75} | {AAAAAAAAAAAAA73084,AAAAA75968,AAAAAAAAAAAAAAAA14047,AAAAAAA80240,AAAAAAAAAAAAAAAAAAA1205,A68938} + 53 | {38,17} | {AAAAAAAAAAA21658} + 65 | {61,5,76,59,17} | {AAAAAA99807,AAAAA64741,AAAAAAAAAAA53908,AA21643,AAAAAAAAA10012} + 77 | {97,15,32,17,55,59,18,37,50,39} | {AAAAAAAAAAAA67946,AAAAAA54032,AAAAAAAA81587,55847,AAAAAAAAAAAAAA28620,AAAAAAAAAAAAAAAAA43052,AAAAAA75463,AAAA49534,AAAAAAAA44066} + 89 | {40,32,17,6,30,88} | {AA44673,AAAAAAAAAAA6119,AAAAAAAAAAAAAAAA23657,AAAAAAAAAAAAAAAAAA47955,AAAAAAAAAAAAAAAA33598,AAAAAAAAAAA33576,AA44673} + (8 rows) + + SELECT * FROM array_index_op_test WHERE i @> '{32,17}' ORDER BY seqno; + seqno | i | t + -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------ + 6 | {39,35,5,94,17,92,60,32} | {AAAAAAAAAAAAAAA35875,AAAAAAAAAAAAAAAA23657} + 77 | {97,15,32,17,55,59,18,37,50,39} | {AAAAAAAAAAAA67946,AAAAAA54032,AAAAAAAA81587,55847,AAAAAAAAAAAAAA28620,AAAAAAAAAAAAAAAAA43052,AAAAAA75463,AAAA49534,AAAAAAAA44066} + 89 | {40,32,17,6,30,88} | {AA44673,AAAAAAAAAAA6119,AAAAAAAAAAAAAAAA23657,AAAAAAAAAAAAAAAAAA47955,AAAAAAAAAAAAAAAA33598,AAAAAAAAAAA33576,AA44673} + (3 rows) + + SELECT * FROM array_index_op_test WHERE i && '{32,17}' ORDER BY seqno; + seqno | i | t + -------+---------------------------------+------------------------------------------------------------------------------------------------------------------------------------ + 6 | {39,35,5,94,17,92,60,32} | {AAAAAAAAAAAAAAA35875,AAAAAAAAAAAAAAAA23657} + 12 | {17,99,18,52,91,72,0,43,96,23} | {AAAAA33250,AAAAAAAAAAAAAAAAAAA85420,AAAAAAAAAAA33576} + 15 | {17,14,16,63,67} | {AA6416,AAAAAAAAAA646,AAAAA95309} + 19 | {52,82,17,74,23,46,69,51,75} | {AAAAAAAAAAAAA73084,AAAAA75968,AAAAAAAAAAAAAAAA14047,AAAAAAA80240,AAAAAAAAAAAAAAAAAAA1205,A68938} + 53 | {38,17} | {AAAAAAAAAAA21658} + 65 | {61,5,76,59,17} | {AAAAAA99807,AAAAA64741,AAAAAAAAAAA53908,AA21643,AAAAAAAAA10012} + 74 | {32} | {AAAAAAAAAAAAAAAA1729,AAAAAAAAAAAAA22860,AAAAAA99807,AAAAA17383,AAAAAAAAAAAAAAA67062,AAAAAAAAAAA15165,AAAAAAAAAAA50956} + 77 | {97,15,32,17,55,59,18,37,50,39} | {AAAAAAAAAAAA67946,AAAAAA54032,AAAAAAAA81587,55847,AAAAAAAAAAAAAA28620,AAAAAAAAAAAAAAAAA43052,AAAAAA75463,AAAA49534,AAAAAAAA44066} + 89 | {40,32,17,6,30,88} | {AA44673,AAAAAAAAAAA6119,AAAAAAAAAAAAAAAA23657,AAAAAAAAAAAAAAAAAA47955,AAAAAAAAAAAAAAAA33598,AAAAAAAAAAA33576,AA44673} + 98 | {38,34,32,89} | {AAAAAAAAAAAAAAAAAA71621,AAAA8857,AAAAAAAAAAAAAAAAAAA65037,AAAAAAAAAAAAAAAA31334,AAAAAAAAAA48845} + 100 | {85,32,57,39,49,84,32,3,30} | {AAAAAAA80240,AAAAAAAAAAAAAAAA1729,AAAAA60038,AAAAAAAAAAA92631,AAAAAAAA9523} + (11 rows) + + SELECT * FROM array_index_op_test WHERE i <@ '{38,34,32,89}' ORDER BY seqno; + seqno | i | t + -------+---------------+---------------------------------------------------------------------------------------------------------------------------- + 40 | {34} | {AAAAAAAAAAAAAA10611,AAAAAAAAAAAAAAAAAAA1205,AAAAAAAAAAA50956,AAAAAAAAAAAAAAAA31334,AAAAA70466,AAAAAAAA81587,AAAAAAA74623} + 74 | {32} | {AAAAAAAAAAAAAAAA1729,AAAAAAAAAAAAA22860,AAAAAA99807,AAAAA17383,AAAAAAAAAAAAAAA67062,AAAAAAAAAAA15165,AAAAAAAAAAA50956} + 98 | {38,34,32,89} | {AAAAAAAAAAAAAAAAAA71621,AAAA8857,AAAAAAAAAAAAAAAAAAA65037,AAAAAAAAAAAAAAAA31334,AAAAAAAAAA48845} + (3 rows) + + SELECT * FROM array_index_op_test WHERE i = '{47,77}' ORDER BY seqno; + seqno | i | t + -------+---------+----------------------------------------------------------------------------------------------------------------- + 95 | {47,77} | {AAAAAAAAAAAAAAAAA764,AAAAAAAAAAA74076,AAAAAAAAAA18107,AAAAA40681,AAAAAAAAAAAAAAA35875,AAAAA60038,AAAAAAA56483} + (1 row) + RESET enable_seqscan; RESET enable_indexscan; RESET enable_bitmapscan; Index: src/test/regress/expected/oidjoins.out =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/test/regress/expected/oidjoins.out,v retrieving revision 1.19 diff -c -r1.19 oidjoins.out *** src/test/regress/expected/oidjoins.out 30 Dec 2006 21:21:56 -0000 1.19 --- src/test/regress/expected/oidjoins.out 8 Mar 2007 20:13:31 -0000 *************** *** 65,76 **** ------+------------ (0 rows) ! SELECT ctid, amgetmulti FROM pg_catalog.pg_am fk ! WHERE amgetmulti != 0 AND ! NOT EXISTS(SELECT 1 FROM pg_catalog.pg_proc pk WHERE pk.oid = fk.amgetmulti); ! ctid | amgetmulti ! ------+------------ (0 rows) SELECT ctid, amrescan --- 65,76 ---- ------+------------ (0 rows) ! SELECT ctid, amgetbitmap FROM pg_catalog.pg_am fk ! WHERE amgetbitmap != 0 AND ! NOT EXISTS(SELECT 1 FROM pg_catalog.pg_proc pk WHERE pk.oid = fk.amgetbitmap); ! ctid | amgetbitmap ! ------+------------- (0 rows) SELECT ctid, amrescan Index: src/test/regress/sql/bitmapops.sql =================================================================== RCS file: src/test/regress/sql/bitmapops.sql diff -N src/test/regress/sql/bitmapops.sql *** /dev/null 1 Jan 1970 00:00:00 -0000 --- src/test/regress/sql/bitmapops.sql 12 Mar 2007 11:53:01 -0000 *************** *** 0 **** --- 1,41 ---- + -- Test bitmap AND and OR + + + -- Generate enough data that we can test the lossy bitmaps. + + -- There's 55 tuples per page in the table. 53 is just + -- below 55, so that an index scan with qual a = constant + -- will return at least one hit per page. 59 is just above + -- 55, so that an index scan with qual b = constant will return + -- hits on most but not all pages. 53 and 59 are prime, so that + -- there's a maximum number of a,b combinations in the table. + -- That allows us to test all the different combinations of + -- lossy and non-lossy pages with the minimum amount of data + + CREATE TABLE bmscantest (a int, b int, t text); + + INSERT INTO bmscantest + SELECT (r%53), (r%59), 'foooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' + FROM generate_series(1,70000) r; + + CREATE INDEX i_bmtest_a ON bmscantest(a); + CREATE INDEX i_bmtest_b ON bmscantest(b); + + -- We want to use bitmapscans. With default settings, the planner currently + -- chooses a bitmap scan for the queries below anyway, but let's make sure. + set enable_indexscan=false; + set enable_seqscan=false; + + -- Lower work_mem to trigger use of lossy bitmaps + set work_mem = 64; + + + -- Test bitmap-and. + SELECT count(*) FROM bmscantest WHERE a = 1 AND b = 1; + + -- Test bitmap-or. + SELECT count(*) FROM bmscantest WHERE a = 1 OR b = 1; + + + -- clean up + DROP TABLE bmscantest; Index: src/test/regress/sql/create_index.sql =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/test/regress/sql/create_index.sql,v retrieving revision 1.22 diff -c -r1.22 create_index.sql *** src/test/regress/sql/create_index.sql 9 Jan 2007 02:14:16 -0000 1.22 --- src/test/regress/sql/create_index.sql 12 Mar 2007 10:56:19 -0000 *************** *** 163,168 **** --- 163,179 ---- SELECT * FROM array_index_op_test WHERE t <@ '{AAAAAAAA72908,AAAAAAAAAAAAAAAAAAA17075,AA88409,AAAAAAAAAAAAAAAAAA36842,AAAAAAA48038,AAAAAAAAAAAAAA10611}'ORDER BY seqno; SELECT * FROM array_index_op_test WHERE t = '{AAAAAAAAAA646,A87088}' ORDER BY seqno; + -- Repeat some of the above tests but make sure we exercise bitmapscans + SET enable_indexscan = OFF; + + SELECT * FROM array_index_op_test WHERE i @> '{32}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i && '{32}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i @> '{17}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i && '{17}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i @> '{32,17}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i && '{32,17}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i <@ '{38,34,32,89}' ORDER BY seqno; + SELECT * FROM array_index_op_test WHERE i = '{47,77}' ORDER BY seqno; RESET enable_seqscan; RESET enable_indexscan; Index: src/test/regress/sql/oidjoins.sql =================================================================== RCS file: /home/hlinnaka/pgcvsrepository/pgsql/src/test/regress/sql/oidjoins.sql,v retrieving revision 1.19 diff -c -r1.19 oidjoins.sql *** src/test/regress/sql/oidjoins.sql 30 Dec 2006 21:21:56 -0000 1.19 --- src/test/regress/sql/oidjoins.sql 8 Mar 2007 20:13:13 -0000 *************** *** 33,42 **** FROM pg_catalog.pg_am fk WHERE amgettuple != 0 AND NOT EXISTS(SELECT 1 FROM pg_catalog.pg_proc pk WHERE pk.oid = fk.amgettuple); ! SELECT ctid, amgetmulti FROM pg_catalog.pg_am fk ! WHERE amgetmulti != 0 AND ! NOT EXISTS(SELECT 1 FROM pg_catalog.pg_proc pk WHERE pk.oid = fk.amgetmulti); SELECT ctid, amrescan FROM pg_catalog.pg_am fk WHERE amrescan != 0 AND --- 33,42 ---- FROM pg_catalog.pg_am fk WHERE amgettuple != 0 AND NOT EXISTS(SELECT 1 FROM pg_catalog.pg_proc pk WHERE pk.oid = fk.amgettuple); ! SELECT ctid, amgetbitmap FROM pg_catalog.pg_am fk ! WHERE amgetbitmap != 0 AND ! NOT EXISTS(SELECT 1 FROM pg_catalog.pg_proc pk WHERE pk.oid = fk.amgetbitmap); SELECT ctid, amrescan FROM pg_catalog.pg_am fk WHERE amrescan != 0 AND
pgsql-patches by date: