Hi,
Here is a patch by Heikki Linnakangas with changes for amgetmulti index
access method to amgetbitmap, which returns all matching tuples at once.
The patch also introduces support for candidate matches. The original
post is here:
http://archives.postgresql.org/pgsql-patches/2007-03/msg00163.php
I've made minor changes to the patch:
- fixed all rejects when applying it to the current CVS head.
- fixed counting ntids in gistnext if TIDBitmap is not null.
- added missing expected/bitmapops.out
It passes all regression tests on my system.
Regards,
--
Alexey Klyukin http://www.commandprompt.com/
The PostgreSQL Company - Command Prompt, Inc.
diff -c -N -r ./src/backend/access/gin/ginget.c ../pgsql.new/src/backend/access/gin/ginget.c
*** ./src/backend/access/gin/ginget.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/access/gin/ginget.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 476,509 ****
#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
--- 476,510 ----
#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
diff -c -N -r ./src/backend/access/gist/gistget.c ../pgsql.new/src/backend/access/gist/gistget.c
*** ./src/backend/access/gist/gistget.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/access/gist/gistget.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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));
ntids++;
! if(tbm != NULL)
! tbm_add_tuples(tbm, &it->t_tid, 1, false);
! else
{
+ *tid = scan->xs_ctup.t_self = it->t_tid;
+
LockBuffer(so->curbuf, GIST_UNLOCK);
! return ntids; /* always 1 */
}
}
}
diff -c -N -r ./src/backend/access/hash/hash.c ../pgsql.new/src/backend/access/hash/hash.c
*** ./src/backend/access/hash/hash.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/access/hash/hash.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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);
}
diff -c -N -r ./src/backend/access/index/indexam.c ../pgsql.new/src/backend/access/index/indexam.c
*** ./src/backend/access/index/indexam.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/access/index/indexam.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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"
/* ----------------------------------------------------------------
***************
*** 506,549 ****
}
/* ----------------
! * 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->indexRelation, *returned_tids);
! return found;
}
/* ----------------
--- 507,545 ----
}
/* ----------------
! * index_getbitmap - get all tuples at once 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->indexRelation, ntids);
! return ntids;
}
/* ----------------
diff -c -N -r ./src/backend/access/nbtree/nbtree.c ../pgsql.new/src/backend/access/nbtree/nbtree.c
*** ./src/backend/access/nbtree/nbtree.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/access/nbtree/nbtree.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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);
}
/*
diff -c -N -r ./src/backend/executor/nodeBitmapHeapscan.c ../pgsql.new/src/backend/executor/nodeBitmapHeapscan.c
*** ./src/backend/executor/nodeBitmapHeapscan.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/executor/nodeBitmapHeapscan.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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);
diff -c -N -r ./src/backend/executor/nodeBitmapIndexscan.c ../pgsql.new/src/backend/executor/nodeBitmapIndexscan.c
*** ./src/backend/executor/nodeBitmapIndexscan.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/executor/nodeBitmapIndexscan.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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 */
diff -c -N -r ./src/backend/nodes/tidbitmap.c ../pgsql.new/src/backend/nodes/tidbitmap.c
*** ./src/backend/nodes/tidbitmap.c 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/backend/nodes/tidbitmap.c 2007-06-19 14:41:46.000000000 +0300
***************
*** 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;
}
***************
*** 936,938 ****
--- 942,994 ----
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
diff -c -N -r ./src/include/access/genam.h ../pgsql.new/src/include/access/genam.h
*** ./src/include/access/genam.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/access/genam.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 17,22 ****
--- 17,23 ----
#include "access/relscan.h"
#include "access/sdir.h"
#include "nodes/primnodes.h"
+ #include "nodes/tidbitmap.h"
#include "storage/lock.h"
/*
***************
*** 109,117 ****
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,
--- 110,116 ----
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,
diff -c -N -r ./src/include/access/gin.h ../pgsql.new/src/include/access/gin.h
*** ./src/include/access/gin.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/access/gin.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 421,427 ****
#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 */
--- 421,427 ----
#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 */
diff -c -N -r ./src/include/access/gist_private.h ../pgsql.new/src/include/access/gist_private.h
*** ./src/include/access/gist_private.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/access/gist_private.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 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 */
diff -c -N -r ./src/include/access/hash.h ../pgsql.new/src/include/access/hash.h
*** ./src/include/access/hash.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/access/hash.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 233,239 ****
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);
--- 233,239 ----
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);
diff -c -N -r ./src/include/access/nbtree.h ../pgsql.new/src/include/access/nbtree.h
*** ./src/include/access/nbtree.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/access/nbtree.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 500,506 ****
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);
--- 500,506 ----
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);
diff -c -N -r ./src/include/catalog/pg_am.h ../pgsql.new/src/include/catalog/pg_am.h
*** ./src/include/catalog/pg_am.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/catalog/pg_am.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 56,62 ****
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 */
--- 56,62 ----
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 */
***************
*** 94,100 ****
#define Anum_pg_am_aminsert 12
#define Anum_pg_am_ambeginscan 13
#define Anum_pg_am_amgettuple 14
! #define Anum_pg_am_amgetmulti 15
#define Anum_pg_am_amrescan 16
#define Anum_pg_am_amendscan 17
#define Anum_pg_am_ammarkpos 18
--- 94,100 ----
#define Anum_pg_am_aminsert 12
#define Anum_pg_am_ambeginscan 13
#define Anum_pg_am_amgettuple 14
! #define Anum_pg_am_amgetbitmap 15
#define Anum_pg_am_amrescan 16
#define Anum_pg_am_amendscan 17
#define Anum_pg_am_ammarkpos 18
***************
*** 110,125 ****
* ----------------
*/
! DATA(insert OID = 403 ( btree 5 1 t t t t t t f t btinsert btbeginscan btgettuple btgetmulti btrescan btendscan btmarkpos btrestrpos 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 f hashinsert hashbeginscan hashgettuple hashgetmulti hashrescan hashendscan hashmarkpos 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 t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos 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 f t f gininsert ginbeginscan gingettuple gingetmulti ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
DESCR("GIN index access method");
#define GIN_AM_OID 2742
--- 110,125 ----
* ----------------
*/
! DATA(insert OID = 403 ( btree 5 1 t t t t t t f t btinsert btbeginscan btgettuple btgetbitmap btrescan btendscan btmarkpos btrestrpos 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 f hashinsert hashbeginscan hashgettuple hashgetbitmap hashrescan hashendscan hashmarkpos 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 t gistinsert gistbeginscan gistgettuple gistgetbitmap gistrescan gistendscan gistmarkpos 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 f t f gininsert ginbeginscan gingettuple gingetbitmap ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
DESCR("GIN index access method");
#define GIN_AM_OID 2742
diff -c -N -r ./src/include/catalog/pg_proc.h ../pgsql.new/src/include/catalog/pg_proc.h
*** ./src/include/catalog/pg_proc.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/catalog/pg_proc.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 658,664 ****
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)");
--- 658,664 ----
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)");
***************
*** 777,783 ****
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)");
--- 777,783 ----
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)");
***************
*** 1045,1051 ****
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)");
--- 1045,1051 ----
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)");
***************
*** 3941,3947 ****
/* 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)");
--- 3941,3947 ----
/* 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)");
diff -c -N -r ./src/include/nodes/tidbitmap.h ../pgsql.new/src/include/nodes/tidbitmap.h
*** ./src/include/nodes/tidbitmap.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/nodes/tidbitmap.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 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);
diff -c -N -r ./src/include/utils/rel.h ../pgsql.new/src/include/utils/rel.h
*** ./src/include/utils/rel.h 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/include/utils/rel.h 2007-06-19 14:41:46.000000000 +0300
***************
*** 98,104 ****
FmgrInfo aminsert;
FmgrInfo ambeginscan;
FmgrInfo amgettuple;
! FmgrInfo amgetmulti;
FmgrInfo amrescan;
FmgrInfo amendscan;
FmgrInfo ammarkpos;
--- 98,104 ----
FmgrInfo aminsert;
FmgrInfo ambeginscan;
FmgrInfo amgettuple;
! FmgrInfo amgetbitmap;
FmgrInfo amrescan;
FmgrInfo amendscan;
FmgrInfo ammarkpos;
diff -c -N -r ./src/test/regress/expected/bitmapops.out ../pgsql.new/src/test/regress/expected/bitmapops.out
*** ./src/test/regress/expected/bitmapops.out 1970-01-01 03:00:00.000000000 +0300
--- ../pgsql.new/src/test/regress/expected/bitmapops.out 2007-06-19 14:41:46.000000000 +0300
***************
*** 0 ****
--- 1,38 ----
+ -- 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;
+ count
+ -------
+ 23
+ (1 row)
+
+ -- Test bitmap-or.
+ SELECT count(*) FROM bmscantest WHERE a = 1 OR b = 1;
+ count
+ -------
+ 2485
+ (1 row)
+
+ -- clean up
+ DROP TABLE bmscantest;
diff -c -N -r ./src/test/regress/expected/create_index.out ../pgsql.new/src/test/regress/expected/create_index.out
*** ./src/test/regress/expected/create_index.out 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/test/regress/expected/create_index.out 2007-06-19 14:41:46.000000000 +0300
***************
*** 327,332 ****
--- 327,420 ----
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;
diff -c -N -r ./src/test/regress/expected/oidjoins.out ../pgsql.new/src/test/regress/expected/oidjoins.out
*** ./src/test/regress/expected/oidjoins.out 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/test/regress/expected/oidjoins.out 2007-06-19 14:41:46.000000000 +0300
***************
*** 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
diff -c -N -r ./src/test/regress/parallel_schedule ../pgsql.new/src/test/regress/parallel_schedule
*** ./src/test/regress/parallel_schedule 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/test/regress/parallel_schedule 2007-06-19 14:41:46.000000000 +0300
***************
*** 61,67 ****
# ----------
# The fourth group of parallel test
# ----------
! test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions 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 aggregates bitmapops transactions random portals arrays btree_index hash_index update namespace prepared_xacts delete
test: privileges
test: misc
diff -c -N -r ./src/test/regress/serial_schedule ../pgsql.new/src/test/regress/serial_schedule
*** ./src/test/regress/serial_schedule 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/test/regress/serial_schedule 2007-06-19 14:41:46.000000000 +0300
***************
*** 69,74 ****
--- 69,75 ----
test: case
test: join
test: aggregates
+ test: bitmapops
test: transactions
ignore: random
test: random
diff -c -N -r ./src/test/regress/sql/bitmapops.sql ../pgsql.new/src/test/regress/sql/bitmapops.sql
*** ./src/test/regress/sql/bitmapops.sql 1970-01-01 03:00:00.000000000 +0300
--- ../pgsql.new/src/test/regress/sql/bitmapops.sql 2007-06-19 14:41:46.000000000 +0300
***************
*** 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;
diff -c -N -r ./src/test/regress/sql/create_index.sql ../pgsql.new/src/test/regress/sql/create_index.sql
*** ./src/test/regress/sql/create_index.sql 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/test/regress/sql/create_index.sql 2007-06-19 14:41:46.000000000 +0300
***************
*** 167,172 ****
--- 167,183 ----
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;
diff -c -N -r ./src/test/regress/sql/oidjoins.sql ../pgsql.new/src/test/regress/sql/oidjoins.sql
*** ./src/test/regress/sql/oidjoins.sql 2007-06-19 14:37:49.000000000 +0300
--- ../pgsql.new/src/test/regress/sql/oidjoins.sql 2007-06-19 14:41:46.000000000 +0300
***************
*** 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
---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match
