Re: Using indices for UNION. - Mailing list pgsql-hackers
| From | Kyotaro HORIGUCHI |
|---|---|
| Subject | Re: Using indices for UNION. |
| Date | |
| Msg-id | 20131119.204158.141802657.horiguchi.kyotaro@lab.ntt.co.jp Whole thread Raw |
| In response to | Re: Using indices for UNION. (Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp>) |
| Responses |
Re: Using indices for UNION.
|
| List | pgsql-hackers |
Hello, I've totally refactored the series of pathes and cut out the appropriate portion as 'UNION stuff'. This patch rquires another 'pathkeys expansion using fully-orderd index' patch to work. http://www.postgresql.org/message-id/20131119.203516.251520490.horiguchi.kyotaro@lab.ntt.co.jp 1. plan_with_pathkeys_v1_20131119.patch This is a patch adding pathkeys (and uniqueness) information onstruct Plan to do what the latter part of grouping_plannerdoeson current_pathkeys in seemingly autonomous way. As in theprevious discussion, this is in a sense a baddirection togo. But this patch make the path manipulations occured in thelatter of grouping_planner simple and would reduceextra sortingand uniq'ing. 2. union_uses_idx_v3_20131119.patch This is made to apply after the first patch above. The core of"Using indices for UNION". This is - as in the previousdiscussion- also not in so smart way to do that. Most of all,this patch runs subquery_planner additionally for UNIONwithsome conditions. Nevertheless, the expected gain should not besmall. regards, -- Kyotaro Horiguchi NTT Open Source Software Center diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 5947e5b..d8a17a0 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -98,11 +98,13 @@ static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);static IndexScan *make_indexscan(List*qptlist, List *qpqual, Index scanrelid, Oid indexid, List *indexqual, List *indexqualorig, List *indexorderby, List *indexorderbyorig, + List *pathkeys, bool uniquely_ordered, ScanDirection indexscandir);static IndexOnlyScan *make_indexonlyscan(List*qptlist, List *qpqual, Index scanrelid, Oid indexid, List *indexqual,List *indexorderby, List *indextlist, + List *pathkeys, bool uniquely_ordered, ScanDirection indexscandir);static BitmapIndexScan*make_bitmap_indexscan(Index scanrelid, Oid indexid, List *indexqual, @@ -150,8 +152,8 @@ static MergeJoin *make_mergejoin(List *tlist, bool *mergenullsfirst, Plan*lefttree, Plan *righttree, JoinType jointype); -static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, - AttrNumber *sortColIdx, Oid *sortOperators, +static Sort *make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys, + int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples);static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, @@ -750,6 +752,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) plan->qual = NIL; plan->lefttree= NULL; plan->righttree = NULL; + plan->pathkeys = pathkeys; + plan->is_unique = false; /* Compute sort column info, and adjust MergeAppend's tlist as needed */ (void) prepare_sort_from_pathkeys(root,plan, pathkeys, @@ -810,7 +814,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) /* Now, insert a Sortnode if subplan isn't sufficiently ordered */ if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) - subplan = (Plan *) make_sort(root, subplan, numsortkeys, + subplan = (Plan *) make_sort(root, subplan, pathkeys, numsortkeys, sortColIdx,sortOperators, collations, nullsFirst, best_path->limit_tuples); @@ -1263,6 +1267,8 @@ create_indexscan_plan(PlannerInfo *root, fixed_indexquals, fixed_indexorderbys, best_path->indexinfo->indextlist, + best_path->path.pathkeys, + false, best_path->indexscandir); else scan_plan = (Scan *) make_indexscan(tlist, @@ -1273,6 +1279,8 @@ create_indexscan_plan(PlannerInfo *root, stripped_indexquals, fixed_indexorderbys, indexorderbys, + best_path->path.pathkeys, + false, best_path->indexscandir); copy_path_costsize(&scan_plan->plan, &best_path->path); @@ -3245,6 +3253,8 @@ make_indexscan(List *qptlist, List *indexqualorig, List *indexorderby, List *indexorderbyorig, + List *pathkeys, + bool uniquely_ordered, ScanDirection indexscandir){ IndexScan *node = makeNode(IndexScan); @@ -3255,6 +3265,8 @@ make_indexscan(List *qptlist, plan->qual = qpqual; plan->lefttree = NULL; plan->righttree= NULL; + plan->pathkeys = pathkeys; + plan->is_unique = uniquely_ordered; node->scan.scanrelid = scanrelid; node->indexid = indexid; node->indexqual= indexqual; @@ -3274,6 +3286,8 @@ make_indexonlyscan(List *qptlist, List *indexqual, List *indexorderby, List *indextlist, + List *pathkeys, + bool uniquely_ordered, ScanDirection indexscandir){ IndexOnlyScan *node = makeNode(IndexOnlyScan); @@ -3284,6 +3298,8 @@ make_indexonlyscan(List *qptlist, plan->qual = qpqual; plan->lefttree = NULL; plan->righttree= NULL; + plan->pathkeys = pathkeys; + plan->is_unique = uniquely_ordered; node->scan.scanrelid = scanrelid; node->indexid = indexid; node->indexqual= indexqual; @@ -3753,8 +3769,8 @@ make_mergejoin(List *tlist, * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)*/static Sort * -make_sort(PlannerInfo *root, Plan *lefttree, int numCols, - AttrNumber *sortColIdx, Oid *sortOperators, +make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys, + int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples){ @@ -3776,6 +3792,8 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols, plan->qual = NIL; plan->lefttree =lefttree; plan->righttree = NULL; + plan->pathkeys = pathkeys; + plan->is_unique = false; node->numCols = numCols; node->sortColIdx = sortColIdx; node->sortOperators = sortOperators; @@ -4125,7 +4143,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, &nullsFirst); /* Now build the Sort node */ - return make_sort(root, lefttree, numsortkeys, + return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, limit_tuples);} @@ -4147,6 +4165,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree) Oid *sortOperators; Oid *collations; bool *nullsFirst; + List *pathkeys; /* Convert list-ish representation to arrays wanted by executor */ numsortkeys = list_length(sortcls); @@ -4168,7 +4187,9 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree) numsortkeys++; } - return make_sort(root, lefttree, numsortkeys, + pathkeys = make_pathkeys_for_sortclauses(root, sortcls, sub_tlist); + + return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0);} @@ -4199,6 +4220,7 @@ make_sort_from_groupcols(PlannerInfo *root, Oid *sortOperators; Oid *collations; bool *nullsFirst; + List *pathkeys; /* Convert list-ish representation to arrays wanted by executor */ numsortkeys = list_length(groupcls); @@ -4220,10 +4242,17 @@ make_sort_from_groupcols(PlannerInfo *root, sortOperators[numsortkeys] = grpcl->sortop; collations[numsortkeys] = exprCollation((Node *) tle->expr); nullsFirst[numsortkeys] = grpcl->nulls_first; + + /* This tlist should not be bound with any other orderig clause */ + Assert(tle->ressortgroupref == 0); + tle->ressortgroupref = grpcl->tleSortGroupRef; + numsortkeys++; } - return make_sort(root, lefttree, numsortkeys, + pathkeys = make_pathkeys_for_sortclauses(root, groupcls, sub_tlist); + + return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0);} @@ -4339,6 +4368,16 @@ make_agg(PlannerInfo *root, List *tlist, List *qual, plan->lefttree = lefttree; plan->righttree= NULL; + /* + * We can safely assume that the lefttree and therefore the result is + * sorted on group pathkeys and unique if given aggstrategy is AGG_SORTED. + */ + if (node->aggstrategy == AGG_SORTED) + plan->pathkeys = root->group_pathkeys; + else + plan->pathkeys = NIL; + plan->is_unique = true; + return node;} @@ -4448,6 +4487,13 @@ make_group(PlannerInfo *root, plan->lefttree = lefttree; plan->righttree = NULL; + /* + * We assume that lefttree is ordered on the same pathkeys with that this + * group node wants. + */ + plan->pathkeys = lefttree->pathkeys; + plan->is_unique = true; + return node;} @@ -4486,6 +4532,8 @@ make_unique(Plan *lefttree, List *distinctList) plan->qual = NIL; plan->lefttree = lefttree; plan->righttree = NULL; + plan->pathkeys = lefttree->pathkeys; + plan->is_unique = true; /* * convert SortGroupClause list into arrays of attr indexes and equality @@ -4669,6 +4717,8 @@ make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount, plan->qual = NIL; plan->lefttree= lefttree; plan->righttree = NULL; + plan->pathkeys = lefttree->pathkeys; + plan->is_unique = lefttree->is_unique; node->limitOffset = limitOffset; node->limitCount = limitCount; @@ -4717,6 +4767,10 @@ make_result(PlannerInfo *root, plan->qual = NIL; plan->lefttree = subplan; plan->righttree= NULL; + + /* this plan emits at most one row when subplan is NULL */ + if (subplan == NULL) plan->is_unique = true; + node->resconstantqual = resconstantqual; return node; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d8aa35d..a09d38f 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -1011,6 +1011,19 @@ inheritance_planner(PlannerInfo *root) SS_assign_special_param(root));} +static bool +plan_is_ordered(Plan *plan, List *pathkeys) +{ + if (pathkeys_contained_in(pathkeys, plan->pathkeys)) + return true; + + if (plan->pathkeys && plan->is_unique && + pathkeys_contained_in(plan->pathkeys, pathkeys)) + return true; + + return false; +} +/*-------------------- * grouping_planner * Perform planning steps related to grouping, aggregation, etc. @@ -1039,7 +1052,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) int64 count_est = 0; double limit_tuples = -1.0; Plan *result_plan; - List *current_pathkeys; double dNumGroups = 0; bool use_hashed_distinct = false; bool tested_hashed_distinct = false; @@ -1081,15 +1093,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) &set_sortclauses); /* - * Calculate pathkeys representing the sort order (if any) of the set - * operation's result. We have to do this before overwriting the sort - * key information... - */ - current_pathkeys = make_pathkeys_for_sortclauses(root, - set_sortclauses, - result_plan->targetlist); - - /* * We should not need to call preprocess_targetlist, since we must be * in a SELECT query node. Instead, use the targetlist returned by * plan_set_operations (since this tells whether it returned any @@ -1442,15 +1445,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) tlist, &agg_costs, best_path); - if (result_plan != NULL) - { - /* - * optimize_minmax_aggregates generated the full plan, with the - * right tlist, and it has no sort order. - */ - current_pathkeys = NIL; - } - else + if (result_plan == NULL) { /* * Normal case --- create a plan according to query_planner's @@ -1459,11 +1454,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) bool need_sort_for_grouping= false; result_plan = create_plan(root, best_path); - current_pathkeys = best_path->pathkeys; /* Detect if we'll need an explicit sort for grouping */ if (parse->groupClause && !use_hashed_grouping && - !pathkeys_contained_in(root->group_pathkeys, current_pathkeys)) + !plan_is_ordered(result_plan, root->group_pathkeys)) { need_sort_for_grouping= true; @@ -1541,37 +1535,20 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) extract_grouping_ops(parse->groupClause), numGroups, result_plan); - /* Hashed aggregation produces randomly-ordered results */ - current_pathkeys = NIL; } else if (parse->hasAggs) { /*Plain aggregate plan --- sort if needed */ AggStrategy aggstrategy; - if (parse->groupClause) + aggstrategy = parse->groupClause ? AGG_SORTED : AGG_PLAIN; + if (aggstrategy == AGG_SORTED && need_sort_for_grouping) { - if (need_sort_for_grouping) - { - result_plan = (Plan *) - make_sort_from_groupcols(root, - parse->groupClause, - groupColIdx, - result_plan); - current_pathkeys = root->group_pathkeys; - } - aggstrategy = AGG_SORTED; - - /* - * The AGG node will not change the sort ordering of its - * groups, so current_pathkeys describes the result too. - */ - } - else - { - aggstrategy = AGG_PLAIN; - /* Result will be only one row anyway; no sort order */ - current_pathkeys = NIL; + result_plan = (Plan *) + make_sort_from_groupcols(root, + parse->groupClause, + groupColIdx, + result_plan); } result_plan = (Plan *) make_agg(root, @@ -1601,7 +1578,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) parse->groupClause, groupColIdx, result_plan); - current_pathkeys = root->group_pathkeys; } result_plan = (Plan *) make_group(root, @@ -1612,7 +1588,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) extract_grouping_ops(parse->groupClause), dNumGroups, result_plan); - /* The Group node won't change sort ordering */ } else if (root->hasHavingQual) { @@ -1722,13 +1697,14 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) result_plan, window_pathkeys, -1.0); - if (!pathkeys_contained_in(window_pathkeys, - current_pathkeys)) - { - /* we do indeed need to sort */ + + /* + * we do indeed need to sort if result_plan is not ordered + * on window_pathkeys + */ + if (!plan_is_ordered(result_plan, window_pathkeys)) result_plan = (Plan *) sort_plan; - current_pathkeys = window_pathkeys; - } + /* In either case, extract the per-column information */ get_column_info_for_window(root,wc, tlist, sort_plan->numCols, @@ -1792,12 +1768,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) long numDistinctRows; /* - * If there was grouping or aggregation, use the current number of - * rows as the estimated number of DISTINCT rows (ie, assume the - * result was already mostly unique). If not, use the number of + * If result_plan emits already distinct'ed rows, use the current + * number of rows as the estimated number of DISTINCT rows (ie, assume + * the result was already unique). If not, use the number of * distinct-groups calculated previously. */ - if (parse->groupClause || root->hasHavingQual || parse->hasAggs) + if (result_plan->is_unique) dNumDistinctRows = result_plan->plan_rows; else dNumDistinctRows= dNumGroups; @@ -1822,7 +1798,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) result_plan->total_cost, result_plan->startup_cost, result_plan->total_cost, - current_pathkeys, + result_plan->pathkeys, dNumDistinctRows); } @@ -1840,8 +1816,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) extract_grouping_ops(parse->distinctClause), numDistinctRows, result_plan); - /* Hashed aggregation produces randomly-ordered results */ - current_pathkeys = NIL; } else { @@ -1865,29 +1839,23 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) else needed_pathkeys= root->distinct_pathkeys; - if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys)) + if (!plan_is_ordered(result_plan, needed_pathkeys)) { - if (list_length(root->distinct_pathkeys) >= - list_length(root->sort_pathkeys)) - current_pathkeys = root->distinct_pathkeys; - else - { - current_pathkeys = root->sort_pathkeys; - /* Assert checks that parser didn't mess up... */ - Assert(pathkeys_contained_in(root->distinct_pathkeys, - current_pathkeys)); - } - + /* Assert checks that parser didn't mess up... */ + Assert(pathkeys_contained_in(root->distinct_pathkeys, + needed_pathkeys)); + Assert(pathkeys_contained_in(root->sort_pathkeys, + needed_pathkeys)); result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, - current_pathkeys, + needed_pathkeys, -1.0); } - result_plan = (Plan *) make_unique(result_plan, - parse->distinctClause); + if (!result_plan->is_unique) + result_plan = (Plan *) make_unique(result_plan, + parse->distinctClause); result_plan->plan_rows = dNumDistinctRows; - /* The Unique node won't change sort ordering */ } } @@ -1897,13 +1865,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) */ if (parse->sortClause) { - if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys)) + if (!plan_is_ordered(result_plan, root->sort_pathkeys)) { result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, root->sort_pathkeys, limit_tuples); - current_pathkeys = root->sort_pathkeys; } } @@ -1914,18 +1881,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) * ModifyTable node instead.) */ if (parse->rowMarks) - { result_plan = (Plan *) make_lockrows(result_plan, root->rowMarks, SS_assign_special_param(root)); - /* - * The result can no longer be assumed sorted, since locking might - * cause the sort key columns to be replaced with new values. - */ - current_pathkeys = NIL; - } - /* * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node. */ @@ -1942,7 +1901,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) * Return the actual output orderingin query_pathkeys for possible use by * an outer query level. */ - root->query_pathkeys = current_pathkeys; + root->query_pathkeys = result_plan->pathkeys; return result_plan;} diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 44ea0b7..ced07d9 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -101,6 +101,8 @@ typedef struct Plan */ double plan_rows; /* number of rows plan is expected to emit*/ int plan_width; /* average row width in bytes */ + List *pathkeys; /* ordered on this pathkeys if any */ + bool is_unique; /* emits unique result */ /* * Common structural data for all Plan types. diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index d8a17a0..8c60b2c 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -813,7 +813,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) numsortkeys* sizeof(bool)) == 0); /* Now, insert a Sort node if subplan isn't sufficiently ordered */ - if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) + if (!path_is_ordered(subpath, pathkeys)) subplan = (Plan *) make_sort(root, subplan, pathkeys, numsortkeys, sortColIdx, sortOperators, collations,nullsFirst, @@ -1151,6 +1151,7 @@ create_indexscan_plan(PlannerInfo *root, List *fixed_indexquals; List *fixed_indexorderbys; ListCell *l; + bool uniquely_ordered = false; /* it should be a base rel... */ Assert(baserelid > 0); @@ -1258,6 +1259,20 @@ create_indexscan_plan(PlannerInfo *root, replace_nestloop_params(root, (Node *) indexorderbys); } + /* + * XXX: This is rather tricky. IndexPath's pathkeys may be both superset + * (including the same) or subset of key columns of the index. This path + * will emit distnct'edly ordered rows when the pathkeys contains the key + * columns and the index is fully ordered on the key columns. + * + * See the point calling truncate_useless_pathkeys in build_index_paths() + * for detail. + */ + if (list_length(best_path->path.pathkeys) >= + best_path->indexinfo->ncolumns && + best_path->indexinfo->full_ordered) + uniquely_ordered = true; + /* Finally ready to build the plan node */ if (indexonly) scan_plan = (Scan *) make_indexonlyscan(tlist, @@ -1268,7 +1283,7 @@ create_indexscan_plan(PlannerInfo *root, fixed_indexorderbys, best_path->indexinfo->indextlist, best_path->path.pathkeys, - false, + uniquely_ordered, best_path->indexscandir); else scan_plan = (Scan *) make_indexscan(tlist, @@ -1280,7 +1295,7 @@ create_indexscan_plan(PlannerInfo *root, fixed_indexorderbys, indexorderbys, best_path->path.pathkeys, - false, + uniquely_ordered, best_path->indexscandir); copy_path_costsize(&scan_plan->plan, &best_path->path); diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index a09d38f..a337c84 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -1075,15 +1075,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) List *set_sortclauses; /* - * If there's a top-level ORDER BY, assume we have to fetch all the - * tuples. This might be too simplistic given all the hackery below - * to possibly avoid the sort; but the odds of accurate estimates here - * are pretty low anyway. - */ - if (parse->sortClause) - tuple_fraction = 0.0; - - /* * Construct the plan for set operations. The result will not need * any work except perhapsa top-level sort and/or LIMIT. Note that * any special work for recursive unions is the responsibility of diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index e249628..9fe0b66 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -29,6 +29,7 @@#include "postgres.h"#include <limits.h> +#include <math.h>#include "access/heapam.h"#include "access/htup_details.h" @@ -44,6 +45,7 @@#include "optimizer/planner.h"#include "optimizer/prep.h"#include "optimizer/tlist.h" +#include "optimizer/paths.h"#include "parser/parse_coerce.h"#include "parser/parsetree.h"#include "utils/lsyscache.h" @@ -60,7 +62,7 @@ typedef structstatic Plan *recurse_set_operations(Node *setOp, PlannerInfo *root, double tuple_fraction, List *colTypes, List *colCollations, - bool junkOK, + List *groupClauses, bool junkOK, int flag, List *refnames_tlist, List **sortClauses, double *pNumGroups);static Plan *generate_recursion_plan(SetOperationStmt *setOp, @@ -78,7 +80,8 @@ static Plan *generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root,static List *recurse_union_children(Node*setOp, PlannerInfo *root, double tuple_fraction, SetOperationStmt *top_union, - List *refnames_tlist); + List *refnames_tlist, + List **child_sortclause);static Plan *make_union_unique(SetOperationStmt *op, Plan *plan, PlannerInfo *root, double tuple_fraction, List **sortClauses); @@ -97,7 +100,8 @@ static List *generate_append_tlist(List *colTypes, List *colCollations, bool flag, List *input_plans, List *refnames_tlist); -static List *generate_setop_grouplist(SetOperationStmt *op, List *targetlist); +static List *generate_setop_grouplist(List *groupClauses, List *targetlist, + List *sortClauses);static void expand_inherited_rtentry(PlannerInfo *root, RangeTblEntry*rte, Index rti);static void make_inh_translation_list(Relation oldrelation, @@ -152,6 +156,15 @@ plan_set_operations(PlannerInfo *root, double tuple_fraction, Assert(parse->distinctClause == NIL); /* + * If there's a top-level ORDER BY, assume we have to fetch all the tuples + * except for UNION. This might be too simplistic given all the hackery + * below to possibly avoid the sort; but the odds of accurate estimates + * here are pretty low anyway. + */ + if (parse->sortClause && topop->op != SETOP_UNION) + tuple_fraction = 0.0; + + /* * We'll need to build RelOptInfos for each of the leaf subqueries, which * are RTE_SUBQUERY rangetable entriesin this Query. Prepare the index * arrays for that. @@ -186,18 +199,49 @@ plan_set_operations(PlannerInfo *root, double tuple_fraction, */ return recurse_set_operations((Node*) topop, root, tuple_fraction, topop->colTypes, topop->colCollations, + topop->groupClauses, true, -1, leftmostQuery->targetList, sortClauses, NULL);}/* + * save_plannerglobal + * + * save planner global to allow multiple calls of subquery_planner at the same + * global status. This is done apartly from copyObject so as to do medium + * shallow copying. + */ +static PlannerGlobal * +save_plannerglobal(const PlannerGlobal *in) +{ + PlannerGlobal *save = makeNode(PlannerGlobal); + + save->boundParams = in->boundParams; + save->subplans = list_copy(in->subplans); + save->subroots = list_copy(in->subroots); + save->rewindPlanIDs = bms_copy(in->rewindPlanIDs); + save->finalrtable = list_copy(in->finalrtable); + save->finalrowmarks = list_copy(in->finalrowmarks); + save->resultRelations = list_copy(in->resultRelations); + save->relationOids = list_copy(in->relationOids); + save->invalItems = list_copy(in->invalItems); + save->nParamExec = in->nParamExec; + save->lastPHId = in->lastPHId; + save->lastRowMarkId = in->lastRowMarkId; + save->transientPlan = in->transientPlan; + + return save; +} + +/* * recurse_set_operations * Recursively handle one step in a tree of set operations * * tuple_fraction: fractionof tuples we expect to retrieve from node * colTypes: OID list of set-op's result column datatypes * colCollations:OID list of set-op's result column collations + * groupClauses: parent setop's grouping clause. * junkOK: if true, child resjunk columns may be left in the result * flag:if >= 0, add a resjunk output column indicating value of flag * refnames_tlist: targetlist to take column names from @@ -215,7 +259,7 @@ static Plan *recurse_set_operations(Node *setOp, PlannerInfo *root, double tuple_fraction, List *colTypes, List *colCollations, - bool junkOK, + List *groupClauses, bool junkOK, int flag, List *refnames_tlist, List **sortClauses, double *pNumGroups){ @@ -224,13 +268,20 @@ recurse_set_operations(Node *setOp, PlannerInfo *root, RangeTblRef *rtr = (RangeTblRef *) setOp; RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex]; Query *subquery = rte->subquery; + Query *pdquery = NULL; /* 'pd' comes from 'pushed down' */ RelOptInfo *rel; - PlannerInfo *subroot; + PlannerInfo *subroot, + *pdsubroot; + PlannerGlobal *pdglob; Plan *subplan, - *plan; + *plan, + *pdplan; + bool try_pushdown = false; Assert(subquery != NULL); + *sortClauses = NIL; + /* * We need to build a RelOptInfo for each leaf subquery. This isn't * used for anything here,but it carries the subroot data structures @@ -243,12 +294,146 @@ recurse_set_operations(Node *setOp, PlannerInfo *root, /* * Generate plan for primitivesubquery + * + * Consider pusing down ORDER BY or groupings of the parent set + * operation onto this subquery. */ + if(root->parse->sortClause && !subquery->sortClause && + tuple_fraction >= 1) + { + ListCell *lcs, *lcd; + int refno = 1; + + /* + * Check if the sort cluase of the root can be applied on this + * subquery. All non-junk tlist items shoud be simple Var and + * their match in types and ressortgroupref should be in their + * appearance order. + */ + try_pushdown = true; + forboth(lcs, root->parse->targetList, lcd, subquery->targetList) + { + TargetEntry *ste = (TargetEntry*) lfirst(lcs); + TargetEntry *dte = (TargetEntry*) lfirst(lcd); + Node *sexpr = (Node*)ste->expr; + Node *dexpr = (Node*)dte->expr; + + if (ste->resjunk && dte->resjunk) continue; + + if (ste->resjunk != dte->resjunk || + !IsA(sexpr, Var) || !IsA(dexpr, Var) || + exprType(sexpr) != exprType(dexpr) || + (root->parse->sortClause && + ste->ressortgroupref != 0 && + ste->ressortgroupref != refno++)) + { + try_pushdown = false; + break; + } + } + } + + if (try_pushdown) + { + pdquery = copyObject(subquery); + + if (!pdquery->sortClause) + { + ListCell *lcs, *lcd; + + pdquery->sortClause = root->parse->sortClause; + + forboth(lcs, root->parse->targetList, + lcd, pdquery->targetList) + { + TargetEntry *ste = (TargetEntry *) lfirst(lcs); + TargetEntry *dte = (TargetEntry *) lfirst(lcd); + dte->ressortgroupref = ste->ressortgroupref; + } + } + + /* + * Pushing down groupings. Set operations doesn't accept + * distinct clauses. + */ + if (!pdquery->setOperations && + !pdquery->distinctClause && groupClauses) + { + if (pdquery->sortClause) + { + ListCell *lct; + int i = 1; + + /* Check if groupClause is coappliable with sortClauses */ + foreach (lct, pdquery->targetList) + { + TargetEntry *te = (TargetEntry *) lfirst(lct); + + if (te->resjunk) continue; + if (te->ressortgroupref != 0 && + te->ressortgroupref != i) + break; + i++; + } + + if (!lct) + pdquery->distinctClause = + generate_setop_grouplist(groupClauses, + pdquery->targetList, + pdquery->sortClause); + } + } + if (tuple_fraction >= 1 && + !pdquery->limitCount && !pdquery->limitOffset) + pdquery->limitCount = + (Node*)makeConst(INT8OID, -1, InvalidOid, sizeof(int64), + Int64GetDatum(tuple_fraction), + false, FLOAT8PASSBYVAL); + + /* + * Save current PlnannerGlobal. subquery_planner could modify + * PlannerGlobal so make a shallow backup in order to make the + * alternative plans selectable. + */ + pdglob = save_plannerglobal(root->glob); + } + subplan = subquery_planner(root->glob, subquery, root, false, tuple_fraction, &subroot); + if (try_pushdown) + { + pdplan = subquery_planner(pdglob, pdquery, + root, + false, tuple_fraction, + &pdsubroot); + + if (pdplan->total_cost < subplan->total_cost) + { + subquery = pdquery; + subplan = pdplan; + subroot = pdsubroot; + /* + * Glob cannot be moved because this is referred to from many + * places by its address. So set the address of the original + * glob to subroot, then copy new values there. + */ + subroot->glob = root->glob; + *root->glob = *pdglob; + } + } + + /* + * This plan is sorted on sortClause if any, else sorted + * on distinctClause. + */ + if (subquery->sortClause) + *sortClauses = subquery->sortClause; + else + *sortClauses = subquery->distinctClause; + /* Save subroot and subplan in RelOptInfo for setrefs.c */ rel->subplan = subplan; rel->subroot =subroot; @@ -291,10 +476,28 @@ recurse_set_operations(Node *setOp, PlannerInfo *root, subplan); /* - * We don't bother to determine the subquery's output ordering since - * it won't be reflected in the set-op result anyhow. + * This plan's pathkeys and is_unique are apparently same to them of + * subplan unless type casting or coercing collations. */ - *sortClauses = NIL; + if (subplan->pathkeys && + tlist_same_datatypes(plan->targetlist, colTypes, junkOK) && + tlist_same_collations(plan->targetlist, colCollations, junkOK)) + { + ListCell *lcp, *lcr; + + forboth (lcp, plan->targetlist, lcr, root->parse->targetList) + { + TargetEntry *tep = (TargetEntry*) lfirst(lcp); + TargetEntry *ter = (TargetEntry*) lfirst(lcr); + + tep->ressortgroupref = ter->ressortgroupref; + } + plan->pathkeys = + make_pathkeys_for_sortclauses(root, + *sortClauses, + plan->targetlist); + plan->is_unique = subplan->is_unique; + } return plan; } @@ -379,12 +582,14 @@ generate_recursion_plan(SetOperationStmt *setOp, PlannerInfo *root, */ lplan = recurse_set_operations(setOp->larg,root, tuple_fraction, setOp->colTypes, setOp->colCollations, + setOp->groupClauses, false, -1, refnames_tlist, sortClauses, NULL); /* The right plan will want to look at the left one ... */ root->non_recursive_plan= lplan; rplan = recurse_set_operations(setOp->rarg, root, tuple_fraction, setOp->colTypes, setOp->colCollations, + setOp->groupClauses, false, -1, refnames_tlist, sortClauses, NULL); root->non_recursive_plan = NULL; @@ -409,7 +614,8 @@ generate_recursion_plan(SetOperationStmt *setOp, PlannerInfo *root, double dNumGroups; /* Identify the grouping semantics */ - groupList = generate_setop_grouplist(setOp, tlist); + groupList = + generate_setop_grouplist(setOp->groupClauses, tlist, NULL); /* We only support hashing here */ if (!grouping_is_hashable(groupList)) @@ -452,20 +658,7 @@ generate_union_plan(SetOperationStmt *op, PlannerInfo *root, List *planlist; List *tlist; Plan *plan; - - /* - * If plain UNION, tell children to fetch all tuples. - * - * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to - * each arm of the UNION ALL. One could make a case for reducing the - * tuple fraction for later arms (discounting by the expected size of the - * earlier arms' results) but it seems not worth the trouble. The normal - * case where tuple_fraction isn't already zero is a LIMIT at top level, - * and passing it down as-is is usually enough to get the desired result - * of preferring fast-start plans. - */ - if (!op->all) - tuple_fraction = 0.0; + List *lsort, *rsort; /* * If any of my children are identical UNION nodes (same op, all-flag, and @@ -475,34 +668,106 @@ generate_union_plan(SetOperationStmt *op, PlannerInfo *root, */ planlist = list_concat(recurse_union_children(op->larg,root, tuple_fraction, - op, refnames_tlist), + op, refnames_tlist, + &lsort), recurse_union_children(op->rarg, root, tuple_fraction, - op, refnames_tlist)); + op, refnames_tlist, + &rsort)); /* - * Generate tlist for Append plan node. + * Generate tlist for Append/MergeAppend plan node. * - * The tlist for an Append plan isn't important as far as the Append is - * concerned, but we must make it look real anyway for the benefit of the - * next plan level up. + * The tlist for an Append/MergeAppend plan isn't important as far as the + * they are concerned, but we must make it look real anyway for the + * benefit of the next plan level up. */ tlist = generate_append_tlist(op->colTypes, op->colCollations, false, planlist, refnames_tlist); - /* - * Append the child results together. - */ - plan = (Plan *) make_append(planlist, tlist); + if (lsort != NIL && equal(lsort, rsort)) + { + /* + * Generate MergeAppend plan if both children are sorted on the same + * sort clause or groupClauses. + */ + ListCell *lc, *slc; + int i = 0; + double total_size; + Plan *p; + List *distinctClause; + + MergeAppend *node = makeNode(MergeAppend); + node->plan.targetlist = tlist; + node->plan.qual = NIL; + node->plan.lefttree = NULL; + node->plan.righttree = NULL; + node->mergeplans = planlist; + node->numCols = list_length(root->parse->targetList); + node->sortColIdx = + (AttrNumber*)palloc(sizeof(AttrNumber) * node->numCols); + node->sortOperators = (Oid*)palloc(sizeof(Oid) * node->numCols); + node->collations = (Oid*)palloc(sizeof(Oid) * node->numCols); + node->nullsFirst = (bool*)palloc(sizeof(bool) * node->numCols); + + distinctClause = + generate_setop_grouplist(op->groupClauses, + node->plan.targetlist, + root->parse->sortClause); + forboth (slc, distinctClause, lc, node->plan.targetlist) + { + TargetEntry *te = (TargetEntry*) lfirst(lc); + SortGroupClause *sgc = (SortGroupClause *) lfirst(slc); + + Assert(sgc->tleSortGroupRef == te->ressortgroupref); + node->sortColIdx[i] = i + 1; + node->sortOperators[i] = sgc->sortop; + node->collations[i] = exprCollation((Node*)te->expr); + node->nullsFirst[i] = sgc->nulls_first; + te->ressortgroupref = sgc->tleSortGroupRef; + i++; + } + node->plan.pathkeys = + make_pathkeys_for_sortclauses(root, lsort, tlist); + + lc = list_head(node->mergeplans); + p = (Plan*) lfirst(lc); + node->plan.startup_cost = p->startup_cost; + node->plan.total_cost = p->total_cost; + node->plan.plan_rows = p->plan_rows; + total_size = p->plan_rows * p->plan_width; + for_each_cell(lc, lnext(lc)) + { + p = (Plan*) lfirst(lc); + node->plan.total_cost += p->total_cost; + node->plan.plan_rows += p->plan_rows; + total_size += p->plan_rows * p->plan_width; + } + node->plan.plan_width = rint(total_size / node->plan.plan_rows); + *sortClauses = root->parse->sortClause; - /* - * For UNION ALL, we just need the Append plan. For UNION, need to add - * node(s) to remove duplicates. - */ - if (op->all) - *sortClauses = NIL; /* result of UNION ALL is always unsorted */ + plan = (Plan*)node; + if (!op->all) + plan = make_union_unique(op, plan, root, tuple_fraction, + &distinctClause); + } else - plan = make_union_unique(op, plan, root, tuple_fraction, sortClauses); + { + /* + * Append the child results together. + */ + plan = (Plan *) make_append(planlist, tlist); + + /* + * For UNION ALL, we just need the Append plan. For UNION, need to + * add node(s) to remove duplicates. + */ + *sortClauses = NIL; + + if (!op->all) + plan = make_union_unique(op, plan, root, tuple_fraction, + sortClauses); + } /* * Estimate number of groups if caller wants it. For now we just assume @@ -544,12 +809,14 @@ generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root, lplan = recurse_set_operations(op->larg,root, 0.0 /* all tuples needed */ , op->colTypes, op->colCollations, + op->groupClauses, false, 0, refnames_tlist, &child_sortclauses, &dLeftGroups); rplan = recurse_set_operations(op->rarg,root, 0.0 /* all tuples needed */ , op->colTypes, op->colCollations, + op->groupClauses, false, 1, refnames_tlist, &child_sortclauses, &dRightGroups); @@ -589,8 +856,7 @@ generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root, plan = (Plan *) make_append(planlist,tlist); /* Identify the grouping semantics */ - groupList = generate_setop_grouplist(op, tlist); - + groupList = generate_setop_grouplist(op->groupClauses, tlist, NULL); /* punt if nothing to group on (can this happen?)*/ if (groupList == NIL) { @@ -678,9 +944,11 @@ static List *recurse_union_children(Node *setOp, PlannerInfo *root, double tuple_fraction, SetOperationStmt *top_union, - List *refnames_tlist) + List *refnames_tlist, + List **child_sortclauses){ - List *child_sortclauses; + List *lplan, *rplan; + List *lsort, *rsort; if (IsA(setOp, SetOperationStmt)) { @@ -690,15 +958,23 @@ recurse_union_children(Node *setOp, PlannerInfo *root, (op->all == top_union->all || op->all)&& equal(op->colTypes, top_union->colTypes)) { - /* Same UNION, so fold children into parent's subplan list */ - return list_concat(recurse_union_children(op->larg, root, - tuple_fraction, - top_union, - refnames_tlist), - recurse_union_children(op->rarg, root, - tuple_fraction, - top_union, - refnames_tlist)); + lplan = recurse_union_children(op->larg, root, + tuple_fraction, + top_union, + refnames_tlist, + &lsort); + rplan = recurse_union_children(op->rarg, root, + tuple_fraction, + top_union, + refnames_tlist, + &rsort); + /* + * Propagate whether all the descendents are sorted with same + * sortClause. + */ + if (lsort != NIL && equal(lsort, rsort)) + *child_sortclauses = lsort; + return list_concat(lplan, rplan); } } @@ -715,13 +991,16 @@ recurse_union_children(Node *setOp, PlannerInfo *root, tuple_fraction, top_union->colTypes, top_union->colCollations, + top_union->groupClauses, false,-1, refnames_tlist, - &child_sortclauses, NULL)); + child_sortclauses, NULL));}/* * Add nodes to the given plan tree to unique-ifythe result of a UNION. + * + * Given a sortClause, we assume the plan is already sorted on it. */static Plan *make_union_unique(SetOperationStmt *op,Plan *plan, @@ -731,9 +1010,11 @@ make_union_unique(SetOperationStmt *op, Plan *plan, List *groupList; double dNumGroups; long numGroups; + bool sort_needed = true; /* Identify the grouping semantics */ - groupList = generate_setop_grouplist(op, plan->targetlist); + groupList = generate_setop_grouplist(op->groupClauses, + plan->targetlist, *sortClauses); /* punt if nothing to group on (can this happen?)*/ if (groupList == NIL) @@ -742,6 +1023,9 @@ make_union_unique(SetOperationStmt *op, Plan *plan, return plan; } + if (*sortClauses && equal(*sortClauses, groupList)) + sort_needed = false; + /* * XXX for the moment, take the number of distinct groups as equal to the * total input size, ie, the worstcase. This is too conservative, but we @@ -756,7 +1040,8 @@ make_union_unique(SetOperationStmt *op, Plan *plan, numGroups = (long) Min(dNumGroups, (double) LONG_MAX); /* Decide whether to hash or sort */ - if (choose_hashed_setop(root, groupList, plan, + if (sort_needed && + choose_hashed_setop(root, groupList, plan, dNumGroups, dNumGroups, tuple_fraction, "UNION")) { @@ -778,7 +1063,9 @@ make_union_unique(SetOperationStmt *op, Plan *plan, else { /* Sort and Unique */ - plan = (Plan *) make_sort_from_sortclauses(root, groupList, plan); + if (sort_needed) + plan = (Plan *) make_sort_from_sortclauses(root, groupList, plan); + plan = (Plan *) make_unique(plan, groupList); plan->plan_rows = dNumGroups; /* We know the sort orderof the result */ @@ -1145,23 +1432,34 @@ generate_append_tlist(List *colTypes, List *colCollations, * the parser output representation doesn'tinclude a tlist for each * setop. So what we need to do here is copy that list and install * proper sortgrouprefsinto it and into the targetlist. + * + * sortClause is consulted if provided to avoid re-sorting in different + * directions on the same keys later. */static List * -generate_setop_grouplist(SetOperationStmt *op, List *targetlist) +generate_setop_grouplist(List *groupClauses, List *targetlist, + List *sortClauses){ - List *grouplist = (List *) copyObject(op->groupClauses); + List *grouplist = (List *) copyObject(groupClauses); ListCell *lg; + ListCell *ls = NULL; ListCell *lt; Index refno = 1; lg = list_head(grouplist); + + if (sortClauses) + ls = list_head(sortClauses); + foreach(lt, targetlist) { TargetEntry *tle = (TargetEntry *) lfirst(lt); - SortGroupClause *sgc; + SortGroupClause *sgc, *sgc_sort = NULL; - /* tlist shouldn't have any sortgrouprefs yet */ - Assert(tle->ressortgroupref == 0); + /* + * tlist shouldn't have any sortgrouprefs yet, or should be unchanged + */ + Assert(tle->ressortgroupref == 0 || tle->ressortgroupref == refno); if (tle->resjunk) continue; /* ignore resjunk columns */ @@ -1174,6 +1472,45 @@ generate_setop_grouplist(SetOperationStmt *op, List *targetlist) /* we could use assignSortGroupRefhere, but seems a bit silly */ sgc->tleSortGroupRef = tle->ressortgroupref = refno++; + + if (ls) + { + /* + * If sortClauses is provided, try to adjust the sorting order to + * get the chance for omitting sorting for grouping later. + */ + sgc_sort = (SortGroupClause *) lfirst(ls); + ls = lnext(ls); + if (sgc->sortop != sgc_sort->sortop) + { + Oid reverse = InvalidOid; + Oid opfamily, opcintype; + int16 strategy; + + if (get_ordering_op_properties(sgc->sortop, + &opfamily, &opcintype, &strategy)) + { + switch (strategy) + { + case BTLessStrategyNumber: + strategy = BTGreaterStrategyNumber; break; + case BTGreaterStrategyNumber: + strategy = BTLessStrategyNumber; break; + } + + reverse = get_opfamily_member(opfamily, + opcintype, + opcintype, + strategy); + if (sgc_sort->sortop == reverse) + { + sgc->sortop = reverse; + sgc->nulls_first = sgc_sort->nulls_first; + } + } + } + } + } Assert(lg == NULL); return grouplist;
pgsql-hackers by date: