Konstantin Knizhnik <k.knizh...@postgrespro.ru> writes:
> I think that the best approach is to generate two different paths:
> original one, when projection is always done before sort and another one
> with postponed projection of non-trivial columns. Then we compare costs
> of two paths and choose the best one.
> Unfortunately, I do not understand now how to implement it with existed
> grouping_planner.
> Do you think that it is possible?
After fooling with this awhile, I don't think it's actually necessary
to do that. See attached proof-of-concept patch.
Although this patch gets through our regression tests, that's only because
it's conservative about deciding to postpone evaluation; if it tried to
postpone evaluation in a query with window functions, it would fail
miserably, because pull_var_clause doesn't know about window functions.
I think that that's a clear oversight and we should extend it to offer
the same sorts of behaviors as it does for Aggrefs. But that would be
slightly invasive, there being a dozen or so callers; so I didn't bother
to do it yet pending comments on this patch.
I think it's probably also broken for SRFs in the tlist; we need to work
out what semantics we want for those. If we postpone any SRF to after
the Sort, we can no longer assume that a query LIMIT enables use of
bounded sort (because the SRF might repeatedly return zero rows).
I don't have a huge problem with that, but I think now would be a good
time to nail down some semantics.
Some other work that would be useful would be to refactor so that the
cost_qual_eval operations aren't so redundant. But that's just a small
time savings not a question of functionality.
And we'd have to document that this changes the behavior for volatile
functions. For the better, I think: this will mean that you get
consistent results no matter whether the query is implemented by
indexscan or seqscan-and-sort, which has never been true before.
But it is a change.
Do people approve of this sort of change in general, or this patch
approach in particular? Want to bikeshed the specific
when-to-postpone-eval policies implemented here? Other comments?
regards, tom lane
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 8937e71..b15fca1 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** static RelOptInfo *create_distinct_paths
*** 126,131 ****
--- 126,132 ----
RelOptInfo *input_rel);
static RelOptInfo *create_ordered_paths(PlannerInfo *root,
RelOptInfo *input_rel,
+ PathTarget *target,
double limit_tuples);
static PathTarget *make_group_input_target(PlannerInfo *root, List *tlist);
static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
*************** static PathTarget *make_window_input_tar
*** 134,139 ****
--- 135,142 ----
List *tlist, List *activeWindows);
static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
List *tlist);
+ static PathTarget *make_sort_input_target(PlannerInfo *root,
+ PathTarget *final_target);
/*****************************************************************************
*************** grouping_planner(PlannerInfo *root, bool
*** 1378,1383 ****
--- 1381,1387 ----
int64 offset_est = 0;
int64 count_est = 0;
double limit_tuples = -1.0;
+ PathTarget *final_target;
RelOptInfo *current_rel;
RelOptInfo *final_rel;
ListCell *lc;
*************** grouping_planner(PlannerInfo *root, bool
*** 1437,1442 ****
--- 1441,1449 ----
/* Save aside the final decorated tlist */
root->processed_tlist = tlist;
+ /* Also extract the PathTarget form of the setop result tlist */
+ final_target = current_rel->cheapest_total_path->pathtarget;
+
/*
* Can't handle FOR [KEY] UPDATE/SHARE here (parser should have
* checked already, but let's make sure).
*************** grouping_planner(PlannerInfo *root, bool
*** 1461,1467 ****
else
{
/* No set operations, do regular planning */
! PathTarget *final_target;
PathTarget *grouping_target;
PathTarget *scanjoin_target;
bool have_grouping;
--- 1468,1474 ----
else
{
/* No set operations, do regular planning */
! PathTarget *sort_input_target;
PathTarget *grouping_target;
PathTarget *scanjoin_target;
bool have_grouping;
*************** grouping_planner(PlannerInfo *root, bool
*** 1657,1678 ****
final_target = create_pathtarget(root, tlist);
/*
* If we have window functions to deal with, the output from any
* grouping step needs to be what the window functions want;
! * otherwise, it should just be final_target.
*/
if (activeWindows)
grouping_target = make_window_input_target(root,
tlist,
activeWindows);
else
! grouping_target = final_target;
/*
* If we have grouping or aggregation to do, the topmost scan/join
! * plan node must emit what the grouping step wants; otherwise, if
! * there's window functions, it must emit what the window functions
! * want; otherwise, it should emit final_target.
*/
have_grouping = (parse->groupClause || parse->groupingSets ||
parse->hasAggs || root->hasHavingQual);
--- 1664,1694 ----
final_target = create_pathtarget(root, tlist);
/*
+ * If ORDER BY was given, consider whether we should use a post-sort
+ * projection, and compute the adjusted target for preceding steps if
+ * so.
+ */
+ if (parse->sortClause)
+ sort_input_target = make_sort_input_target(root, final_target);
+ else
+ sort_input_target = final_target;
+
+ /*
* If we have window functions to deal with, the output from any
* grouping step needs to be what the window functions want;
! * otherwise, it should be sort_input_target.
*/
if (activeWindows)
grouping_target = make_window_input_target(root,
tlist,
activeWindows);
else
! grouping_target = sort_input_target;
/*
* If we have grouping or aggregation to do, the topmost scan/join
! * plan node must emit what the grouping step wants; otherwise, it
! * should emit grouping_target.
*/
have_grouping = (parse->groupClause || parse->groupingSets ||
parse->hasAggs || root->hasHavingQual);
*************** grouping_planner(PlannerInfo *root, bool
*** 1733,1739 ****
current_rel = create_window_paths(root,
current_rel,
grouping_target,
! final_target,
tlist,
wflists,
activeWindows);
--- 1749,1755 ----
current_rel = create_window_paths(root,
current_rel,
grouping_target,
! sort_input_target,
tlist,
wflists,
activeWindows);
*************** grouping_planner(PlannerInfo *root, bool
*** 1793,1798 ****
--- 1809,1815 ----
{
current_rel = create_ordered_paths(root,
current_rel,
+ final_target,
limit_tuples);
}
*************** create_distinct_paths(PlannerInfo *root,
*** 3704,3715 ****
--- 3721,3734 ----
* cheapest-total existing path.
*
* input_rel: contains the source-data Paths
+ * target: the output tlist the result Paths must emit
* limit_tuples: estimated bound on the number of output tuples,
* or -1 if no LIMIT or couldn't estimate
*/
static RelOptInfo *
create_ordered_paths(PlannerInfo *root,
RelOptInfo *input_rel,
+ PathTarget *target,
double limit_tuples)
{
Path *cheapest_input_path = input_rel->cheapest_total_path;
*************** create_ordered_paths(PlannerInfo *root,
*** 3737,3742 ****
--- 3756,3767 ----
root->sort_pathkeys,
limit_tuples);
}
+
+ /* Add projection step if needed */
+ if (path->pathtarget != target)
+ path = apply_projection_to_path(root, ordered_rel,
+ path, target);
+
add_path(ordered_rel, path);
}
}
*************** make_pathkeys_for_window(PlannerInfo *ro
*** 4140,4145 ****
--- 4165,4357 ----
}
/*
+ * make_sort_input_target
+ * Generate appropriate PathTarget for initial input to Sort step.
+ *
+ * If the query has ORDER BY, this function chooses the target list to be
+ * computed by the node just below the Sort (and Distinct, if any) steps.
+ * This might or might not be identical to the query's final output tlist.
+ *
+ * The main argument for keeping the sort-input tlist the same as the final
+ * is that we avoid a separate projection node (which will be needed if
+ * they're different, because Sort can't project). However, there are also
+ * advantages to postponing tlist evaluation till after the Sort: it ensures
+ * a consistent order of evaluation for any volatile functions in the tlist,
+ * and if there's also a LIMIT, we can stop the query without ever computing
+ * tlist functions for later rows, which is beneficial for both volatile and
+ * expensive functions.
+ *
+ * Our current policy is to postpone volatile expressions till after the sort
+ * unconditionally (assuming that that's possible, ie they are in plain tlist
+ * columns and not ORDER/GROUP BY/DISTINCT columns). Expensive expressions
+ * are postponed if there is a LIMIT, or if root->tuple_fraction shows that
+ * partial evaluation of the query is possible (if neither is true, we expect
+ * to have to evaluate the expressions for every row anyway), or if there are
+ * any volatile expressions (since once we've put in a projection at all,
+ * it won't cost any more to postpone more stuff).
+ *
+ * Another issue that could potentially be considered here is that
+ * evaluating tlist expressions could result in data that's either wider
+ * or narrower than the input Vars, thus changing the volume of data that
+ * has to go through the Sort. However, we usually have only a very bad
+ * idea of the output width of any expression more complex than a Var,
+ * so for now it seems too risky to try to optimize on that basis.
+ *
+ * Note that if we do produce a modified sort-input target, and then the
+ * query ends up not using an explicit Sort, no particular harm is done:
+ * we'll initially use the modified target for the preceding path nodes,
+ * but then change them to the final target with apply_projection_to_path.
+ * Moreover, in such a case the guarantees about evaluation order of
+ * volatile functions still hold, since the rows are sorted already.
+ *
+ * This function has some things in common with make_group_input_target and
+ * make_window_input_target, though the detailed rules for what to do are
+ * different. We never flatten/postpone any grouping or ordering columns;
+ * those are needed before the sort. If we do flatten a particular
+ * expression, we leave Aggref and WindowFunc nodes alone, since those were
+ * computed earlier.
+ *
+ * 'final_target' is the query's final target list (in PathTarget form)
+ *
+ * The result is the PathTarget to be computed by the plan node immediately
+ * below the Sort step (and the Distinct step, if any). This will be
+ * exactly final_target if we decide a projection step wouldn't be helpful.
+ */
+ static PathTarget *
+ make_sort_input_target(PlannerInfo *root,
+ PathTarget *final_target)
+ {
+ Query *parse = root->parse;
+ PathTarget *input_target;
+ int ncols;
+ bool *postpone_col;
+ bool have_volatile;
+ bool have_expensive;
+ List *flattenable_cols;
+ List *flattenable_vars;
+ int i;
+ ListCell *lc;
+
+ /* Shouldn't get here unless query has ORDER BY */
+ Assert(parse->sortClause);
+
+ /* Inspect tlist and collect per-column information */
+ ncols = list_length(final_target->exprs);
+ postpone_col = (bool *) palloc0(ncols * sizeof(bool));
+ have_volatile = have_expensive = false;
+
+ i = 0;
+ foreach(lc, final_target->exprs)
+ {
+ Expr *expr = (Expr *) lfirst(lc);
+
+ /*
+ * If the column has a sortgroupref, assume it has to be evaluated
+ * before sorting. Generally such columns would be ORDER BY, GROUP
+ * BY, etc targets. One exception is columns that were removed from
+ * GROUP BY by remove_useless_groupby_columns() ... but those would
+ * only be Vars anyway.
+ */
+ if (final_target->sortgrouprefs[i] == 0)
+ {
+ /*
+ * If it's volatile, that's an unconditional reason to postpone.
+ */
+ if (contain_volatile_functions((Node *) expr))
+ {
+ postpone_col[i] = true;
+ have_volatile = true;
+ }
+ else
+ {
+ /*
+ * Else check the cost. XXX it's annoying to have to do this
+ * when set_pathtarget_cost_width() just did it. Refactor to
+ * allow sharing the work?
+ */
+ QualCost cost;
+
+ cost_qual_eval_node(&cost, (Node *) expr, root);
+
+ /*
+ * We arbitrarily define "expensive" as "more than 10X
+ * cpu_operator_cost". Note this will take in any PL function
+ * with default cost.
+ */
+ if (cost.per_tuple >= 10 * cpu_operator_cost)
+ {
+ postpone_col[i] = true;
+ have_expensive = true;
+ }
+ }
+ }
+ i++;
+ }
+
+ /*
+ * If we don't need a post-sort projection, just return final_target.
+ */
+ if (!(have_volatile ||
+ (have_expensive &&
+ (parse->limitCount || root->tuple_fraction > 0))))
+ return final_target;
+
+ /*
+ * Otherwise, construct the sort-input target, taking all non-postponable
+ * columns and then adding Vars, PlaceHolderVars, Aggrefs, and WindowFuncs
+ * found in the postponable ones. XXX define a create_empty_pathtarget()
+ */
+ input_target = palloc0(sizeof(PathTarget));
+ flattenable_cols = NIL;
+
+ i = 0;
+ foreach(lc, final_target->exprs)
+ {
+ Expr *expr = (Expr *) lfirst(lc);
+
+ if (postpone_col[i])
+ {
+ flattenable_cols = lappend(flattenable_cols, expr);
+ }
+ else
+ {
+ add_column_to_pathtarget(input_target, expr,
+ final_target->sortgrouprefs[i]);
+ }
+ i++;
+ }
+
+ /*
+ * Pull out all the Vars and Aggrefs mentioned in flattenable columns, and
+ * add them to the result tlist if not already present. (Some might be
+ * there already because they're used directly as window/group clauses.)
+ *
+ * Note: it's essential to use PVC_INCLUDE_AGGREGATES here, so that the
+ * Aggrefs are placed in the Agg node's tlist and not left to be computed
+ * at higher levels.
+ *
+ * XXX need to extend pull_var_clause to handle windowfuncs specially.
+ */
+ flattenable_vars = pull_var_clause((Node *) flattenable_cols,
+ PVC_INCLUDE_AGGREGATES,
+ PVC_INCLUDE_PLACEHOLDERS);
+ foreach(lc, flattenable_vars)
+ {
+ Expr *expr = (Expr *) lfirst(lc);
+
+ if (!list_member(input_target->exprs, expr))
+ add_column_to_pathtarget(input_target, expr, 0);
+ }
+
+ /* clean up cruft */
+ list_free(flattenable_vars);
+ list_free(flattenable_cols);
+
+ /* XXX this represents even more redundant cost calculation ... */
+ return set_pathtarget_cost_width(root, input_target);
+ }
+
+ /*
* get_cheapest_fractional_path
* Find the cheapest path for retrieving a specified fraction of all
* the tuples expected to be returned by the given relation.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
