diff options
Diffstat (limited to 'src/include')
| -rw-r--r-- | src/include/executor/nodeBitmapAnd.h | 25 | ||||
| -rw-r--r-- | src/include/executor/nodeBitmapHeapscan.h | 25 | ||||
| -rw-r--r-- | src/include/executor/nodeBitmapIndexscan.h | 25 | ||||
| -rw-r--r-- | src/include/executor/nodeBitmapOr.h | 25 | ||||
| -rw-r--r-- | src/include/executor/nodeIndexscan.h | 4 | ||||
| -rw-r--r-- | src/include/nodes/execnodes.h | 72 | ||||
| -rw-r--r-- | src/include/nodes/nodes.h | 11 | ||||
| -rw-r--r-- | src/include/nodes/plannodes.h | 73 | ||||
| -rw-r--r-- | src/include/nodes/relation.h | 29 | ||||
| -rw-r--r-- | src/include/optimizer/cost.h | 4 | ||||
| -rw-r--r-- | src/include/optimizer/pathnode.h | 5 |
11 files changed, 288 insertions, 10 deletions
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); |