diff options
Diffstat (limited to 'src')
30 files changed, 2783 insertions, 76 deletions
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 4b2abb9e7b4..e26406365de 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994-5, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/commands/explain.c,v 1.132 2005/04/16 20:07:35 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/commands/explain.c,v 1.133 2005/04/19 22:35:10 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -423,6 +423,12 @@ explain_outNode(StringInfo str, case T_Append: pname = "Append"; break; + case T_BitmapAnd: + pname = "BitmapAnd"; + break; + case T_BitmapOr: + pname = "BitmapOr"; + break; case T_NestLoop: switch (((NestLoop *) plan)->join.jointype) { @@ -498,6 +504,12 @@ explain_outNode(StringInfo str, case T_IndexScan: pname = "Index Scan"; break; + case T_BitmapIndexScan: + pname = "Bitmap Index Scan"; + break; + case T_BitmapHeapScan: + pname = "Bitmap Heap Scan"; + break; case T_TidScan: pname = "Tid Scan"; break; @@ -586,6 +598,7 @@ explain_outNode(StringInfo str, } /* FALL THRU */ case T_SeqScan: + case T_BitmapHeapScan: case T_TidScan: if (((Scan *) plan)->scanrelid > 0) { @@ -606,6 +619,10 @@ explain_outNode(StringInfo str, quote_identifier(rte->eref->aliasname)); } break; + case T_BitmapIndexScan: + appendStringInfo(str, " on %s", + quote_identifier(get_rel_name(((BitmapIndexScan *) plan)->indxid))); + break; case T_SubqueryScan: if (((Scan *) plan)->scanrelid > 0) { @@ -696,6 +713,21 @@ explain_outNode(StringInfo str, outer_plan, str, indent, es); break; + case T_BitmapIndexScan: + show_scan_qual(((BitmapIndexScan *) plan)->indxqualorig, false, + "Index Cond", + ((Scan *) plan)->scanrelid, + outer_plan, + str, indent, es); + break; + case T_BitmapHeapScan: + /* XXX do we want to show this in production? */ + show_scan_qual(((BitmapHeapScan *) plan)->bitmapqualorig, false, + "Recheck Cond", + ((Scan *) plan)->scanrelid, + outer_plan, + str, indent, es); + /* FALL THRU */ case T_SeqScan: case T_TidScan: case T_SubqueryScan: @@ -857,6 +889,54 @@ explain_outNode(StringInfo str, } } + if (IsA(plan, BitmapAnd)) + { + BitmapAnd *bitmapandplan = (BitmapAnd *) plan; + BitmapAndState *bitmapandstate = (BitmapAndState *) planstate; + ListCell *lst; + int j; + + j = 0; + foreach(lst, bitmapandplan->bitmapplans) + { + Plan *subnode = (Plan *) lfirst(lst); + + for (i = 0; i < indent; i++) + appendStringInfo(str, " "); + appendStringInfo(str, " -> "); + + explain_outNode(str, subnode, + bitmapandstate->bitmapplans[j], + NULL, + indent + 3, es); + j++; + } + } + + if (IsA(plan, BitmapOr)) + { + BitmapOr *bitmaporplan = (BitmapOr *) plan; + BitmapOrState *bitmaporstate = (BitmapOrState *) planstate; + ListCell *lst; + int j; + + j = 0; + foreach(lst, bitmaporplan->bitmapplans) + { + Plan *subnode = (Plan *) lfirst(lst); + + for (i = 0; i < indent; i++) + appendStringInfo(str, " "); + appendStringInfo(str, " -> "); + + explain_outNode(str, subnode, + bitmaporstate->bitmapplans[j], + NULL, + indent + 3, es); + j++; + } + } + if (IsA(plan, SubqueryScan)) { SubqueryScan *subqueryscan = (SubqueryScan *) plan; diff --git a/src/backend/executor/Makefile b/src/backend/executor/Makefile index 7c0bc25352c..e9caf7d8373 100644 --- a/src/backend/executor/Makefile +++ b/src/backend/executor/Makefile @@ -4,7 +4,7 @@ # Makefile for executor # # IDENTIFICATION -# $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.22 2003/11/29 19:51:48 pgsql Exp $ +# $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.23 2005/04/19 22:35:11 tgl Exp $ # #------------------------------------------------------------------------- @@ -14,7 +14,9 @@ include $(top_builddir)/src/Makefile.global OBJS = execAmi.o execGrouping.o execJunk.o execMain.o \ execProcnode.o execQual.o execScan.o execTuples.o \ - execUtils.o functions.o instrument.o nodeAppend.o nodeAgg.o nodeHash.o \ + execUtils.o functions.o instrument.o nodeAppend.o nodeAgg.o \ + nodeBitmapAnd.o nodeBitmapOr.o \ + nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \ nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \ nodeNestloop.o nodeFunctionscan.o nodeResult.o nodeSeqscan.o \ nodeSetOp.o nodeSort.o nodeUnique.o nodeLimit.o nodeGroup.o \ diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c index 008768c3942..ddcd37ae286 100644 --- a/src/backend/executor/execAmi.c +++ b/src/backend/executor/execAmi.c @@ -6,7 +6,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.82 2004/12/31 21:59:45 pgsql Exp $ + * $PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.83 2005/04/19 22:35:11 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -19,6 +19,10 @@ #include "executor/instrument.h" #include "executor/nodeAgg.h" #include "executor/nodeAppend.h" +#include "executor/nodeBitmapAnd.h" +#include "executor/nodeBitmapHeapscan.h" +#include "executor/nodeBitmapIndexscan.h" +#include "executor/nodeBitmapOr.h" #include "executor/nodeFunctionscan.h" #include "executor/nodeGroup.h" #include "executor/nodeGroup.h" @@ -107,6 +111,14 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt) ExecReScanAppend((AppendState *) node, exprCtxt); break; + case T_BitmapAndState: + ExecReScanBitmapAnd((BitmapAndState *) node, exprCtxt); + break; + + case T_BitmapOrState: + ExecReScanBitmapOr((BitmapOrState *) node, exprCtxt); + break; + case T_SeqScanState: ExecSeqReScan((SeqScanState *) node, exprCtxt); break; @@ -115,6 +127,14 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt) ExecIndexReScan((IndexScanState *) node, exprCtxt); break; + case T_BitmapIndexScanState: + ExecBitmapIndexReScan((BitmapIndexScanState *) node, exprCtxt); + break; + + case T_BitmapHeapScanState: + ExecBitmapHeapReScan((BitmapHeapScanState *) node, exprCtxt); + break; + case T_TidScanState: ExecTidReScan((TidScanState *) node, exprCtxt); break; @@ -380,6 +400,7 @@ ExecMayReturnRawTuples(PlanState *node) /* Table scan nodes */ case T_SeqScanState: case T_IndexScanState: + case T_BitmapHeapScanState: case T_TidScanState: case T_SubqueryScanState: case T_FunctionScanState: diff --git a/src/backend/executor/execProcnode.c b/src/backend/executor/execProcnode.c index 555668e7799..28f67a2562f 100644 --- a/src/backend/executor/execProcnode.c +++ b/src/backend/executor/execProcnode.c @@ -12,7 +12,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.49 2005/04/16 20:07:35 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.50 2005/04/19 22:35:11 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -81,6 +81,10 @@ #include "executor/instrument.h" #include "executor/nodeAgg.h" #include "executor/nodeAppend.h" +#include "executor/nodeBitmapAnd.h" +#include "executor/nodeBitmapHeapscan.h" +#include "executor/nodeBitmapIndexscan.h" +#include "executor/nodeBitmapOr.h" #include "executor/nodeFunctionscan.h" #include "executor/nodeGroup.h" #include "executor/nodeHash.h" @@ -140,6 +144,14 @@ ExecInitNode(Plan *node, EState *estate) result = (PlanState *) ExecInitAppend((Append *) node, estate); break; + case T_BitmapAnd: + result = (PlanState *) ExecInitBitmapAnd((BitmapAnd *) node, estate); + break; + + case T_BitmapOr: + result = (PlanState *) ExecInitBitmapOr((BitmapOr *) node, estate); + break; + /* * scan nodes */ @@ -151,6 +163,14 @@ ExecInitNode(Plan *node, EState *estate) result = (PlanState *) ExecInitIndexScan((IndexScan *) node, estate); break; + case T_BitmapIndexScan: + result = (PlanState *) ExecInitBitmapIndexScan((BitmapIndexScan *) node, estate); + break; + + case T_BitmapHeapScan: + result = (PlanState *) ExecInitBitmapHeapScan((BitmapHeapScan *) node, estate); + break; + case T_TidScan: result = (PlanState *) ExecInitTidScan((TidScan *) node, estate); break; @@ -290,6 +310,10 @@ ExecProcNode(PlanState *node) result = ExecAppend((AppendState *) node); break; + /* BitmapAndState does not yield tuples */ + + /* BitmapOrState does not yield tuples */ + /* * scan nodes */ @@ -301,6 +325,12 @@ ExecProcNode(PlanState *node) result = ExecIndexScan((IndexScanState *) node); break; + /* BitmapIndexScanState does not yield tuples */ + + case T_BitmapHeapScanState: + result = ExecBitmapHeapScan((BitmapHeapScanState *) node); + break; + case T_TidScanState: result = ExecTidScan((TidScanState *) node); break; @@ -409,6 +439,18 @@ MultiExecProcNode(PlanState *node) result = MultiExecHash((HashState *) node); break; + case T_BitmapIndexScanState: + result = MultiExecBitmapIndexScan((BitmapIndexScanState *) node); + break; + + case T_BitmapAndState: + result = MultiExecBitmapAnd((BitmapAndState *) node); + break; + + case T_BitmapOrState: + result = MultiExecBitmapOr((BitmapOrState *) node); + break; + default: elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node)); result = NULL; @@ -442,6 +484,12 @@ ExecCountSlotsNode(Plan *node) case T_Append: return ExecCountSlotsAppend((Append *) node); + case T_BitmapAnd: + return ExecCountSlotsBitmapAnd((BitmapAnd *) node); + + case T_BitmapOr: + return ExecCountSlotsBitmapOr((BitmapOr *) node); + /* * scan nodes */ @@ -451,6 +499,12 @@ ExecCountSlotsNode(Plan *node) case T_IndexScan: return ExecCountSlotsIndexScan((IndexScan *) node); + case T_BitmapIndexScan: + return ExecCountSlotsBitmapIndexScan((BitmapIndexScan *) node); + + case T_BitmapHeapScan: + return ExecCountSlotsBitmapHeapScan((BitmapHeapScan *) node); + case T_TidScan: return ExecCountSlotsTidScan((TidScan *) node); @@ -554,6 +608,14 @@ ExecEndNode(PlanState *node) ExecEndAppend((AppendState *) node); break; + case T_BitmapAndState: + ExecEndBitmapAnd((BitmapAndState *) node); + break; + + case T_BitmapOrState: + ExecEndBitmapOr((BitmapOrState *) node); + break; + /* * scan nodes */ @@ -565,6 +627,14 @@ ExecEndNode(PlanState *node) ExecEndIndexScan((IndexScanState *) node); break; + case T_BitmapIndexScanState: + ExecEndBitmapIndexScan((BitmapIndexScanState *) node); + break; + + case T_BitmapHeapScanState: + ExecEndBitmapHeapScan((BitmapHeapScanState *) node); + break; + case T_TidScanState: ExecEndTidScan((TidScanState *) node); break; diff --git a/src/backend/executor/nodeBitmapAnd.c b/src/backend/executor/nodeBitmapAnd.c new file mode 100644 index 00000000000..4af1624012b --- /dev/null +++ b/src/backend/executor/nodeBitmapAnd.c @@ -0,0 +1,208 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapAnd.c + * routines to handle BitmapAnd nodes. + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeBitmapAnd.c,v 1.1 2005/04/19 22:35:12 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +/* INTERFACE ROUTINES + * ExecInitBitmapAnd - initialize the BitmapAnd node + * MultiExecBitmapAnd - retrieve the result bitmap from the node + * ExecEndBitmapAnd - shut down the BitmapAnd node + * ExecReScanBitmapAnd - rescan the BitmapAnd node + * + * NOTES + * BitmapAnd nodes don't make use of their left and right + * subtrees, rather they maintain a list of subplans, + * much like Append nodes. The logic is much simpler than + * Append, however, since we needn't cope with forward/backward + * execution. + */ + +#include "postgres.h" + +#include "executor/execdebug.h" +#include "executor/instrument.h" +#include "executor/nodeBitmapAnd.h" + + +/* ---------------------------------------------------------------- + * ExecInitBitmapAnd + * + * Begin all of the subscans of the BitmapAnd node. + * ---------------------------------------------------------------- + */ +BitmapAndState * +ExecInitBitmapAnd(BitmapAnd *node, EState *estate) +{ + BitmapAndState *bitmapandstate = makeNode(BitmapAndState); + PlanState **bitmapplanstates; + int nplans; + int i; + Plan *initNode; + + CXT1_printf("ExecInitBitmapAnd: context is %d\n", CurrentMemoryContext); + + /* + * Set up empty vector of subplan states + */ + nplans = list_length(node->bitmapplans); + + bitmapplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *)); + + /* + * create new BitmapAndState for our BitmapAnd node + */ + bitmapandstate->ps.plan = (Plan *) node; + bitmapandstate->ps.state = estate; + bitmapandstate->bitmapplans = bitmapplanstates; + bitmapandstate->nplans = nplans; + + /* + * Miscellaneous initialization + * + * BitmapAnd plans don't have expression contexts because they never call + * ExecQual or ExecProject. They don't need any tuple slots either. + */ + +#define BITMAPAND_NSLOTS 0 + + /* + * call ExecInitNode on each of the plans to be executed and save the + * results into the array "bitmapplanstates". + */ + for (i = 0; i < nplans; i++) + { + initNode = (Plan *) list_nth(node->bitmapplans, i); + bitmapplanstates[i] = ExecInitNode(initNode, estate); + } + + return bitmapandstate; +} + +int +ExecCountSlotsBitmapAnd(BitmapAnd *node) +{ + ListCell *plan; + int nSlots = 0; + + foreach(plan, node->bitmapplans) + nSlots += ExecCountSlotsNode((Plan *) lfirst(plan)); + return nSlots + BITMAPAND_NSLOTS; +} + +/* ---------------------------------------------------------------- + * MultiExecBitmapAnd + * ---------------------------------------------------------------- + */ +Node * +MultiExecBitmapAnd(BitmapAndState *node) +{ + PlanState **bitmapplans; + int nplans; + int i; + TIDBitmap *result = NULL; + + /* must provide our own instrumentation support */ + if (node->ps.instrument) + InstrStartNode(node->ps.instrument); + + /* + * get information from the node + */ + bitmapplans = node->bitmapplans; + nplans = node->nplans; + + /* + * Scan all the subplans and AND their result bitmaps + */ + for (i = 0; i < nplans; i++) + { + PlanState *subnode = bitmapplans[i]; + TIDBitmap *subresult; + + subresult = (TIDBitmap *) MultiExecProcNode(subnode); + + if (!subresult || !IsA(subresult, TIDBitmap)) + elog(ERROR, "unrecognized result from subplan"); + + if (result == NULL) + result = subresult; /* first subplan */ + else + { + tbm_intersect(result, subresult); + tbm_free(subresult); + } + } + + if (result == NULL) + elog(ERROR, "BitmapAnd doesn't support zero inputs"); + + /* must provide our own instrumentation support */ + if (node->ps.instrument) + InstrStopNodeMulti(node->ps.instrument, 0 /* XXX */); + + return (Node *) result; +} + +/* ---------------------------------------------------------------- + * ExecEndBitmapAnd + * + * Shuts down the subscans of the BitmapAnd node. + * + * Returns nothing of interest. + * ---------------------------------------------------------------- + */ +void +ExecEndBitmapAnd(BitmapAndState *node) +{ + PlanState **bitmapplans; + int nplans; + int i; + + /* + * get information from the node + */ + bitmapplans = node->bitmapplans; + nplans = node->nplans; + + /* + * shut down each of the subscans (that we've initialized) + */ + for (i = 0; i < nplans; i++) + { + if (bitmapplans[i]) + ExecEndNode(bitmapplans[i]); + } +} + +void +ExecReScanBitmapAnd(BitmapAndState *node, ExprContext *exprCtxt) +{ + int i; + + for (i = 0; i < node->nplans; i++) + { + PlanState *subnode = node->bitmapplans[i]; + + /* + * ExecReScan doesn't know about my subplans, so I have to do + * changed-parameter signaling myself. + */ + if (node->ps.chgParam != NULL) + UpdateChangedParamSet(subnode, node->ps.chgParam); + + /* + * Always rescan the inputs immediately, to ensure we can pass down + * any outer tuple that might be used in index quals. + */ + ExecReScan(subnode, exprCtxt); + } +} diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c new file mode 100644 index 00000000000..141e29dd293 --- /dev/null +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -0,0 +1,499 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapHeapscan.c + * Routines to support bitmapped scans of relations + * + * NOTE: it is critical that this plan type only be used with MVCC-compliant + * snapshots (ie, regular snapshots, not SnapshotNow or one of the other + * special snapshots). The reason is that since index and heap scans are + * decoupled, there can be no assurance that the index tuple prompting a + * visit to a particular heap TID still exists when the visit is made. + * Therefore the tuple might not exist anymore either (which is OK because + * heap_fetch will cope) --- but worse, the tuple slot could have been + * re-used for a newer tuple. With an MVCC snapshot the newer tuple is + * certain to fail the time qual and so it will not be mistakenly returned. + * With SnapshotNow we might return a tuple that doesn't meet the required + * index qual conditions. + * + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeBitmapHeapscan.c,v 1.1 2005/04/19 22:35:12 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +/* + * INTERFACE ROUTINES + * ExecBitmapHeapScan scans a relation using bitmap info + * ExecBitmapHeapNext workhorse for above + * ExecInitBitmapHeapScan creates and initializes state info. + * ExecBitmapHeapReScan prepares to rescan the plan. + * ExecEndBitmapHeapScan releases all storage. + */ +#include "postgres.h" + +#include "access/heapam.h" +#include "executor/execdebug.h" +#include "executor/nodeBitmapHeapscan.h" +#include "parser/parsetree.h" + + +static TupleTableSlot *BitmapHeapNext(BitmapHeapScanState *node); + + +/* ---------------------------------------------------------------- + * BitmapHeapNext + * + * Retrieve next tuple from the BitmapHeapScan node's currentRelation + * ---------------------------------------------------------------- + */ +static TupleTableSlot * +BitmapHeapNext(BitmapHeapScanState *node) +{ + EState *estate; + ExprContext *econtext; + HeapScanDesc scandesc; + Index scanrelid; + TIDBitmap *tbm; + TBMIterateResult *tbmres; + OffsetNumber targoffset; + TupleTableSlot *slot; + + /* + * extract necessary information from index scan node + */ + estate = node->ss.ps.state; + econtext = node->ss.ps.ps_ExprContext; + slot = node->ss.ss_ScanTupleSlot; + scandesc = node->ss.ss_currentScanDesc; + scanrelid = ((BitmapHeapScan *) node->ss.ps.plan)->scan.scanrelid; + tbm = node->tbm; + tbmres = node->tbmres; + + /* + * Clear any reference to the previously returned tuple. The idea + * here is to not have the tuple slot be the last holder of a pin on + * that tuple's buffer; if it is, we'll need a separate visit to the + * bufmgr to release the buffer. By clearing here, we get to have the + * release done by ReleaseAndReadBuffer, below. + */ + ExecClearTuple(slot); + + /* + * Check if we are evaluating PlanQual for tuple of this relation. + * Additional checking is not good, but no other way for now. We could + * introduce new nodes for this case and handle IndexScan --> NewNode + * switching in Init/ReScan plan... + */ + if (estate->es_evTuple != NULL && + estate->es_evTuple[scanrelid - 1] != NULL) + { + if (estate->es_evTupleNull[scanrelid - 1]) + return slot; /* return empty slot */ + + ExecStoreTuple(estate->es_evTuple[scanrelid - 1], + slot, InvalidBuffer, false); + + /* Does the tuple meet the original qual conditions? */ + econtext->ecxt_scantuple = slot; + + ResetExprContext(econtext); + + if (!ExecQual(node->bitmapqualorig, econtext, false)) + ExecClearTuple(slot); /* would not be returned by scan */ + + /* Flag for the next call that no more tuples */ + estate->es_evTupleNull[scanrelid - 1] = true; + + return slot; + } + + /* + * If we haven't yet performed the underlying index scan, do it, + * and prepare the bitmap to be iterated over. + */ + if (tbm == NULL) + { + tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node)); + + if (!tbm || !IsA(tbm, TIDBitmap)) + elog(ERROR, "unrecognized result from subplan"); + + node->tbm = tbm; + node->tbmres = tbmres = NULL; + + tbm_begin_iterate(tbm); + } + + for (;;) + { + /* + * Get next page of results if needed + */ + if (tbmres == NULL) + { + node->tbmres = tbmres = tbm_iterate(tbm); + if (tbmres == NULL) + { + /* no more entries in the bitmap */ + break; + } + + /* + * Ignore any claimed entries past what we think is the end of + * the relation. (This is probably not necessary given that we + * got AccessShareLock before performing any of the indexscans, + * but let's be safe.) + */ + if (tbmres->blockno >= scandesc->rs_nblocks) + { + node->tbmres = tbmres = NULL; + continue; + } + + /* + * Acquire pin on the current heap page. We'll hold the pin + * until done looking at the page. We trade in any pin we + * held before. + */ + scandesc->rs_cbuf = ReleaseAndReadBuffer(scandesc->rs_cbuf, + scandesc->rs_rd, + tbmres->blockno); + + /* + * Determine how many entries we need to look at on this page. + * If the bitmap is lossy then we need to look at each physical + * item pointer; otherwise we just look through the offsets + * listed in tbmres. + */ + if (tbmres->ntuples >= 0) + { + /* non-lossy case */ + node->minslot = 0; + node->maxslot = tbmres->ntuples - 1; + } + else + { + /* lossy case */ + Page dp; + + LockBuffer(scandesc->rs_cbuf, BUFFER_LOCK_SHARE); + dp = (Page) BufferGetPage(scandesc->rs_cbuf); + + node->minslot = FirstOffsetNumber; + node->maxslot = PageGetMaxOffsetNumber(dp); + + LockBuffer(scandesc->rs_cbuf, BUFFER_LOCK_UNLOCK); + } + + /* + * Set curslot to first slot to examine + */ + node->curslot = node->minslot; + } + else + { + /* + * Continuing in previously obtained page; advance curslot + */ + node->curslot++; + } + + /* + * Out of range? If so, nothing more to look at on this page + */ + if (node->curslot < node->minslot || node->curslot > node->maxslot) + { + node->tbmres = tbmres = NULL; + continue; + } + + /* + * Okay to try to fetch the tuple + */ + if (tbmres->ntuples >= 0) + { + /* non-lossy case */ + targoffset = tbmres->offsets[node->curslot]; + } + else + { + /* lossy case */ + targoffset = (OffsetNumber) node->curslot; + } + + ItemPointerSet(&scandesc->rs_ctup.t_self, tbmres->blockno, targoffset); + + /* + * Fetch the heap tuple and see if it matches the snapshot. + * We use heap_release_fetch to avoid useless bufmgr traffic. + */ + if (heap_release_fetch(scandesc->rs_rd, + scandesc->rs_snapshot, + &scandesc->rs_ctup, + &scandesc->rs_cbuf, + true, + &scandesc->rs_pgstat_info)) + { + /* + * Set up the result slot to point to this tuple. + * Note that the slot acquires a pin on the buffer. + */ + ExecStoreTuple(&scandesc->rs_ctup, + slot, + scandesc->rs_cbuf, + false); + + /* + * 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); + + if (!ExecQual(node->bitmapqualorig, econtext, false)) + { + /* Fails recheck, so drop it and loop back for another */ + ExecClearTuple(slot); + continue; + } + } + + /* OK to return this tuple */ + return slot; + } + + /* + * Failed the snap, so loop back and try again. + */ + } + + /* + * if we get here it means we are at the end of the scan.. + */ + return ExecClearTuple(slot); +} + +/* ---------------------------------------------------------------- + * ExecBitmapHeapScan(node) + * ---------------------------------------------------------------- + */ +TupleTableSlot * +ExecBitmapHeapScan(BitmapHeapScanState *node) +{ + /* + * use BitmapHeapNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) BitmapHeapNext); +} + +/* ---------------------------------------------------------------- + * ExecBitmapHeapReScan(node) + * ---------------------------------------------------------------- + */ +void +ExecBitmapHeapReScan(BitmapHeapScanState *node, ExprContext *exprCtxt) +{ + EState *estate; + Index scanrelid; + + estate = node->ss.ps.state; + scanrelid = ((BitmapHeapScan *) node->ss.ps.plan)->scan.scanrelid; + + /* + * If we are being passed an outer tuple, link it into the "regular" + * per-tuple econtext for possible qual eval. + */ + if (exprCtxt != NULL) + { + ExprContext *stdecontext; + + stdecontext = node->ss.ps.ps_ExprContext; + stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple; + } + + /* If this is re-scanning of PlanQual ... */ + if (estate->es_evTuple != NULL && + estate->es_evTuple[scanrelid - 1] != NULL) + { + estate->es_evTupleNull[scanrelid - 1] = false; + } + + /* rescan to release any page pin */ + heap_rescan(node->ss.ss_currentScanDesc, NULL); + + if (node->tbm) + tbm_free(node->tbm); + node->tbm = NULL; + node->tbmres = NULL; + + /* + * Always rescan the input immediately, to ensure we can pass down + * any outer tuple that might be used in index quals. + */ + ExecReScan(outerPlanState(node), exprCtxt); +} + +/* ---------------------------------------------------------------- + * ExecEndBitmapHeapScan + * ---------------------------------------------------------------- + */ +void +ExecEndBitmapHeapScan(BitmapHeapScanState *node) +{ + Relation relation; + HeapScanDesc scanDesc; + + /* + * extract information from the node + */ + relation = node->ss.ss_currentRelation; + scanDesc = node->ss.ss_currentScanDesc; + + /* + * Free the exprcontext + */ + ExecFreeExprContext(&node->ss.ps); + + /* + * clear out tuple table slots + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + ExecClearTuple(node->ss.ss_ScanTupleSlot); + + /* + * close down subplans + */ + ExecEndNode(outerPlanState(node)); + + /* + * release bitmap if any + */ + if (node->tbm) + tbm_free(node->tbm); + + /* + * close heap scan + */ + heap_endscan(scanDesc); + + /* + * close the heap relation. + * + * Currently, we do not release the AccessShareLock acquired by + * ExecInitBitmapHeapScan. This lock should be held till end of + * transaction. (There is a faction that considers this too much + * locking, however.) + */ + heap_close(relation, NoLock); +} + +/* ---------------------------------------------------------------- + * ExecInitBitmapHeapScan + * + * Initializes the scan's state information. + * ---------------------------------------------------------------- + */ +BitmapHeapScanState * +ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate) +{ + BitmapHeapScanState *scanstate; + RangeTblEntry *rtentry; + Index relid; + Oid reloid; + Relation currentRelation; + + /* + * create state structure + */ + scanstate = makeNode(BitmapHeapScanState); + scanstate->ss.ps.plan = (Plan *) node; + scanstate->ss.ps.state = estate; + + scanstate->tbm = NULL; + scanstate->tbmres = NULL; + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &scanstate->ss.ps); + + /* + * initialize child expressions + */ + scanstate->ss.ps.targetlist = (List *) + ExecInitExpr((Expr *) node->scan.plan.targetlist, + (PlanState *) scanstate); + scanstate->ss.ps.qual = (List *) + ExecInitExpr((Expr *) node->scan.plan.qual, + (PlanState *) scanstate); + scanstate->bitmapqualorig = (List *) + ExecInitExpr((Expr *) node->bitmapqualorig, + (PlanState *) scanstate); + + /* + * initialize child nodes + */ + outerPlanState(scanstate) = ExecInitNode(outerPlan(node), estate); + +#define BITMAPHEAPSCAN_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &scanstate->ss.ps); + ExecInitScanTupleSlot(estate, &scanstate->ss); + + CXT1_printf("ExecInitBitmapHeapScan: context is %d\n", CurrentMemoryContext); + + /* + * open the base relation and acquire AccessShareLock on it. + */ + relid = node->scan.scanrelid; + rtentry = rt_fetch(relid, estate->es_range_table); + reloid = rtentry->relid; + + currentRelation = heap_open(reloid, AccessShareLock); + + scanstate->ss.ss_currentRelation = currentRelation; + + /* + * Even though we aren't going to do a conventional seqscan, it is + * useful to create a HeapScanDesc --- this checks the relation size + * and sets up statistical infrastructure for us. + */ + scanstate->ss.ss_currentScanDesc = heap_beginscan(currentRelation, + estate->es_snapshot, + 0, + NULL); + + /* + * get the scan type from the relation descriptor. + */ + ExecAssignScanType(&scanstate->ss, RelationGetDescr(currentRelation), false); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&scanstate->ss.ps); + ExecAssignScanProjectionInfo(&scanstate->ss); + + /* + * all done. + */ + return scanstate; +} + +int +ExecCountSlotsBitmapHeapScan(BitmapHeapScan *node) +{ + return ExecCountSlotsNode(outerPlan((Plan *) node)) + + ExecCountSlotsNode(innerPlan((Plan *) node)) + BITMAPHEAPSCAN_NSLOTS; +} diff --git a/src/backend/executor/nodeBitmapIndexscan.c b/src/backend/executor/nodeBitmapIndexscan.c new file mode 100644 index 00000000000..3ed03eb7cb8 --- /dev/null +++ b/src/backend/executor/nodeBitmapIndexscan.c @@ -0,0 +1,519 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapIndexscan.c + * Routines to support bitmapped index scans of relations + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.1 2005/04/19 22:35:12 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +/* + * INTERFACE ROUTINES + * MultiExecBitmapIndexScan scans a relation using index. + * ExecInitBitmapIndexScan creates and initializes state info. + * ExecBitmapIndexReScan prepares to rescan the plan. + * ExecEndBitmapIndexScan releases all storage. + */ +#include "postgres.h" + +#include "access/genam.h" +#include "access/heapam.h" +#include "executor/execdebug.h" +#include "executor/instrument.h" +#include "executor/nodeBitmapIndexscan.h" +#include "miscadmin.h" +#include "nodes/nodeFuncs.h" +#include "optimizer/clauses.h" +#include "parser/parsetree.h" + + +/* ---------------------------------------------------------------- + * MultiExecBitmapIndexScan(node) + * ---------------------------------------------------------------- + */ +Node * +MultiExecBitmapIndexScan(BitmapIndexScanState *node) +{ +#define MAX_TIDS 1024 + TIDBitmap *tbm; + IndexScanDesc scandesc; + ItemPointerData tids[MAX_TIDS]; + int32 ntids; + double nTuples = 0; + + /* must provide our own instrumentation support */ + if (node->ss.ps.instrument) + InstrStartNode(node->ss.ps.instrument); + + /* + * If we have runtime keys and they've not already been set up, do it + * now. + */ + if (node->biss_RuntimeKeyInfo && !node->biss_RuntimeKeysReady) + ExecReScan((PlanState *) node, NULL); + + /* + * extract necessary information from index scan node + */ + scandesc = node->biss_ScanDesc; + + /* + * Prepare result bitmap + */ + tbm = tbm_create(work_mem * 1024L); + + /* + * Get TIDs from index and insert into bitmap + */ + for (;;) + { + bool more = index_getmulti(scandesc, tids, MAX_TIDS, &ntids); + + if (ntids > 0) + { + tbm_add_tuples(tbm, tids, ntids); + nTuples += ntids; + } + + if (!more) + break; + + CHECK_FOR_INTERRUPTS(); + } + + /* must provide our own instrumentation support */ + if (node->ss.ps.instrument) + InstrStopNodeMulti(node->ss.ps.instrument, nTuples); + + return (Node *) tbm; +} + +/* ---------------------------------------------------------------- + * ExecBitmapIndexReScan(node) + * + * Recalculates the value of the scan keys whose value depends on + * information known at runtime and rescans the indexed relation. + * Updating the scan key was formerly done separately in + * ExecUpdateIndexScanKeys. Integrating it into ReScan makes + * rescans of indices and relations/general streams more uniform. + * + * ---------------------------------------------------------------- + */ +void +ExecBitmapIndexReScan(BitmapIndexScanState *node, ExprContext *exprCtxt) +{ + ExprContext *econtext; + ExprState **runtimeKeyInfo; + Index scanrelid; + + econtext = node->biss_RuntimeContext; /* context for runtime + * keys */ + runtimeKeyInfo = node->biss_RuntimeKeyInfo; + scanrelid = ((BitmapIndexScan *) node->ss.ps.plan)->scan.scanrelid; + + if (econtext) + { + /* + * If we are being passed an outer tuple, save it for runtime key + * calc. We also need to link it into the "regular" per-tuple + * econtext. + */ + if (exprCtxt != NULL) + { + ExprContext *stdecontext; + + econtext->ecxt_outertuple = exprCtxt->ecxt_outertuple; + stdecontext = node->ss.ps.ps_ExprContext; + stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple; + } + + /* + * Reset the runtime-key context so we don't leak memory as each + * outer tuple is scanned. Note this assumes that we will + * recalculate *all* runtime keys on each call. + */ + ResetExprContext(econtext); + } + + /* + * If we are doing runtime key calculations (ie, the index keys depend + * on data from an outer scan), compute the new key values + */ + if (runtimeKeyInfo) + { + int n_keys; + ScanKey scan_keys; + ExprState **run_keys; + int j; + + n_keys = node->biss_NumScanKeys; + scan_keys = node->biss_ScanKeys; + run_keys = runtimeKeyInfo; + + for (j = 0; j < n_keys; j++) + { + /* + * If we have a run-time key, then extract the run-time + * expression and evaluate it with respect to the current + * outer tuple. We then stick the result into the scan + * key. + * + * Note: the result of the eval could be a pass-by-ref value + * that's stored in the outer scan's tuple, not in + * econtext->ecxt_per_tuple_memory. We assume that the + * outer tuple will stay put throughout our scan. If this + * is wrong, we could copy the result into our context + * explicitly, but I think that's not necessary... + */ + if (run_keys[j] != NULL) + { + Datum scanvalue; + bool isNull; + + scanvalue = ExecEvalExprSwitchContext(run_keys[j], + econtext, + &isNull, + NULL); + scan_keys[j].sk_argument = scanvalue; + if (isNull) + scan_keys[j].sk_flags |= SK_ISNULL; + else + scan_keys[j].sk_flags &= ~SK_ISNULL; + } + } + + node->biss_RuntimeKeysReady = true; + } + + index_rescan(node->biss_ScanDesc, node->biss_ScanKeys); +} + +/* ---------------------------------------------------------------- + * ExecEndBitmapIndexScan + * ---------------------------------------------------------------- + */ +void +ExecEndBitmapIndexScan(BitmapIndexScanState *node) +{ + Relation relation; + + /* + * extract information from the node + */ + relation = node->ss.ss_currentRelation; + + /* + * Free the exprcontext(s) + */ + ExecFreeExprContext(&node->ss.ps); + if (node->biss_RuntimeContext) + FreeExprContext(node->biss_RuntimeContext); + + /* + * close the index relation + */ + if (node->biss_ScanDesc != NULL) + index_endscan(node->biss_ScanDesc); + + if (node->biss_RelationDesc != NULL) + index_close(node->biss_RelationDesc); + + /* + * close the heap relation. + * + * Currently, we do not release the AccessShareLock acquired by + * ExecInitBitmapIndexScan. This lock should be held till end of + * transaction. (There is a faction that considers this too much + * locking, however.) + */ + heap_close(relation, NoLock); +} + +/* ---------------------------------------------------------------- + * ExecInitBitmapIndexScan + * + * Initializes the index scan's state information, creates + * scan keys, and opens the base and index relations. + * + * Note: index scans have 2 sets of state information because + * we have to keep track of the base relation and the + * index relations. + * + * old comments + * Creates the run-time state information for the node and + * sets the relation id to contain relevant descriptors. + * + * Parameters: + * node: BitmapIndexNode node produced by the planner. + * estate: the execution state initialized in InitPlan. + * ---------------------------------------------------------------- + */ +BitmapIndexScanState * +ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate) +{ + BitmapIndexScanState *indexstate; + ExprState **runtimeKeyInfo; + bool have_runtime_keys; + RangeTblEntry *rtentry; + Index relid; + Oid reloid; + Relation currentRelation; + + /* + * create state structure + */ + indexstate = makeNode(BitmapIndexScanState); + indexstate->ss.ps.plan = (Plan *) node; + indexstate->ss.ps.state = estate; + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &indexstate->ss.ps); + + /* + * initialize child expressions + * + * We don't need to initialize targetlist or qual since neither are used. + * + * Note: we don't initialize all of the indxqual expression, only the + * sub-parts corresponding to runtime keys (see below). + */ + +#define BITMAPINDEXSCAN_NSLOTS 0 + + /* + * Initialize index-specific scan state + */ + indexstate->biss_ScanKeys = NULL; + indexstate->biss_NumScanKeys = 0; + indexstate->biss_RuntimeKeyInfo = NULL; + indexstate->biss_RuntimeContext = NULL; + indexstate->biss_RuntimeKeysReady = false; + indexstate->biss_RelationDesc = NULL; + indexstate->biss_ScanDesc = NULL; + + CXT1_printf("ExecInitBitmapIndexScan: context is %d\n", CurrentMemoryContext); + + /* + * initialize space for runtime key info (may not be needed) + */ + have_runtime_keys = false; + + /* + * build the index scan keys from the index qualification + */ + { + List *quals; + List *strategies; + List *subtypes; + ListCell *qual_cell; + ListCell *strategy_cell; + ListCell *subtype_cell; + int n_keys; + ScanKey scan_keys; + ExprState **run_keys; + int j; + + quals = node->indxqual; + strategies = node->indxstrategy; + subtypes = node->indxsubtype; + n_keys = list_length(quals); + scan_keys = (n_keys <= 0) ? NULL : + (ScanKey) palloc(n_keys * sizeof(ScanKeyData)); + run_keys = (n_keys <= 0) ? NULL : + (ExprState **) palloc(n_keys * sizeof(ExprState *)); + + /* + * for each opclause in the given qual, convert each qual's + * opclause into a single scan key + */ + qual_cell = list_head(quals); + strategy_cell = list_head(strategies); + subtype_cell = list_head(subtypes); + for (j = 0; j < n_keys; j++) + { + OpExpr *clause; /* one clause of index qual */ + Expr *leftop; /* expr on lhs of operator */ + Expr *rightop; /* expr on rhs ... */ + int flags = 0; + AttrNumber varattno; /* att number used in scan */ + StrategyNumber strategy; /* op's strategy number */ + Oid subtype; /* op's strategy subtype */ + RegProcedure opfuncid; /* operator proc id used in scan */ + Datum scanvalue; /* value used in scan (if const) */ + + /* + * extract clause information from the qualification + */ + clause = (OpExpr *) lfirst(qual_cell); + qual_cell = lnext(qual_cell); + strategy = lfirst_int(strategy_cell); + strategy_cell = lnext(strategy_cell); + subtype = lfirst_oid(subtype_cell); + subtype_cell = lnext(subtype_cell); + + if (!IsA(clause, OpExpr)) + elog(ERROR, "indxqual is not an OpExpr"); + + opfuncid = clause->opfuncid; + + /* + * Here we figure out the contents of the index qual. The + * usual case is (var op const) which means we form a scan key + * for the attribute listed in the var node and use the value + * of the const as comparison data. + * + * If we don't have a const node, it means our scan key is a + * function of information obtained during the execution of + * the plan, in which case we need to recalculate the index + * scan key at run time. Hence, we set have_runtime_keys to + * true and place the appropriate subexpression in run_keys. + * The corresponding scan key values are recomputed at run + * time. + */ + run_keys[j] = NULL; + + /* + * determine information in leftop + */ + leftop = (Expr *) get_leftop((Expr *) clause); + + if (leftop && IsA(leftop, RelabelType)) + leftop = ((RelabelType *) leftop)->arg; + + Assert(leftop != NULL); + + if (!(IsA(leftop, Var) && + var_is_rel((Var *) leftop))) + elog(ERROR, "indxqual doesn't have key on left side"); + + varattno = ((Var *) leftop)->varattno; + + /* + * now determine information in rightop + */ + rightop = (Expr *) get_rightop((Expr *) clause); + + if (rightop && IsA(rightop, RelabelType)) + rightop = ((RelabelType *) rightop)->arg; + + Assert(rightop != NULL); + + if (IsA(rightop, Const)) + { + /* + * if the rightop is a const node then it means it + * identifies the value to place in our scan key. + */ + scanvalue = ((Const *) rightop)->constvalue; + if (((Const *) rightop)->constisnull) + flags |= SK_ISNULL; + } + else + { + /* + * otherwise, the rightop contains an expression evaluable + * at runtime to figure out the value to place in our scan + * key. + */ + have_runtime_keys = true; + run_keys[j] = ExecInitExpr(rightop, (PlanState *) indexstate); + scanvalue = (Datum) 0; + } + + /* + * initialize the scan key's fields appropriately + */ + ScanKeyEntryInitialize(&scan_keys[j], + flags, + varattno, /* attribute number to + * scan */ + strategy, /* op's strategy */ + subtype, /* strategy subtype */ + opfuncid, /* reg proc to use */ + scanvalue); /* constant */ + } + + /* + * store the key information into the node. + */ + indexstate->biss_NumScanKeys = n_keys; + indexstate->biss_ScanKeys = scan_keys; + runtimeKeyInfo = run_keys; + } + + + /* + * If all of our keys have the form (var op const), then we have no + * runtime keys so we store NULL in the runtime key info. Otherwise + * runtime key info contains an array of pointers (one for each index) + * to arrays of flags (one for each key) which indicate that the qual + * needs to be evaluated at runtime. -cim 10/24/89 + * + * If we do have runtime keys, we need an ExprContext to evaluate them; + * the node's standard context won't do because we want to reset that + * context for every tuple. So, build another context just like the + * other one... -tgl 7/11/00 + */ + if (have_runtime_keys) + { + ExprContext *stdecontext = indexstate->ss.ps.ps_ExprContext; + + ExecAssignExprContext(estate, &indexstate->ss.ps); + indexstate->biss_RuntimeKeyInfo = runtimeKeyInfo; + indexstate->biss_RuntimeContext = indexstate->ss.ps.ps_ExprContext; + indexstate->ss.ps.ps_ExprContext = stdecontext; + } + else + { + indexstate->biss_RuntimeKeyInfo = NULL; + indexstate->biss_RuntimeContext = NULL; + /* Get rid of the speculatively-allocated flag array, too */ + pfree(runtimeKeyInfo); + } + + /* + * open the base relation and acquire AccessShareLock on it. + */ + relid = node->scan.scanrelid; + rtentry = rt_fetch(relid, estate->es_range_table); + reloid = rtentry->relid; + + currentRelation = heap_open(reloid, AccessShareLock); + + indexstate->ss.ss_currentRelation = currentRelation; + indexstate->ss.ss_currentScanDesc = NULL; /* no heap scan here */ + + /* + * open the index relation and initialize relation and scan + * descriptors. Note we acquire no locks here; the index machinery + * does its own locks and unlocks. (We rely on having AccessShareLock + * on the parent table to ensure the index won't go away!) + */ + indexstate->biss_RelationDesc = index_open(node->indxid); + indexstate->biss_ScanDesc = + index_beginscan_multi(indexstate->biss_RelationDesc, + estate->es_snapshot, + indexstate->biss_NumScanKeys, + indexstate->biss_ScanKeys); + + /* + * all done. + */ + return indexstate; +} + +int +ExecCountSlotsBitmapIndexScan(BitmapIndexScan *node) +{ + return ExecCountSlotsNode(outerPlan((Plan *) node)) + + ExecCountSlotsNode(innerPlan((Plan *) node)) + BITMAPINDEXSCAN_NSLOTS; +} diff --git a/src/backend/executor/nodeBitmapOr.c b/src/backend/executor/nodeBitmapOr.c new file mode 100644 index 00000000000..f4ef17223c8 --- /dev/null +++ b/src/backend/executor/nodeBitmapOr.c @@ -0,0 +1,209 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapOr.c + * routines to handle BitmapOr nodes. + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeBitmapOr.c,v 1.1 2005/04/19 22:35:12 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +/* INTERFACE ROUTINES + * ExecInitBitmapOr - initialize the BitmapOr node + * MultiExecBitmapOr - retrieve the result bitmap from the node + * ExecEndBitmapOr - shut down the BitmapOr node + * ExecReScanBitmapOr - rescan the BitmapOr node + * + * NOTES + * BitmapOr nodes don't make use of their left and right + * subtrees, rather they maintain a list of subplans, + * much like Append nodes. The logic is much simpler than + * Append, however, since we needn't cope with forward/backward + * execution. + */ + +#include "postgres.h" + +#include "executor/execdebug.h" +#include "executor/instrument.h" +#include "executor/nodeBitmapOr.h" + + +/* ---------------------------------------------------------------- + * ExecInitBitmapOr + * + * Begin all of the subscans of the BitmapOr node. + * ---------------------------------------------------------------- + */ +BitmapOrState * +ExecInitBitmapOr(BitmapOr *node, EState *estate) +{ + BitmapOrState *bitmaporstate = makeNode(BitmapOrState); + PlanState **bitmapplanstates; + int nplans; + int i; + Plan *initNode; + + CXT1_printf("ExecInitBitmapOr: context is %d\n", CurrentMemoryContext); + + /* + * Set up empty vector of subplan states + */ + nplans = list_length(node->bitmapplans); + + bitmapplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *)); + + /* + * create new BitmapOrState for our BitmapOr node + */ + bitmaporstate->ps.plan = (Plan *) node; + bitmaporstate->ps.state = estate; + bitmaporstate->bitmapplans = bitmapplanstates; + bitmaporstate->nplans = nplans; + + /* + * Miscellaneous initialization + * + * BitmapOr plans don't have expression contexts because they never call + * ExecQual or ExecProject. They don't need any tuple slots either. + */ + +#define BITMAPOR_NSLOTS 0 + + /* + * call ExecInitNode on each of the plans to be executed and save the + * results into the array "bitmapplanstates". + */ + for (i = 0; i < nplans; i++) + { + initNode = (Plan *) list_nth(node->bitmapplans, i); + bitmapplanstates[i] = ExecInitNode(initNode, estate); + } + + return bitmaporstate; +} + +int +ExecCountSlotsBitmapOr(BitmapOr *node) +{ + ListCell *plan; + int nSlots = 0; + + foreach(plan, node->bitmapplans) + nSlots += ExecCountSlotsNode((Plan *) lfirst(plan)); + return nSlots + BITMAPOR_NSLOTS; +} + +/* ---------------------------------------------------------------- + * MultiExecBitmapOr + * ---------------------------------------------------------------- + */ +Node * +MultiExecBitmapOr(BitmapOrState *node) +{ + PlanState **bitmapplans; + int nplans; + int i; + TIDBitmap *result = NULL; + + /* must provide our own instrumentation support */ + if (node->ps.instrument) + InstrStartNode(node->ps.instrument); + + /* + * get information from the node + */ + bitmapplans = node->bitmapplans; + nplans = node->nplans; + + /* + * Scan all the subplans and OR their result bitmaps + */ + for (i = 0; i < nplans; i++) + { + PlanState *subnode = bitmapplans[i]; + TIDBitmap *subresult; + + subresult = (TIDBitmap *) MultiExecProcNode(subnode); + + if (!subresult || !IsA(subresult, TIDBitmap)) + elog(ERROR, "unrecognized result from subplan"); + + if (result == NULL) + result = subresult; /* first subplan */ + else + { + tbm_union(result, subresult); + tbm_free(subresult); + } + } + + /* We could return an empty result set here? */ + if (result == NULL) + elog(ERROR, "BitmapOr doesn't support zero inputs"); + + /* must provide our own instrumentation support */ + if (node->ps.instrument) + InstrStopNodeMulti(node->ps.instrument, 0 /* XXX */); + + return (Node *) result; +} + +/* ---------------------------------------------------------------- + * ExecEndBitmapOr + * + * Shuts down the subscans of the BitmapOr node. + * + * Returns nothing of interest. + * ---------------------------------------------------------------- + */ +void +ExecEndBitmapOr(BitmapOrState *node) +{ + PlanState **bitmapplans; + int nplans; + int i; + + /* + * get information from the node + */ + bitmapplans = node->bitmapplans; + nplans = node->nplans; + + /* + * shut down each of the subscans (that we've initialized) + */ + for (i = 0; i < nplans; i++) + { + if (bitmapplans[i]) + ExecEndNode(bitmapplans[i]); + } +} + +void +ExecReScanBitmapOr(BitmapOrState *node, ExprContext *exprCtxt) +{ + int i; + + for (i = 0; i < node->nplans; i++) + { + PlanState *subnode = node->bitmapplans[i]; + + /* + * ExecReScan doesn't know about my subplans, so I have to do + * changed-parameter signaling myself. + */ + if (node->ps.chgParam != NULL) + UpdateChangedParamSet(subnode, node->ps.chgParam); + + /* + * Always rescan the inputs immediately, to ensure we can pass down + * any outer tuple that might be used in index quals. + */ + ExecReScan(subnode, exprCtxt); + } +} diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 0e480f5e086..71cea4bc2f3 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -15,7 +15,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.301 2005/04/07 01:51:38 neilc Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.302 2005/04/19 22:35:13 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -148,6 +148,48 @@ _copyAppend(Append *from) return newnode; } +/* + * _copyBitmapAnd + */ +static BitmapAnd * +_copyBitmapAnd(BitmapAnd *from) +{ + BitmapAnd *newnode = makeNode(BitmapAnd); + + /* + * copy node superclass fields + */ + CopyPlanFields((Plan *) from, (Plan *) newnode); + + /* + * copy remainder of node + */ + COPY_NODE_FIELD(bitmapplans); + + return newnode; +} + +/* + * _copyBitmapOr + */ +static BitmapOr * +_copyBitmapOr(BitmapOr *from) +{ + BitmapOr *newnode = makeNode(BitmapOr); + + /* + * copy node superclass fields + */ + CopyPlanFields((Plan *) from, (Plan *) newnode); + + /* + * copy remainder of node + */ + COPY_NODE_FIELD(bitmapplans); + + return newnode; +} + /* * CopyScanFields @@ -223,6 +265,52 @@ _copyIndexScan(IndexScan *from) } /* + * _copyBitmapIndexScan + */ +static BitmapIndexScan * +_copyBitmapIndexScan(BitmapIndexScan *from) +{ + BitmapIndexScan *newnode = makeNode(BitmapIndexScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(indxid); + COPY_NODE_FIELD(indxqual); + COPY_NODE_FIELD(indxqualorig); + COPY_NODE_FIELD(indxstrategy); + COPY_NODE_FIELD(indxsubtype); + + return newnode; +} + +/* + * _copyBitmapHeapScan + */ +static BitmapHeapScan * +_copyBitmapHeapScan(BitmapHeapScan *from) +{ + BitmapHeapScan *newnode = makeNode(BitmapHeapScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_NODE_FIELD(bitmapqualorig); + + return newnode; +} + +/* * _copyTidScan */ static TidScan * @@ -2598,6 +2686,12 @@ copyObject(void *from) case T_Append: retval = _copyAppend(from); break; + case T_BitmapAnd: + retval = _copyBitmapAnd(from); + break; + case T_BitmapOr: + retval = _copyBitmapOr(from); + break; case T_Scan: retval = _copyScan(from); break; @@ -2607,6 +2701,12 @@ copyObject(void *from) case T_IndexScan: retval = _copyIndexScan(from); break; + case T_BitmapIndexScan: + retval = _copyBitmapIndexScan(from); + break; + case T_BitmapHeapScan: + retval = _copyBitmapHeapScan(from); + break; case T_TidScan: retval = _copyTidScan(from); break; diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 91a7abf5749..c241b113674 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.246 2005/04/06 16:34:05 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.247 2005/04/19 22:35:14 tgl Exp $ * * NOTES * Every node type that can appear in stored rules' parsetrees *must* @@ -309,6 +309,26 @@ _outAppend(StringInfo str, Append *node) } static void +_outBitmapAnd(StringInfo str, BitmapAnd *node) +{ + WRITE_NODE_TYPE("BITMAPAND"); + + _outPlanInfo(str, (Plan *) node); + + WRITE_NODE_FIELD(bitmapplans); +} + +static void +_outBitmapOr(StringInfo str, BitmapOr *node) +{ + WRITE_NODE_TYPE("BITMAPOR"); + + _outPlanInfo(str, (Plan *) node); + + WRITE_NODE_FIELD(bitmapplans); +} + +static void _outScan(StringInfo str, Scan *node) { WRITE_NODE_TYPE("SCAN"); @@ -341,6 +361,30 @@ _outIndexScan(StringInfo str, IndexScan *node) } static void +_outBitmapIndexScan(StringInfo str, BitmapIndexScan *node) +{ + WRITE_NODE_TYPE("BITMAPINDEXSCAN"); + + _outScanInfo(str, (Scan *) node); + + WRITE_OID_FIELD(indxid); + WRITE_NODE_FIELD(indxqual); + WRITE_NODE_FIELD(indxqualorig); + WRITE_NODE_FIELD(indxstrategy); + WRITE_NODE_FIELD(indxsubtype); +} + +static void +_outBitmapHeapScan(StringInfo str, BitmapHeapScan *node) +{ + WRITE_NODE_TYPE("BITMAPHEAPSCAN"); + + _outScanInfo(str, (Scan *) node); + + WRITE_NODE_FIELD(bitmapqualorig); +} + +static void _outTidScan(StringInfo str, TidScan *node) { WRITE_NODE_TYPE("TIDSCAN"); @@ -968,9 +1012,6 @@ _outPath(StringInfo str, Path *node) _outPathInfo(str, (Path *) node); } -/* - * IndexPath is a subclass of Path. - */ static void _outIndexPath(StringInfo str, IndexPath *node) { @@ -987,6 +1028,18 @@ _outIndexPath(StringInfo str, IndexPath *node) } static void +_outBitmapHeapPath(StringInfo str, BitmapHeapPath *node) +{ + WRITE_NODE_TYPE("BITMAPHEAPPATH"); + + _outPathInfo(str, (Path *) node); + + WRITE_NODE_FIELD(bitmapqual); + WRITE_BOOL_FIELD(isjoininner); + WRITE_FLOAT_FIELD(rows, "%.0f"); +} + +static void _outTidPath(StringInfo str, TidPath *node) { WRITE_NODE_TYPE("TIDPATH"); @@ -1620,6 +1673,12 @@ _outNode(StringInfo str, void *obj) case T_Append: _outAppend(str, obj); break; + case T_BitmapAnd: + _outBitmapAnd(str, obj); + break; + case T_BitmapOr: + _outBitmapOr(str, obj); + break; case T_Scan: _outScan(str, obj); break; @@ -1629,6 +1688,12 @@ _outNode(StringInfo str, void *obj) case T_IndexScan: _outIndexScan(str, obj); break; + case T_BitmapIndexScan: + _outBitmapIndexScan(str, obj); + break; + case T_BitmapHeapScan: + _outBitmapHeapScan(str, obj); + break; case T_TidScan: _outTidScan(str, obj); break; @@ -1783,6 +1848,9 @@ _outNode(StringInfo str, void *obj) case T_IndexPath: _outIndexPath(str, obj); break; + case T_BitmapHeapPath: + _outBitmapHeapPath(str, obj); + break; case T_TidPath: _outTidPath(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 35bb99b62fd..3e5b5bb78fc 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.74 2005/04/06 16:34:05 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.75 2005/04/19 22:35:15 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -493,12 +493,20 @@ plannode_type(Plan *p) return "RESULT"; case T_Append: return "APPEND"; + case T_BitmapAnd: + return "BITMAPAND"; + case T_BitmapOr: + return "BITMAPOR"; case T_Scan: return "SCAN"; case T_SeqScan: return "SEQSCAN"; case T_IndexScan: return "INDEXSCAN"; + case T_BitmapIndexScan: + return "BITMAPINDEXSCAN"; + case T_BitmapHeapScan: + return "BITMAPHEAPSCAN"; case T_TidScan: return "TIDSCAN"; case T_SubqueryScan: @@ -551,7 +559,8 @@ print_plan_recursive(Plan *p, Query *parsetree, int indentLevel, char *label) p->startup_cost, p->total_cost, p->plan_rows, p->plan_width); if (IsA(p, Scan) || - IsA(p, SeqScan)) + IsA(p, SeqScan) || + IsA(p, BitmapHeapScan)) { RangeTblEntry *rte; @@ -584,27 +593,48 @@ print_plan_recursive(Plan *p, Query *parsetree, int indentLevel, char *label) if (IsA(p, Append)) { ListCell *l; - int whichplan = 0; Append *appendplan = (Append *) p; foreach(l, appendplan->appendplans) { Plan *subnode = (Plan *) lfirst(l); - /* - * I don't think we need to fiddle with the range table here, - * bjm - */ print_plan_recursive(subnode, parsetree, indentLevel + 3, "a: "); + } + } + + if (IsA(p, BitmapAnd)) + { + ListCell *l; + BitmapAnd *bitmapandplan = (BitmapAnd *) p; + + foreach(l, bitmapandplan->bitmapplans) + { + Plan *subnode = (Plan *) lfirst(l); - whichplan++; + print_plan_recursive(subnode, parsetree, indentLevel + 3, "a: "); } } -} -/* print_plan - prints just the plan node types */ + if (IsA(p, BitmapOr)) + { + ListCell *l; + BitmapOr *bitmaporplan = (BitmapOr *) p; + foreach(l, bitmaporplan->bitmapplans) + { + Plan *subnode = (Plan *) lfirst(l); + + print_plan_recursive(subnode, parsetree, indentLevel + 3, "a: "); + } + } +} + +/* + * print_plan + * + * prints just the plan node types + */ void print_plan(Plan *p, Query *parsetree) { diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c index f2505159218..69820380424 100644 --- a/src/backend/nodes/tidbitmap.c +++ b/src/backend/nodes/tidbitmap.c @@ -23,7 +23,7 @@ * Copyright (c) 2003-2005, PostgreSQL Global Development Group * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/tidbitmap.c,v 1.1 2005/04/17 22:24:02 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/tidbitmap.c,v 1.2 2005/04/19 22:35:15 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -160,7 +160,7 @@ tbm_create(long maxbytes) hash_ctl.hash = tag_hash; hash_ctl.hcxt = CurrentMemoryContext; tbm->pagetable = hash_create("TIDBitmap", - nbuckets, + 128, /* start small and extend */ &hash_ctl, HASH_ELEM | HASH_FUNCTION | HASH_CONTEXT); diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 16513108450..dc5091c69af 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.125 2005/04/06 16:34:05 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.126 2005/04/19 22:35:15 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -898,6 +898,9 @@ print_path(Query *root, Path *path, int indent) case T_IndexPath: ptype = "IdxScan"; break; + case T_BitmapHeapPath: + ptype = "BitmapHeapScan"; + break; case T_TidPath: ptype = "TidScan"; break; diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 967536393ee..06ebe18fe78 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -49,7 +49,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.141 2005/04/04 01:43:12 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.142 2005/04/19 22:35:15 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -401,6 +401,36 @@ cost_index(Path *path, Query *root, } /* + * cost_bitmap_scan + * Determines and returns the cost of scanning a relation using a bitmap + * index-then-heap plan. + * + * 'root' is the query root + * 'baserel' is the relation to be scanned + * 'bitmapqual' is an AND/OR tree of IndexPaths for the component scans + * 'is_injoin' is T if we are considering using the scan as the inside + * of a nestloop join (hence, some of the quals are join clauses) + */ +void +cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel, + Node *bitmapqual, bool is_injoin) +{ + Cost startup_cost = 0; + Cost run_cost = 0; + + /* Should only be applied to base relations */ + Assert(IsA(baserel, RelOptInfo)); + Assert(baserel->relid > 0); + Assert(baserel->rtekind == RTE_RELATION); + + /* XXX lots to do here */ + run_cost += 10; + + path->startup_cost = startup_cost; + path->total_cost = startup_cost + run_cost; +} + +/* * cost_tidscan * Determines and returns the cost of scanning a relation using TIDs. */ @@ -760,6 +790,8 @@ cost_nestloop(NestPath *path, Query *root) */ if (IsA(inner_path, IndexPath)) inner_path_rows = ((IndexPath *) inner_path)->rows; + else if (IsA(inner_path, BitmapHeapPath)) + inner_path_rows = ((BitmapHeapPath *) inner_path)->rows; if (!enable_nestloop) startup_cost += disable_cost; diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 97e4d7dda87..b75cb6128d7 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.92 2005/01/23 02:21:26 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.93 2005/04/19 22:35:15 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -391,6 +391,7 @@ match_unsorted_outer(Query *root, * waste of time.) */ if (!(IsA(inner_cheapest_total, IndexPath) || + IsA(inner_cheapest_total, BitmapHeapPath) || IsA(inner_cheapest_total, TidPath))) matpath = (Path *) create_material_path(innerrel, inner_cheapest_total); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 6f378c76dd8..d15f0c6dcae 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.179 2005/04/12 05:11:28 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.180 2005/04/19 22:35:16 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -48,6 +48,12 @@ static SeqScan *create_seqscan_plan(Query *root, Path *best_path, List *tlist, List *scan_clauses); static IndexScan *create_indexscan_plan(Query *root, IndexPath *best_path, List *tlist, List *scan_clauses); +static BitmapHeapScan *create_bitmap_scan_plan(Query *root, + BitmapHeapPath *best_path, + List *tlist, List *scan_clauses); +static Plan *create_bitmap_subplan(Query *root, Node *bitmapqual); +static List *create_bitmap_qual(Node *bitmapqual); +static List *create_bitmap_indxqual(Node *bitmapqual); static TidScan *create_tidscan_plan(Query *root, TidPath *best_path, List *tlist, List *scan_clauses); static SubqueryScan *create_subqueryscan_plan(Query *root, Path *best_path, @@ -80,10 +86,22 @@ static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, List *indxid, List *indxqual, List *indxqualorig, List *indxstrategy, List *indxsubtype, List *indxlossy, ScanDirection indexscandir); +static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indxid, + List *indxqual, + List *indxqualorig, + List *indxstrategy, + List *indxsubtype); +static BitmapHeapScan *make_bitmap_heapscan(List *qptlist, + List *qpqual, + Plan *lefttree, + List *bitmapqualorig, + Index scanrelid); static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid, List *tideval); static FunctionScan *make_functionscan(List *qptlist, List *qpqual, Index scanrelid); +static BitmapAnd *make_bitmap_and(List *bitmapplans); +static BitmapOr *make_bitmap_or(List *bitmapplans); static NestLoop *make_nestloop(List *tlist, List *joinclauses, List *otherclauses, Plan *lefttree, Plan *righttree, @@ -127,8 +145,9 @@ create_plan(Query *root, Path *best_path) switch (best_path->pathtype) { - case T_IndexScan: case T_SeqScan: + case T_IndexScan: + case T_BitmapHeapScan: case T_TidScan: case T_SubqueryScan: case T_FunctionScan: @@ -220,6 +239,13 @@ create_scan_plan(Query *root, Path *best_path) scan_clauses); break; + case T_BitmapHeapScan: + plan = (Scan *) create_bitmap_scan_plan(root, + (BitmapHeapPath *) best_path, + tlist, + scan_clauses); + break; + case T_TidScan: plan = (Scan *) create_tidscan_plan(root, (TidPath *) best_path, @@ -328,8 +354,9 @@ disuse_physical_tlist(Plan *plan, Path *path) /* Only need to undo it for path types handled by create_scan_plan() */ switch (path->pathtype) { - case T_IndexScan: case T_SeqScan: + case T_IndexScan: + case T_BitmapHeapScan: case T_TidScan: case T_SubqueryScan: case T_FunctionScan: @@ -671,7 +698,7 @@ create_seqscan_plan(Query *root, Path *best_path, /* * create_indexscan_plan - * Returns a indexscan plan for the base relation scanned by 'best_path' + * Returns an indexscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. * * The indexquals list of the path contains a sublist of implicitly-ANDed @@ -705,6 +732,37 @@ create_indexscan_plan(Query *root, Assert(baserelid > 0); Assert(best_path->path.parent->rtekind == RTE_RELATION); + /* Build list of index OIDs */ + indexids = NIL; + foreach(l, best_path->indexinfo) + { + IndexOptInfo *index = (IndexOptInfo *) lfirst(l); + + indexids = lappend_oid(indexids, index->indexoid); + } + + /* + * Build "stripped" indexquals structure (no RestrictInfos) to pass to + * executor as indxqualorig + */ + stripped_indxquals = NIL; + foreach(l, indxquals) + { + List *andlist = (List *) lfirst(l); + + stripped_indxquals = lappend(stripped_indxquals, + get_actual_clauses(andlist)); + } + + /* + * The executor needs a copy with the indexkey on the left of each + * clause and with index attr numbers substituted for table ones. This + * pass also gets strategy info and looks for "lossy" operators. + */ + fix_indxqual_references(indxquals, best_path, + &fixed_indxquals, + &indxstrategy, &indxsubtype, &indxlossy); + /* * If this is a innerjoin scan, the indexclauses will contain join * clauses that are not present in scan_clauses (since the passed-in @@ -729,31 +787,6 @@ create_indexscan_plan(Query *root, /* Reduce RestrictInfo list to bare expressions */ scan_clauses = get_actual_clauses(scan_clauses); - /* Sort clauses into best execution order */ - scan_clauses = order_qual_clauses(root, scan_clauses); - - /* Build list of index OIDs */ - indexids = NIL; - foreach(l, best_path->indexinfo) - { - IndexOptInfo *index = (IndexOptInfo *) lfirst(l); - - indexids = lappend_oid(indexids, index->indexoid); - } - - /* - * Build "stripped" indexquals structure (no RestrictInfos) to pass to - * executor as indxqualorig - */ - stripped_indxquals = NIL; - foreach(l, indxquals) - { - List *andlist = (List *) lfirst(l); - - stripped_indxquals = lappend(stripped_indxquals, - get_actual_clauses(andlist)); - } - /* * The qpqual list must contain all restrictions not automatically * handled by the index. All the predicates in the indexquals will be @@ -784,14 +817,8 @@ create_indexscan_plan(Query *root, qpqual = list_difference(scan_clauses, linitial(stripped_indxquals)); } - /* - * The executor needs a copy with the indexkey on the left of each - * clause and with index attr numbers substituted for table ones. This - * pass also gets strategy info and looks for "lossy" operators. - */ - fix_indxqual_references(indxquals, best_path, - &fixed_indxquals, - &indxstrategy, &indxsubtype, &indxlossy); + /* Sort clauses into best execution order */ + qpqual = order_qual_clauses(root, qpqual); /* Finally ready to build the plan node */ scan_plan = make_indexscan(tlist, @@ -813,6 +840,339 @@ create_indexscan_plan(Query *root, } /* + * create_bitmap_scan_plan + * Returns a bitmap scan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ +static BitmapHeapScan * +create_bitmap_scan_plan(Query *root, + BitmapHeapPath *best_path, + List *tlist, + List *scan_clauses) +{ + Index baserelid = best_path->path.parent->relid; + Plan *bitmapqualplan; + List *bitmapqualorig; + List *indexquals; + List *qpqual; + BitmapHeapScan *scan_plan; + + /* it should be a base rel... */ + Assert(baserelid > 0); + Assert(best_path->path.parent->rtekind == RTE_RELATION); + + /* Process the bitmapqual tree into a Plan tree */ + bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual); + + /* Process the bitmapqual tree into an expression tree, too */ + bitmapqualorig = create_bitmap_qual(best_path->bitmapqual); + + /* Also extract the true index conditions */ + indexquals = create_bitmap_indxqual(best_path->bitmapqual); + + /* + * If this is a innerjoin scan, the indexclauses will contain join + * clauses that are not present in scan_clauses (since the passed-in + * value is just the rel's baserestrictinfo list). We must add these + * clauses to scan_clauses to ensure they get checked. In most cases + * we will remove the join clauses again below, but if a join clause + * contains a special operator, we need to make sure it gets into the + * scan_clauses. + */ + if (best_path->isjoininner) + { + /* + * Pointer comparison should be enough to determine RestrictInfo + * matches. + */ + scan_clauses = list_union_ptr(scan_clauses, bitmapqualorig); + } + + /* Reduce RestrictInfo list to bare expressions */ + scan_clauses = get_actual_clauses(scan_clauses); + + /* + * The qpqual list must contain all restrictions not automatically + * handled by the index. All the predicates in the indexquals will be + * checked (either by the index itself, or by nodeBitmapHeapscan.c), + * but if there are any "special" or lossy operators involved then they + * must be added to qpqual. The upshot is that qpquals must contain + * scan_clauses minus whatever appears in indexquals. + * + * NOTE: when there are OR clauses in indexquals, the simple equality + * check used by list_difference will only detect matches in case of + * chance equality of the OR subclause ordering. This is probably all + * right for now because that order will match what's in scan_clauses + * ... but perhaps we need more smarts here. + */ + qpqual = list_difference(scan_clauses, indexquals); + + /* Sort clauses into best execution order */ + qpqual = order_qual_clauses(root, qpqual); + + /* Finally ready to build the plan node */ + scan_plan = make_bitmap_heapscan(tlist, + qpqual, + bitmapqualplan, + bitmapqualorig, + baserelid); + + copy_path_costsize(&scan_plan->scan.plan, &best_path->path); + /* use the indexscan-specific rows estimate, not the parent rel's */ + scan_plan->scan.plan.plan_rows = best_path->rows; + + return scan_plan; +} + +/* + * Given a bitmapqual tree, generate the Plan tree that implements it + */ +static Plan * +create_bitmap_subplan(Query *root, Node *bitmapqual) +{ + Plan *plan; + Plan *subplan; + + if (bitmapqual == NULL) + return NULL; /* probably can't happen */ + if (IsA(bitmapqual, List)) + { + /* this case is to handle the List arguments of AND/OR */ + List *newlist = NIL; + ListCell *l; + + foreach(l, (List *) bitmapqual) + { + subplan = create_bitmap_subplan(root, lfirst(l)); + newlist = lappend(newlist, subplan); + } + plan = (Plan *) newlist; + } + else if (and_clause(bitmapqual)) + { + subplan = create_bitmap_subplan(root, + (Node *) ((BoolExpr *) bitmapqual)->args); + plan = (Plan *) make_bitmap_and((List *) subplan); + } + else if (or_clause(bitmapqual)) + { + subplan = create_bitmap_subplan(root, + (Node *) ((BoolExpr *) bitmapqual)->args); + plan = (Plan *) make_bitmap_or((List *) subplan); + } + else if (IsA(bitmapqual, IndexPath)) + { + IndexPath *ipath = (IndexPath *) bitmapqual; + IndexScan *iscan; + BitmapIndexScan *bscan; + + /* Use the regular indexscan plan build machinery... */ + iscan = create_indexscan_plan(root, ipath, NIL, NIL); + Assert(list_length(iscan->indxid) == 1); + /* then convert to a bitmap indexscan */ + bscan = make_bitmap_indexscan(iscan->scan.scanrelid, + linitial_oid(iscan->indxid), + linitial(iscan->indxqual), + linitial(iscan->indxqualorig), + linitial(iscan->indxstrategy), + linitial(iscan->indxsubtype)); + /* XXX this cost is wrong: */ + copy_path_costsize(&bscan->scan.plan, &ipath->path); + /* use the indexscan-specific rows estimate, not the parent rel's */ + bscan->scan.plan.plan_rows = ipath->rows; + plan = (Plan *) bscan; + } + else + { + elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual)); + plan = NULL; /* keep compiler quiet */ + } + + return plan; +} + +/* + * Given a bitmapqual tree, generate the equivalent ordinary expression tree + * (which we need for the bitmapqualorig field of the BitmapHeapScan plan). + * The result is expressed as an implicit-AND list. + */ +static List * +create_bitmap_qual(Node *bitmapqual) +{ + List *result; + List *sublist; + + if (and_clause(bitmapqual)) + { + ListCell *l; + + result = NIL; + foreach(l, ((BoolExpr *) bitmapqual)->args) + { + sublist = create_bitmap_qual(lfirst(l)); + result = list_concat(result, sublist); + } + } + else if (or_clause(bitmapqual)) + { + List *newlist = NIL; + ListCell *l; + + foreach(l, ((BoolExpr *) bitmapqual)->args) + { + sublist = create_bitmap_qual(lfirst(l)); + if (sublist == NIL) + { + /* constant TRUE input yields constant TRUE OR result */ + return NIL; + } + newlist = lappend(newlist, make_ands_explicit(sublist)); + } + result = list_make1(make_orclause(newlist)); + } + else if (IsA(bitmapqual, IndexPath)) + { + IndexPath *ipath = (IndexPath *) bitmapqual; + + Assert(list_length(ipath->indexclauses) == 1); + result = get_actual_clauses(linitial(ipath->indexclauses)); + } + else + { + elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual)); + result = NIL; /* keep compiler quiet */ + } + + return result; +} + +/* + * Same as above, except extract the indxqual conditions (which are different + * if there are special index operators or lossy operators involved). + * + * The result essentially represents the conditions the indexscan guarantees + * to enforce, which may be weaker than the original qual expressions. + */ +static List * +create_bitmap_indxqual(Node *bitmapqual) +{ + List *result; + List *sublist; + ListCell *l; + + if (and_clause(bitmapqual)) + { + result = NIL; + foreach(l, ((BoolExpr *) bitmapqual)->args) + { + sublist = create_bitmap_indxqual(lfirst(l)); + result = list_concat(result, sublist); + } + } + else if (or_clause(bitmapqual)) + { + List *newlist = NIL; + + foreach(l, ((BoolExpr *) bitmapqual)->args) + { + sublist = create_bitmap_indxqual(lfirst(l)); + if (sublist == NIL) + { + /* constant TRUE input yields constant TRUE OR result */ + return NIL; + } + newlist = lappend(newlist, make_ands_explicit(sublist)); + } + result = list_make1(make_orclause(newlist)); + } + else if (IsA(bitmapqual, IndexPath)) + { + IndexPath *ipath = (IndexPath *) bitmapqual; + IndexOptInfo *index; + + Assert(list_length(ipath->indexinfo) == 1); + index = linitial(ipath->indexinfo); + + /* + * We have to remove "lossy" index operators from the result, since + * the index isn't guaranteeing they are enforced. (This will lead + * to the operators being rechecked as qpquals of the BitmapHeapScan + * node.) + * + * XXX look at restructuring to share code better with + * fix_indxqual_references() + */ + result = NIL; + Assert(list_length(ipath->indexquals) == 1); + foreach(l, (List *) linitial(ipath->indexquals)) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + OpExpr *clause; + Oid opno; + Node *indexkey; + Oid opclass; + int stratno; + Oid stratsubtype; + bool recheck; + + Assert(IsA(rinfo, RestrictInfo)); + clause = (OpExpr *) rinfo->clause; + if (!IsA(clause, OpExpr) || list_length(clause->args) != 2) + elog(ERROR, "indexqual clause is not binary opclause"); + opno = clause->opno; + + /* + * Check to see if the indexkey is on the right; if so, commute + * the operator. The indexkey should be the side that refers to + * (only) the base relation. + */ + if (!bms_equal(rinfo->left_relids, index->rel->relids)) + { + opno = get_commutator(opno); + if (!OidIsValid(opno)) + elog(ERROR, "could not find commutator for operator %u", + clause->opno); + indexkey = lsecond(clause->args); + } + else + indexkey = linitial(clause->args); + + /* + * Identify the index attribute and get the index opclass. + * We use fix_indxqual_operand() which does a little more + * than we really need, but it will do. + */ + (void) fix_indxqual_operand(indexkey, + index, + &opclass); + + /* + * Look up the (possibly commuted) operator in the operator class + * to get its strategy numbers and the recheck indicator. This + * also double-checks that we found an operator matching the + * index. + */ + get_op_opclass_properties(opno, opclass, + &stratno, &stratsubtype, &recheck); + + /* + * Finally, we can include the clause in the result if it's + * not a lossy operator. + */ + if (!recheck) + result = lappend(result, clause); + } + } + else + { + elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual)); + result = NIL; /* keep compiler quiet */ + } + + return result; +} + +/* * create_tidscan_plan * Returns a tidscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. @@ -1550,6 +1910,53 @@ make_indexscan(List *qptlist, return node; } +static BitmapIndexScan * +make_bitmap_indexscan(Index scanrelid, + Oid indxid, + List *indxqual, + List *indxqualorig, + List *indxstrategy, + List *indxsubtype) +{ + BitmapIndexScan *node = makeNode(BitmapIndexScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = NIL; /* not used */ + plan->qual = NIL; /* not used */ + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->indxid = indxid; + node->indxqual = indxqual; + node->indxqualorig = indxqualorig; + node->indxstrategy = indxstrategy; + node->indxsubtype = indxsubtype; + + return node; +} + +static BitmapHeapScan * +make_bitmap_heapscan(List *qptlist, + List *qpqual, + Plan *lefttree, + List *bitmapqualorig, + Index scanrelid) +{ + BitmapHeapScan *node = makeNode(BitmapHeapScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = lefttree; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->bitmapqualorig = bitmapqualorig; + + return node; +} + static TidScan * make_tidscan(List *qptlist, List *qpqual, @@ -1653,6 +2060,82 @@ make_append(List *appendplans, bool isTarget, List *tlist) return node; } +static BitmapAnd * +make_bitmap_and(List *bitmapplans) +{ + BitmapAnd *node = makeNode(BitmapAnd); + Plan *plan = &node->plan; + ListCell *subnode; + + /* + * Compute cost as sum of subplan costs, plus 10x cpu_operator_cost + * (a pretty arbitrary amount, agreed) for each tbm_intersect needed. + */ + plan->startup_cost = 0; + plan->total_cost = 0; + plan->plan_rows = 0; + plan->plan_width = 0; /* meaningless */ + foreach(subnode, bitmapplans) + { + Plan *subplan = (Plan *) lfirst(subnode); + + if (subnode == list_head(bitmapplans)) /* first node? */ + { + plan->startup_cost = subplan->startup_cost; + plan->plan_rows = subplan->plan_rows; + } + else + plan->plan_rows = Min(plan->plan_rows, subplan->plan_rows); + plan->total_cost += subplan->total_cost; + } + + plan->targetlist = NIL; + plan->qual = NIL; + plan->lefttree = NULL; + plan->righttree = NULL; + node->bitmapplans = bitmapplans; + + return node; +} + +static BitmapOr * +make_bitmap_or(List *bitmapplans) +{ + BitmapOr *node = makeNode(BitmapOr); + Plan *plan = &node->plan; + ListCell *subnode; + + /* + * Compute cost as sum of subplan costs, plus 10x cpu_operator_cost + * (a pretty arbitrary amount, agreed) for each tbm_union needed. + * We assume that tbm_union can be optimized away for BitmapIndexScan + * subplans. + */ + plan->startup_cost = 0; + plan->total_cost = 0; + plan->plan_rows = 0; + plan->plan_width = 0; /* meaningless */ + foreach(subnode, bitmapplans) + { + Plan *subplan = (Plan *) lfirst(subnode); + + if (subnode == list_head(bitmapplans)) /* first node? */ + plan->startup_cost = subplan->startup_cost; + else if (!IsA(subplan, BitmapIndexScan)) + plan->total_cost += cpu_operator_cost * 10; + plan->total_cost += subplan->total_cost; + plan->plan_rows += subplan->plan_rows; /* ignore overlap */ + } + + plan->targetlist = NIL; + plan->qual = NIL; + plan->lefttree = NULL; + plan->righttree = NULL; + node->bitmapplans = bitmapplans; + + return node; +} + static NestLoop * make_nestloop(List *tlist, List *joinclauses, diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 075c6a339df..0688d86b1b1 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.106 2005/04/06 16:34:05 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.107 2005/04/19 22:35:16 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -107,6 +107,21 @@ set_plan_references(Plan *plan, List *rtable) fix_expr_references(plan, (Node *) ((IndexScan *) plan)->indxqualorig); break; + case T_BitmapIndexScan: + /* no need to fix targetlist and qual */ + Assert(plan->targetlist == NIL); + Assert(plan->qual == NIL); + fix_expr_references(plan, + (Node *) ((BitmapIndexScan *) plan)->indxqual); + fix_expr_references(plan, + (Node *) ((BitmapIndexScan *) plan)->indxqualorig); + break; + case T_BitmapHeapScan: + fix_expr_references(plan, (Node *) plan->targetlist); + fix_expr_references(plan, (Node *) plan->qual); + fix_expr_references(plan, + (Node *) ((BitmapHeapScan *) plan)->bitmapqualorig); + break; case T_TidScan: fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); @@ -225,6 +240,16 @@ set_plan_references(Plan *plan, List *rtable) foreach(l, ((Append *) plan)->appendplans) set_plan_references((Plan *) lfirst(l), rtable); break; + case T_BitmapAnd: + /* BitmapAnd works like Append */ + foreach(l, ((BitmapAnd *) plan)->bitmapplans) + set_plan_references((Plan *) lfirst(l), rtable); + break; + case T_BitmapOr: + /* BitmapOr works like Append */ + foreach(l, ((BitmapOr *) plan)->bitmapplans) + set_plan_references((Plan *) lfirst(l), rtable); + break; default: elog(ERROR, "unrecognized node type: %d", (int) nodeTag(plan)); diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index f1519569a85..7f5a4fde63b 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.96 2005/04/11 23:06:55 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.97 2005/04/19 22:35:16 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -1037,6 +1037,20 @@ finalize_plan(Plan *plan, List *rtable, */ break; + case T_BitmapIndexScan: + finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indxqual, + &context); + /* + * we need not look at indxqualorig, since it will have the + * same param references as indxqual. + */ + break; + + case T_BitmapHeapScan: + finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig, + &context); + break; + case T_TidScan: finalize_primnode((Node *) ((TidScan *) plan)->tideval, &context); @@ -1082,6 +1096,38 @@ finalize_plan(Plan *plan, List *rtable, } break; + case T_BitmapAnd: + { + ListCell *l; + + foreach(l, ((BitmapAnd *) plan)->bitmapplans) + { + context.paramids = + bms_add_members(context.paramids, + finalize_plan((Plan *) lfirst(l), + rtable, + outer_params, + valid_params)); + } + } + break; + + case T_BitmapOr: + { + ListCell *l; + + foreach(l, ((BitmapOr *) plan)->bitmapplans) + { + context.paramids = + bms_add_members(context.paramids, + finalize_plan((Plan *) lfirst(l), + rtable, + outer_params, + valid_params)); + } + } + break; + case T_NestLoop: finalize_primnode((Node *) ((Join *) plan)->joinqual, &context); diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 14b62b80fc8..ec0fc8a29ab 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.115 2005/04/06 16:34:06 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.116 2005/04/19 22:35:17 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -472,6 +472,39 @@ create_index_path(Query *root, } /* + * create_bitmap_heap_path + * Creates a path node for a bitmap scan. + * + * 'bitmapqual' is an AND/OR tree of IndexPath nodes. + */ +BitmapHeapPath * +create_bitmap_heap_path(Query *root, + RelOptInfo *rel, + Node *bitmapqual) +{ + BitmapHeapPath *pathnode = makeNode(BitmapHeapPath); + + pathnode->path.pathtype = T_BitmapHeapScan; + pathnode->path.parent = rel; + pathnode->path.pathkeys = NIL; /* always unordered */ + + pathnode->bitmapqual = bitmapqual; + + /* It's not an innerjoin path. */ + pathnode->isjoininner = false; + + /* + * The number of rows is the same as the parent rel's estimate, since + * this isn't a join inner indexscan. + */ + pathnode->rows = rel->rows; + + cost_bitmap_scan(&pathnode->path, root, rel, bitmapqual, false); + + return pathnode; +} + +/* * create_tidscan_path * Creates a path corresponding to a tid_direct scan, returning the * pathnode. diff --git a/src/include/executor/nodeBitmapAnd.h b/src/include/executor/nodeBitmapAnd.h new file mode 100644 index 00000000000..320fc71ab7c --- /dev/null +++ b/src/include/executor/nodeBitmapAnd.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapAnd.h + * + * + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeBitmapAnd.h,v 1.1 2005/04/19 22:35:17 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODEBITMAPAND_H +#define NODEBITMAPAND_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsBitmapAnd(BitmapAnd *node); +extern BitmapAndState *ExecInitBitmapAnd(BitmapAnd *node, EState *estate); +extern Node *MultiExecBitmapAnd(BitmapAndState *node); +extern void ExecEndBitmapAnd(BitmapAndState *node); +extern void ExecReScanBitmapAnd(BitmapAndState *node, ExprContext *exprCtxt); + +#endif /* NODEBITMAPAND_H */ diff --git a/src/include/executor/nodeBitmapHeapscan.h b/src/include/executor/nodeBitmapHeapscan.h new file mode 100644 index 00000000000..48c4b6ad79a --- /dev/null +++ b/src/include/executor/nodeBitmapHeapscan.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapHeapscan.h + * + * + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeBitmapHeapscan.h,v 1.1 2005/04/19 22:35:17 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODEBITMAPHEAPSCAN_H +#define NODEBITMAPHEAPSCAN_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsBitmapHeapScan(BitmapHeapScan *node); +extern BitmapHeapScanState *ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate); +extern TupleTableSlot *ExecBitmapHeapScan(BitmapHeapScanState *node); +extern void ExecEndBitmapHeapScan(BitmapHeapScanState *node); +extern void ExecBitmapHeapReScan(BitmapHeapScanState *node, ExprContext *exprCtxt); + +#endif /* NODEBITMAPHEAPSCAN_H */ diff --git a/src/include/executor/nodeBitmapIndexscan.h b/src/include/executor/nodeBitmapIndexscan.h new file mode 100644 index 00000000000..7ca5553abbd --- /dev/null +++ b/src/include/executor/nodeBitmapIndexscan.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapIndexscan.h + * + * + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeBitmapIndexscan.h,v 1.1 2005/04/19 22:35:17 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODEBITMAPINDEXSCAN_H +#define NODEBITMAPINDEXSCAN_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsBitmapIndexScan(BitmapIndexScan *node); +extern BitmapIndexScanState *ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate); +extern Node *MultiExecBitmapIndexScan(BitmapIndexScanState *node); +extern void ExecEndBitmapIndexScan(BitmapIndexScanState *node); +extern void ExecBitmapIndexReScan(BitmapIndexScanState *node, ExprContext *exprCtxt); + +#endif /* NODEBITMAPINDEXSCAN_H */ diff --git a/src/include/executor/nodeBitmapOr.h b/src/include/executor/nodeBitmapOr.h new file mode 100644 index 00000000000..927231a708a --- /dev/null +++ b/src/include/executor/nodeBitmapOr.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeBitmapOr.h + * + * + * + * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeBitmapOr.h,v 1.1 2005/04/19 22:35:17 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODEBITMAPOR_H +#define NODEBITMAPOR_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsBitmapOr(BitmapOr *node); +extern BitmapOrState *ExecInitBitmapOr(BitmapOr *node, EState *estate); +extern Node *MultiExecBitmapOr(BitmapOrState *node); +extern void ExecEndBitmapOr(BitmapOrState *node); +extern void ExecReScanBitmapOr(BitmapOrState *node, ExprContext *exprCtxt); + +#endif /* NODEBITMAPOR_H */ diff --git a/src/include/executor/nodeIndexscan.h b/src/include/executor/nodeIndexscan.h index e4e3026038b..530ac5117bb 100644 --- a/src/include/executor/nodeIndexscan.h +++ b/src/include/executor/nodeIndexscan.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/executor/nodeIndexscan.h,v 1.21 2004/12/31 22:03:29 pgsql Exp $ + * $PostgreSQL: pgsql/src/include/executor/nodeIndexscan.h,v 1.22 2005/04/19 22:35:17 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,6 +24,4 @@ extern void ExecIndexMarkPos(IndexScanState *node); extern void ExecIndexRestrPos(IndexScanState *node); extern void ExecIndexReScan(IndexScanState *node, ExprContext *exprCtxt); -extern void ExecUpdateIndexScanKeys(IndexScanState *node, ExprContext *econtext); - #endif /* NODEINDEXSCAN_H */ diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index da82daaac98..a5176c2f955 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.125 2005/03/25 21:58:00 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.126 2005/04/19 22:35:17 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -20,6 +20,7 @@ #include "nodes/bitmapset.h" #include "nodes/params.h" #include "nodes/plannodes.h" +#include "nodes/tidbitmap.h" #include "utils/hsearch.h" #include "utils/tuplestore.h" @@ -803,6 +804,28 @@ typedef struct AppendState int as_lastplan; } AppendState; +/* ---------------- + * BitmapAndState information + * ---------------- + */ +typedef struct BitmapAndState +{ + PlanState ps; /* its first field is NodeTag */ + PlanState **bitmapplans; /* array of PlanStates for my inputs */ + int nplans; /* number of input plans */ +} BitmapAndState; + +/* ---------------- + * BitmapOrState information + * ---------------- + */ +typedef struct BitmapOrState +{ + PlanState ps; /* its first field is NodeTag */ + PlanState **bitmapplans; /* array of PlanStates for my inputs */ + int nplans; /* number of input plans */ +} BitmapOrState; + /* ---------------------------------------------------------------- * Scan State Information * ---------------------------------------------------------------- @@ -876,6 +899,53 @@ typedef struct IndexScanState } IndexScanState; /* ---------------- + * BitmapIndexScanState information + * + * ScanKeys Skey structures to scan index rel + * NumScanKeys number of Skey structs + * RuntimeKeyInfo array of exprstates for Skeys + * that will be evaluated at runtime + * RuntimeContext expr context for evaling runtime Skeys + * RuntimeKeysReady true if runtime Skeys have been computed + * RelationDesc relation descriptor + * ScanDesc scan descriptor + * ---------------- + */ +typedef struct BitmapIndexScanState +{ + ScanState ss; /* its first field is NodeTag */ + ScanKey biss_ScanKeys; + int biss_NumScanKeys; + ExprState **biss_RuntimeKeyInfo; + ExprContext *biss_RuntimeContext; + bool biss_RuntimeKeysReady; + Relation biss_RelationDesc; + IndexScanDesc biss_ScanDesc; +} BitmapIndexScanState; + +/* ---------------- + * BitmapHeapScanState information + * + * bitmapqualorig execution state for bitmapqualorig expressions + * tbm bitmap obtained from child index scan(s) + * tbmres current-page data + * curslot current tbmres index or tuple offset on page + * minslot lowest tbmres index or tuple offset to try + * maxslot highest tbmres index or tuple offset to try + * ---------------- + */ +typedef struct BitmapHeapScanState +{ + ScanState ss; /* its first field is NodeTag */ + List *bitmapqualorig; + TIDBitmap *tbm; + TBMIterateResult *tbmres; + int curslot; + int minslot; + int maxslot; +} BitmapHeapScanState; + +/* ---------------- * TidScanState information * * NumTids number of tids in this scan diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 3c5528546af..32df3bff0eb 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.166 2005/04/17 22:24:02 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.167 2005/04/19 22:35:17 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -44,9 +44,13 @@ typedef enum NodeTag T_Plan = 100, T_Result, T_Append, + T_BitmapAnd, + T_BitmapOr, T_Scan, T_SeqScan, T_IndexScan, + T_BitmapIndexScan, + T_BitmapHeapScan, T_TidScan, T_SubqueryScan, T_FunctionScan, @@ -71,9 +75,13 @@ typedef enum NodeTag T_PlanState = 200, T_ResultState, T_AppendState, + T_BitmapAndState, + T_BitmapOrState, T_ScanState, T_SeqScanState, T_IndexScanState, + T_BitmapIndexScanState, + T_BitmapHeapScanState, T_TidScanState, T_SubqueryScanState, T_FunctionScanState, @@ -161,6 +169,7 @@ typedef enum NodeTag T_IndexOptInfo, T_Path, T_IndexPath, + T_BitmapHeapPath, T_NestPath, T_MergePath, T_HashPath, diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 50eb59cc654..4ab8473e562 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.77 2004/12/31 22:03:34 pgsql Exp $ + * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.78 2005/04/19 22:35:17 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -134,6 +134,34 @@ typedef struct Append bool isTarget; } Append; +/* ---------------- + * BitmapAnd node - + * Generate the intersection of the results of sub-plans. + * + * The subplans must be of types that yield tuple bitmaps. The targetlist + * and qual fields of the plan are unused and are always NIL. + * ---------------- + */ +typedef struct BitmapAnd +{ + Plan plan; + List *bitmapplans; +} BitmapAnd; + +/* ---------------- + * BitmapOr node - + * Generate the union of the results of sub-plans. + * + * The subplans must be of types that yield tuple bitmaps. The targetlist + * and qual fields of the plan are unused and are always NIL. + * ---------------- + */ +typedef struct BitmapOr +{ + Plan plan; + List *bitmapplans; +} BitmapOr; + /* * ========== * Scan nodes @@ -156,6 +184,8 @@ typedef Scan SeqScan; * * Note: this can actually represent N indexscans, all on the same table * but potentially using different indexes, put together with OR semantics. + * (XXX that extension should probably go away, because bitmapindexscan will + * largely eliminate the need for it.) * ---------------- */ typedef struct IndexScan @@ -171,7 +201,46 @@ typedef struct IndexScan } IndexScan; /* ---------------- - * tid scan node + * bitmap index scan node + * + * BitmapIndexScan delivers a bitmap of potential tuple locations; + * it does not access the heap itself. The bitmap is used by an + * ancestor BitmapHeapScan node, possibly after passing through + * intermediate BitmapAnd and/or BitmapOr nodes to combine it with + * the results of other BitmapIndexScans. + * + * In a BitmapIndexScan plan node, the targetlist and qual fields are + * not used and are always NIL. The indxqualorig field is useless at + * run time too, but is saved for the benefit of EXPLAIN. + * ---------------- + */ +typedef struct BitmapIndexScan +{ + Scan scan; + Oid indxid; /* OID of index to scan */ + List *indxqual; /* list of index quals */ + List *indxqualorig; /* list of original forms of index quals */ + List *indxstrategy; /* list of strategy numbers */ + List *indxsubtype; /* list of strategy subtypes */ +} BitmapIndexScan; + +/* ---------------- + * bitmap sequential scan node + * + * This needs a copy of the qual conditions being used by the input index + * scans because there are various cases where we need to recheck the quals; + * for example, when the bitmap is lossy about the specific rows on a page + * that meet the index condition. + * ---------------- + */ +typedef struct BitmapHeapScan +{ + Scan scan; + List *bitmapqualorig; /* index quals, in standard expr form */ +} BitmapHeapScan; + +/* ---------------- + * tid scan node * ---------------- */ typedef struct TidScan diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 4698e4d8cb3..2e4e1834fe6 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.104 2005/03/27 06:29:45 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.105 2005/04/19 22:35:17 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -342,6 +342,9 @@ typedef struct Path * tuples matched during any scan. (The executor is smart enough not to return * the same tuple more than once, even if it is matched in multiple scans.) * + * XXX bitmap index scans will probably obviate the need for plain OR + * indexscans, allowing a lot of this to be simplified. + * * 'indexinfo' is a list of IndexOptInfo nodes, one per scan to be performed. * * 'indexclauses' is a list of index qualifications, also one per scan. @@ -390,6 +393,30 @@ typedef struct IndexPath } IndexPath; /* + * BitmapHeapPath represents one or more indexscans that generate TID bitmaps + * instead of directly accessing the heap, followed by AND/OR combinations + * to produce a single bitmap, followed by a heap scan that uses the bitmap. + * Note that the output is always considered unordered, since it will come + * out in physical heap order no matter what the underlying indexes did. + * + * The individual indexscans are represented by IndexPath nodes, and any + * logic on top of them is represented by regular AND and OR expressions. + * Notice that we can use the same IndexPath node both to represent an + * ordered index scan, and as the child of a BitmapHeapPath that represents + * scanning the same index in an unordered way. + * + * BitmapHeapPaths can be nestloop inner indexscans. The isjoininner and + * rows fields serve the same purpose as for plain IndexPaths. + */ +typedef struct BitmapHeapPath +{ + Path path; + Node *bitmapqual; /* the IndexPath/AND/OR tree */ + bool isjoininner; /* T if it's a nestloop inner scan */ + double rows; /* estimated number of result tuples */ +} BitmapHeapPath; + +/* * TidPath represents a scan by TID * * tideval is an implicitly OR'ed list of quals of the form CTID = something. diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index 9e379dd0c4b..8b1445dadf1 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.63 2005/03/27 06:29:49 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.64 2005/04/19 22:35:18 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -53,6 +53,8 @@ extern double clamp_row_est(double nrows); extern void cost_seqscan(Path *path, Query *root, RelOptInfo *baserel); extern void cost_index(Path *path, Query *root, IndexOptInfo *index, List *indexQuals, bool is_injoin); +extern void cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel, + Node *bitmapqual, bool is_injoin); extern void cost_tidscan(Path *path, Query *root, RelOptInfo *baserel, List *tideval); extern void cost_subqueryscan(Path *path, RelOptInfo *baserel); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 44e9b087b33..308c5daa6cd 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.57 2005/03/27 06:29:49 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.58 2005/04/19 22:35:18 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -33,6 +33,9 @@ extern IndexPath *create_index_path(Query *root, List *restriction_clauses, List *pathkeys, ScanDirection indexscandir); +extern BitmapHeapPath *create_bitmap_heap_path(Query *root, + RelOptInfo *rel, + Node *bitmapqual); extern TidPath *create_tidscan_path(Query *root, RelOptInfo *rel, List *tideval); extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths); |