X-Git-Url: https://granicus.if.org/sourcecode?a=blobdiff_plain;f=src%2Fbackend%2Foptimizer%2Fplan%2Fcreateplan.c;h=e202b1364fc0d55c814ea57d6a6c8214f7100113;hb=fa601357fb6c907a8e339b8a2ea7b4a8e2acf212;hp=1b4c9d478097b538b353384f919c92f4381283d2;hpb=1812d3b233e40d6e94e2105c3da4b1fca93c9385;p=postgresql diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 1b4c9d4780..e202b1364f 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -5,12 +5,12 @@ * Planning is complete, we just need to convert the selected * Path into a Plan. * - * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group + * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.169 2004/04/25 18:23:56 neilc Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.213 2006/07/11 16:35:31 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -22,72 +22,83 @@ #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" -#include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/planmain.h" +#include "optimizer/predtest.h" #include "optimizer/restrictinfo.h" #include "optimizer/tlist.h" #include "optimizer/var.h" -#include "parser/parsetree.h" #include "parser/parse_clause.h" #include "parser/parse_expr.h" +#include "parser/parsetree.h" #include "utils/lsyscache.h" #include "utils/syscache.h" -static Scan *create_scan_plan(Query *root, Path *best_path); +static Plan *create_scan_plan(PlannerInfo *root, Path *best_path); static List *build_relation_tlist(RelOptInfo *rel); static bool use_physical_tlist(RelOptInfo *rel); static void disuse_physical_tlist(Plan *plan, Path *path); -static Join *create_join_plan(Query *root, JoinPath *best_path); -static Append *create_append_plan(Query *root, AppendPath *best_path); -static Result *create_result_plan(Query *root, ResultPath *best_path); -static Material *create_material_plan(Query *root, MaterialPath *best_path); -static Plan *create_unique_plan(Query *root, UniquePath *best_path); -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 TidScan *create_tidscan_plan(Query *root, TidPath *best_path, - List *tlist, List *scan_clauses); -static SubqueryScan *create_subqueryscan_plan(Query *root, Path *best_path, +static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals); +static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path); +static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path); +static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path); +static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path); +static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path); +static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); +static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path, + List *tlist, List *scan_clauses, + List **nonlossy_clauses); +static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root, + BitmapHeapPath *best_path, + List *tlist, List *scan_clauses); +static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual, + List **qual, List **indexqual); +static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path, + List *tlist, List *scan_clauses); +static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses); -static FunctionScan *create_functionscan_plan(Query *root, Path *best_path, +static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses); -static NestLoop *create_nestloop_plan(Query *root, NestPath *best_path, +static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path, Plan *outer_plan, Plan *inner_plan); -static MergeJoin *create_mergejoin_plan(Query *root, MergePath *best_path, +static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path, Plan *outer_plan, Plan *inner_plan); -static HashJoin *create_hashjoin_plan(Query *root, HashPath *best_path, +static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path, Plan *outer_plan, Plan *inner_plan); -static void fix_indxqual_references(List *indexquals, IndexPath *index_path, - List **fixed_indexquals, - List **indxstrategy, - List **indxsubtype, - List **indxlossy); -static void fix_indxqual_sublist(List *indexqual, - Relids baserelids, int baserelid, - IndexOptInfo *index, - List **fixed_quals, - List **strategy, - List **subtype, - List **lossy); -static Node *fix_indxqual_operand(Node *node, int baserelid, - IndexOptInfo *index, - Oid *opclass); +static void fix_indexqual_references(List *indexquals, IndexPath *index_path, + List **fixed_indexquals, + List **nonlossy_indexquals, + List **indexstrategy, + List **indexsubtype); +static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, + Oid *opclass); static List *get_switched_clauses(List *clauses, Relids outerrelids); -static List *order_qual_clauses(Query *root, List *clauses); +static List *order_qual_clauses(PlannerInfo *root, List *clauses); static void copy_path_costsize(Plan *dest, Path *src); static void copy_plan_costsize(Plan *dest, Plan *src); static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, - List *indxid, List *indxqual, List *indxqualorig, - List *indxstrategy, List *indxsubtype, List *indxlossy, + Oid indexid, List *indexqual, List *indexqualorig, + List *indexstrategy, List *indexsubtype, ScanDirection indexscandir); +static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid, + List *indexqual, + List *indexqualorig, + List *indexstrategy, + List *indexsubtype); +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); + List *tidquals); 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, @@ -103,9 +114,9 @@ static MergeJoin *make_mergejoin(List *tlist, List *mergeclauses, Plan *lefttree, Plan *righttree, JoinType jointype); -static Sort *make_sort(Query *root, Plan *lefttree, int numCols, +static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators); -static Sort *make_sort_from_pathkeys(Query *root, Plan *lefttree, +static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys); @@ -125,28 +136,29 @@ static Sort *make_sort_from_pathkeys(Query *root, Plan *lefttree, * Returns a Plan tree. */ Plan * -create_plan(Query *root, Path *best_path) +create_plan(PlannerInfo *root, Path *best_path) { Plan *plan; 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: - plan = (Plan *) create_scan_plan(root, best_path); + plan = create_scan_plan(root, best_path); break; case T_HashJoin: case T_MergeJoin: case T_NestLoop: - plan = (Plan *) create_join_plan(root, - (JoinPath *) best_path); + plan = create_join_plan(root, + (JoinPath *) best_path); break; case T_Append: - plan = (Plan *) create_append_plan(root, - (AppendPath *) best_path); + plan = create_append_plan(root, + (AppendPath *) best_path); break; case T_Result: plan = (Plan *) create_result_plan(root, @@ -154,11 +166,11 @@ create_plan(Query *root, Path *best_path) break; case T_Material: plan = (Plan *) create_material_plan(root, - (MaterialPath *) best_path); + (MaterialPath *) best_path); break; case T_Unique: - plan = (Plan *) create_unique_plan(root, - (UniquePath *) best_path); + plan = create_unique_plan(root, + (UniquePath *) best_path); break; default: elog(ERROR, "unrecognized node type: %d", @@ -173,24 +185,22 @@ create_plan(Query *root, Path *best_path) /* * create_scan_plan * Create a scan plan for the parent relation of 'best_path'. - * - * Returns a Plan node. */ -static Scan * -create_scan_plan(Query *root, Path *best_path) +static Plan * +create_scan_plan(PlannerInfo *root, Path *best_path) { RelOptInfo *rel = best_path->parent; List *tlist; List *scan_clauses; - Scan *plan; + Plan *plan; /* - * For table scans, rather than using the relation targetlist (which - * is only those Vars actually needed by the query), we prefer to - * generate a tlist containing all Vars in order. This will allow the - * executor to optimize away projection of the table tuples, if - * possible. (Note that planner.c may replace the tlist we generate - * here, forcing projection to occur.) + * For table scans, rather than using the relation targetlist (which is + * only those Vars actually needed by the query), we prefer to generate a + * tlist containing all Vars in order. This will allow the executor to + * optimize away projection of the table tuples, if possible. (Note that + * planner.c may replace the tlist we generate here, forcing projection to + * occur.) */ if (use_physical_tlist(rel)) { @@ -203,43 +213,52 @@ create_scan_plan(Query *root, Path *best_path) tlist = build_relation_tlist(rel); /* - * Extract the relevant restriction clauses from the parent relation; - * the executor must apply all these restrictions during the scan. + * Extract the relevant restriction clauses from the parent relation. + * The executor must apply all these restrictions during the scan, + * except for pseudoconstants which we'll take care of below. */ scan_clauses = rel->baserestrictinfo; switch (best_path->pathtype) { case T_SeqScan: - plan = (Scan *) create_seqscan_plan(root, + plan = (Plan *) create_seqscan_plan(root, best_path, tlist, scan_clauses); break; case T_IndexScan: - plan = (Scan *) create_indexscan_plan(root, + plan = (Plan *) create_indexscan_plan(root, (IndexPath *) best_path, tlist, - scan_clauses); + scan_clauses, + NULL); + break; + + case T_BitmapHeapScan: + plan = (Plan *) create_bitmap_scan_plan(root, + (BitmapHeapPath *) best_path, + tlist, + scan_clauses); break; case T_TidScan: - plan = (Scan *) create_tidscan_plan(root, + plan = (Plan *) create_tidscan_plan(root, (TidPath *) best_path, tlist, scan_clauses); break; case T_SubqueryScan: - plan = (Scan *) create_subqueryscan_plan(root, + plan = (Plan *) create_subqueryscan_plan(root, best_path, tlist, scan_clauses); break; case T_FunctionScan: - plan = (Scan *) create_functionscan_plan(root, + plan = (Plan *) create_functionscan_plan(root, best_path, tlist, scan_clauses); @@ -252,6 +271,14 @@ create_scan_plan(Query *root, Path *best_path) break; } + /* + * If there are any pseudoconstant clauses attached to this node, + * insert a gating Result node that evaluates the pseudoconstants + * as one-time quals. + */ + if (root->hasPseudoConstantQuals) + plan = create_gating_plan(root, plan, scan_clauses); + return plan; } @@ -261,20 +288,22 @@ create_scan_plan(Query *root, Path *best_path) static List * build_relation_tlist(RelOptInfo *rel) { - FastList tlist; - int resdomno = 1; - List *v; + List *tlist = NIL; + int resno = 1; + ListCell *v; - FastListInit(&tlist); - foreach(v, FastListValue(&rel->reltargetlist)) + foreach(v, rel->reltargetlist) { /* Do we really need to copy here? Not sure */ Var *var = (Var *) copyObject(lfirst(v)); - FastAppend(&tlist, create_tl_element(var, resdomno)); - resdomno++; + tlist = lappend(tlist, makeTargetEntry((Expr *) var, + resno, + NULL, + false)); + resno++; } - return FastListValue(&tlist); + return tlist; } /* @@ -288,11 +317,12 @@ use_physical_tlist(RelOptInfo *rel) int i; /* - * Currently, can't do this for subquery or function scans. (This is - * mainly because we don't have an equivalent of build_physical_tlist - * for them; worth adding?) + * We can do this for real relation scans, subquery scans, and function + * scans (but not for, eg, joins). */ - if (rel->rtekind != RTE_RELATION) + if (rel->rtekind != RTE_RELATION && + rel->rtekind != RTE_SUBQUERY && + rel->rtekind != RTE_FUNCTION) return false; /* @@ -303,15 +333,16 @@ use_physical_tlist(RelOptInfo *rel) return false; /* - * Can't do it if any system columns are requested, either. (This - * could possibly be fixed but would take some fragile assumptions in - * setrefs.c, I think.) + * Can't do it if any system columns or whole-row Vars are requested, + * either. (This could possibly be fixed but would take some fragile + * assumptions in setrefs.c, I think.) */ for (i = rel->min_attr; i <= 0; i++) { if (!bms_is_empty(rel->attr_needed[i - rel->min_attr])) return false; } + return true; } @@ -330,8 +361,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: @@ -342,19 +374,54 @@ disuse_physical_tlist(Plan *plan, Path *path) } } +/* + * create_gating_plan + * Deal with pseudoconstant qual clauses + * + * If the node's quals list includes any pseudoconstant quals, put them + * into a gating Result node atop the already-built plan. Otherwise, + * return the plan as-is. + * + * Note that we don't change cost or size estimates when doing gating. + * The costs of qual eval were already folded into the plan's startup cost. + * Leaving the size alone amounts to assuming that the gating qual will + * succeed, which is the conservative estimate for planning upper queries. + * We certainly don't want to assume the output size is zero (unless the + * gating qual is actually constant FALSE, and that case is dealt with in + * clausesel.c). Interpolating between the two cases is silly, because + * it doesn't reflect what will really happen at runtime, and besides which + * in most cases we have only a very bad idea of the probability of the gating + * qual being true. + */ +static Plan * +create_gating_plan(PlannerInfo *root, Plan *plan, List *quals) +{ + List *pseudoconstants; + + /* Pull out any pseudoconstant quals from the RestrictInfo list */ + pseudoconstants = extract_actual_clauses(quals, true); + + if (!pseudoconstants) + return plan; + + pseudoconstants = order_qual_clauses(root, pseudoconstants); + + return (Plan *) make_result((List *) copyObject(plan->targetlist), + (Node *) pseudoconstants, + plan); +} + /* * create_join_plan * Create a join plan for 'best_path' and (recursively) plans for its * inner and outer paths. - * - * Returns a Plan node. */ -static Join * -create_join_plan(Query *root, JoinPath *best_path) +static Plan * +create_join_plan(PlannerInfo *root, JoinPath *best_path) { Plan *outer_plan; Plan *inner_plan; - Join *plan; + Plan *plan; outer_plan = create_plan(root, best_path->outerjoinpath); inner_plan = create_plan(root, best_path->innerjoinpath); @@ -362,19 +429,19 @@ create_join_plan(Query *root, JoinPath *best_path) switch (best_path->path.pathtype) { case T_MergeJoin: - plan = (Join *) create_mergejoin_plan(root, + plan = (Plan *) create_mergejoin_plan(root, (MergePath *) best_path, outer_plan, inner_plan); break; case T_HashJoin: - plan = (Join *) create_hashjoin_plan(root, + plan = (Plan *) create_hashjoin_plan(root, (HashPath *) best_path, outer_plan, inner_plan); break; case T_NestLoop: - plan = (Join *) create_nestloop_plan(root, + plan = (Plan *) create_nestloop_plan(root, (NestPath *) best_path, outer_plan, inner_plan); @@ -386,17 +453,25 @@ create_join_plan(Query *root, JoinPath *best_path) break; } + /* + * If there are any pseudoconstant clauses attached to this node, + * insert a gating Result node that evaluates the pseudoconstants + * as one-time quals. + */ + if (root->hasPseudoConstantQuals) + plan = create_gating_plan(root, plan, best_path->joinrestrictinfo); + #ifdef NOT_USED /* - * * Expensive function pullups may have pulled local predicates * - * into this path node. Put them in the qpqual of the plan node. * - * JMH, 6/15/92 + * * Expensive function pullups may have pulled local predicates * into + * this path node. Put them in the qpqual of the plan node. * JMH, + * 6/15/92 */ if (get_loc_restrictinfo(best_path) != NIL) set_qpqual((Plan) plan, - nconc(get_qpqual((Plan) plan), - get_actual_clauses(get_loc_restrictinfo(best_path)))); + list_concat(get_qpqual((Plan) plan), + get_actual_clauses(get_loc_restrictinfo(best_path)))); #endif return plan; @@ -409,14 +484,33 @@ create_join_plan(Query *root, JoinPath *best_path) * * Returns a Plan node. */ -static Append * -create_append_plan(Query *root, AppendPath *best_path) +static Plan * +create_append_plan(PlannerInfo *root, AppendPath *best_path) { Append *plan; List *tlist = build_relation_tlist(best_path->path.parent); List *subplans = NIL; - List *subpaths; + ListCell *subpaths; + /* + * It is possible for the subplans list to contain only one entry, or even + * no entries. Handle these cases specially. + * + * XXX ideally, if there's just one entry, we'd not bother to generate an + * Append node but just return the single child. At the moment this does + * not work because the varno of the child scan plan won't match the + * parent-rel Vars it'll be asked to emit. + */ + if (best_path->subpaths == NIL) + { + /* Generate a Result plan with constant-FALSE gating qual */ + return (Plan *) make_result(tlist, + (Node *) list_make1(makeBoolConst(false, + false)), + NULL); + } + + /* Normal case with multiple subpaths */ foreach(subpaths, best_path->subpaths) { Path *subpath = (Path *) lfirst(subpaths); @@ -426,39 +520,29 @@ create_append_plan(Query *root, AppendPath *best_path) plan = make_append(subplans, false, tlist); - return plan; + return (Plan *) plan; } /* * create_result_plan - * Create a Result plan for 'best_path' and (recursively) plans - * for its subpaths. + * Create a Result plan for 'best_path'. + * This is only used for the case of a query with an empty jointree. * * Returns a Plan node. */ static Result * -create_result_plan(Query *root, ResultPath *best_path) +create_result_plan(PlannerInfo *root, ResultPath *best_path) { - Result *plan; List *tlist; - List *constclauses; - Plan *subplan; + List *quals; - if (best_path->path.parent) - tlist = build_relation_tlist(best_path->path.parent); - else - tlist = NIL; /* will be filled in later */ - - if (best_path->subpath) - subplan = create_plan(root, best_path->subpath); - else - subplan = NULL; + /* The tlist will be installed later, since we have no RelOptInfo */ + Assert(best_path->path.parent == NULL); + tlist = NIL; - constclauses = order_qual_clauses(root, best_path->constantqual); + quals = order_qual_clauses(root, best_path->quals); - plan = make_result(tlist, (Node *) constclauses, subplan); - - return plan; + return make_result(tlist, (Node *) quals, NULL); } /* @@ -469,7 +553,7 @@ create_result_plan(Query *root, ResultPath *best_path) * Returns a Plan node. */ static Material * -create_material_plan(Query *root, MaterialPath *best_path) +create_material_plan(PlannerInfo *root, MaterialPath *best_path) { Material *plan; Plan *subplan; @@ -494,44 +578,44 @@ create_material_plan(Query *root, MaterialPath *best_path) * Returns a Plan node. */ static Plan * -create_unique_plan(Query *root, UniquePath *best_path) +create_unique_plan(PlannerInfo *root, UniquePath *best_path) { Plan *plan; Plan *subplan; List *uniq_exprs; - int numGroupCols; - AttrNumber *groupColIdx; - int groupColPos; List *newtlist; int nextresno; bool newitems; - List *l; + int numGroupCols; + AttrNumber *groupColIdx; + int groupColPos; + ListCell *l; subplan = create_plan(root, best_path->subpath); - /* + /* Done if we don't need to do any actual unique-ifying */ + if (best_path->umethod == UNIQUE_PATH_NOOP) + return subplan; + + /*---------- * As constructed, the subplan has a "flat" tlist containing just the * Vars needed here and at upper levels. The values we are supposed * to unique-ify may be expressions in these variables. We have to - * add any such expressions to the subplan's tlist. We then build - * control information showing which subplan output columns are to be - * examined by the grouping step. (Since we do not remove any - * existing subplan outputs, not all the output columns may be used - * for grouping.) + * add any such expressions to the subplan's tlist. * - * Note: the reason we don't remove any subplan outputs is that there are - * scenarios where a Var is needed at higher levels even though it is - * not one of the nominal outputs of an IN clause. Consider WHERE x - * IN (SELECT y FROM t1,t2 WHERE y = z) Implied equality deduction - * will generate an "x = z" clause, which may get used instead of "x = - * y" in the upper join step. Therefore the sub-select had better - * deliver both y and z in its targetlist. It is sufficient to - * unique-ify on y, however. + * The subplan may have a "physical" tlist if it is a simple scan plan. + * This should be left as-is if we don't need to add any expressions; + * but if we do have to add expressions, then a projection step will be + * needed at runtime anyway, and so we may as well remove unneeded items. + * Therefore newtlist starts from build_relation_tlist() not just a + * copy of the subplan's tlist; and we don't install it into the subplan + * unless stuff has to be added. * * To find the correct list of values to unique-ify, we look in the * information saved for IN expressions. If this code is ever used in * other scenarios, some other way of finding what to unique-ify will * be needed. + *---------- */ uniq_exprs = NIL; /* just to keep compiler quiet */ foreach(l, root->in_info_list) @@ -544,16 +628,12 @@ create_unique_plan(Query *root, UniquePath *best_path) break; } } - if (l == NIL) /* fell out of loop? */ + if (l == NULL) /* fell out of loop? */ elog(ERROR, "could not find UniquePath in in_info_list"); - /* set up to record positions of unique columns */ - numGroupCols = length(uniq_exprs); - groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber)); - groupColPos = 0; - /* not sure if tlist might be shared with other nodes, so copy */ - newtlist = copyObject(subplan->targetlist); - nextresno = length(newtlist) + 1; + /* initialize modified subplan tlist as just the "required" vars */ + newtlist = build_relation_tlist(best_path->path.parent); + nextresno = list_length(newtlist) + 1; newitems = false; foreach(l, uniq_exprs) @@ -561,27 +641,24 @@ create_unique_plan(Query *root, UniquePath *best_path) Node *uniqexpr = lfirst(l); TargetEntry *tle; - tle = tlistentry_member(uniqexpr, newtlist); + tle = tlist_member(uniqexpr, newtlist); if (!tle) { - tle = makeTargetEntry(makeResdom(nextresno, - exprType(uniqexpr), - exprTypmod(uniqexpr), - NULL, - false), - (Expr *) uniqexpr); + tle = makeTargetEntry((Expr *) uniqexpr, + nextresno, + NULL, + false); newtlist = lappend(newtlist, tle); nextresno++; newitems = true; } - groupColIdx[groupColPos++] = tle->resdom->resno; } if (newitems) { /* - * If the top plan node can't do projections, we need to add a - * Result node to help it along. + * If the top plan node can't do projections, we need to add a Result + * node to help it along. */ if (!is_projection_capable_plan(subplan)) subplan = (Plan *) make_result(newtlist, NULL, subplan); @@ -589,9 +666,27 @@ create_unique_plan(Query *root, UniquePath *best_path) subplan->targetlist = newtlist; } - /* Done if we don't need to do any actual unique-ifying */ - if (best_path->umethod == UNIQUE_PATH_NOOP) - return subplan; + /* + * Build control information showing which subplan output columns are to + * be examined by the grouping step. Unfortunately we can't merge this + * with the previous loop, since we didn't then know which version of the + * subplan tlist we'd end up using. + */ + newtlist = subplan->targetlist; + numGroupCols = list_length(uniq_exprs); + groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber)); + groupColPos = 0; + + foreach(l, uniq_exprs) + { + Node *uniqexpr = lfirst(l); + TargetEntry *tle; + + tle = tlist_member(uniqexpr, newtlist); + if (!tle) /* shouldn't happen */ + elog(ERROR, "failed to find unique expression in subplan tlist"); + groupColIdx[groupColPos++] = tle->resno; + } if (best_path->umethod == UNIQUE_PATH_HASH) { @@ -599,8 +694,13 @@ create_unique_plan(Query *root, UniquePath *best_path) numGroups = (long) Min(best_path->rows, (double) LONG_MAX); + /* + * Since the Agg node is going to project anyway, we can give it the + * minimum output tlist, without any stuff we might have added to the + * subplan tlist. + */ plan = (Plan *) make_agg(root, - copyObject(subplan->targetlist), + build_relation_tlist(best_path->path.parent), NIL, AGG_HASHED, numGroupCols, @@ -648,7 +748,7 @@ create_unique_plan(Query *root, UniquePath *best_path) * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static SeqScan * -create_seqscan_plan(Query *root, Path *best_path, +create_seqscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses) { SeqScan *scan_plan; @@ -658,8 +758,8 @@ create_seqscan_plan(Query *root, Path *best_path, Assert(scan_relid > 0); Assert(best_path->parent->rtekind == RTE_RELATION); - /* Reduce RestrictInfo list to bare expressions */ - scan_clauses = get_actual_clauses(scan_clauses); + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); /* Sort clauses into best execution order */ scan_clauses = order_qual_clauses(root, scan_clauses); @@ -675,34 +775,33 @@ 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 - * qual conditions for each scan of the index(es); if there is more than one - * scan then the retrieved tuple sets are ORed together. The indexquals - * and indexinfo lists must have the same length, ie, the number of scans - * that will occur. Note it is possible for a qual condition sublist - * to be empty --- then no index restrictions will be applied during that - * scan. + * The indexquals list of the path contains implicitly-ANDed qual conditions. + * The list can be empty --- then no index restrictions will be applied during + * the scan. + * + * If nonlossy_clauses isn't NULL, *nonlossy_clauses receives a list of the + * nonlossy indexquals. */ static IndexScan * -create_indexscan_plan(Query *root, +create_indexscan_plan(PlannerInfo *root, IndexPath *best_path, List *tlist, - List *scan_clauses) + List *scan_clauses, + List **nonlossy_clauses) { - List *indxquals = best_path->indexquals; + List *indexquals = best_path->indexquals; Index baserelid = best_path->path.parent->relid; + Oid indexoid = best_path->indexinfo->indexoid; List *qpqual; - Expr *indxqual_or_expr = NULL; - List *stripped_indxquals; - List *fixed_indxquals; - List *indxstrategy; - List *indxsubtype; - List *indxlossy; - FastList indexids; - List *i; + List *stripped_indexquals; + List *fixed_indexquals; + List *nonlossy_indexquals; + List *indexstrategy; + List *indexsubtype; + ListCell *l; IndexScan *scan_plan; /* it should be a base rel... */ @@ -710,104 +809,220 @@ create_indexscan_plan(Query *root, Assert(best_path->path.parent->rtekind == RTE_RELATION); /* - * 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. + * Build "stripped" indexquals structure (no RestrictInfos) to pass to + * executor as indexqualorig + */ + stripped_indexquals = get_actual_clauses(indexquals); + + /* + * 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_indexqual_references(indexquals, best_path, + &fixed_indexquals, + &nonlossy_indexquals, + &indexstrategy, + &indexsubtype); + + /* pass back nonlossy quals if caller wants 'em */ + if (nonlossy_clauses) + *nonlossy_clauses = nonlossy_indexquals; + + /* + * If this is an 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. + * + * Note: pointer comparison should be enough to determine RestrictInfo + * matches. */ if (best_path->isjoininner) + scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses); + + /* + * 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 nodeIndexscan.c), but if there are + * any "special" operators involved then they must be included in qpqual. + * Also, any lossy index operators must be rechecked in the qpqual. The + * upshot is that qpqual must contain scan_clauses minus whatever appears + * in nonlossy_indexquals. + * + * In normal cases simple pointer equality checks will be enough to spot + * duplicate RestrictInfos, so we try that first. In some situations + * (particularly with OR'd index conditions) we may have scan_clauses that + * are not equal to, but are logically implied by, the index quals; so we + * also try a predicate_implied_by() check to see if we can discard quals + * that way. (predicate_implied_by assumes its first input contains only + * immutable functions, so we have to check that.) + * + * We can also discard quals that are implied by a partial index's + * predicate, but only in a plain SELECT; when scanning a target relation + * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the + * plan so that they'll be properly rechecked by EvalPlanQual testing. + * + * While at it, we strip off the RestrictInfos to produce a list of plain + * expressions (this loop replaces extract_actual_clauses used in the + * other routines in this file). We have to ignore pseudoconstants. + */ + qpqual = NIL; + foreach(l, scan_clauses) { - /* - * We don't currently support OR indexscans in joins, so we only - * need to worry about the plain AND case. Also, pointer comparison - * should be enough to determine RestrictInfo matches. - */ - Assert(length(best_path->indexclauses) == 1); - scan_clauses = set_ptrUnion(scan_clauses, - (List *) lfirst(best_path->indexclauses)); - } + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + + Assert(IsA(rinfo, RestrictInfo)); + if (rinfo->pseudoconstant) + continue; + if (list_member_ptr(nonlossy_indexquals, rinfo)) + continue; + if (!contain_mutable_functions((Node *) rinfo->clause)) + { + List *clausel = list_make1(rinfo->clause); - /* Reduce RestrictInfo list to bare expressions */ - scan_clauses = get_actual_clauses(scan_clauses); + if (predicate_implied_by(clausel, nonlossy_indexquals)) + continue; + if (best_path->indexinfo->indpred) + { + if (baserelid != root->parse->resultRelation && + get_rowmark(root->parse, baserelid) == NULL) + if (predicate_implied_by(clausel, + best_path->indexinfo->indpred)) + continue; + } + } + qpqual = lappend(qpqual, rinfo->clause); + } /* Sort clauses into best execution order */ - scan_clauses = order_qual_clauses(root, scan_clauses); + qpqual = order_qual_clauses(root, qpqual); - /* Build list of index OIDs */ - FastListInit(&indexids); - foreach(i, best_path->indexinfo) - { - IndexOptInfo *index = (IndexOptInfo *) lfirst(i); + /* Finally ready to build the plan node */ + scan_plan = make_indexscan(tlist, + qpqual, + baserelid, + indexoid, + fixed_indexquals, + stripped_indexquals, + indexstrategy, + indexsubtype, + best_path->indexscandir); - FastAppendo(&indexids, index->indexoid); - } + 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; +} + +/* + * 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(PlannerInfo *root, + BitmapHeapPath *best_path, + List *tlist, + List *scan_clauses) +{ + Index baserelid = best_path->path.parent->relid; + Plan *bitmapqualplan; + List *bitmapqualorig; + List *indexquals; + List *qpqual; + ListCell *l; + 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 and qual lists */ + bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual, + &bitmapqualorig, &indexquals); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); /* - * Build "stripped" indexquals structure (no RestrictInfos) to pass to - * executor as indxqualorig + * 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. */ - stripped_indxquals = NIL; - foreach(i, indxquals) + if (best_path->isjoininner) { - List *andlist = (List *) lfirst(i); - - stripped_indxquals = lappend(stripped_indxquals, - get_actual_clauses(andlist)); + scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig); } /* - * 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 nodeIndexscan.c), but - * if there are any "special" operators involved then they must be - * added to qpqual. The upshot is that qpquals must contain scan_clauses - * minus whatever appears in indxquals. + * 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 qpqual must contain scan_clauses minus + * whatever appears in indexquals. + * + * In normal cases simple equal() checks will be enough to spot duplicate + * clauses, so we try that first. In some situations (particularly with + * OR'd index conditions) we may have scan_clauses that are not equal to, + * but are logically implied by, the index quals; so we also try a + * predicate_implied_by() check to see if we can discard quals that way. + * (predicate_implied_by assumes its first input contains only immutable + * functions, so we have to check that.) + * + * Unlike create_indexscan_plan(), we need take no special thought here + * for partial index predicates; this is because the predicate conditions + * are already listed in bitmapqualorig and indexquals. Bitmap scans + * have to do it that way because predicate conditions need to be rechecked + * if the scan becomes lossy. */ - if (length(indxquals) > 1) + qpqual = NIL; + foreach(l, scan_clauses) { - /* - * Build an expression representation of the indexqual, expanding - * the implicit OR and AND semantics of the first- and - * second-level lists. (The odds that this will exactly match any - * scan_clause are not great; perhaps we need more smarts here.) - */ - indxqual_or_expr = make_expr_from_indexclauses(indxquals); - qpqual = set_difference(scan_clauses, makeList1(indxqual_or_expr)); - } - else - { - /* - * Here, we can simply treat the first sublist as an independent - * set of qual expressions, since there is no top-level OR - * behavior. - */ - Assert(stripped_indxquals != NIL); - qpqual = set_difference(scan_clauses, lfirst(stripped_indxquals)); + Node *clause = (Node *) lfirst(l); + + if (list_member(indexquals, clause)) + continue; + if (!contain_mutable_functions(clause)) + { + List *clausel = list_make1(clause); + + if (predicate_implied_by(clausel, indexquals)) + continue; + } + qpqual = lappend(qpqual, clause); } + /* Sort clauses into best execution order */ + qpqual = order_qual_clauses(root, qpqual); + /* - * 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. + * When dealing with special or lossy operators, we will at this point + * have duplicate clauses in qpqual and bitmapqualorig. We may as well + * drop 'em from bitmapqualorig, since there's no point in making the + * tests twice. */ - fix_indxqual_references(indxquals, best_path, - &fixed_indxquals, - &indxstrategy, &indxsubtype, &indxlossy); + bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual); + + /* + * Copy the finished bitmapqualorig to make sure we have an independent + * copy --- needed in case there are subplans in the index quals + */ + bitmapqualorig = copyObject(bitmapqualorig); /* Finally ready to build the plan node */ - scan_plan = make_indexscan(tlist, - qpqual, - baserelid, - FastListValue(&indexids), - fixed_indxquals, - stripped_indxquals, - indxstrategy, - indxsubtype, - indxlossy, - best_path->indexscandir); + 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 */ @@ -816,24 +1031,214 @@ create_indexscan_plan(Query *root, return scan_plan; } +/* + * Given a bitmapqual tree, generate the Plan tree that implements it + * + * As byproducts, we also return in *qual and *indexqual the qual lists + * (in implicit-AND form, without RestrictInfos) describing the original index + * conditions and the generated indexqual conditions. The latter is made to + * exclude lossy index operators. Both lists include partial-index predicates, + * because we have to recheck predicates as well as index conditions if the + * bitmap scan becomes lossy. + * + * Note: if you find yourself changing this, you probably need to change + * make_restrictinfo_from_bitmapqual too. + */ +static Plan * +create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual, + List **qual, List **indexqual) +{ + Plan *plan; + + if (IsA(bitmapqual, BitmapAndPath)) + { + BitmapAndPath *apath = (BitmapAndPath *) bitmapqual; + List *subplans = NIL; + List *subquals = NIL; + List *subindexquals = NIL; + ListCell *l; + + /* + * There may well be redundant quals among the subplans, since a + * top-level WHERE qual might have gotten used to form several + * different index quals. We don't try exceedingly hard to eliminate + * redundancies, but we do eliminate obvious duplicates by using + * list_concat_unique. + */ + foreach(l, apath->bitmapquals) + { + Plan *subplan; + List *subqual; + List *subindexqual; + + subplan = create_bitmap_subplan(root, (Path *) lfirst(l), + &subqual, &subindexqual); + subplans = lappend(subplans, subplan); + subquals = list_concat_unique(subquals, subqual); + subindexquals = list_concat_unique(subindexquals, subindexqual); + } + plan = (Plan *) make_bitmap_and(subplans); + plan->startup_cost = apath->path.startup_cost; + plan->total_cost = apath->path.total_cost; + plan->plan_rows = + clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples); + plan->plan_width = 0; /* meaningless */ + *qual = subquals; + *indexqual = subindexquals; + } + else if (IsA(bitmapqual, BitmapOrPath)) + { + BitmapOrPath *opath = (BitmapOrPath *) bitmapqual; + List *subplans = NIL; + List *subquals = NIL; + List *subindexquals = NIL; + bool const_true_subqual = false; + bool const_true_subindexqual = false; + ListCell *l; + + /* + * Here, we only detect qual-free subplans. A qual-free subplan would + * cause us to generate "... OR true ..." which we may as well reduce + * to just "true". We do not try to eliminate redundant subclauses + * because (a) it's not as likely as in the AND case, and (b) we might + * well be working with hundreds or even thousands of OR conditions, + * perhaps from a long IN list. The performance of list_append_unique + * would be unacceptable. + */ + foreach(l, opath->bitmapquals) + { + Plan *subplan; + List *subqual; + List *subindexqual; + + subplan = create_bitmap_subplan(root, (Path *) lfirst(l), + &subqual, &subindexqual); + subplans = lappend(subplans, subplan); + if (subqual == NIL) + const_true_subqual = true; + else if (!const_true_subqual) + subquals = lappend(subquals, + make_ands_explicit(subqual)); + if (subindexqual == NIL) + const_true_subindexqual = true; + else if (!const_true_subindexqual) + subindexquals = lappend(subindexquals, + make_ands_explicit(subindexqual)); + } + /* + * In the presence of ScalarArrayOpExpr quals, we might have built + * BitmapOrPaths with just one subpath; don't add an OR step. + */ + if (list_length(subplans) == 1) + { + plan = (Plan *) linitial(subplans); + } + else + { + plan = (Plan *) make_bitmap_or(subplans); + plan->startup_cost = opath->path.startup_cost; + plan->total_cost = opath->path.total_cost; + plan->plan_rows = + clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples); + plan->plan_width = 0; /* meaningless */ + } + + /* + * If there were constant-TRUE subquals, the OR reduces to constant + * TRUE. Also, avoid generating one-element ORs, which could happen + * due to redundancy elimination or ScalarArrayOpExpr quals. + */ + if (const_true_subqual) + *qual = NIL; + else if (list_length(subquals) <= 1) + *qual = subquals; + else + *qual = list_make1(make_orclause(subquals)); + if (const_true_subindexqual) + *indexqual = NIL; + else if (list_length(subindexquals) <= 1) + *indexqual = subindexquals; + else + *indexqual = list_make1(make_orclause(subindexquals)); + } + else if (IsA(bitmapqual, IndexPath)) + { + IndexPath *ipath = (IndexPath *) bitmapqual; + IndexScan *iscan; + List *nonlossy_clauses; + ListCell *l; + + /* Use the regular indexscan plan build machinery... */ + iscan = create_indexscan_plan(root, ipath, NIL, NIL, + &nonlossy_clauses); + /* then convert to a bitmap indexscan */ + plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid, + iscan->indexid, + iscan->indexqual, + iscan->indexqualorig, + iscan->indexstrategy, + iscan->indexsubtype); + plan->startup_cost = 0.0; + plan->total_cost = ipath->indextotalcost; + plan->plan_rows = + clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples); + plan->plan_width = 0; /* meaningless */ + *qual = get_actual_clauses(ipath->indexclauses); + *indexqual = get_actual_clauses(nonlossy_clauses); + foreach(l, ipath->indexinfo->indpred) + { + Expr *pred = (Expr *) lfirst(l); + + /* + * We know that the index predicate must have been implied by + * the query condition as a whole, but it may or may not be + * implied by the conditions that got pushed into the + * bitmapqual. Avoid generating redundant conditions. + */ + if (!predicate_implied_by(list_make1(pred), ipath->indexclauses)) + { + *qual = lappend(*qual, pred); + *indexqual = lappend(*indexqual, pred); + } + } + } + else + { + elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual)); + plan = NULL; /* keep compiler quiet */ + } + + return plan; +} + /* * create_tidscan_plan * Returns a tidscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static TidScan * -create_tidscan_plan(Query *root, TidPath *best_path, +create_tidscan_plan(PlannerInfo *root, TidPath *best_path, List *tlist, List *scan_clauses) { TidScan *scan_plan; Index scan_relid = best_path->path.parent->relid; + List *ortidquals; /* it should be a base rel... */ Assert(scan_relid > 0); Assert(best_path->path.parent->rtekind == RTE_RELATION); - /* Reduce RestrictInfo list to bare expressions */ - scan_clauses = get_actual_clauses(scan_clauses); + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + /* + * Remove any clauses that are TID quals. This is a bit tricky since + * the tidquals list has implicit OR semantics. + */ + ortidquals = best_path->tidquals; + if (list_length(ortidquals) > 1) + ortidquals = list_make1(make_orclause(ortidquals)); + scan_clauses = list_difference(scan_clauses, ortidquals); /* Sort clauses into best execution order */ scan_clauses = order_qual_clauses(root, scan_clauses); @@ -841,7 +1246,7 @@ create_tidscan_plan(Query *root, TidPath *best_path, scan_plan = make_tidscan(tlist, scan_clauses, scan_relid, - best_path->tideval); + best_path->tidquals); copy_path_costsize(&scan_plan->scan.plan, &best_path->path); @@ -854,7 +1259,7 @@ create_tidscan_plan(Query *root, TidPath *best_path, * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static SubqueryScan * -create_subqueryscan_plan(Query *root, Path *best_path, +create_subqueryscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses) { SubqueryScan *scan_plan; @@ -864,8 +1269,8 @@ create_subqueryscan_plan(Query *root, Path *best_path, Assert(scan_relid > 0); Assert(best_path->parent->rtekind == RTE_SUBQUERY); - /* Reduce RestrictInfo list to bare expressions */ - scan_clauses = get_actual_clauses(scan_clauses); + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); /* Sort clauses into best execution order */ scan_clauses = order_qual_clauses(root, scan_clauses); @@ -886,7 +1291,7 @@ create_subqueryscan_plan(Query *root, Path *best_path, * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static FunctionScan * -create_functionscan_plan(Query *root, Path *best_path, +create_functionscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses) { FunctionScan *scan_plan; @@ -896,8 +1301,8 @@ create_functionscan_plan(Query *root, Path *best_path, Assert(scan_relid > 0); Assert(best_path->parent->rtekind == RTE_FUNCTION); - /* Reduce RestrictInfo list to bare expressions */ - scan_clauses = get_actual_clauses(scan_clauses); + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); /* Sort clauses into best execution order */ scan_clauses = order_qual_clauses(root, scan_clauses); @@ -916,7 +1321,7 @@ create_functionscan_plan(Query *root, Path *best_path, *****************************************************************************/ static NestLoop * -create_nestloop_plan(Query *root, +create_nestloop_plan(PlannerInfo *root, NestPath *best_path, Plan *outer_plan, Plan *inner_plan) @@ -930,46 +1335,74 @@ create_nestloop_plan(Query *root, if (IsA(best_path->innerjoinpath, IndexPath)) { /* - * An index is being used to reduce the number of tuples scanned - * in the inner relation. If there are join clauses being used - * with the index, we may remove those join clauses from the list - * of clauses that have to be checked as qpquals at the join node - * --- but only if there's just one indexscan in the inner path - * (otherwise, several different sets of clauses are being ORed - * together). + * An index is being used to reduce the number of tuples scanned in + * the inner relation. If there are join clauses being used with the + * index, we may remove those join clauses from the list of clauses + * that have to be checked as qpquals at the join node. * * We can also remove any join clauses that are redundant with those - * being used in the index scan; prior redundancy checks will not - * have caught this case because the join clauses would never have - * been put in the same joininfo list. + * being used in the index scan; prior redundancy checks will not have + * caught this case because the join clauses would never have been put + * in the same joininfo list. * - * We can skip this if the index path is an ordinary indexpath and - * not a special innerjoin path. + * We can skip this if the index path is an ordinary indexpath and not + * a special innerjoin path. */ IndexPath *innerpath = (IndexPath *) best_path->innerjoinpath; - List *indexclauses = innerpath->indexclauses; - if (innerpath->isjoininner && - length(indexclauses) == 1) /* single indexscan? */ + if (innerpath->isjoininner) + { + joinrestrictclauses = + select_nonredundant_join_clauses(root, + joinrestrictclauses, + innerpath->indexclauses, + IS_OUTER_JOIN(best_path->jointype)); + } + } + else if (IsA(best_path->innerjoinpath, BitmapHeapPath)) + { + /* + * Same deal for bitmapped index scans. + * + * Note: both here and above, we ignore any implicit index + * restrictions associated with the use of partial indexes. This is + * OK because we're only trying to prove we can dispense with some + * join quals; failing to prove that doesn't result in an incorrect + * plan. It is the right way to proceed because adding more quals to + * the stuff we got from the original query would just make it harder + * to detect duplication. (Also, to change this we'd have to be + * wary of UPDATE/DELETE/SELECT FOR UPDATE target relations; see + * notes above about EvalPlanQual.) + */ + BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath; + + if (innerpath->isjoininner) { + List *bitmapclauses; + + bitmapclauses = + make_restrictinfo_from_bitmapqual(innerpath->bitmapqual, + true, + false); joinrestrictclauses = select_nonredundant_join_clauses(root, joinrestrictclauses, - lfirst(indexclauses), - best_path->jointype); + bitmapclauses, + IS_OUTER_JOIN(best_path->jointype)); } } /* Get the join qual clauses (in plain expression form) */ + /* Any pseudoconstant clauses are ignored here */ if (IS_OUTER_JOIN(best_path->jointype)) { - get_actual_join_clauses(joinrestrictclauses, - &joinclauses, &otherclauses); + extract_actual_join_clauses(joinrestrictclauses, + &joinclauses, &otherclauses); } else { /* We can treat all clauses alike for an inner join */ - joinclauses = get_actual_clauses(joinrestrictclauses); + joinclauses = extract_actual_clauses(joinrestrictclauses, false); otherclauses = NIL; } @@ -990,7 +1423,7 @@ create_nestloop_plan(Query *root, } static MergeJoin * -create_mergejoin_plan(Query *root, +create_mergejoin_plan(PlannerInfo *root, MergePath *best_path, Plan *outer_plan, Plan *inner_plan) @@ -1002,31 +1435,33 @@ create_mergejoin_plan(Query *root, MergeJoin *join_plan; /* Get the join qual clauses (in plain expression form) */ + /* Any pseudoconstant clauses are ignored here */ if (IS_OUTER_JOIN(best_path->jpath.jointype)) { - get_actual_join_clauses(best_path->jpath.joinrestrictinfo, - &joinclauses, &otherclauses); + extract_actual_join_clauses(best_path->jpath.joinrestrictinfo, + &joinclauses, &otherclauses); } else { /* We can treat all clauses alike for an inner join */ - joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo); + joinclauses = extract_actual_clauses(best_path->jpath.joinrestrictinfo, + false); otherclauses = NIL; } /* - * Remove the mergeclauses from the list of join qual clauses, leaving - * the list of quals that must be checked as qpquals. + * Remove the mergeclauses from the list of join qual clauses, leaving the + * list of quals that must be checked as qpquals. */ mergeclauses = get_actual_clauses(best_path->path_mergeclauses); - joinclauses = set_difference(joinclauses, mergeclauses); + joinclauses = list_difference(joinclauses, mergeclauses); /* - * Rearrange mergeclauses, if needed, so that the outer variable is - * always on the left. + * Rearrange mergeclauses, if needed, so that the outer variable is always + * on the left. */ mergeclauses = get_switched_clauses(best_path->path_mergeclauses, - best_path->jpath.outerjoinpath->parent->relids); + best_path->jpath.outerjoinpath->parent->relids); /* Sort clauses into best execution order */ /* NB: do NOT reorder the mergeclauses */ @@ -1035,8 +1470,8 @@ create_mergejoin_plan(Query *root, /* * Create explicit sort nodes for the outer and inner join paths if - * necessary. The sort cost was already accounted for in the path. - * Make sure there are no excess columns in the inputs if sorting. + * necessary. The sort cost was already accounted for in the path. Make + * sure there are no excess columns in the inputs if sorting. */ if (best_path->outersortkeys) { @@ -1073,7 +1508,7 @@ create_mergejoin_plan(Query *root, } static HashJoin * -create_hashjoin_plan(Query *root, +create_hashjoin_plan(PlannerInfo *root, HashPath *best_path, Plan *outer_plan, Plan *inner_plan) @@ -1086,31 +1521,33 @@ create_hashjoin_plan(Query *root, Hash *hash_plan; /* Get the join qual clauses (in plain expression form) */ + /* Any pseudoconstant clauses are ignored here */ if (IS_OUTER_JOIN(best_path->jpath.jointype)) { - get_actual_join_clauses(best_path->jpath.joinrestrictinfo, - &joinclauses, &otherclauses); + extract_actual_join_clauses(best_path->jpath.joinrestrictinfo, + &joinclauses, &otherclauses); } else { /* We can treat all clauses alike for an inner join */ - joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo); + joinclauses = extract_actual_clauses(best_path->jpath.joinrestrictinfo, + false); otherclauses = NIL; } /* - * Remove the hashclauses from the list of join qual clauses, leaving - * the list of quals that must be checked as qpquals. + * Remove the hashclauses from the list of join qual clauses, leaving the + * list of quals that must be checked as qpquals. */ hashclauses = get_actual_clauses(best_path->path_hashclauses); - joinclauses = set_difference(joinclauses, hashclauses); + joinclauses = list_difference(joinclauses, hashclauses); /* - * Rearrange hashclauses, if needed, so that the outer variable is - * always on the left. + * Rearrange hashclauses, if needed, so that the outer variable is always + * on the left. */ hashclauses = get_switched_clauses(best_path->path_hashclauses, - best_path->jpath.outerjoinpath->parent->relids); + best_path->jpath.outerjoinpath->parent->relids); /* Sort clauses into best execution order */ joinclauses = order_qual_clauses(root, joinclauses); @@ -1145,171 +1582,187 @@ create_hashjoin_plan(Query *root, *****************************************************************************/ /* - * fix_indxqual_references + * fix_indexqual_references * Adjust indexqual clauses to the form the executor's indexqual * machinery needs, and check for recheckable (lossy) index conditions. * - * We have four tasks here: + * We have five tasks here: * * Remove RestrictInfo nodes from the input clauses. * * Index keys must be represented by Var nodes with varattno set to the * index's attribute number, not the attribute number in the original rel. * * If the index key is on the right, commute the clause to put it on the - * left. (Someday the executor might not need this, but for now it does.) - * * We must construct lists of operator strategy numbers, subtypes, and - * recheck (lossy-operator) flags for the top-level operators of each - * index clause. - * - * Both the input list and the "fixed" output list have the form of lists of - * sublists of qual clauses --- the top-level list has one entry for each - * indexscan to be performed. The semantics are OR-of-ANDs. Note however - * that the input list contains RestrictInfos, while the output list doesn't. + * left. + * * We must construct lists of operator strategy numbers and subtypes + * for the top-level operators of each index clause. + * * We must detect any lossy index operators. The API is that we return + * a list of the input clauses whose operators are NOT lossy. * - * fixed_indexquals receives a modified copy of the indexqual list --- the + * fixed_indexquals receives a modified copy of the indexquals list --- the * original is not changed. Note also that the copy shares no substructure * with the original; this is needed in case there is a subplan in it (we need * two separate copies of the subplan tree, or things will go awry). * - * indxstrategy receives a list of integer sublists of strategy numbers. - * indxsubtype receives a list of OID sublists of strategy subtypes. - * indxlossy receives a list of integer sublists of lossy-operator booleans. + * nonlossy_indexquals receives a list of the original input clauses (with + * RestrictInfos) that contain non-lossy operators. + * + * indexstrategy receives an integer list of strategy numbers. + * indexsubtype receives an OID list of strategy subtypes. */ static void -fix_indxqual_references(List *indexquals, IndexPath *index_path, - List **fixed_indexquals, - List **indxstrategy, - List **indxsubtype, - List **indxlossy) +fix_indexqual_references(List *indexquals, IndexPath *index_path, + List **fixed_indexquals, + List **nonlossy_indexquals, + List **indexstrategy, + List **indexsubtype) { - Relids baserelids = index_path->path.parent->relids; - int baserelid = index_path->path.parent->relid; - List *ixinfo = index_path->indexinfo; - List *i; + IndexOptInfo *index = index_path->indexinfo; + ListCell *l; *fixed_indexquals = NIL; - *indxstrategy = NIL; - *indxsubtype = NIL; - *indxlossy = NIL; - foreach(i, indexquals) - { - List *indexqual = lfirst(i); - IndexOptInfo *index = (IndexOptInfo *) lfirst(ixinfo); - List *fixed_qual; - List *strategy; - List *subtype; - List *lossy; - - fix_indxqual_sublist(indexqual, baserelids, baserelid, index, - &fixed_qual, &strategy, &subtype, &lossy); - *fixed_indexquals = lappend(*fixed_indexquals, fixed_qual); - *indxstrategy = lappend(*indxstrategy, strategy); - *indxsubtype = lappend(*indxsubtype, subtype); - *indxlossy = lappend(*indxlossy, lossy); - - ixinfo = lnext(ixinfo); - } -} - -/* - * Fix the sublist of indexquals to be used in a particular scan. - * - * For each qual clause, commute if needed to put the indexkey operand on the - * left, and then fix its varattno. (We do not need to change the other side - * of the clause.) Then determine the operator's strategy number and subtype - * number, and check for lossy index behavior. - * - * Returns four lists: - * the list of fixed indexquals - * the integer list of strategy numbers - * the OID list of strategy subtypes - * the integer list of lossiness flags (1/0) - */ -static void -fix_indxqual_sublist(List *indexqual, - Relids baserelids, int baserelid, - IndexOptInfo *index, - List **fixed_quals, - List **strategy, - List **subtype, - List **lossy) -{ - List *i; + *nonlossy_indexquals = NIL; + *indexstrategy = NIL; + *indexsubtype = NIL; - *fixed_quals = NIL; - *strategy = NIL; - *subtype = NIL; - *lossy = NIL; - foreach(i, indexqual) + /* + * For each qual clause, commute if needed to put the indexkey operand on + * the left, and then fix its varattno. (We do not need to change the + * other side of the clause.) Then determine the operator's strategy + * number and subtype number, and check for lossy index behavior. + */ + foreach(l, indexquals) { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(i); - OpExpr *clause; - OpExpr *newclause; + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + Expr *clause; + Oid clause_op; Oid opclass; int stratno; Oid stratsubtype; bool recheck; Assert(IsA(rinfo, RestrictInfo)); - clause = (OpExpr *) rinfo->clause; - if (!IsA(clause, OpExpr) || - length(clause->args) != 2) - elog(ERROR, "indexqual clause is not binary opclause"); /* * Make a copy that will become the fixed clause. * * We used to try to do a shallow copy here, but that fails if there - * is a subplan in the arguments of the opclause. So just do a - * full copy. + * is a subplan in the arguments of the opclause. So just do a full + * copy. */ - newclause = (OpExpr *) copyObject((Node *) clause); + clause = (Expr *) copyObject((Node *) rinfo->clause); - /* - * Check to see if the indexkey is on the right; if so, commute - * the clause. The indexkey should be the side that refers to - * (only) the base relation. - */ - if (!bms_equal(rinfo->left_relids, baserelids)) - CommuteClause(newclause); + if (IsA(clause, OpExpr)) + { + OpExpr *op = (OpExpr *) clause; - /* - * Now, determine which index attribute this is, change the - * indexkey operand as needed, and get the index opclass. - */ - lfirst(newclause->args) = fix_indxqual_operand(lfirst(newclause->args), - baserelid, + if (list_length(op->args) != 2) + elog(ERROR, "indexqual clause is not binary opclause"); + + /* + * Check to see if the indexkey is on the right; if so, commute + * the clause. The indexkey should be the side that refers to + * (only) the base relation. + */ + if (!bms_equal(rinfo->left_relids, index->rel->relids)) + CommuteOpExpr(op); + + /* + * Now, determine which index attribute this is, change the + * indexkey operand as needed, and get the index opclass. + */ + linitial(op->args) = fix_indexqual_operand(linitial(op->args), index, &opclass); + clause_op = op->opno; + } + else if (IsA(clause, RowCompareExpr)) + { + RowCompareExpr *rc = (RowCompareExpr *) clause; + ListCell *lc; + + /* + * Check to see if the indexkey is on the right; if so, commute + * the clause. The indexkey should be the side that refers to + * (only) the base relation. + */ + if (!bms_overlap(pull_varnos(linitial(rc->largs)), + index->rel->relids)) + CommuteRowCompareExpr(rc); + + /* + * For each column in the row comparison, determine which index + * attribute this is and change the indexkey operand as needed. + * + * Save the index opclass for only the first column. We will + * return the operator and opclass info for just the first + * column of the row comparison; the executor will have to + * look up the rest if it needs them. + */ + foreach(lc, rc->largs) + { + Oid tmp_opclass; - *fixed_quals = lappend(*fixed_quals, newclause); + lfirst(lc) = fix_indexqual_operand(lfirst(lc), + index, + &tmp_opclass); + if (lc == list_head(rc->largs)) + opclass = tmp_opclass; + } + clause_op = linitial_oid(rc->opnos); + } + else if (IsA(clause, ScalarArrayOpExpr)) + { + ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause; + + /* Never need to commute... */ + + /* + * Now, determine which index attribute this is, change the + * indexkey operand as needed, and get the index opclass. + */ + linitial(saop->args) = fix_indexqual_operand(linitial(saop->args), + index, + &opclass); + clause_op = saop->opno; + } + else + { + elog(ERROR, "unsupported indexqual type: %d", + (int) nodeTag(clause)); + continue; /* keep compiler quiet */ + } + + *fixed_indexquals = lappend(*fixed_indexquals, clause); /* * Look up the (possibly commuted) operator in the operator class to - * get its strategy numbers and the recheck indicator. This also + * get its strategy numbers and the recheck indicator. This also * double-checks that we found an operator matching the index. */ - get_op_opclass_properties(newclause->opno, opclass, + get_op_opclass_properties(clause_op, opclass, &stratno, &stratsubtype, &recheck); - *strategy = lappendi(*strategy, stratno); - *subtype = lappendo(*subtype, stratsubtype); - *lossy = lappendi(*lossy, (int) recheck); + *indexstrategy = lappend_int(*indexstrategy, stratno); + *indexsubtype = lappend_oid(*indexsubtype, stratsubtype); + + /* If it's not lossy, add to nonlossy_indexquals */ + if (!recheck) + *nonlossy_indexquals = lappend(*nonlossy_indexquals, rinfo); } } static Node * -fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index, - Oid *opclass) +fix_indexqual_operand(Node *node, IndexOptInfo *index, Oid *opclass) { /* - * We represent index keys by Var nodes having the varno of the base - * table but varattno equal to the index's attribute number (index - * column position). This is a bit hokey ... would be cleaner to use - * a special-purpose node type that could not be mistaken for a - * regular Var. But it will do for now. + * We represent index keys by Var nodes having the varno of the base table + * but varattno equal to the index's attribute number (index column + * position). This is a bit hokey ... would be cleaner to use a + * special-purpose node type that could not be mistaken for a regular Var. + * But it will do for now. */ Var *result; int pos; - List *indexprs; + ListCell *indexpr_item; /* * Remove any binary-compatible relabeling of the indexkey @@ -1318,7 +1771,7 @@ fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index, node = (Node *) ((RelabelType *) node)->arg; if (IsA(node, Var) && - ((Var *) node)->varno == baserelid) + ((Var *) node)->varno == index->rel->relid) { /* Try to match against simple index columns */ int varatt = ((Var *) node)->varattno; @@ -1340,35 +1793,36 @@ fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index, } /* Try to match against index expressions */ - indexprs = index->indexprs; + indexpr_item = list_head(index->indexprs); for (pos = 0; pos < index->ncolumns; pos++) { if (index->indexkeys[pos] == 0) { Node *indexkey; - if (indexprs == NIL) + if (indexpr_item == NULL) elog(ERROR, "too few entries in indexprs list"); - indexkey = (Node *) lfirst(indexprs); + indexkey = (Node *) lfirst(indexpr_item); if (indexkey && IsA(indexkey, RelabelType)) indexkey = (Node *) ((RelabelType *) indexkey)->arg; if (equal(node, indexkey)) { /* Found a match */ - result = makeVar(baserelid, pos + 1, - exprType(lfirst(indexprs)), -1, + result = makeVar(index->rel->relid, pos + 1, + exprType(lfirst(indexpr_item)), -1, 0); /* return the correct opclass, too */ *opclass = index->classlist[pos]; return (Node *) result; } - indexprs = lnext(indexprs); + indexpr_item = lnext(indexpr_item); } } /* Ooops... */ elog(ERROR, "node is not an index attribute"); - return NULL; /* keep compiler quiet */ + *opclass = InvalidOid; /* keep compiler quiet */ + return NULL; } /* @@ -1383,19 +1837,19 @@ static List * get_switched_clauses(List *clauses, Relids outerrelids) { List *t_list = NIL; - List *i; + ListCell *l; - foreach(i, clauses) + foreach(l, clauses) { - RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i); + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); OpExpr *clause = (OpExpr *) restrictinfo->clause; Assert(is_opclause(clause)); if (bms_is_subset(restrictinfo->right_relids, outerrelids)) { /* - * Duplicate just enough of the structure to allow commuting - * the clause without changing the original list. Could use + * Duplicate just enough of the structure to allow commuting the + * clause without changing the original list. Could use * copyObject, but a complete deep copy is overkill. */ OpExpr *temp = makeNode(OpExpr); @@ -1404,9 +1858,9 @@ get_switched_clauses(List *clauses, Relids outerrelids) temp->opfuncid = InvalidOid; temp->opresulttype = clause->opresulttype; temp->opretset = clause->opretset; - temp->args = listCopy(clause->args); + temp->args = list_copy(clause->args); /* Commute it --- note this modifies the temp node in-place. */ - CommuteClause(temp); + CommuteOpExpr(temp); t_list = lappend(t_list, temp); } else @@ -1428,30 +1882,29 @@ get_switched_clauses(List *clauses, Relids outerrelids) * InitPlan references) to the end of the list. */ static List * -order_qual_clauses(Query *root, List *clauses) +order_qual_clauses(PlannerInfo *root, List *clauses) { - FastList nosubplans; - FastList withsubplans; - List *l; + List *nosubplans; + List *withsubplans; + ListCell *l; /* No need to work hard if the query is subselect-free */ - if (!root->hasSubLinks) + if (!root->parse->hasSubLinks) return clauses; - FastListInit(&nosubplans); - FastListInit(&withsubplans); + nosubplans = NIL; + withsubplans = NIL; foreach(l, clauses) { - Node *clause = lfirst(l); + Node *clause = (Node *) lfirst(l); if (contain_subplans(clause)) - FastAppend(&withsubplans, clause); + withsubplans = lappend(withsubplans, clause); else - FastAppend(&nosubplans, clause); + nosubplans = lappend(nosubplans, clause); } - FastConcFast(&nosubplans, &withsubplans); - return FastListValue(&nosubplans); + return list_concat(nosubplans, withsubplans); } /* @@ -1534,12 +1987,11 @@ static IndexScan * make_indexscan(List *qptlist, List *qpqual, Index scanrelid, - List *indxid, - List *indxqual, - List *indxqualorig, - List *indxstrategy, - List *indxsubtype, - List *indxlossy, + Oid indexid, + List *indexqual, + List *indexqualorig, + List *indexstrategy, + List *indexsubtype, ScanDirection indexscandir) { IndexScan *node = makeNode(IndexScan); @@ -1551,13 +2003,59 @@ make_indexscan(List *qptlist, 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; - node->indxlossy = indxlossy; - node->indxorderdir = indexscandir; + node->indexid = indexid; + node->indexqual = indexqual; + node->indexqualorig = indexqualorig; + node->indexstrategy = indexstrategy; + node->indexsubtype = indexsubtype; + node->indexorderdir = indexscandir; + + return node; +} + +static BitmapIndexScan * +make_bitmap_indexscan(Index scanrelid, + Oid indexid, + List *indexqual, + List *indexqualorig, + List *indexstrategy, + List *indexsubtype) +{ + 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->indexid = indexid; + node->indexqual = indexqual; + node->indexqualorig = indexqualorig; + node->indexstrategy = indexstrategy; + node->indexsubtype = indexsubtype; + + 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; } @@ -1566,7 +2064,7 @@ static TidScan * make_tidscan(List *qptlist, List *qpqual, Index scanrelid, - List *tideval) + List *tidquals) { TidScan *node = makeNode(TidScan); Plan *plan = &node->scan.plan; @@ -1577,7 +2075,7 @@ make_tidscan(List *qptlist, plan->lefttree = NULL; plan->righttree = NULL; node->scan.scanrelid = scanrelid; - node->tideval = tideval; + node->tidquals = tidquals; return node; } @@ -1592,9 +2090,9 @@ make_subqueryscan(List *qptlist, Plan *plan = &node->scan.plan; /* - * Cost is figured here for the convenience of prepunion.c. Note this - * is only correct for the case where qpqual is empty; otherwise - * caller should overwrite cost with a better estimate. + * Cost is figured here for the convenience of prepunion.c. Note this is + * only correct for the case where qpqual is empty; otherwise caller + * should overwrite cost with a better estimate. */ copy_plan_costsize(plan, subplan); plan->total_cost += cpu_tuple_cost * subplan->plan_rows; @@ -1632,12 +2130,12 @@ make_append(List *appendplans, bool isTarget, List *tlist) { Append *node = makeNode(Append); Plan *plan = &node->plan; - List *subnode; + ListCell *subnode; /* - * Compute cost as sum of subplan costs. We charge nothing extra for - * the Append itself, which perhaps is too optimistic, but since it - * doesn't do any selection or projection, it is a pretty cheap node. + * Compute cost as sum of subplan costs. We charge nothing extra for the + * Append itself, which perhaps is too optimistic, but since it doesn't do + * any selection or projection, it is a pretty cheap node. */ plan->startup_cost = 0; plan->total_cost = 0; @@ -1647,7 +2145,7 @@ make_append(List *appendplans, bool isTarget, List *tlist) { Plan *subplan = (Plan *) lfirst(subnode); - if (subnode == appendplans) /* first node? */ + if (subnode == list_head(appendplans)) /* first node? */ plan->startup_cost = subplan->startup_cost; plan->total_cost += subplan->total_cost; plan->plan_rows += subplan->plan_rows; @@ -1665,6 +2163,38 @@ 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; + + /* cost should be inserted by caller */ + 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; + + /* cost should be inserted by caller */ + 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, @@ -1720,8 +2250,8 @@ make_hash(Plan *lefttree) copy_plan_costsize(plan, lefttree); /* - * For plausibility, make startup & total costs equal total cost of - * input plan; this only affects EXPLAIN display not decisions. + * For plausibility, make startup & total costs equal total cost of input + * plan; this only affects EXPLAIN display not decisions. */ plan->startup_cost = plan->total_cost; plan->targetlist = copyObject(lefttree->targetlist); @@ -1762,7 +2292,7 @@ make_mergejoin(List *tlist, * Caller must have built the sortColIdx and sortOperators arrays already. */ static Sort * -make_sort(Query *root, Plan *lefttree, int numCols, +make_sort(PlannerInfo *root, Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators) { Sort *node = makeNode(Sort); @@ -1834,16 +2364,18 @@ add_sort_column(AttrNumber colIdx, Oid sortOp, * adding a Result node just to do the projection. */ static Sort * -make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys) +make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys) { List *tlist = lefttree->targetlist; - List *i; + ListCell *i; int numsortkeys; AttrNumber *sortColIdx; Oid *sortOperators; - /* We will need at most length(pathkeys) sort columns; possibly less */ - numsortkeys = length(pathkeys); + /* + * We will need at most list_length(pathkeys) sort columns; possibly less + */ + numsortkeys = list_length(pathkeys); sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber)); sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid)); @@ -1853,45 +2385,45 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys) { List *keysublist = (List *) lfirst(i); PathKeyItem *pathkey = NULL; - Resdom *resdom = NULL; - List *j; + TargetEntry *tle = NULL; + ListCell *j; /* * We can sort by any one of the sort key items listed in this * sublist. For now, we take the first one that corresponds to an - * available Var in the tlist. If there isn't any, use the first - * one that is an expression in the input's vars. + * available Var in the tlist. If there isn't any, use the first one + * that is an expression in the input's vars. * * XXX if we have a choice, is there any way of figuring out which - * might be cheapest to execute? (For example, int4lt is likely - * much cheaper to execute than numericlt, but both might appear - * in the same pathkey sublist...) Not clear that we ever will - * have a choice in practice, so it may not matter. + * might be cheapest to execute? (For example, int4lt is likely much + * cheaper to execute than numericlt, but both might appear in the + * same pathkey sublist...) Not clear that we ever will have a choice + * in practice, so it may not matter. */ foreach(j, keysublist) { - pathkey = lfirst(j); + pathkey = (PathKeyItem *) lfirst(j); Assert(IsA(pathkey, PathKeyItem)); - resdom = tlist_member(pathkey->key, tlist); - if (resdom) + tle = tlist_member(pathkey->key, tlist); + if (tle) break; } - if (!resdom) + if (!tle) { /* No matching Var; look for a computable expression */ foreach(j, keysublist) { - List *exprvars; - List *k; + List *exprvars; + ListCell *k; - pathkey = lfirst(j); + pathkey = (PathKeyItem *) lfirst(j); exprvars = pull_var_clause(pathkey->key, false); foreach(k, exprvars) { if (!tlist_member(lfirst(k), tlist)) break; } - freeList(exprvars); + list_free(exprvars); if (!k) break; /* found usable expression */ } @@ -1910,25 +2442,22 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys) /* * Add resjunk entry to input's tlist */ - resdom = makeResdom(length(tlist) + 1, - exprType(pathkey->key), - exprTypmod(pathkey->key), - NULL, - true); - tlist = lappend(tlist, - makeTargetEntry(resdom, - (Expr *) pathkey->key)); + tle = makeTargetEntry((Expr *) pathkey->key, + list_length(tlist) + 1, + NULL, + true); + tlist = lappend(tlist, tle); lefttree->targetlist = tlist; /* just in case NIL before */ } /* - * The column might already be selected as a sort key, if the - * pathkeys contain duplicate entries. (This can happen in - * scenarios where multiple mergejoinable clauses mention the same - * var, for example.) So enter it only once in the sort arrays. + * The column might already be selected as a sort key, if the pathkeys + * contain duplicate entries. (This can happen in scenarios where + * multiple mergejoinable clauses mention the same var, for example.) + * So enter it only once in the sort arrays. */ - numsortkeys = add_sort_column(resdom->resno, pathkey->sortop, - numsortkeys, sortColIdx, sortOperators); + numsortkeys = add_sort_column(tle->resno, pathkey->sortop, + numsortkeys, sortColIdx, sortOperators); } Assert(numsortkeys > 0); @@ -1945,24 +2474,26 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys) * 'lefttree' is the node which yields input tuples */ Sort * -make_sort_from_sortclauses(Query *root, List *sortcls, Plan *lefttree) +make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree) { List *sub_tlist = lefttree->targetlist; - List *i; + ListCell *l; int numsortkeys; AttrNumber *sortColIdx; Oid *sortOperators; - /* We will need at most length(sortcls) sort columns; possibly less */ - numsortkeys = length(sortcls); + /* + * We will need at most list_length(sortcls) sort columns; possibly less + */ + numsortkeys = list_length(sortcls); sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber)); sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid)); numsortkeys = 0; - foreach(i, sortcls) + foreach(l, sortcls) { - SortClause *sortcl = (SortClause *) lfirst(i); + SortClause *sortcl = (SortClause *) lfirst(l); TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist); /* @@ -1970,8 +2501,8 @@ make_sort_from_sortclauses(Query *root, List *sortcls, Plan *lefttree) * parser should have removed 'em, but no point in sorting * redundantly. */ - numsortkeys = add_sort_column(tle->resdom->resno, sortcl->sortop, - numsortkeys, sortColIdx, sortOperators); + numsortkeys = add_sort_column(tle->resno, sortcl->sortop, + numsortkeys, sortColIdx, sortOperators); } Assert(numsortkeys > 0); @@ -1994,28 +2525,30 @@ make_sort_from_sortclauses(Query *root, List *sortcls, Plan *lefttree) * GroupClause entries. */ Sort * -make_sort_from_groupcols(Query *root, +make_sort_from_groupcols(PlannerInfo *root, List *groupcls, AttrNumber *grpColIdx, Plan *lefttree) { List *sub_tlist = lefttree->targetlist; int grpno = 0; - List *i; + ListCell *l; int numsortkeys; AttrNumber *sortColIdx; Oid *sortOperators; - /* We will need at most length(groupcls) sort columns; possibly less */ - numsortkeys = length(groupcls); + /* + * We will need at most list_length(groupcls) sort columns; possibly less + */ + numsortkeys = list_length(groupcls); sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber)); sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid)); numsortkeys = 0; - foreach(i, groupcls) + foreach(l, groupcls) { - GroupClause *grpcl = (GroupClause *) lfirst(i); + GroupClause *grpcl = (GroupClause *) lfirst(l); TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]); /* @@ -2023,8 +2556,8 @@ make_sort_from_groupcols(Query *root, * parser should have removed 'em, but no point in sorting * redundantly. */ - numsortkeys = add_sort_column(tle->resdom->resno, grpcl->sortop, - numsortkeys, sortColIdx, sortOperators); + numsortkeys = add_sort_column(tle->resno, grpcl->sortop, + numsortkeys, sortColIdx, sortOperators); grpno++; } @@ -2085,7 +2618,7 @@ materialize_finished_plan(Plan *subplan) } Agg * -make_agg(Query *root, List *tlist, List *qual, +make_agg(PlannerInfo *root, List *tlist, List *qual, AggStrategy aggstrategy, int numGroupCols, AttrNumber *grpColIdx, long numGroups, int numAggs, @@ -2112,8 +2645,8 @@ make_agg(Query *root, List *tlist, List *qual, plan->total_cost = agg_path.total_cost; /* - * We will produce a single output tuple if not grouping, and a tuple - * per group otherwise. + * We will produce a single output tuple if not grouping, and a tuple per + * group otherwise. */ if (aggstrategy == AGG_PLAIN) plan->plan_rows = 1; @@ -2121,13 +2654,13 @@ make_agg(Query *root, List *tlist, List *qual, plan->plan_rows = numGroups; /* - * We also need to account for the cost of evaluation of the qual (ie, - * the HAVING clause) and the tlist. Note that cost_qual_eval doesn't - * charge anything for Aggref nodes; this is okay since they are - * really comparable to Vars. + * We also need to account for the cost of evaluation of the qual (ie, the + * HAVING clause) and the tlist. Note that cost_qual_eval doesn't charge + * anything for Aggref nodes; this is okay since they are really + * comparable to Vars. * - * See notes in grouping_planner about why this routine and make_group - * are the only ones in this file that worry about tlist eval cost. + * See notes in grouping_planner about why this routine and make_group are + * the only ones in this file that worry about tlist eval cost. */ if (qual) { @@ -2150,8 +2683,9 @@ make_agg(Query *root, List *tlist, List *qual, } Group * -make_group(Query *root, +make_group(PlannerInfo *root, List *tlist, + List *qual, int numGroupCols, AttrNumber *grpColIdx, double numGroups, @@ -2178,7 +2712,8 @@ make_group(Query *root, plan->plan_rows = numGroups; /* - * We also need to account for the cost of evaluation of the tlist. + * We also need to account for the cost of evaluation of the qual (ie, the + * HAVING clause) and the tlist. * * XXX this double-counts the cost of evaluation of any expressions used * for grouping, since in reality those will have been evaluated at a @@ -2188,12 +2723,19 @@ make_group(Query *root, * See notes in grouping_planner about why this routine and make_agg are * the only ones in this file that worry about tlist eval cost. */ + if (qual) + { + cost_qual_eval(&qual_cost, qual); + plan->startup_cost += qual_cost.startup; + plan->total_cost += qual_cost.startup; + plan->total_cost += qual_cost.per_tuple * plan->plan_rows; + } cost_qual_eval(&qual_cost, tlist); plan->startup_cost += qual_cost.startup; plan->total_cost += qual_cost.startup; plan->total_cost += qual_cost.per_tuple * plan->plan_rows; - plan->qual = NIL; + plan->qual = qual; plan->targetlist = tlist; plan->lefttree = lefttree; plan->righttree = NULL; @@ -2210,24 +2752,24 @@ make_unique(Plan *lefttree, List *distinctList) { Unique *node = makeNode(Unique); Plan *plan = &node->plan; - int numCols = length(distinctList); + int numCols = list_length(distinctList); int keyno = 0; AttrNumber *uniqColIdx; - List *slitem; + ListCell *slitem; copy_plan_costsize(plan, lefttree); /* - * Charge one cpu_operator_cost per comparison per input tuple. We - * assume all columns get compared at most of the tuples. (XXX - * probably this is an overestimate.) + * Charge one cpu_operator_cost per comparison per input tuple. We assume + * all columns get compared at most of the tuples. (XXX probably this is + * an overestimate.) */ plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols; /* - * plan->plan_rows is left as a copy of the input subplan's plan_rows; - * ie, we assume the filter removes nothing. The caller must alter - * this if he has a better idea. + * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie, + * we assume the filter removes nothing. The caller must alter this if he + * has a better idea. */ plan->targetlist = copyObject(lefttree->targetlist); @@ -2236,8 +2778,7 @@ make_unique(Plan *lefttree, List *distinctList) plan->righttree = NULL; /* - * convert SortClause list into array of attr indexes, as wanted by - * exec + * convert SortClause list into array of attr indexes, as wanted by exec */ Assert(numCols > 0); uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols); @@ -2247,7 +2788,7 @@ make_unique(Plan *lefttree, List *distinctList) SortClause *sortcl = (SortClause *) lfirst(slitem); TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist); - uniqColIdx[keyno++] = tle->resdom->resno; + uniqColIdx[keyno++] = tle->resno; } node->numCols = numCols; @@ -2267,16 +2808,16 @@ make_setop(SetOpCmd cmd, Plan *lefttree, { SetOp *node = makeNode(SetOp); Plan *plan = &node->plan; - int numCols = length(distinctList); + int numCols = list_length(distinctList); int keyno = 0; AttrNumber *dupColIdx; - List *slitem; + ListCell *slitem; copy_plan_costsize(plan, lefttree); /* - * Charge one cpu_operator_cost per comparison per input tuple. We - * assume all columns get compared at most of the tuples. + * Charge one cpu_operator_cost per comparison per input tuple. We assume + * all columns get compared at most of the tuples. */ plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols; @@ -2294,8 +2835,7 @@ make_setop(SetOpCmd cmd, Plan *lefttree, plan->righttree = NULL; /* - * convert SortClause list into array of attr indexes, as wanted by - * exec + * convert SortClause list into array of attr indexes, as wanted by exec */ Assert(numCols > 0); dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols); @@ -2305,7 +2845,7 @@ make_setop(SetOpCmd cmd, Plan *lefttree, SortClause *sortcl = (SortClause *) lfirst(slitem); TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist); - dupColIdx[keyno++] = tle->resdom->resno; + dupColIdx[keyno++] = tle->resno; } node->cmd = cmd; @@ -2316,8 +2856,16 @@ make_setop(SetOpCmd cmd, Plan *lefttree, return node; } +/* + * Note: offset_est and count_est are passed in to save having to repeat + * work already done to estimate the values of the limitOffset and limitCount + * expressions. Their values are as returned by preprocess_limit (0 means + * "not relevant", -1 means "couldn't estimate"). Keep the code below in sync + * with that function! + */ Limit * -make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount) +make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount, + int offset_est, int count_est) { Limit *node = makeNode(Limit); Plan *plan = &node->plan; @@ -2325,46 +2873,50 @@ make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount) copy_plan_costsize(plan, lefttree); /* - * If offset/count are constants, adjust the output rows count and - * costs accordingly. This is only a cosmetic issue if we are at top - * level, but if we are building a subquery then it's important to - * report correct info to the outer planner. + * Adjust the output rows count and costs according to the offset/limit. + * This is only a cosmetic issue if we are at top level, but if we are + * building a subquery then it's important to report correct info to the + * outer planner. + * + * When the offset or count couldn't be estimated, use 10% of the + * estimated number of rows emitted from the subplan. */ - if (limitOffset && IsA(limitOffset, Const)) + if (offset_est != 0) { - Const *limito = (Const *) limitOffset; - int32 offset = DatumGetInt32(limito->constvalue); + double offset_rows; - if (!limito->constisnull && offset > 0) - { - if (offset > plan->plan_rows) - offset = (int32) plan->plan_rows; - if (plan->plan_rows > 0) - plan->startup_cost += - (plan->total_cost - plan->startup_cost) - * ((double) offset) / plan->plan_rows; - plan->plan_rows -= offset; - if (plan->plan_rows < 1) - plan->plan_rows = 1; - } + if (offset_est > 0) + offset_rows = (double) offset_est; + else + offset_rows = clamp_row_est(lefttree->plan_rows * 0.10); + if (offset_rows > plan->plan_rows) + offset_rows = plan->plan_rows; + if (plan->plan_rows > 0) + plan->startup_cost += + (plan->total_cost - plan->startup_cost) + * offset_rows / plan->plan_rows; + plan->plan_rows -= offset_rows; + if (plan->plan_rows < 1) + plan->plan_rows = 1; } - if (limitCount && IsA(limitCount, Const)) + + if (count_est != 0) { - Const *limitc = (Const *) limitCount; - int32 count = DatumGetInt32(limitc->constvalue); + double count_rows; - if (!limitc->constisnull && count >= 0) - { - if (count > plan->plan_rows) - count = (int32) plan->plan_rows; - if (plan->plan_rows > 0) - plan->total_cost = plan->startup_cost + - (plan->total_cost - plan->startup_cost) - * ((double) count) / plan->plan_rows; - plan->plan_rows = count; - if (plan->plan_rows < 1) - plan->plan_rows = 1; - } + if (count_est > 0) + count_rows = (double) count_est; + else + count_rows = clamp_row_est(lefttree->plan_rows * 0.10); + if (count_rows > plan->plan_rows) + count_rows = plan->plan_rows; + if (plan->plan_rows > 0) + plan->total_cost = plan->startup_cost + + (plan->total_cost - plan->startup_cost) + * count_rows / plan->plan_rows; + plan->plan_rows = count_rows; + if (plan->plan_rows < 1) + plan->plan_rows = 1; } plan->targetlist = copyObject(lefttree->targetlist); @@ -2378,6 +2930,15 @@ make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount) return node; } +/* + * make_result + * Build a Result plan node + * + * If we have a subplan, assume that any evaluation costs for the gating qual + * were already factored into the subplan's startup cost, and just copy the + * subplan cost. If there's no subplan, we should include the qual eval + * cost. In either case, tlist eval cost is not to be included here. + */ Result * make_result(List *tlist, Node *resconstantqual, @@ -2393,17 +2954,16 @@ make_result(List *tlist, plan->startup_cost = 0; plan->total_cost = cpu_tuple_cost; plan->plan_rows = 1; /* wrong if we have a set-valued function? */ - plan->plan_width = 0; /* XXX try to be smarter? */ - } - - if (resconstantqual) - { - QualCost qual_cost; + plan->plan_width = 0; /* XXX is it worth being smarter? */ + if (resconstantqual) + { + QualCost qual_cost; - cost_qual_eval(&qual_cost, (List *) resconstantqual); - /* resconstantqual is evaluated once at startup */ - plan->startup_cost += qual_cost.startup + qual_cost.per_tuple; - plan->total_cost += qual_cost.startup + qual_cost.per_tuple; + cost_qual_eval(&qual_cost, (List *) resconstantqual); + /* resconstantqual is evaluated once at startup */ + plan->startup_cost += qual_cost.startup + qual_cost.per_tuple; + plan->total_cost += qual_cost.startup + qual_cost.per_tuple; + } } plan->targetlist = tlist;