Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pathkeys.c
4 : : * Utilities for matching and building path keys
5 : : *
6 : : * See src/backend/optimizer/README for a great deal of information about
7 : : * the nature and use of path keys.
8 : : *
9 : : *
10 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
11 : : * Portions Copyright (c) 1994, Regents of the University of California
12 : : *
13 : : * IDENTIFICATION
14 : : * src/backend/optimizer/path/pathkeys.c
15 : : *
16 : : *-------------------------------------------------------------------------
17 : : */
18 : : #include "postgres.h"
19 : :
20 : : #include "access/stratnum.h"
21 : : #include "catalog/pg_opfamily.h"
22 : : #include "nodes/nodeFuncs.h"
23 : : #include "optimizer/cost.h"
24 : : #include "optimizer/optimizer.h"
25 : : #include "optimizer/pathnode.h"
26 : : #include "optimizer/paths.h"
27 : : #include "partitioning/partbounds.h"
28 : : #include "rewrite/rewriteManip.h"
29 : : #include "utils/lsyscache.h"
30 : :
31 : : /* Consider reordering of GROUP BY keys? */
32 : : bool enable_group_by_reordering = true;
33 : :
34 : : static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
35 : : static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
36 : : RelOptInfo *partrel,
37 : : int partkeycol);
38 : : static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
39 : : static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
40 : :
41 : :
42 : : /****************************************************************************
43 : : * PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
44 : : ****************************************************************************/
45 : :
46 : : /*
47 : : * make_canonical_pathkey
48 : : * Given the parameters for a PathKey, find any pre-existing matching
49 : : * pathkey in the query's list of "canonical" pathkeys. Make a new
50 : : * entry if there's not one already.
51 : : *
52 : : * Note that this function must not be used until after we have completed
53 : : * merging EquivalenceClasses.
54 : : */
55 : : PathKey *
6804 tgl@sss.pgh.pa.us 56 :CBC 1089597 : make_canonical_pathkey(PlannerInfo *root,
57 : : EquivalenceClass *eclass, Oid opfamily,
58 : : CompareType cmptype, bool nulls_first)
59 : : {
60 : : PathKey *pk;
61 : : ListCell *lc;
62 : : MemoryContext oldcontext;
63 : :
64 : : /* Can't make canonical pathkeys if the set of ECs might still change */
2239 drowley@postgresql.o 65 [ - + ]: 1089597 : if (!root->ec_merging_done)
2239 drowley@postgresql.o 66 [ # # ]:UBC 0 : elog(ERROR, "too soon to build canonical pathkeys");
67 : :
68 : : /* The passed eclass might be non-canonical, so chase up to the top */
6804 tgl@sss.pgh.pa.us 69 [ - + ]:CBC 1089597 : while (eclass->ec_merged)
6804 tgl@sss.pgh.pa.us 70 :UBC 0 : eclass = eclass->ec_merged;
71 : :
6804 tgl@sss.pgh.pa.us 72 [ + + + + :CBC 5728304 : foreach(lc, root->canon_pathkeys)
+ + ]
73 : : {
74 : 5403089 : pk = (PathKey *) lfirst(lc);
75 [ + + ]: 5403089 : if (eclass == pk->pk_eclass &&
76 [ + - ]: 1020520 : opfamily == pk->pk_opfamily &&
155 peter@eisentraut.org 77 [ + + ]: 1020520 : cmptype == pk->pk_cmptype &&
6804 tgl@sss.pgh.pa.us 78 [ + + ]: 764412 : nulls_first == pk->pk_nulls_first)
79 : 764382 : return pk;
80 : : }
81 : :
82 : : /*
83 : : * Be sure canonical pathkeys are allocated in the main planning context.
84 : : * Not an issue in normal planning, but it is for GEQO.
85 : : */
86 : 325215 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
87 : :
4513 88 : 325215 : pk = makeNode(PathKey);
89 : 325215 : pk->pk_eclass = eclass;
90 : 325215 : pk->pk_opfamily = opfamily;
155 peter@eisentraut.org 91 : 325215 : pk->pk_cmptype = cmptype;
4513 tgl@sss.pgh.pa.us 92 : 325215 : pk->pk_nulls_first = nulls_first;
93 : :
6804 94 : 325215 : root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
95 : :
96 : 325215 : MemoryContextSwitchTo(oldcontext);
97 : :
98 : 325215 : return pk;
99 : : }
100 : :
101 : : /*
102 : : * append_pathkeys
103 : : * Append all non-redundant PathKeys in 'source' onto 'target' and
104 : : * returns the updated 'target' list.
105 : : */
106 : : List *
1131 drowley@postgresql.o 107 : 749 : append_pathkeys(List *target, List *source)
108 : : {
109 : : ListCell *lc;
110 : :
111 [ - + ]: 749 : Assert(target != NIL);
112 : :
113 [ + - + + : 1531 : foreach(lc, source)
+ + ]
114 : : {
115 : 782 : PathKey *pk = lfirst_node(PathKey, lc);
116 : :
117 [ + + ]: 782 : if (!pathkey_is_redundant(pk, target))
118 : 695 : target = lappend(target, pk);
119 : : }
120 : 749 : return target;
121 : : }
122 : :
123 : : /*
124 : : * pathkey_is_redundant
125 : : * Is a pathkey redundant with one already in the given list?
126 : : *
127 : : * We detect two cases:
128 : : *
129 : : * 1. If the new pathkey's equivalence class contains a constant, and isn't
130 : : * below an outer join, then we can disregard it as a sort key. An example:
131 : : * SELECT ... WHERE x = 42 ORDER BY x, y;
132 : : * We may as well just sort by y. Note that because of opfamily matching,
133 : : * this is semantically correct: we know that the equality constraint is one
134 : : * that actually binds the variable to a single value in the terms of any
135 : : * ordering operator that might go with the eclass. This rule not only lets
136 : : * us simplify (or even skip) explicit sorts, but also allows matching index
137 : : * sort orders to a query when there are don't-care index columns.
138 : : *
139 : : * 2. If the new pathkey's equivalence class is the same as that of any
140 : : * existing member of the pathkey list, then it is redundant. Some examples:
141 : : * SELECT ... ORDER BY x, x;
142 : : * SELECT ... ORDER BY x, x DESC;
143 : : * SELECT ... WHERE x = y ORDER BY x, y;
144 : : * In all these cases the second sort key cannot distinguish values that are
145 : : * considered equal by the first, and so there's no point in using it.
146 : : * Note in particular that we need not compare opfamily (all the opfamilies
147 : : * of the EC have the same notion of equality) nor sort direction.
148 : : *
149 : : * Both the given pathkey and the list members must be canonical for this
150 : : * to work properly, but that's okay since we no longer ever construct any
151 : : * non-canonical pathkeys. (Note: the notion of a pathkey *list* being
152 : : * canonical includes the additional requirement of no redundant entries,
153 : : * which is exactly what we are checking for here.)
154 : : *
155 : : * Because the equivclass.c machinery forms only one copy of any EC per query,
156 : : * pointer comparison is enough to decide whether canonical ECs are the same.
157 : : */
158 : : static bool
6505 bruce@momjian.us 159 : 1443491 : pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
160 : : {
6804 tgl@sss.pgh.pa.us 161 : 1443491 : EquivalenceClass *new_ec = new_pathkey->pk_eclass;
162 : : ListCell *lc;
163 : :
164 : : /* Check for EC containing a constant --- unconditionally redundant */
6450 165 [ + + ]: 1443491 : if (EC_MUST_BE_REDUNDANT(new_ec))
6804 166 : 162204 : return true;
167 : :
168 : : /* If same EC already used in list, then redundant */
169 [ + + + + : 1521110 : foreach(lc, pathkeys)
+ + ]
170 : : {
6505 bruce@momjian.us 171 : 240224 : PathKey *old_pathkey = (PathKey *) lfirst(lc);
172 : :
6804 tgl@sss.pgh.pa.us 173 [ + + ]: 240224 : if (new_ec == old_pathkey->pk_eclass)
174 : 401 : return true;
175 : : }
176 : :
8261 177 : 1280886 : return false;
178 : : }
179 : :
180 : : /*
181 : : * make_pathkey_from_sortinfo
182 : : * Given an expression and sort-order information, create a PathKey.
183 : : * The result is always a "canonical" PathKey, but it might be redundant.
184 : : *
185 : : * If the PathKey is being generated from a SortGroupClause, sortref should be
186 : : * the SortGroupClause's SortGroupRef; otherwise zero.
187 : : *
188 : : * If rel is not NULL, it identifies a specific relation we're considering
189 : : * a path for, and indicates that child EC members for that relation can be
190 : : * considered. Otherwise child members are ignored. (See the comments for
191 : : * get_eclass_for_sort_expr.)
192 : : *
193 : : * create_it is true if we should create any missing EquivalenceClass
194 : : * needed to represent the sort key. If it's false, we return NULL if the
195 : : * sort key isn't already present in any EquivalenceClass.
196 : : */
197 : : static PathKey *
6804 198 : 925176 : make_pathkey_from_sortinfo(PlannerInfo *root,
199 : : Expr *expr,
200 : : Oid opfamily,
201 : : Oid opcintype,
202 : : Oid collation,
203 : : bool reverse_sort,
204 : : bool nulls_first,
205 : : Index sortref,
206 : : Relids rel,
207 : : bool create_it)
208 : : {
209 : : CompareType cmptype;
210 : : Oid equality_op;
211 : : List *opfamilies;
212 : : EquivalenceClass *eclass;
213 : :
155 peter@eisentraut.org 214 [ + + ]: 925176 : cmptype = reverse_sort ? COMPARE_GT : COMPARE_LT;
215 : :
216 : : /*
217 : : * EquivalenceClasses need to contain opfamily lists based on the family
218 : : * membership of mergejoinable equality operators, which could belong to
219 : : * more than one opfamily. So we have to look up the opfamily's equality
220 : : * operator and get its membership.
221 : : */
153 222 : 925176 : equality_op = get_opfamily_member_for_cmptype(opfamily,
223 : : opcintype,
224 : : opcintype,
225 : : COMPARE_EQ);
2999 tgl@sss.pgh.pa.us 226 [ - + ]: 925176 : if (!OidIsValid(equality_op)) /* shouldn't happen */
2966 tgl@sss.pgh.pa.us 227 [ # # ]:UBC 0 : elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
228 : : COMPARE_EQ, opcintype, opcintype, opfamily);
6804 tgl@sss.pgh.pa.us 229 :CBC 925176 : opfamilies = get_mergejoin_opfamilies(equality_op);
230 [ - + ]: 925176 : if (!opfamilies) /* certainly should find some */
5395 tgl@sss.pgh.pa.us 231 [ # # ]:UBC 0 : elog(ERROR, "could not find opfamilies for equality operator %u",
232 : : equality_op);
233 : :
234 : : /* Now find or (optionally) create a matching EquivalenceClass */
950 tgl@sss.pgh.pa.us 235 :CBC 925176 : eclass = get_eclass_for_sort_expr(root, expr,
236 : : opfamilies, opcintype, collation,
237 : : sortref, rel, create_it);
238 : :
239 : : /* Fail if no EC and !create_it */
5426 240 [ + + ]: 925176 : if (!eclass)
241 : 317236 : return NULL;
242 : :
243 : : /* And finally we can find or create a PathKey node */
4513 244 : 607940 : return make_canonical_pathkey(root, eclass, opfamily,
245 : : cmptype, nulls_first);
246 : : }
247 : :
248 : : /*
249 : : * make_pathkey_from_sortop
250 : : * Like make_pathkey_from_sortinfo, but work from a sort operator.
251 : : *
252 : : * This should eventually go away, but we need to restructure SortGroupClause
253 : : * first.
254 : : */
255 : : static PathKey *
5395 256 : 95760 : make_pathkey_from_sortop(PlannerInfo *root,
257 : : Expr *expr,
258 : : Oid ordering_op,
259 : : bool reverse_sort,
260 : : bool nulls_first,
261 : : Index sortref,
262 : : bool create_it)
263 : : {
264 : : Oid opfamily,
265 : : opcintype,
266 : : collation;
267 : : CompareType cmptype;
268 : :
269 : : /* Find the operator in pg_amop --- failure shouldn't happen */
270 [ - + ]: 95760 : if (!get_ordering_op_properties(ordering_op,
271 : : &opfamily, &opcintype, &cmptype))
5395 tgl@sss.pgh.pa.us 272 [ # # ]:UBC 0 : elog(ERROR, "operator %u is not a valid ordering operator",
273 : : ordering_op);
274 : :
275 : : /* Because SortGroupClause doesn't carry collation, consult the expr */
5285 tgl@sss.pgh.pa.us 276 :CBC 95760 : collation = exprCollation((Node *) expr);
277 : :
5395 278 : 95760 : return make_pathkey_from_sortinfo(root,
279 : : expr,
280 : : opfamily,
281 : : opcintype,
282 : : collation,
283 : : reverse_sort,
284 : : nulls_first,
285 : : sortref,
286 : : NULL,
287 : : create_it);
288 : : }
289 : :
290 : :
291 : : /****************************************************************************
292 : : * PATHKEY COMPARISONS
293 : : ****************************************************************************/
294 : :
295 : : /*
296 : : * compare_pathkeys
297 : : * Compare two pathkeys to see if they are equivalent, and if not whether
298 : : * one is "better" than the other.
299 : : *
300 : : * We assume the pathkeys are canonical, and so they can be checked for
301 : : * equality by simple pointer comparison.
302 : : */
303 : : PathKeysComparison
9518 304 : 6433744 : compare_pathkeys(List *keys1, List *keys2)
305 : : {
306 : : ListCell *key1,
307 : : *key2;
308 : :
309 : : /*
310 : : * Fall out quickly if we are passed two identical lists. This mostly
311 : : * catches the case where both are NIL, but that's common enough to
312 : : * warrant the test.
313 : : */
6034 314 [ + + ]: 6433744 : if (keys1 == keys2)
315 : 2245024 : return PATHKEYS_EQUAL;
316 : :
7773 neilc@samurai.com 317 [ + + + + : 5081296 : forboth(key1, keys1, key2, keys2)
+ + + + +
+ + + +
+ ]
318 : : {
6505 bruce@momjian.us 319 : 1317513 : PathKey *pathkey1 = (PathKey *) lfirst(key1);
320 : 1317513 : PathKey *pathkey2 = (PathKey *) lfirst(key2);
321 : :
6804 tgl@sss.pgh.pa.us 322 [ + + ]: 1317513 : if (pathkey1 != pathkey2)
9032 323 : 424937 : return PATHKEYS_DIFFERENT; /* no need to keep looking */
324 : : }
325 : :
326 : : /*
327 : : * If we reached the end of only one list, the other is longer and
328 : : * therefore not a subset.
329 : : */
7773 neilc@samurai.com 330 [ + + ]: 3763783 : if (key1 != NULL)
8714 bruce@momjian.us 331 : 2742680 : return PATHKEYS_BETTER1; /* key1 is longer */
6034 tgl@sss.pgh.pa.us 332 [ + + ]: 1021103 : if (key2 != NULL)
333 : 338062 : return PATHKEYS_BETTER2; /* key2 is longer */
334 : 683041 : return PATHKEYS_EQUAL;
335 : : }
336 : :
337 : : /*
338 : : * pathkeys_contained_in
339 : : * Common special case of compare_pathkeys: we just want to know
340 : : * if keys2 are at least as well sorted as keys1.
341 : : */
342 : : bool
9518 343 : 2555106 : pathkeys_contained_in(List *keys1, List *keys2)
344 : : {
345 [ + + ]: 2555106 : switch (compare_pathkeys(keys1, keys2))
346 : : {
8717 bruce@momjian.us 347 : 502746 : case PATHKEYS_EQUAL:
348 : : case PATHKEYS_BETTER2:
9518 tgl@sss.pgh.pa.us 349 : 502746 : return true;
350 : 2052360 : default:
351 : 2052360 : break;
352 : : }
353 : 2052360 : return false;
354 : : }
355 : :
356 : : /*
357 : : * group_keys_reorder_by_pathkeys
358 : : * Reorder GROUP BY pathkeys and clauses to match the input pathkeys.
359 : : *
360 : : * 'pathkeys' is an input list of pathkeys
361 : : * '*group_pathkeys' and '*group_clauses' are pathkeys and clauses lists to
362 : : * reorder. The pointers are redirected to new lists, original lists
363 : : * stay untouched.
364 : : * 'num_groupby_pathkeys' is the number of first '*group_pathkeys' items to
365 : : * search matching pathkeys.
366 : : *
367 : : * Returns the number of GROUP BY keys with a matching pathkey.
368 : : */
369 : : static int
594 akorotkov@postgresql 370 : 82 : group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys,
371 : : List **group_clauses,
372 : : int num_groupby_pathkeys)
373 : : {
374 : 82 : List *new_group_pathkeys = NIL,
375 : 82 : *new_group_clauses = NIL;
376 : : List *grouping_pathkeys;
377 : : ListCell *lc;
378 : : int n;
379 : :
380 [ + - - + ]: 82 : if (pathkeys == NIL || *group_pathkeys == NIL)
594 akorotkov@postgresql 381 :UBC 0 : return 0;
382 : :
383 : : /*
384 : : * We're going to search within just the first num_groupby_pathkeys of
385 : : * *group_pathkeys. The thing is that root->group_pathkeys is passed as
386 : : * *group_pathkeys containing grouping pathkeys altogether with aggregate
387 : : * pathkeys. If we process aggregate pathkeys we could get an invalid
388 : : * result of get_sortgroupref_clause_noerr(), because their
389 : : * pathkey->pk_eclass->ec_sortref doesn't reference query targetlist. So,
390 : : * we allocate a separate list of pathkeys for lookups.
391 : : */
575 akorotkov@postgresql 392 :CBC 82 : grouping_pathkeys = list_copy_head(*group_pathkeys, num_groupby_pathkeys);
393 : :
394 : : /*
395 : : * Walk the pathkeys (determining ordering of the input path) and see if
396 : : * there's a matching GROUP BY key. If we find one, we append it to the
397 : : * list, and do the same for the clauses.
398 : : *
399 : : * Once we find the first pathkey without a matching GROUP BY key, the
400 : : * rest of the pathkeys are useless and can't be used to evaluate the
401 : : * grouping, so we abort the loop and ignore the remaining pathkeys.
402 : : */
594 403 [ + - + + : 199 : foreach(lc, pathkeys)
+ + ]
404 : : {
405 : 130 : PathKey *pathkey = (PathKey *) lfirst(lc);
406 : : SortGroupClause *sgc;
407 : :
408 : : /*
409 : : * Pathkeys are built in a way that allows simply comparing pointers.
410 : : * Give up if we can't find the matching pointer. Also give up if
411 : : * there is no sortclause reference for some reason.
412 : : */
413 [ + + ]: 130 : if (foreach_current_index(lc) >= num_groupby_pathkeys ||
575 414 [ + + ]: 127 : !list_member_ptr(grouping_pathkeys, pathkey) ||
594 415 [ + - ]: 117 : pathkey->pk_eclass->ec_sortref == 0)
416 : : break;
417 : :
418 : : /*
419 : : * Since 1349d27 pathkey coming from underlying node can be in the
420 : : * root->group_pathkeys but not in the processed_groupClause. So, we
421 : : * should be careful here.
422 : : */
423 : 117 : sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
424 : : *group_clauses);
425 [ - + ]: 117 : if (!sgc)
426 : : /* The grouping clause does not cover this pathkey */
594 akorotkov@postgresql 427 :UBC 0 : break;
428 : :
429 : : /*
430 : : * Sort group clause should have an ordering operator as long as there
431 : : * is an associated pathkey.
432 : : */
594 akorotkov@postgresql 433 [ - + ]:CBC 117 : Assert(OidIsValid(sgc->sortop));
434 : :
435 : 117 : new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
436 : 117 : new_group_clauses = lappend(new_group_clauses, sgc);
437 : : }
438 : :
439 : : /* remember the number of pathkeys with a matching GROUP BY key */
440 : 82 : n = list_length(new_group_pathkeys);
441 : :
442 : : /* append the remaining group pathkeys (will be treated as not sorted) */
443 : 82 : *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
444 : : *group_pathkeys);
445 : 82 : *group_clauses = list_concat_unique_ptr(new_group_clauses,
446 : : *group_clauses);
447 : :
575 448 : 82 : list_free(grouping_pathkeys);
594 449 : 82 : return n;
450 : : }
451 : :
452 : : /*
453 : : * get_useful_group_keys_orderings
454 : : * Determine which orderings of GROUP BY keys are potentially interesting.
455 : : *
456 : : * Returns a list of GroupByOrdering items, each representing an interesting
457 : : * ordering of GROUP BY keys. Each item stores pathkeys and clauses in the
458 : : * matching order.
459 : : *
460 : : * The function considers (and keeps) following GROUP BY orderings:
461 : : *
462 : : * - GROUP BY keys as ordered by preprocess_groupclause() to match target
463 : : * ORDER BY clause (as much as possible),
464 : : * - GROUP BY keys reordered to match 'path' ordering (as much as possible).
465 : : */
466 : : List *
467 : 22623 : get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
468 : : {
469 : 22623 : Query *parse = root->parse;
470 : 22623 : List *infos = NIL;
471 : : GroupByOrdering *info;
472 : :
473 : 22623 : List *pathkeys = root->group_pathkeys;
474 : 22623 : List *clauses = root->processed_groupClause;
475 : :
476 : : /* always return at least the original pathkeys/clauses */
457 477 : 22623 : info = makeNode(GroupByOrdering);
594 478 : 22623 : info->pathkeys = pathkeys;
479 : 22623 : info->clauses = clauses;
480 : 22623 : infos = lappend(infos, info);
481 : :
482 : : /*
483 : : * Should we try generating alternative orderings of the group keys? If
484 : : * not, we produce only the order specified in the query, i.e. the
485 : : * optimization is effectively disabled.
486 : : */
487 [ - + ]: 22623 : if (!enable_group_by_reordering)
594 akorotkov@postgresql 488 :UBC 0 : return infos;
489 : :
490 : : /*
491 : : * Grouping sets have own and more complex logic to decide the ordering.
492 : : */
594 akorotkov@postgresql 493 [ + + ]:CBC 22623 : if (parse->groupingSets)
494 : 472 : return infos;
495 : :
496 : : /*
497 : : * If the path is sorted in some way, try reordering the group keys to
498 : : * match the path as much of the ordering as possible. Then thanks to
499 : : * incremental sort we would get this sort as cheap as possible.
500 : : */
501 [ + + ]: 22151 : if (path->pathkeys &&
502 [ + + ]: 1897 : !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
503 : : {
504 : : int n;
505 : :
506 : 82 : n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
507 : : root->num_groupby_pathkeys);
508 : :
509 [ + + ]: 82 : if (n > 0 &&
510 [ - + - - : 144 : (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
+ - ]
457 511 : 72 : compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
512 : : {
513 : 72 : info = makeNode(GroupByOrdering);
594 514 : 72 : info->pathkeys = pathkeys;
515 : 72 : info->clauses = clauses;
516 : :
517 : 72 : infos = lappend(infos, info);
518 : : }
519 : : }
520 : :
521 : : #ifdef USE_ASSERT_CHECKING
522 : : {
457 523 : 22151 : GroupByOrdering *pinfo = linitial_node(GroupByOrdering, infos);
524 : : ListCell *lc;
525 : :
526 : : /* Test consistency of info structures */
527 [ + - + + : 22223 : for_each_from(lc, infos, 1)
+ + ]
528 : : {
529 : : ListCell *lc1,
530 : : *lc2;
531 : :
532 : 72 : info = lfirst_node(GroupByOrdering, lc);
533 : :
534 [ - + ]: 72 : Assert(list_length(info->clauses) == list_length(pinfo->clauses));
535 [ - + ]: 72 : Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
536 [ - + ]: 72 : Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
537 [ - + ]: 72 : Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == NIL);
538 : :
539 [ + - + + : 249 : forboth(lc1, info->clauses, lc2, info->pathkeys)
+ - + + +
+ + - +
+ ]
540 : : {
541 : 177 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc1);
542 : 177 : PathKey *pk = lfirst_node(PathKey, lc2);
543 : :
544 [ - + ]: 177 : Assert(pk->pk_eclass->ec_sortref == sgc->tleSortGroupRef);
545 : : }
546 : : }
547 : : }
548 : : #endif
594 549 : 22151 : return infos;
550 : : }
551 : :
552 : : /*
553 : : * pathkeys_count_contained_in
554 : : * Same as pathkeys_contained_in, but also sets length of longest
555 : : * common prefix of keys1 and keys2.
556 : : */
557 : : bool
1979 tomas.vondra@postgre 558 : 3195496 : pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
559 : : {
560 : 3195496 : int n = 0;
561 : : ListCell *key1,
562 : : *key2;
563 : :
564 : : /*
565 : : * See if we can avoiding looping through both lists. This optimization
566 : : * gains us several percent in planning time in a worst-case test.
567 : : */
568 [ + + ]: 3195496 : if (keys1 == keys2)
569 : : {
570 : 762504 : *n_common = list_length(keys1);
571 : 762504 : return true;
572 : : }
573 [ + + ]: 2432992 : else if (keys1 == NIL)
574 : : {
575 : 946210 : *n_common = 0;
576 : 946210 : return true;
577 : : }
578 [ + + ]: 1486782 : else if (keys2 == NIL)
579 : : {
580 : 740433 : *n_common = 0;
581 : 740433 : return false;
582 : : }
583 : :
584 : : /*
585 : : * If both lists are non-empty, iterate through both to find out how many
586 : : * items are shared.
587 : : */
588 [ + - + + : 960247 : forboth(key1, keys1, key2, keys2)
+ - + + +
+ + + +
+ ]
589 : : {
590 : 767636 : PathKey *pathkey1 = (PathKey *) lfirst(key1);
591 : 767636 : PathKey *pathkey2 = (PathKey *) lfirst(key2);
592 : :
593 [ + + ]: 767636 : if (pathkey1 != pathkey2)
594 : : {
595 : 553738 : *n_common = n;
596 : 553738 : return false;
597 : : }
598 : 213898 : n++;
599 : : }
600 : :
601 : : /* If we ended with a null value, then we've processed the whole list. */
602 : 192611 : *n_common = n;
603 : 192611 : return (key1 == NULL);
604 : : }
605 : :
606 : : /*
607 : : * get_cheapest_path_for_pathkeys
608 : : * Find the cheapest path (according to the specified criterion) that
609 : : * satisfies the given pathkeys and parameterization, and is parallel-safe
610 : : * if required.
611 : : * Return NULL if no such path.
612 : : *
613 : : * 'paths' is a list of possible paths that all generate the same relation
614 : : * 'pathkeys' represents a required ordering (in canonical form!)
615 : : * 'required_outer' denotes allowable outer relations for parameterized paths
616 : : * 'cost_criterion' is STARTUP_COST or TOTAL_COST
617 : : * 'require_parallel_safe' causes us to consider only parallel-safe paths
618 : : */
619 : : Path *
9513 tgl@sss.pgh.pa.us 620 : 437848 : get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
621 : : Relids required_outer,
622 : : CostSelector cost_criterion,
623 : : bool require_parallel_safe)
624 : : {
10225 bruce@momjian.us 625 : 437848 : Path *matched_path = NULL;
626 : : ListCell *l;
627 : :
7773 neilc@samurai.com 628 [ + - + + : 1581943 : foreach(l, paths)
+ + ]
629 : : {
630 : 1144095 : Path *path = (Path *) lfirst(l);
631 : :
632 : : /* If required, reject paths that are not parallel-safe */
730 rhaas@postgresql.org 633 [ + + + + ]: 1144095 : if (require_parallel_safe && !path->parallel_safe)
634 : 198 : continue;
635 : :
636 : : /*
637 : : * Since cost comparison is a lot cheaper than pathkey comparison, do
638 : : * that first. (XXX is that still true?)
639 : : */
9335 tgl@sss.pgh.pa.us 640 [ + + + + ]: 1201100 : if (matched_path != NULL &&
641 : 57203 : compare_path_costs(matched_path, path, cost_criterion) <= 0)
9513 642 : 46618 : continue;
643 : :
4971 644 [ + + + + ]: 1567368 : if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
4888 645 [ + + ]: 470089 : bms_is_subset(PATH_REQ_OUTER(path), required_outer))
9335 646 : 283747 : matched_path = path;
647 : : }
648 : 437848 : return matched_path;
649 : : }
650 : :
651 : : /*
652 : : * get_cheapest_fractional_path_for_pathkeys
653 : : * Find the cheapest path (for retrieving a specified fraction of all
654 : : * the tuples) that satisfies the given pathkeys and parameterization.
655 : : * Return NULL if no such path.
656 : : *
657 : : * See compare_fractional_path_costs() for the interpretation of the fraction
658 : : * parameter.
659 : : *
660 : : * 'paths' is a list of possible paths that all generate the same relation
661 : : * 'pathkeys' represents a required ordering (in canonical form!)
662 : : * 'required_outer' denotes allowable outer relations for parameterized paths
663 : : * 'fraction' is the fraction of the total tuples expected to be retrieved
664 : : */
665 : : Path *
666 : 963 : get_cheapest_fractional_path_for_pathkeys(List *paths,
667 : : List *pathkeys,
668 : : Relids required_outer,
669 : : double fraction)
670 : : {
671 : 963 : Path *matched_path = NULL;
672 : : ListCell *l;
673 : :
7773 neilc@samurai.com 674 [ + - + + : 2765 : foreach(l, paths)
+ + ]
675 : : {
676 : 1802 : Path *path = (Path *) lfirst(l);
677 : :
678 : : /*
679 : : * Since cost comparison is a lot cheaper than pathkey comparison, do
680 : : * that first. (XXX is that still true?)
681 : : */
9335 tgl@sss.pgh.pa.us 682 [ + + + + ]: 2041 : if (matched_path != NULL &&
7266 bruce@momjian.us 683 : 239 : compare_fractional_path_costs(matched_path, path, fraction) <= 0)
9335 tgl@sss.pgh.pa.us 684 : 122 : continue;
685 : :
4971 686 [ + + + + ]: 2439 : if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
4888 687 [ + + ]: 759 : bms_is_subset(PATH_REQ_OUTER(path), required_outer))
9335 688 : 661 : matched_path = path;
689 : : }
10226 bruce@momjian.us 690 : 963 : return matched_path;
691 : : }
692 : :
693 : :
694 : : /*
695 : : * get_cheapest_parallel_safe_total_inner
696 : : * Find the unparameterized parallel-safe path with the least total cost.
697 : : */
698 : : Path *
3105 rhaas@postgresql.org 699 : 28332 : get_cheapest_parallel_safe_total_inner(List *paths)
700 : : {
701 : : ListCell *l;
702 : :
703 [ + - + + : 31861 : foreach(l, paths)
+ + ]
704 : : {
705 : 31234 : Path *innerpath = (Path *) lfirst(l);
706 : :
707 [ + + ]: 31234 : if (innerpath->parallel_safe &&
708 [ + + - + ]: 30268 : bms_is_empty(PATH_REQ_OUTER(innerpath)))
709 : 27705 : return innerpath;
710 : : }
711 : :
712 : 627 : return NULL;
713 : : }
714 : :
715 : : /****************************************************************************
716 : : * NEW PATHKEY FORMATION
717 : : ****************************************************************************/
718 : :
719 : : /*
720 : : * build_index_pathkeys
721 : : * Build a pathkeys list that describes the ordering induced by an index
722 : : * scan using the given index. (Note that an unordered index doesn't
723 : : * induce any ordering, so we return NIL.)
724 : : *
725 : : * If 'scandir' is BackwardScanDirection, build pathkeys representing a
726 : : * backwards scan of the index.
727 : : *
728 : : * We iterate only key columns of covering indexes, since non-key columns
729 : : * don't influence index ordering. The result is canonical, meaning that
730 : : * redundant pathkeys are removed; it may therefore have fewer entries than
731 : : * there are key columns in the index.
732 : : *
733 : : * Another reason for stopping early is that we may be able to tell that
734 : : * an index column's sort order is uninteresting for this query. However,
735 : : * that test is just based on the existence of an EquivalenceClass and not
736 : : * on position in pathkey lists, so it's not complete. Caller should call
737 : : * truncate_useless_pathkeys() to possibly remove more pathkeys.
738 : : */
739 : : List *
7398 tgl@sss.pgh.pa.us 740 : 622796 : build_index_pathkeys(PlannerInfo *root,
741 : : IndexOptInfo *index,
742 : : ScanDirection scandir)
743 : : {
9518 744 : 622796 : List *retval = NIL;
745 : : ListCell *lc;
746 : : int i;
747 : :
5395 748 [ - + ]: 622796 : if (index->sortopfamily == NULL)
5395 tgl@sss.pgh.pa.us 749 :UBC 0 : return NIL; /* non-orderable index */
750 : :
5079 tgl@sss.pgh.pa.us 751 :CBC 622796 : i = 0;
752 [ + - + + : 1119030 : foreach(lc, index->indextlist)
+ + ]
753 : : {
754 : 804854 : TargetEntry *indextle = (TargetEntry *) lfirst(lc);
755 : : Expr *indexkey;
756 : : bool reverse_sort;
757 : : bool nulls_first;
758 : : PathKey *cpathkey;
759 : :
760 : : /*
761 : : * INCLUDE columns are stored in index unordered, so they don't
762 : : * support ordered index scan.
763 : : */
2709 teodor@sigaev.ru 764 [ - + ]: 804854 : if (i >= index->nkeycolumns)
2709 teodor@sigaev.ru 765 :UBC 0 : break;
766 : :
767 : : /* We assume we don't need to make a copy of the tlist item */
5079 tgl@sss.pgh.pa.us 768 :CBC 804854 : indexkey = indextle->expr;
769 : :
8304 770 [ + + ]: 804854 : if (ScanDirectionIsBackward(scandir))
771 : : {
5395 772 : 402427 : reverse_sort = !index->reverse_sort[i];
6815 773 : 402427 : nulls_first = !index->nulls_first[i];
774 : : }
775 : : else
776 : : {
5395 777 : 402427 : reverse_sort = index->reverse_sort[i];
6815 778 : 402427 : nulls_first = index->nulls_first[i];
779 : : }
780 : :
781 : : /*
782 : : * OK, try to make a canonical pathkey for this sort key.
783 : : */
6804 784 : 804854 : cpathkey = make_pathkey_from_sortinfo(root,
785 : : indexkey,
5395 786 : 804854 : index->sortopfamily[i],
787 : 804854 : index->opcintype[i],
5285 788 : 804854 : index->indexcollations[i],
789 : : reverse_sort,
790 : : nulls_first,
791 : : 0,
4922 792 : 804854 : index->rel->relids,
793 : : false);
794 : :
3156 795 [ + + ]: 804854 : if (cpathkey)
796 : : {
797 : : /*
798 : : * We found the sort key in an EquivalenceClass, so it's relevant
799 : : * for this query. Add it to list, unless it's redundant.
800 : : */
801 [ + + ]: 495614 : if (!pathkey_is_redundant(cpathkey, retval))
802 : 352126 : retval = lappend(retval, cpathkey);
803 : : }
804 : : else
805 : : {
806 : : /*
807 : : * Boolean index keys might be redundant even if they do not
808 : : * appear in an EquivalenceClass, because of our special treatment
809 : : * of boolean equality conditions --- see the comment for
810 : : * indexcol_is_bool_constant_for_query(). If that applies, we can
811 : : * continue to examine lower-order index columns. Otherwise, the
812 : : * sort key is not an interesting sort order for this query, so we
813 : : * should stop considering index columns; any lower-order sort
814 : : * keys won't be useful either.
815 : : */
1689 816 [ + + ]: 309240 : if (!indexcol_is_bool_constant_for_query(root, index, i))
3156 817 : 308620 : break;
818 : : }
819 : :
5079 820 : 496234 : i++;
821 : : }
822 : :
823 : 622796 : return retval;
824 : : }
825 : :
826 : : /*
827 : : * partkey_is_bool_constant_for_query
828 : : *
829 : : * If a partition key column is constrained to have a constant value by the
830 : : * query's WHERE conditions, then it's irrelevant for sort-order
831 : : * considerations. Usually that means we have a restriction clause
832 : : * WHERE partkeycol = constant, which gets turned into an EquivalenceClass
833 : : * containing a constant, which is recognized as redundant by
834 : : * build_partition_pathkeys(). But if the partition key column is a
835 : : * boolean variable (or expression), then we are not going to see such a
836 : : * WHERE clause, because expression preprocessing will have simplified it
837 : : * to "WHERE partkeycol" or "WHERE NOT partkeycol". So we are not going
838 : : * to have a matching EquivalenceClass (unless the query also contains
839 : : * "ORDER BY partkeycol"). To allow such cases to work the same as they would
840 : : * for non-boolean values, this function is provided to detect whether the
841 : : * specified partition key column matches a boolean restriction clause.
842 : : */
843 : : static bool
2346 844 : 7802 : partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
845 : : {
846 : 7802 : PartitionScheme partscheme = partrel->part_scheme;
847 : : ListCell *lc;
848 : :
849 : : /*
850 : : * If the partkey isn't boolean, we can't possibly get a match.
851 : : *
852 : : * Partitioning currently can only use built-in AMs, so checking for
853 : : * built-in boolean opfamilies is good enough.
854 : : */
1100 855 [ + + + - ]: 7802 : if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
2346 856 : 7562 : return false;
857 : :
858 : : /* Check each restriction clause for the partitioned rel */
859 [ + - + + : 396 : foreach(lc, partrel->baserestrictinfo)
+ + ]
860 : : {
861 : 276 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
862 : :
863 : : /* Ignore pseudoconstant quals, they won't match */
864 [ - + ]: 276 : if (rinfo->pseudoconstant)
2346 tgl@sss.pgh.pa.us 865 :UBC 0 : continue;
866 : :
867 : : /* See if we can match the clause's expression to the partkey column */
2346 tgl@sss.pgh.pa.us 868 [ + + ]:CBC 276 : if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
869 : 120 : return true;
870 : : }
871 : :
872 : 120 : return false;
873 : : }
874 : :
875 : : /*
876 : : * matches_boolean_partition_clause
877 : : * Determine if the boolean clause described by rinfo matches
878 : : * partrel's partkeycol-th partition key column.
879 : : *
880 : : * "Matches" can be either an exact match (equivalent to partkey = true),
881 : : * or a NOT above an exact match (equivalent to partkey = false).
882 : : */
883 : : static bool
884 : 276 : matches_boolean_partition_clause(RestrictInfo *rinfo,
885 : : RelOptInfo *partrel, int partkeycol)
886 : : {
887 : 276 : Node *clause = (Node *) rinfo->clause;
888 : 276 : Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
889 : :
890 : : /* Direct match? */
891 [ + + ]: 276 : if (equal(partexpr, clause))
892 : 60 : return true;
893 : : /* NOT clause? */
894 [ + + ]: 216 : else if (is_notclause(clause))
895 : : {
896 : 72 : Node *arg = (Node *) get_notclausearg((Expr *) clause);
897 : :
898 [ + + ]: 72 : if (equal(partexpr, arg))
899 : 60 : return true;
900 : : }
901 : :
902 : 156 : return false;
903 : : }
904 : :
905 : : /*
906 : : * build_partition_pathkeys
907 : : * Build a pathkeys list that describes the ordering induced by the
908 : : * partitions of partrel, under either forward or backward scan
909 : : * as per scandir.
910 : : *
911 : : * Caller must have checked that the partitions are properly ordered,
912 : : * as detected by partitions_are_ordered().
913 : : *
914 : : * Sets *partialkeys to true if pathkeys were only built for a prefix of the
915 : : * partition key, or false if the pathkeys include all columns of the
916 : : * partition key.
917 : : */
918 : : List *
919 : 23158 : build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
920 : : ScanDirection scandir, bool *partialkeys)
921 : : {
922 : 23158 : List *retval = NIL;
923 : 23158 : PartitionScheme partscheme = partrel->part_scheme;
924 : : int i;
925 : :
926 [ - + ]: 23158 : Assert(partscheme != NULL);
1495 drowley@postgresql.o 927 [ - + ]: 23158 : Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
928 : : /* For now, we can only cope with baserels */
2346 tgl@sss.pgh.pa.us 929 [ + + - + ]: 23158 : Assert(IS_SIMPLE_REL(partrel));
930 : :
931 [ + + ]: 39576 : for (i = 0; i < partscheme->partnatts; i++)
932 : : {
933 : : PathKey *cpathkey;
934 : 24100 : Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
935 : :
936 : : /*
937 : : * Try to make a canonical pathkey for this partkey.
938 : : *
939 : : * We assume the PartitionDesc lists any NULL partition last, so we
940 : : * treat the scan like a NULLS LAST index: we have nulls_first for
941 : : * backwards scan only.
942 : : */
943 : 24100 : cpathkey = make_pathkey_from_sortinfo(root,
944 : : keyCol,
945 : 24100 : partscheme->partopfamily[i],
946 : 24100 : partscheme->partopcintype[i],
947 : 24100 : partscheme->partcollation[i],
948 : : ScanDirectionIsBackward(scandir),
949 : : ScanDirectionIsBackward(scandir),
950 : : 0,
951 : : partrel->relids,
952 : : false);
953 : :
954 : :
955 [ + + ]: 24100 : if (cpathkey)
956 : : {
957 : : /*
958 : : * We found the sort key in an EquivalenceClass, so it's relevant
959 : : * for this query. Add it to list, unless it's redundant.
960 : : */
961 [ + + ]: 16298 : if (!pathkey_is_redundant(cpathkey, retval))
962 : 6110 : retval = lappend(retval, cpathkey);
963 : : }
964 : : else
965 : : {
966 : : /*
967 : : * Boolean partition keys might be redundant even if they do not
968 : : * appear in an EquivalenceClass, because of our special treatment
969 : : * of boolean equality conditions --- see the comment for
970 : : * partkey_is_bool_constant_for_query(). If that applies, we can
971 : : * continue to examine lower-order partition keys. Otherwise, the
972 : : * sort key is not an interesting sort order for this query, so we
973 : : * should stop considering partition columns; any lower-order sort
974 : : * keys won't be useful either.
975 : : */
976 [ + + ]: 7802 : if (!partkey_is_bool_constant_for_query(partrel, i))
977 : : {
978 : 7682 : *partialkeys = true;
979 : 7682 : return retval;
980 : : }
981 : : }
982 : : }
983 : :
984 : 15476 : *partialkeys = false;
985 : 15476 : return retval;
986 : : }
987 : :
988 : : /*
989 : : * build_expression_pathkey
990 : : * Build a pathkeys list that describes an ordering by a single expression
991 : : * using the given sort operator.
992 : : *
993 : : * expr and rel are as for make_pathkey_from_sortinfo.
994 : : * We induce the other arguments assuming default sort order for the operator.
995 : : *
996 : : * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
997 : : * is false and the expression isn't already in some EquivalenceClass.
998 : : */
999 : : List *
4307 1000 : 462 : build_expression_pathkey(PlannerInfo *root,
1001 : : Expr *expr,
1002 : : Oid opno,
1003 : : Relids rel,
1004 : : bool create_it)
1005 : : {
1006 : : List *pathkeys;
1007 : : Oid opfamily,
1008 : : opcintype;
1009 : : CompareType cmptype;
1010 : : PathKey *cpathkey;
1011 : :
1012 : : /* Find the operator in pg_amop --- failure shouldn't happen */
1013 [ - + ]: 462 : if (!get_ordering_op_properties(opno,
1014 : : &opfamily, &opcintype, &cmptype))
4307 tgl@sss.pgh.pa.us 1015 [ # # ]:UBC 0 : elog(ERROR, "operator %u is not a valid ordering operator",
1016 : : opno);
1017 : :
4307 tgl@sss.pgh.pa.us 1018 :CBC 462 : cpathkey = make_pathkey_from_sortinfo(root,
1019 : : expr,
1020 : : opfamily,
1021 : : opcintype,
1022 : : exprCollation((Node *) expr),
1023 : : (cmptype == COMPARE_GT),
1024 : : (cmptype == COMPARE_GT),
1025 : : 0,
1026 : : rel,
1027 : : create_it);
1028 : :
1029 [ + + ]: 462 : if (cpathkey)
1030 : 268 : pathkeys = list_make1(cpathkey);
1031 : : else
1032 : 194 : pathkeys = NIL;
1033 : :
1034 : 462 : return pathkeys;
1035 : : }
1036 : :
1037 : : /*
1038 : : * convert_subquery_pathkeys
1039 : : * Build a pathkeys list that describes the ordering of a subquery's
1040 : : * result, in the terms of the outer query. This is essentially a
1041 : : * task of conversion.
1042 : : *
1043 : : * 'rel': outer query's RelOptInfo for the subquery relation.
1044 : : * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
1045 : : * 'subquery_tlist': the subquery's output targetlist, in its terms.
1046 : : *
1047 : : * We intentionally don't do truncate_useless_pathkeys() here, because there
1048 : : * are situations where seeing the raw ordering of the subquery is helpful.
1049 : : * For example, if it returns ORDER BY x DESC, that may prompt us to
1050 : : * construct a mergejoin using DESC order rather than ASC order; but the
1051 : : * right_merge_direction heuristic would have us throw the knowledge away.
1052 : : */
1053 : : List *
7398 1054 : 26390 : convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
1055 : : List *subquery_pathkeys,
1056 : : List *subquery_tlist)
1057 : : {
8239 1058 : 26390 : List *retval = NIL;
1059 : 26390 : int retvallen = 0;
7769 neilc@samurai.com 1060 : 26390 : int outer_query_keys = list_length(root->query_pathkeys);
1061 : : ListCell *i;
1062 : :
7398 tgl@sss.pgh.pa.us 1063 [ + + + + : 44815 : foreach(i, subquery_pathkeys)
+ + ]
1064 : : {
6505 bruce@momjian.us 1065 : 19667 : PathKey *sub_pathkey = (PathKey *) lfirst(i);
6804 tgl@sss.pgh.pa.us 1066 : 19667 : EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
6505 bruce@momjian.us 1067 : 19667 : PathKey *best_pathkey = NULL;
1068 : :
6512 tgl@sss.pgh.pa.us 1069 [ + + ]: 19667 : if (sub_eclass->ec_has_volatile)
1070 : : {
1071 : : /*
1072 : : * If the sub_pathkey's EquivalenceClass is volatile, then it must
1073 : : * have come from an ORDER BY clause, and we have to match it to
1074 : : * that same targetlist entry.
1075 : : */
1076 : : TargetEntry *tle;
1077 : : Var *outer_var;
1078 : :
6505 bruce@momjian.us 1079 [ - + ]: 43 : if (sub_eclass->ec_sortref == 0) /* can't happen */
6512 tgl@sss.pgh.pa.us 1080 [ # # ]:UBC 0 : elog(ERROR, "volatile EquivalenceClass has no sortref");
3470 tgl@sss.pgh.pa.us 1081 :CBC 43 : tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
6512 1082 [ - + ]: 43 : Assert(tle);
1083 : : /* Is TLE actually available to the outer query? */
2312 1084 : 43 : outer_var = find_var_for_subquery_tle(rel, tle);
1085 [ + + ]: 43 : if (outer_var)
1086 : : {
1087 : : /* We can represent this sub_pathkey */
1088 : : EquivalenceMember *sub_member;
1089 : : EquivalenceClass *outer_ec;
1090 : :
6512 1091 [ - + ]: 30 : Assert(list_length(sub_eclass->ec_members) == 1);
1092 : 30 : sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1093 : :
1094 : : /*
1095 : : * Note: it might look funny to be setting sortref = 0 for a
1096 : : * reference to a volatile sub_eclass. However, the
1097 : : * expression is *not* volatile in the outer query: it's just
1098 : : * a Var referencing whatever the subquery emitted. (IOW, the
1099 : : * outer query isn't going to re-execute the volatile
1100 : : * expression itself.) So this is okay.
1101 : : */
1102 : : outer_ec =
1103 : 30 : get_eclass_for_sort_expr(root,
1104 : : (Expr *) outer_var,
1105 : : sub_eclass->ec_opfamilies,
1106 : : sub_member->em_datatype,
1107 : : sub_eclass->ec_collation,
1108 : : 0,
1109 : : rel->relids,
1110 : : false);
1111 : :
1112 : : /*
1113 : : * If we don't find a matching EC, sub-pathkey isn't
1114 : : * interesting to the outer query
1115 : : */
5426 1116 [ + + ]: 30 : if (outer_ec)
1117 : : best_pathkey =
1118 : 6 : make_canonical_pathkey(root,
1119 : : outer_ec,
1120 : : sub_pathkey->pk_opfamily,
1121 : : sub_pathkey->pk_cmptype,
1122 : 6 : sub_pathkey->pk_nulls_first);
1123 : : }
1124 : : }
1125 : : else
1126 : : {
1127 : : /*
1128 : : * Otherwise, the sub_pathkey's EquivalenceClass could contain
1129 : : * multiple elements (representing knowledge that multiple items
1130 : : * are effectively equal). Each element might match none, one, or
1131 : : * more of the output columns that are visible to the outer query.
1132 : : * This means we may have multiple possible representations of the
1133 : : * sub_pathkey in the context of the outer query. Ideally we
1134 : : * would generate them all and put them all into an EC of the
1135 : : * outer query, thereby propagating equality knowledge up to the
1136 : : * outer query. Right now we cannot do so, because the outer
1137 : : * query's EquivalenceClasses are already frozen when this is
1138 : : * called. Instead we prefer the one that has the highest "score"
1139 : : * (number of EC peers, plus one if it matches the outer
1140 : : * query_pathkeys). This is the most likely to be useful in the
1141 : : * outer query.
1142 : : */
6512 1143 : 19624 : int best_score = -1;
1144 : : ListCell *j;
1145 : :
1146 : : /* Ignore children here */
1147 [ + - + + : 39282 : foreach(j, sub_eclass->ec_members)
+ + ]
1148 : : {
1149 : 19658 : EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1150 : 19658 : Expr *sub_expr = sub_member->em_expr;
5285 1151 : 19658 : Oid sub_expr_type = sub_member->em_datatype;
1152 : 19658 : Oid sub_expr_coll = sub_eclass->ec_collation;
1153 : : ListCell *k;
1154 : :
1155 : : /* Child members should not exist in ec_members */
151 drowley@postgresql.o 1156 [ - + ]: 19658 : Assert(!sub_member->em_is_child);
1157 : :
3470 tgl@sss.pgh.pa.us 1158 [ + - + + : 111743 : foreach(k, subquery_tlist)
+ + ]
1159 : : {
6512 1160 : 92085 : TargetEntry *tle = (TargetEntry *) lfirst(k);
1161 : : Var *outer_var;
1162 : : Expr *tle_expr;
1163 : : EquivalenceClass *outer_ec;
1164 : : PathKey *outer_pk;
1165 : : int score;
1166 : :
1167 : : /* Is TLE actually available to the outer query? */
2312 1168 : 92085 : outer_var = find_var_for_subquery_tle(rel, tle);
1169 [ + + ]: 92085 : if (!outer_var)
6512 1170 : 19259 : continue;
1171 : :
1172 : : /*
1173 : : * The targetlist entry is considered to match if it
1174 : : * matches after sort-key canonicalization. That is
1175 : : * needed since the sub_expr has been through the same
1176 : : * process.
1177 : : */
5285 1178 : 72826 : tle_expr = canonicalize_ec_expression(tle->expr,
1179 : : sub_expr_type,
1180 : : sub_expr_coll);
1181 [ + + ]: 72826 : if (!equal(tle_expr, sub_expr))
1182 : 53770 : continue;
1183 : :
1184 : : /* See if we have a matching EC for the TLE */
6512 1185 : 19056 : outer_ec = get_eclass_for_sort_expr(root,
1186 : : (Expr *) outer_var,
1187 : : sub_eclass->ec_opfamilies,
1188 : : sub_expr_type,
1189 : : sub_expr_coll,
1190 : : 0,
1191 : : rel->relids,
1192 : : false);
1193 : :
1194 : : /*
1195 : : * If we don't find a matching EC, this sub-pathkey isn't
1196 : : * interesting to the outer query
1197 : : */
5426 1198 [ + + ]: 19056 : if (!outer_ec)
1199 : 629 : continue;
1200 : :
6512 1201 : 18427 : outer_pk = make_canonical_pathkey(root,
1202 : : outer_ec,
1203 : : sub_pathkey->pk_opfamily,
1204 : : sub_pathkey->pk_cmptype,
2999 1205 : 18427 : sub_pathkey->pk_nulls_first);
1206 : : /* score = # of equivalence peers */
6512 1207 : 18427 : score = list_length(outer_ec->ec_members) - 1;
1208 : : /* +1 if it matches the proper query_pathkeys item */
1209 [ + + + + ]: 36707 : if (retvallen < outer_query_keys &&
1210 : 18280 : list_nth(root->query_pathkeys, retvallen) == outer_pk)
1211 : 17439 : score++;
1212 [ + + ]: 18427 : if (score > best_score)
1213 : : {
1214 : 18419 : best_pathkey = outer_pk;
1215 : 18419 : best_score = score;
1216 : : }
1217 : : }
1218 : : }
1219 : : }
1220 : :
1221 : : /*
1222 : : * If we couldn't find a representation of this sub_pathkey, we're
1223 : : * done (we can't use the ones to its right, either).
1224 : : */
6804 1225 [ + + ]: 19667 : if (!best_pathkey)
8239 1226 : 1242 : break;
1227 : :
1228 : : /*
1229 : : * Eliminate redundant ordering info; could happen if outer query
1230 : : * equivalences subquery keys...
1231 : : */
6804 1232 [ + + ]: 18425 : if (!pathkey_is_redundant(best_pathkey, retval))
1233 : : {
1234 : 18419 : retval = lappend(retval, best_pathkey);
8239 1235 : 18419 : retvallen++;
1236 : : }
1237 : : }
1238 : :
1239 : 26390 : return retval;
1240 : : }
1241 : :
1242 : : /*
1243 : : * find_var_for_subquery_tle
1244 : : *
1245 : : * If the given subquery tlist entry is due to be emitted by the subquery's
1246 : : * scan node, return a Var for it, else return NULL.
1247 : : *
1248 : : * We need this to ensure that we don't return pathkeys describing values
1249 : : * that are unavailable above the level of the subquery scan.
1250 : : */
1251 : : static Var *
2312 1252 : 92128 : find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
1253 : : {
1254 : : ListCell *lc;
1255 : :
1256 : : /* If the TLE is resjunk, it's certainly not visible to the outer query */
1257 [ - + ]: 92128 : if (tle->resjunk)
2312 tgl@sss.pgh.pa.us 1258 :UBC 0 : return NULL;
1259 : :
1260 : : /* Search the rel's targetlist to see what it will return */
2312 tgl@sss.pgh.pa.us 1261 [ + + + + :CBC 558062 : foreach(lc, rel->reltarget->exprs)
+ + ]
1262 : : {
1263 : 538790 : Var *var = (Var *) lfirst(lc);
1264 : :
1265 : : /* Ignore placeholders */
1266 [ + + ]: 538790 : if (!IsA(var, Var))
1267 : 26926 : continue;
1268 [ - + ]: 511864 : Assert(var->varno == rel->relid);
1269 : :
1270 : : /* If we find a Var referencing this TLE, we're good */
1271 [ + + ]: 511864 : if (var->varattno == tle->resno)
1272 : 72856 : return copyObject(var); /* Make a copy for safety */
1273 : : }
1274 : 19272 : return NULL;
1275 : : }
1276 : :
1277 : : /*
1278 : : * build_join_pathkeys
1279 : : * Build the path keys for a join relation constructed by mergejoin or
1280 : : * nestloop join. This is normally the same as the outer path's keys.
1281 : : *
1282 : : * EXCEPTION: in a FULL, RIGHT or RIGHT_ANTI join, we cannot treat the
1283 : : * result as having the outer path's path keys, because null lefthand rows
1284 : : * may be inserted at random points. It must be treated as unsorted.
1285 : : *
1286 : : * We truncate away any pathkeys that are uninteresting for higher joins.
1287 : : *
1288 : : * 'joinrel' is the join relation that paths are being formed for
1289 : : * 'jointype' is the join type (inner, left, full, etc)
1290 : : * 'outer_pathkeys' is the list of the current outer path's path keys
1291 : : *
1292 : : * Returns the list of new path keys.
1293 : : */
1294 : : List *
7398 1295 : 914761 : build_join_pathkeys(PlannerInfo *root,
1296 : : RelOptInfo *joinrel,
1297 : : JoinType jointype,
1298 : : List *outer_pathkeys)
1299 : : {
1300 : : /* RIGHT_SEMI should not come here */
428 rguo@postgresql.org 1301 [ - + ]: 914761 : Assert(jointype != JOIN_RIGHT_SEMI);
1302 : :
885 tgl@sss.pgh.pa.us 1303 [ + + + + ]: 914761 : if (jointype == JOIN_FULL ||
1304 [ + + ]: 778200 : jointype == JOIN_RIGHT ||
1305 : : jointype == JOIN_RIGHT_ANTI)
7531 1306 : 144714 : return NIL;
1307 : :
1308 : : /*
1309 : : * This used to be quite a complex bit of code, but now that all pathkey
1310 : : * sublists start out life canonicalized, we don't have to do a darn thing
1311 : : * here!
1312 : : *
1313 : : * We do, however, need to truncate the pathkeys list, since it may
1314 : : * contain pathkeys that were useful for forming this joinrel but are
1315 : : * uninteresting to higher levels.
1316 : : */
9032 1317 : 770047 : return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1318 : : }
1319 : :
1320 : : /****************************************************************************
1321 : : * PATHKEYS AND SORT CLAUSES
1322 : : ****************************************************************************/
1323 : :
1324 : : /*
1325 : : * make_pathkeys_for_sortclauses
1326 : : * Generate a pathkeys list that represents the sort order specified
1327 : : * by a list of SortGroupClauses
1328 : : *
1329 : : * The resulting PathKeys are always in canonical form. (Actually, there
1330 : : * is no longer any code anywhere that creates non-canonical PathKeys.)
1331 : : *
1332 : : * 'sortclauses' is a list of SortGroupClause nodes
1333 : : * 'tlist' is the targetlist to find the referenced tlist entries in
1334 : : */
1335 : : List *
6804 1336 : 267262 : make_pathkeys_for_sortclauses(PlannerInfo *root,
1337 : : List *sortclauses,
1338 : : List *tlist)
1339 : : {
1340 : : List *result;
1341 : : bool sortable;
1342 : :
962 1343 : 267262 : result = make_pathkeys_for_sortclauses_extended(root,
1344 : : &sortclauses,
1345 : : tlist,
1346 : : false,
1347 : : false,
1348 : : &sortable,
1349 : : false);
1350 : : /* It's caller error if not all clauses were sortable */
1351 [ - + ]: 267262 : Assert(sortable);
1352 : 267262 : return result;
1353 : : }
1354 : :
1355 : : /*
1356 : : * make_pathkeys_for_sortclauses_extended
1357 : : * Generate a pathkeys list that represents the sort order specified
1358 : : * by a list of SortGroupClauses
1359 : : *
1360 : : * The comments for make_pathkeys_for_sortclauses apply here too. In addition:
1361 : : *
1362 : : * If remove_redundant is true, then any sort clauses that are found to
1363 : : * give rise to redundant pathkeys are removed from the sortclauses list
1364 : : * (which therefore must be pass-by-reference in this version).
1365 : : *
1366 : : * If remove_group_rtindex is true, then we need to remove the RT index of the
1367 : : * grouping step from the sort expressions before we make PathKeys for them.
1368 : : *
1369 : : * *sortable is set to true if all the sort clauses are in fact sortable.
1370 : : * If any are not, they are ignored except for setting *sortable false.
1371 : : * (In that case, the output pathkey list isn't really useful. However,
1372 : : * we process the whole sortclauses list anyway, because it's still valid
1373 : : * to remove any clauses that can be proven redundant via the eclass logic.
1374 : : * Even though we'll have to hash in that case, we might as well not hash
1375 : : * redundant columns.)
1376 : : *
1377 : : * If set_ec_sortref is true then sets the value of the pathkey's
1378 : : * EquivalenceClass unless it's already initialized.
1379 : : */
1380 : : List *
1381 : 278692 : make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
1382 : : List **sortclauses,
1383 : : List *tlist,
1384 : : bool remove_redundant,
1385 : : bool remove_group_rtindex,
1386 : : bool *sortable,
1387 : : bool set_ec_sortref)
1388 : : {
9513 1389 : 278692 : List *pathkeys = NIL;
1390 : : ListCell *l;
1391 : :
962 1392 : 278692 : *sortable = true;
1393 [ + + + + : 374557 : foreach(l, *sortclauses)
+ + ]
1394 : : {
6244 1395 : 95865 : SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1396 : : Expr *sortkey;
1397 : : PathKey *pathkey;
1398 : :
6804 1399 : 95865 : sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
962 1400 [ + + ]: 95865 : if (!OidIsValid(sortcl->sortop))
1401 : : {
1402 : 105 : *sortable = false;
1403 : 105 : continue;
1404 : : }
361 rguo@postgresql.org 1405 [ + + ]: 95760 : if (remove_group_rtindex)
1406 : : {
1407 [ - + ]: 706 : Assert(root->group_rtindex > 0);
1408 : : sortkey = (Expr *)
1409 : 706 : remove_nulling_relids((Node *) sortkey,
1410 : 706 : bms_make_singleton(root->group_rtindex),
1411 : : NULL);
1412 : : }
5395 tgl@sss.pgh.pa.us 1413 : 95760 : pathkey = make_pathkey_from_sortop(root,
1414 : : sortkey,
1415 : : sortcl->sortop,
327 peter@eisentraut.org 1416 : 95760 : sortcl->reverse_sort,
5395 tgl@sss.pgh.pa.us 1417 : 95760 : sortcl->nulls_first,
1418 : : sortcl->tleSortGroupRef,
1419 : : true);
457 akorotkov@postgresql 1420 [ + + + + ]: 95760 : if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1421 : : {
1422 : : /*
1423 : : * Copy the sortref if it hasn't been set yet. That may happen if
1424 : : * the EquivalenceClass was constructed from a WHERE clause, i.e.
1425 : : * it doesn't have a target reference at all.
1426 : : */
1427 : 278 : pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1428 : : }
1429 : :
1430 : : /* Canonical form eliminates redundant ordering keys */
4513 tgl@sss.pgh.pa.us 1431 [ + + ]: 95760 : if (!pathkey_is_redundant(pathkey, pathkeys))
6804 1432 : 87005 : pathkeys = lappend(pathkeys, pathkey);
962 1433 [ + + ]: 8755 : else if (remove_redundant)
1434 : 335 : *sortclauses = foreach_delete_current(*sortclauses, l);
1435 : : }
9513 1436 : 278692 : return pathkeys;
1437 : : }
1438 : :
1439 : : /****************************************************************************
1440 : : * PATHKEYS AND MERGECLAUSES
1441 : : ****************************************************************************/
1442 : :
1443 : : /*
1444 : : * initialize_mergeclause_eclasses
1445 : : * Set the EquivalenceClass links in a mergeclause restrictinfo.
1446 : : *
1447 : : * RestrictInfo contains fields in which we may cache pointers to
1448 : : * EquivalenceClasses for the left and right inputs of the mergeclause.
1449 : : * (If the mergeclause is a true equivalence clause these will be the
1450 : : * same EquivalenceClass, otherwise not.) If the mergeclause is either
1451 : : * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
1452 : : * then it's easy to set up the left_ec and right_ec members --- otherwise,
1453 : : * this function should be called to set them up. We will generate new
1454 : : * EquivalenceClauses if necessary to represent the mergeclause's left and
1455 : : * right sides.
1456 : : *
1457 : : * Note this is called before EC merging is complete, so the links won't
1458 : : * necessarily point to canonical ECs. Before they are actually used for
1459 : : * anything, update_mergeclause_eclasses must be called to ensure that
1460 : : * they've been updated to point to canonical ECs.
1461 : : */
1462 : : void
5426 1463 : 28561 : initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1464 : : {
1465 : 28561 : Expr *clause = restrictinfo->clause;
1466 : : Oid lefttype,
1467 : : righttype;
1468 : :
1469 : : /* Should be a mergeclause ... */
6804 1470 [ - + ]: 28561 : Assert(restrictinfo->mergeopfamilies != NIL);
1471 : : /* ... with links not yet set */
5426 1472 [ - + ]: 28561 : Assert(restrictinfo->left_ec == NULL);
1473 [ - + ]: 28561 : Assert(restrictinfo->right_ec == NULL);
1474 : :
1475 : : /* Need the declared input types of the operator */
1476 : 28561 : op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1477 : :
1478 : : /* Find or create a matching EquivalenceClass for each side */
1479 : 28561 : restrictinfo->left_ec =
1480 : 28561 : get_eclass_for_sort_expr(root,
1481 : 28561 : (Expr *) get_leftop(clause),
1482 : : restrictinfo->mergeopfamilies,
1483 : : lefttype,
1484 : : ((OpExpr *) clause)->inputcollid,
1485 : : 0,
1486 : : NULL,
1487 : : true);
1488 : 28561 : restrictinfo->right_ec =
1489 : 28561 : get_eclass_for_sort_expr(root,
1490 : 28561 : (Expr *) get_rightop(clause),
1491 : : restrictinfo->mergeopfamilies,
1492 : : righttype,
1493 : : ((OpExpr *) clause)->inputcollid,
1494 : : 0,
1495 : : NULL,
1496 : : true);
1497 : 28561 : }
1498 : :
1499 : : /*
1500 : : * update_mergeclause_eclasses
1501 : : * Make the cached EquivalenceClass links valid in a mergeclause
1502 : : * restrictinfo.
1503 : : *
1504 : : * These pointers should have been set by process_equivalence or
1505 : : * initialize_mergeclause_eclasses, but they might have been set to
1506 : : * non-canonical ECs that got merged later. Chase up to the canonical
1507 : : * merged parent if so.
1508 : : */
1509 : : void
1510 : 2385136 : update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1511 : : {
1512 : : /* Should be a merge clause ... */
1513 [ - + ]: 2385136 : Assert(restrictinfo->mergeopfamilies != NIL);
1514 : : /* ... with pointers already set */
1515 [ - + ]: 2385136 : Assert(restrictinfo->left_ec != NULL);
1516 [ - + ]: 2385136 : Assert(restrictinfo->right_ec != NULL);
1517 : :
1518 : : /* Chase up to the top as needed */
1519 [ - + ]: 2385136 : while (restrictinfo->left_ec->ec_merged)
5426 tgl@sss.pgh.pa.us 1520 :UBC 0 : restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
5426 tgl@sss.pgh.pa.us 1521 [ - + ]:CBC 2385136 : while (restrictinfo->right_ec->ec_merged)
5426 tgl@sss.pgh.pa.us 1522 :UBC 0 : restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
9032 tgl@sss.pgh.pa.us 1523 :CBC 2385136 : }
1524 : :
1525 : : /*
1526 : : * find_mergeclauses_for_outer_pathkeys
1527 : : * This routine attempts to find a list of mergeclauses that can be
1528 : : * used with a specified ordering for the join's outer relation.
1529 : : * If successful, it returns a list of mergeclauses.
1530 : : *
1531 : : * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
1532 : : * 'restrictinfos' is a list of mergejoinable restriction clauses for the
1533 : : * join relation being formed, in no particular order.
1534 : : *
1535 : : * The restrictinfos must be marked (via outer_is_left) to show which side
1536 : : * of each clause is associated with the current outer path. (See
1537 : : * select_mergejoin_clauses())
1538 : : *
1539 : : * The result is NIL if no merge can be done, else a maximal list of
1540 : : * usable mergeclauses (represented as a list of their restrictinfo nodes).
1541 : : * The list is ordered to match the pathkeys, as required for execution.
1542 : : */
1543 : : List *
2752 1544 : 900355 : find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
1545 : : List *pathkeys,
1546 : : List *restrictinfos)
1547 : : {
9518 1548 : 900355 : List *mergeclauses = NIL;
1549 : : ListCell *i;
1550 : :
1551 : : /* make sure we have eclasses cached in the clauses */
8700 1552 [ + + + + : 1873707 : foreach(i, restrictinfos)
+ + ]
1553 : : {
6804 1554 : 973352 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1555 : :
5426 1556 : 973352 : update_mergeclause_eclasses(root, rinfo);
1557 : : }
1558 : :
9518 1559 [ + + + + : 1463483 : foreach(i, pathkeys)
+ + ]
1560 : : {
6505 bruce@momjian.us 1561 : 684506 : PathKey *pathkey = (PathKey *) lfirst(i);
6804 tgl@sss.pgh.pa.us 1562 : 684506 : EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
8700 1563 : 684506 : List *matched_restrictinfos = NIL;
1564 : : ListCell *j;
1565 : :
1566 : : /*----------
1567 : : * A mergejoin clause matches a pathkey if it has the same EC.
1568 : : * If there are multiple matching clauses, take them all. In plain
1569 : : * inner-join scenarios we expect only one match, because
1570 : : * equivalence-class processing will have removed any redundant
1571 : : * mergeclauses. However, in outer-join scenarios there might be
1572 : : * multiple matches. An example is
1573 : : *
1574 : : * select * from a full join b
1575 : : * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1576 : : *
1577 : : * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1578 : : * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1579 : : * we *must* do so or we will be unable to form a valid plan.
1580 : : *
1581 : : * We expect that the given pathkeys list is canonical, which means
1582 : : * no two members have the same EC, so it's not possible for this
1583 : : * code to enter the same mergeclause into the result list twice.
1584 : : *
1585 : : * It's possible that multiple matching clauses might have different
1586 : : * ECs on the other side, in which case the order we put them into our
1587 : : * result makes a difference in the pathkeys required for the inner
1588 : : * input rel. However this routine hasn't got any info about which
1589 : : * order would be best, so we don't worry about that.
1590 : : *
1591 : : * It's also possible that the selected mergejoin clauses produce
1592 : : * a noncanonical ordering of pathkeys for the inner side, ie, we
1593 : : * might select clauses that reference b.v1, b.v2, b.v1 in that
1594 : : * order. This is not harmful in itself, though it suggests that
1595 : : * the clauses are partially redundant. Since the alternative is
1596 : : * to omit mergejoin clauses and thereby possibly fail to generate a
1597 : : * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1598 : : * has to delete duplicates when it constructs the inner pathkeys
1599 : : * list, and we also have to deal with such cases specially in
1600 : : * create_mergejoin_plan().
1601 : : *----------
1602 : : */
9032 1603 [ + + + + : 1544177 : foreach(j, restrictinfos)
+ + ]
1604 : : {
6804 1605 : 859671 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1606 : : EquivalenceClass *clause_ec;
1607 : :
2752 1608 : 1719342 : clause_ec = rinfo->outer_is_left ?
1609 [ + + ]: 859671 : rinfo->left_ec : rinfo->right_ec;
6804 1610 [ + + ]: 859671 : if (clause_ec == pathkey_ec)
1611 : 563185 : matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1612 : : }
1613 : :
1614 : : /*
1615 : : * If we didn't find a mergeclause, we're done --- any additional
1616 : : * sort-key positions in the pathkeys are useless. (But we can still
1617 : : * mergejoin if we found at least one mergeclause.)
1618 : : */
8700 1619 [ + + ]: 684506 : if (matched_restrictinfos == NIL)
9518 1620 : 121378 : break;
1621 : :
1622 : : /*
1623 : : * If we did find usable mergeclause(s) for this sort-key position,
1624 : : * add them to result list.
1625 : : */
7769 neilc@samurai.com 1626 : 563128 : mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1627 : : }
1628 : :
9518 tgl@sss.pgh.pa.us 1629 : 900355 : return mergeclauses;
1630 : : }
1631 : :
1632 : : /*
1633 : : * select_outer_pathkeys_for_merge
1634 : : * Builds a pathkey list representing a possible sort ordering
1635 : : * that can be used with the given mergeclauses.
1636 : : *
1637 : : * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
1638 : : * that will be used in a merge join.
1639 : : * 'joinrel' is the join relation we are trying to construct.
1640 : : *
1641 : : * The restrictinfos must be marked (via outer_is_left) to show which side
1642 : : * of each clause is associated with the current outer path. (See
1643 : : * select_mergejoin_clauses())
1644 : : *
1645 : : * Returns a pathkeys list that can be applied to the outer relation.
1646 : : *
1647 : : * Since we assume here that a sort is required, there is no particular use
1648 : : * in matching any available ordering of the outerrel. (joinpath.c has an
1649 : : * entirely separate code path for considering sort-free mergejoins.) Rather,
1650 : : * it's interesting to try to match, or match a prefix of the requested
1651 : : * query_pathkeys so that a second output sort may be avoided or an
1652 : : * incremental sort may be done instead. We can get away with just a prefix
1653 : : * of the query_pathkeys when that prefix covers the entire join condition.
1654 : : * Failing that, we try to list "more popular" keys (those with the most
1655 : : * unmatched EquivalenceClass peers) earlier, in hopes of making the resulting
1656 : : * ordering useful for as many higher-level mergejoins as possible.
1657 : : */
1658 : : List *
6804 1659 : 257299 : select_outer_pathkeys_for_merge(PlannerInfo *root,
1660 : : List *mergeclauses,
1661 : : RelOptInfo *joinrel)
1662 : : {
1663 : 257299 : List *pathkeys = NIL;
1664 : 257299 : int nClauses = list_length(mergeclauses);
1665 : : EquivalenceClass **ecs;
1666 : : int *scores;
1667 : : int necs;
1668 : : ListCell *lc;
1669 : : int j;
1670 : :
1671 : : /* Might have no mergeclauses */
1672 [ - + ]: 257299 : if (nClauses == 0)
6804 tgl@sss.pgh.pa.us 1673 :UBC 0 : return NIL;
1674 : :
1675 : : /*
1676 : : * Make arrays of the ECs used by the mergeclauses (dropping any
1677 : : * duplicates) and their "popularity" scores.
1678 : : */
6804 tgl@sss.pgh.pa.us 1679 :CBC 257299 : ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1680 : 257299 : scores = (int *) palloc(nClauses * sizeof(int));
1681 : 257299 : necs = 0;
1682 : :
1683 [ + - + + : 544130 : foreach(lc, mergeclauses)
+ + ]
1684 : : {
1685 : 286831 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1686 : : EquivalenceClass *oeclass;
1687 : : int score;
1688 : : ListCell *lc2;
1689 : :
1690 : : /* get the outer eclass */
5426 1691 : 286831 : update_mergeclause_eclasses(root, rinfo);
1692 : :
6804 1693 [ + + ]: 286831 : if (rinfo->outer_is_left)
1694 : 145170 : oeclass = rinfo->left_ec;
1695 : : else
1696 : 141661 : oeclass = rinfo->right_ec;
1697 : :
1698 : : /* reject duplicates */
1699 [ + + ]: 317750 : for (j = 0; j < necs; j++)
1700 : : {
1701 [ + + ]: 30952 : if (ecs[j] == oeclass)
1702 : 33 : break;
1703 : : }
1704 [ + + ]: 286831 : if (j < necs)
1705 : 33 : continue;
1706 : :
1707 : : /* compute score */
1708 : 286798 : score = 0;
1709 [ + - + + : 809970 : foreach(lc2, oeclass->ec_members)
+ + ]
1710 : : {
1711 : 523172 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1712 : :
1713 : : /* Child members should not exist in ec_members */
151 drowley@postgresql.o 1714 [ - + ]: 523172 : Assert(!em->em_is_child);
1715 : :
1716 : : /* Potential future join partner? */
1717 [ + - ]: 523172 : if (!em->em_is_const &&
6804 tgl@sss.pgh.pa.us 1718 [ + + ]: 523172 : !bms_overlap(em->em_relids, joinrel->relids))
1719 : 38962 : score++;
1720 : : }
1721 : :
1722 : 286798 : ecs[necs] = oeclass;
1723 : 286798 : scores[necs] = score;
1724 : 286798 : necs++;
1725 : : }
1726 : :
1727 : : /*
1728 : : * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1729 : : * can generate a sort order that's also useful for final output. If we
1730 : : * only have a prefix of the query_pathkeys, and that prefix is the entire
1731 : : * join condition, then it's useful to use the prefix as the pathkeys as
1732 : : * this increases the chances that an incremental sort will be able to be
1733 : : * used by the upper planner.
1734 : : */
1735 [ + + ]: 257299 : if (root->query_pathkeys)
1736 : : {
1131 drowley@postgresql.o 1737 : 172699 : int matches = 0;
1738 : :
6804 tgl@sss.pgh.pa.us 1739 [ + - + + : 205699 : foreach(lc, root->query_pathkeys)
+ + ]
1740 : : {
6505 bruce@momjian.us 1741 : 197689 : PathKey *query_pathkey = (PathKey *) lfirst(lc);
6804 tgl@sss.pgh.pa.us 1742 : 197689 : EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1743 : :
1744 [ + + ]: 383419 : for (j = 0; j < necs; j++)
1745 : : {
1746 [ + + ]: 218730 : if (ecs[j] == query_ec)
1747 : 33000 : break; /* found match */
1748 : : }
1749 [ + + ]: 197689 : if (j >= necs)
1750 : 164689 : break; /* didn't find match */
1751 : :
1131 drowley@postgresql.o 1752 : 33000 : matches++;
1753 : : }
1754 : : /* if we got to the end of the list, we have them all */
6804 tgl@sss.pgh.pa.us 1755 [ + + ]: 172699 : if (lc == NULL)
1756 : : {
1757 : : /* copy query_pathkeys as starting point for our output */
1758 : 8010 : pathkeys = list_copy(root->query_pathkeys);
1759 : : /* mark their ECs as already-emitted */
1760 [ + - + + : 16407 : foreach(lc, root->query_pathkeys)
+ + ]
1761 : : {
6505 bruce@momjian.us 1762 : 8397 : PathKey *query_pathkey = (PathKey *) lfirst(lc);
6804 tgl@sss.pgh.pa.us 1763 : 8397 : EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1764 : :
1765 [ + - ]: 8847 : for (j = 0; j < necs; j++)
1766 : : {
1767 [ + + ]: 8847 : if (ecs[j] == query_ec)
1768 : : {
1769 : 8397 : scores[j] = -1;
1770 : 8397 : break;
1771 : : }
1772 : : }
1773 : : }
1774 : : }
1775 : :
1776 : : /*
1777 : : * If we didn't match to all of the query_pathkeys, but did match to
1778 : : * all of the join clauses then we'll make use of these as partially
1779 : : * sorted input is better than nothing for the upper planner as it may
1780 : : * lead to incremental sorts instead of full sorts.
1781 : : */
1131 drowley@postgresql.o 1782 [ + + ]: 164689 : else if (matches == nClauses)
1783 : : {
1784 : 19790 : pathkeys = list_copy_head(root->query_pathkeys, matches);
1785 : :
1786 : : /* we have all of the join pathkeys, so nothing more to do */
1787 : 19790 : pfree(ecs);
1788 : 19790 : pfree(scores);
1789 : :
1790 : 19790 : return pathkeys;
1791 : : }
1792 : : }
1793 : :
1794 : : /*
1795 : : * Add remaining ECs to the list in popularity order, using a default sort
1796 : : * ordering. (We could use qsort() here, but the list length is usually
1797 : : * so small it's not worth it.)
1798 : : */
1799 : : for (;;)
6804 tgl@sss.pgh.pa.us 1800 : 258605 : {
1801 : : int best_j;
1802 : : int best_score;
1803 : : EquivalenceClass *ec;
1804 : : PathKey *pathkey;
1805 : :
1806 : 496114 : best_j = 0;
1807 : 496114 : best_score = scores[0];
1808 [ + + ]: 585228 : for (j = 1; j < necs; j++)
1809 : : {
1810 [ + + ]: 89114 : if (scores[j] > best_score)
1811 : : {
1812 : 29052 : best_j = j;
1813 : 29052 : best_score = scores[j];
1814 : : }
1815 : : }
1816 [ + + ]: 496114 : if (best_score < 0)
1817 : 237509 : break; /* all done */
1818 : 258605 : ec = ecs[best_j];
1819 : 258605 : scores[best_j] = -1;
1820 : 258605 : pathkey = make_canonical_pathkey(root,
1821 : : ec,
1822 : 258605 : linitial_oid(ec->ec_opfamilies),
1823 : : COMPARE_LT,
1824 : : false);
1825 : : /* can't be redundant because no duplicate ECs */
1826 [ - + ]: 258605 : Assert(!pathkey_is_redundant(pathkey, pathkeys));
1827 : 258605 : pathkeys = lappend(pathkeys, pathkey);
1828 : : }
1829 : :
1830 : 237509 : pfree(ecs);
1831 : 237509 : pfree(scores);
1832 : :
1833 : 237509 : return pathkeys;
1834 : : }
1835 : :
1836 : : /*
1837 : : * make_inner_pathkeys_for_merge
1838 : : * Builds a pathkey list representing the explicit sort order that
1839 : : * must be applied to an inner path to make it usable with the
1840 : : * given mergeclauses.
1841 : : *
1842 : : * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
1843 : : * that will be used in a merge join, in order.
1844 : : * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
1845 : : * side of the join.
1846 : : *
1847 : : * The restrictinfos must be marked (via outer_is_left) to show which side
1848 : : * of each clause is associated with the current outer path. (See
1849 : : * select_mergejoin_clauses())
1850 : : *
1851 : : * Returns a pathkeys list that can be applied to the inner relation.
1852 : : *
1853 : : * Note that it is not this routine's job to decide whether sorting is
1854 : : * actually needed for a particular input path. Assume a sort is necessary;
1855 : : * just make the keys, eh?
1856 : : */
1857 : : List *
1858 : 486582 : make_inner_pathkeys_for_merge(PlannerInfo *root,
1859 : : List *mergeclauses,
1860 : : List *outer_pathkeys)
1861 : : {
9518 1862 : 486582 : List *pathkeys = NIL;
1863 : : EquivalenceClass *lastoeclass;
1864 : : PathKey *opathkey;
1865 : : ListCell *lc;
1866 : : ListCell *lop;
1867 : :
6804 1868 : 486582 : lastoeclass = NULL;
1869 : 486582 : opathkey = NULL;
1870 : 486582 : lop = list_head(outer_pathkeys);
1871 : :
1872 [ + + + + : 1044589 : foreach(lc, mergeclauses)
+ + ]
1873 : : {
1874 : 558007 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1875 : : EquivalenceClass *oeclass;
1876 : : EquivalenceClass *ieclass;
1877 : : PathKey *pathkey;
1878 : :
5426 1879 : 558007 : update_mergeclause_eclasses(root, rinfo);
1880 : :
6804 1881 [ + + ]: 558007 : if (rinfo->outer_is_left)
1882 : : {
1883 : 296408 : oeclass = rinfo->left_ec;
1884 : 296408 : ieclass = rinfo->right_ec;
1885 : : }
1886 : : else
1887 : : {
1888 : 261599 : oeclass = rinfo->right_ec;
1889 : 261599 : ieclass = rinfo->left_ec;
1890 : : }
1891 : :
1892 : : /* outer eclass should match current or next pathkeys */
1893 : : /* we check this carefully for debugging reasons */
1894 [ + + ]: 558007 : if (oeclass != lastoeclass)
1895 : : {
1896 [ - + ]: 557956 : if (!lop)
6804 tgl@sss.pgh.pa.us 1897 [ # # ]:UBC 0 : elog(ERROR, "too few pathkeys for mergeclauses");
6804 tgl@sss.pgh.pa.us 1898 :CBC 557956 : opathkey = (PathKey *) lfirst(lop);
2245 1899 : 557956 : lop = lnext(outer_pathkeys, lop);
6804 1900 : 557956 : lastoeclass = opathkey->pk_eclass;
1901 [ - + ]: 557956 : if (oeclass != lastoeclass)
6804 tgl@sss.pgh.pa.us 1902 [ # # ]:UBC 0 : elog(ERROR, "outer pathkeys do not match mergeclause");
1903 : : }
1904 : :
1905 : : /*
1906 : : * Often, we'll have same EC on both sides, in which case the outer
1907 : : * pathkey is also canonical for the inner side, and we can skip a
1908 : : * useless search.
1909 : : */
6804 tgl@sss.pgh.pa.us 1910 [ + + ]:CBC 558007 : if (ieclass == oeclass)
1911 : 353707 : pathkey = opathkey;
1912 : : else
1913 : 204300 : pathkey = make_canonical_pathkey(root,
1914 : : ieclass,
1915 : : opathkey->pk_opfamily,
1916 : : opathkey->pk_cmptype,
1917 : 204300 : opathkey->pk_nulls_first);
1918 : :
1919 : : /*
1920 : : * Don't generate redundant pathkeys (which can happen if multiple
1921 : : * mergeclauses refer to the same EC). Because we do this, the output
1922 : : * pathkey list isn't necessarily ordered like the mergeclauses, which
1923 : : * complicates life for create_mergejoin_plan(). But if we didn't,
1924 : : * we'd have a noncanonical sort key list, which would be bad; for one
1925 : : * reason, it certainly wouldn't match any available sort order for
1926 : : * the input relation.
1927 : : */
1928 [ + + ]: 558007 : if (!pathkey_is_redundant(pathkey, pathkeys))
1929 : 557926 : pathkeys = lappend(pathkeys, pathkey);
1930 : : }
1931 : :
9032 1932 : 486582 : return pathkeys;
1933 : : }
1934 : :
1935 : : /*
1936 : : * trim_mergeclauses_for_inner_pathkeys
1937 : : * This routine trims a list of mergeclauses to include just those that
1938 : : * work with a specified ordering for the join's inner relation.
1939 : : *
1940 : : * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
1941 : : * join relation being formed, in an order known to work for the
1942 : : * currently-considered sort ordering of the join's outer rel.
1943 : : * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
1944 : : * it should be equal to, or a truncation of, the result of
1945 : : * make_inner_pathkeys_for_merge for these mergeclauses.
1946 : : *
1947 : : * What we return will be a prefix of the given mergeclauses list.
1948 : : *
1949 : : * We need this logic because make_inner_pathkeys_for_merge's result isn't
1950 : : * necessarily in the same order as the mergeclauses. That means that if we
1951 : : * consider an inner-rel pathkey list that is a truncation of that result,
1952 : : * we might need to drop mergeclauses even though they match a surviving inner
1953 : : * pathkey. This happens when they are to the right of a mergeclause that
1954 : : * matches a removed inner pathkey.
1955 : : *
1956 : : * The mergeclauses must be marked (via outer_is_left) to show which side
1957 : : * of each clause is associated with the current outer path. (See
1958 : : * select_mergejoin_clauses())
1959 : : */
1960 : : List *
2752 1961 : 2745 : trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
1962 : : List *mergeclauses,
1963 : : List *pathkeys)
1964 : : {
1965 : 2745 : List *new_mergeclauses = NIL;
1966 : : PathKey *pathkey;
1967 : : EquivalenceClass *pathkey_ec;
1968 : : bool matched_pathkey;
1969 : : ListCell *lip;
1970 : : ListCell *i;
1971 : :
1972 : : /* No pathkeys => no mergeclauses (though we don't expect this case) */
1973 [ - + ]: 2745 : if (pathkeys == NIL)
2752 tgl@sss.pgh.pa.us 1974 :UBC 0 : return NIL;
1975 : : /* Initialize to consider first pathkey */
2752 tgl@sss.pgh.pa.us 1976 :CBC 2745 : lip = list_head(pathkeys);
1977 : 2745 : pathkey = (PathKey *) lfirst(lip);
1978 : 2745 : pathkey_ec = pathkey->pk_eclass;
2245 1979 : 2745 : lip = lnext(pathkeys, lip);
2752 1980 : 2745 : matched_pathkey = false;
1981 : :
1982 : : /* Scan mergeclauses to see how many we can use */
1983 [ + - + - : 5490 : foreach(i, mergeclauses)
+ - ]
1984 : : {
1985 : 5490 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1986 : : EquivalenceClass *clause_ec;
1987 : :
1988 : : /* Assume we needn't do update_mergeclause_eclasses again here */
1989 : :
1990 : : /* Check clause's inner-rel EC against current pathkey */
1991 : 10980 : clause_ec = rinfo->outer_is_left ?
1992 [ + + ]: 5490 : rinfo->right_ec : rinfo->left_ec;
1993 : :
1994 : : /* If we don't have a match, attempt to advance to next pathkey */
1995 [ + + ]: 5490 : if (clause_ec != pathkey_ec)
1996 : : {
1997 : : /* If we had no clauses matching this inner pathkey, must stop */
1998 [ - + ]: 2745 : if (!matched_pathkey)
2752 tgl@sss.pgh.pa.us 1999 :UBC 0 : break;
2000 : :
2001 : : /* Advance to next inner pathkey, if any */
2752 tgl@sss.pgh.pa.us 2002 [ + - ]:CBC 2745 : if (lip == NULL)
2003 : 2745 : break;
2752 tgl@sss.pgh.pa.us 2004 :UBC 0 : pathkey = (PathKey *) lfirst(lip);
2005 : 0 : pathkey_ec = pathkey->pk_eclass;
2245 2006 : 0 : lip = lnext(pathkeys, lip);
2752 2007 : 0 : matched_pathkey = false;
2008 : : }
2009 : :
2010 : : /* If mergeclause matches current inner pathkey, we can use it */
2752 tgl@sss.pgh.pa.us 2011 [ + - ]:CBC 2745 : if (clause_ec == pathkey_ec)
2012 : : {
2013 : 2745 : new_mergeclauses = lappend(new_mergeclauses, rinfo);
2014 : 2745 : matched_pathkey = true;
2015 : : }
2016 : : else
2017 : : {
2018 : : /* Else, no hope of adding any more mergeclauses */
2752 tgl@sss.pgh.pa.us 2019 :UBC 0 : break;
2020 : : }
2021 : : }
2022 : :
2752 tgl@sss.pgh.pa.us 2023 :CBC 2745 : return new_mergeclauses;
2024 : : }
2025 : :
2026 : :
2027 : : /****************************************************************************
2028 : : * PATHKEY USEFULNESS CHECKS
2029 : : *
2030 : : * We only want to remember as many of the pathkeys of a path as have some
2031 : : * potential use, either for subsequent mergejoins or for meeting the query's
2032 : : * requested output ordering. This ensures that add_path() won't consider
2033 : : * a path to have a usefully different ordering unless it really is useful.
2034 : : * These routines check for usefulness of given pathkeys.
2035 : : ****************************************************************************/
2036 : :
2037 : : /*
2038 : : * pathkeys_useful_for_merging
2039 : : * Count the number of pathkeys that may be useful for mergejoins
2040 : : * above the given relation.
2041 : : *
2042 : : * We consider a pathkey potentially useful if it corresponds to the merge
2043 : : * ordering of either side of any joinclause for the rel. This might be
2044 : : * overoptimistic, since joinclauses that require different other relations
2045 : : * might never be usable at the same time, but trying to be exact is likely
2046 : : * to be more trouble than it's worth.
2047 : : *
2048 : : * To avoid doubling the number of mergejoin paths considered, we would like
2049 : : * to consider only one of the two scan directions (ASC or DESC) as useful
2050 : : * for merging for any given target column. The choice is arbitrary unless
2051 : : * one of the directions happens to match an ORDER BY key, in which case
2052 : : * that direction should be preferred, in hopes of avoiding a final sort step.
2053 : : * right_merge_direction() implements this heuristic.
2054 : : */
2055 : : static int
7398 2056 : 1392843 : pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
2057 : : {
9032 2058 : 1392843 : int useful = 0;
2059 : : ListCell *i;
2060 : :
2061 [ + + + + : 1706718 : foreach(i, pathkeys)
+ + ]
2062 : : {
6505 bruce@momjian.us 2063 : 864341 : PathKey *pathkey = (PathKey *) lfirst(i);
9032 tgl@sss.pgh.pa.us 2064 : 864341 : bool matched = false;
2065 : : ListCell *j;
2066 : :
2067 : : /* If "wrong" direction, not useful for merging */
6524 2068 [ + + ]: 864341 : if (!right_merge_direction(root, pathkey))
2069 : 158921 : break;
2070 : :
2071 : : /*
2072 : : * First look into the EquivalenceClass of the pathkey, to see if
2073 : : * there are any members not yet joined to the rel. If so, it's
2074 : : * surely possible to generate a mergejoin clause using them.
2075 : : */
6804 2076 [ + + + + ]: 1089927 : if (rel->has_eclass_joins &&
3684 2077 : 384507 : eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
6804 2078 : 217956 : matched = true;
2079 : : else
2080 : : {
2081 : : /*
2082 : : * Otherwise search the rel's joininfo list, which contains
2083 : : * non-EquivalenceClass-derivable join clauses that might
2084 : : * nonetheless be mergejoinable.
2085 : : */
2086 [ + + + + : 743271 : foreach(j, rel->joininfo)
+ + ]
2087 : : {
2088 : 351726 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
2089 : :
2090 [ + + ]: 351726 : if (restrictinfo->mergeopfamilies == NIL)
2091 : 76911 : continue;
5426 2092 : 274815 : update_mergeclause_eclasses(root, restrictinfo);
2093 : :
6804 2094 [ + + ]: 274815 : if (pathkey->pk_eclass == restrictinfo->left_ec ||
2095 [ + + ]: 223673 : pathkey->pk_eclass == restrictinfo->right_ec)
2096 : : {
2097 : 95919 : matched = true;
2098 : 95919 : break;
2099 : : }
2100 : : }
2101 : : }
2102 : :
2103 : : /*
2104 : : * If we didn't find a mergeclause, we're done --- any additional
2105 : : * sort-key positions in the pathkeys are useless. (But we can still
2106 : : * mergejoin if we found at least one mergeclause.)
2107 : : */
9032 2108 [ + + ]: 705420 : if (matched)
2109 : 313875 : useful++;
2110 : : else
2111 : 391545 : break;
2112 : : }
2113 : :
2114 : 1392843 : return useful;
2115 : : }
2116 : :
2117 : : /*
2118 : : * right_merge_direction
2119 : : * Check whether the pathkey embodies the preferred sort direction
2120 : : * for merging its target column.
2121 : : */
2122 : : static bool
6505 bruce@momjian.us 2123 : 864341 : right_merge_direction(PlannerInfo *root, PathKey *pathkey)
2124 : : {
2125 : : ListCell *l;
2126 : :
6524 tgl@sss.pgh.pa.us 2127 [ + + + + : 1634170 : foreach(l, root->query_pathkeys)
+ + ]
2128 : : {
6505 bruce@momjian.us 2129 : 967234 : PathKey *query_pathkey = (PathKey *) lfirst(l);
2130 : :
6524 tgl@sss.pgh.pa.us 2131 [ + + ]: 967234 : if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
2132 [ + - ]: 197405 : pathkey->pk_opfamily == query_pathkey->pk_opfamily)
2133 : : {
2134 : : /*
2135 : : * Found a matching query sort column. Prefer this pathkey's
2136 : : * direction iff it matches. Note that we ignore pk_nulls_first,
2137 : : * which means that a sort might be needed anyway ... but we still
2138 : : * want to prefer only one of the two possible directions, and we
2139 : : * might as well use this one.
2140 : : */
155 peter@eisentraut.org 2141 : 197405 : return (pathkey->pk_cmptype == query_pathkey->pk_cmptype);
2142 : : }
2143 : : }
2144 : :
2145 : : /* If no matching ORDER BY request, prefer the ASC direction */
2146 : 666936 : return (pathkey->pk_cmptype == COMPARE_LT);
2147 : : }
2148 : :
2149 : : /*
2150 : : * pathkeys_useful_for_ordering
2151 : : * Count the number of pathkeys that are useful for meeting the
2152 : : * query's requested output ordering.
2153 : : *
2154 : : * Because we the have the possibility of incremental sort, a prefix list of
2155 : : * keys is potentially useful for improving the performance of the requested
2156 : : * ordering. Thus we return 0, if no valuable keys are found, or the number
2157 : : * of leading keys shared by the list and the requested ordering..
2158 : : */
2159 : : static int
7398 tgl@sss.pgh.pa.us 2160 : 1392843 : pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
2161 : : {
2162 : : int n_common_pathkeys;
2163 : :
1979 tomas.vondra@postgre 2164 : 1392843 : (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
2165 : : &n_common_pathkeys);
2166 : :
2167 : 1392843 : return n_common_pathkeys;
2168 : : }
2169 : :
2170 : : /*
2171 : : * pathkeys_useful_for_grouping
2172 : : * Count the number of pathkeys that are useful for grouping (instead of
2173 : : * explicit sort)
2174 : : *
2175 : : * Group pathkeys could be reordered to benefit from the ordering. The
2176 : : * ordering may not be "complete" and may require incremental sort, but that's
2177 : : * fine. So we simply count prefix pathkeys with a matching group key, and
2178 : : * stop once we find the first pathkey without a match.
2179 : : *
2180 : : * So e.g. with pathkeys (a,b,c) and group keys (a,b,e) this determines (a,b)
2181 : : * pathkeys are useful for grouping, and we might do incremental sort to get
2182 : : * path ordered by (a,b,e).
2183 : : *
2184 : : * This logic is necessary to retain paths with ordering not matching grouping
2185 : : * keys directly, without the reordering.
2186 : : *
2187 : : * Returns the length of pathkey prefix with matching group keys.
2188 : : */
2189 : : static int
594 akorotkov@postgresql 2190 : 1392843 : pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
2191 : : {
2192 : : ListCell *key;
2193 : 1392843 : int n = 0;
2194 : :
2195 : : /* no special ordering requested for grouping */
2196 [ + + ]: 1392843 : if (root->group_pathkeys == NIL)
2197 : 1379329 : return 0;
2198 : :
2199 : : /* walk the pathkeys and search for matching group key */
2200 [ + + + + : 16773 : foreach(key, pathkeys)
+ + ]
2201 : : {
2202 : 6707 : PathKey *pathkey = (PathKey *) lfirst(key);
2203 : :
2204 : : /* no matching group key, we're done */
2205 [ + + ]: 6707 : if (!list_member_ptr(root->group_pathkeys, pathkey))
2206 : 3448 : break;
2207 : :
2208 : 3259 : n++;
2209 : : }
2210 : :
2211 : 13514 : return n;
2212 : : }
2213 : :
2214 : : /*
2215 : : * pathkeys_useful_for_distinct
2216 : : * Count the number of pathkeys that are useful for DISTINCT or DISTINCT
2217 : : * ON clause.
2218 : : *
2219 : : * DISTINCT keys could be reordered to benefit from the given pathkey list. As
2220 : : * with pathkeys_useful_for_grouping, we return the number of leading keys in
2221 : : * the list that are shared by the distinctClause pathkeys.
2222 : : */
2223 : : static int
284 rguo@postgresql.org 2224 : 1392843 : pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
2225 : : {
2226 : : int n_common_pathkeys;
2227 : :
2228 : : /*
2229 : : * distinct_pathkeys may have become empty if all of the pathkeys were
2230 : : * determined to be redundant. Return 0 in this case.
2231 : : */
2232 [ + + ]: 1392843 : if (root->distinct_pathkeys == NIL)
2233 : 1361592 : return 0;
2234 : :
2235 : : /* walk the pathkeys and search for matching DISTINCT key */
2236 : 31251 : n_common_pathkeys = 0;
2237 [ + + + + : 66459 : foreach_node(PathKey, pathkey, pathkeys)
+ + ]
2238 : : {
2239 : : /* no matching DISTINCT key, we're done */
2240 [ + + ]: 21188 : if (!list_member_ptr(root->distinct_pathkeys, pathkey))
2241 : 17231 : break;
2242 : :
2243 : 3957 : n_common_pathkeys++;
2244 : : }
2245 : :
2246 : 31251 : return n_common_pathkeys;
2247 : : }
2248 : :
2249 : : /*
2250 : : * pathkeys_useful_for_setop
2251 : : * Count the number of leading common pathkeys root's 'setop_pathkeys' in
2252 : : * 'pathkeys'.
2253 : : */
2254 : : static int
473 rhaas@postgresql.org 2255 : 1392843 : pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
2256 : : {
2257 : : int n_common_pathkeys;
2258 : :
2259 : 1392843 : (void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
2260 : : &n_common_pathkeys);
2261 : :
2262 : 1392843 : return n_common_pathkeys;
2263 : : }
2264 : :
2265 : : /*
2266 : : * truncate_useless_pathkeys
2267 : : * Shorten the given pathkey list to just the useful pathkeys.
2268 : : */
2269 : : List *
7398 tgl@sss.pgh.pa.us 2270 : 1392843 : truncate_useless_pathkeys(PlannerInfo *root,
2271 : : RelOptInfo *rel,
2272 : : List *pathkeys)
2273 : : {
2274 : : int nuseful;
2275 : : int nuseful2;
2276 : :
9032 2277 : 1392843 : nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2278 : 1392843 : nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
594 akorotkov@postgresql 2279 [ + + ]: 1392843 : if (nuseful2 > nuseful)
2280 : 92433 : nuseful = nuseful2;
2281 : 1392843 : nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
284 rguo@postgresql.org 2282 [ + + ]: 1392843 : if (nuseful2 > nuseful)
2283 : 208 : nuseful = nuseful2;
2284 : 1392843 : nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
473 rhaas@postgresql.org 2285 [ + + ]: 1392843 : if (nuseful2 > nuseful)
2286 : 1662 : nuseful = nuseful2;
2287 : 1392843 : nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
9032 tgl@sss.pgh.pa.us 2288 [ - + ]: 1392843 : if (nuseful2 > nuseful)
9032 tgl@sss.pgh.pa.us 2289 :UBC 0 : nuseful = nuseful2;
2290 : :
2291 : : /*
2292 : : * Note: not safe to modify input list destructively, but we can avoid
2293 : : * copying the list if we're not actually going to change it
2294 : : */
6719 tgl@sss.pgh.pa.us 2295 [ + + ]:CBC 1392843 : if (nuseful == 0)
2296 : 1016122 : return NIL;
2297 [ + + ]: 376721 : else if (nuseful == list_length(pathkeys))
9032 2298 : 358493 : return pathkeys;
2299 : : else
1151 drowley@postgresql.o 2300 : 18228 : return list_copy_head(pathkeys, nuseful);
2301 : : }
2302 : :
2303 : : /*
2304 : : * has_useful_pathkeys
2305 : : * Detect whether the specified rel could have any pathkeys that are
2306 : : * useful according to truncate_useless_pathkeys().
2307 : : *
2308 : : * This is a cheap test that lets us skip building pathkeys at all in very
2309 : : * simple queries. It's OK to err in the direction of returning "true" when
2310 : : * there really aren't any usable pathkeys, but erring in the other direction
2311 : : * is bad --- so keep this in sync with the routines above!
2312 : : *
2313 : : * We could make the test more complex, for example checking to see if any of
2314 : : * the joinclauses are really mergejoinable, but that likely wouldn't win
2315 : : * often enough to repay the extra cycles. Queries with neither a join nor
2316 : : * a sort are reasonably common, though, so this much work seems worthwhile.
2317 : : */
2318 : : bool
6719 tgl@sss.pgh.pa.us 2319 : 437514 : has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
2320 : : {
2321 [ + + + + ]: 437514 : if (rel->joininfo != NIL || rel->has_eclass_joins)
2322 : 271841 : return true; /* might be able to use pathkeys for merging */
594 akorotkov@postgresql 2323 [ + + ]: 165673 : if (root->group_pathkeys != NIL)
2324 : 3422 : return true; /* might be able to use pathkeys for grouping */
6719 tgl@sss.pgh.pa.us 2325 [ + + ]: 162251 : if (root->query_pathkeys != NIL)
2326 : 45697 : return true; /* might be able to use them for ordering */
2327 : 116554 : return false; /* definitely useless */
2328 : : }
|
