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-2023, 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/makefuncs.h"
23 : #include "nodes/nodeFuncs.h"
24 : #include "nodes/plannodes.h"
25 : #include "optimizer/optimizer.h"
26 : #include "optimizer/pathnode.h"
27 : #include "optimizer/paths.h"
28 : #include "partitioning/partbounds.h"
29 : #include "utils/lsyscache.h"
30 :
31 :
32 : static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
33 : static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
34 : RelOptInfo *partrel,
35 : int partkeycol);
36 : static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
37 : static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
38 :
39 :
40 : /****************************************************************************
41 : * PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
42 : ****************************************************************************/
43 :
44 : /*
45 : * make_canonical_pathkey
46 : * Given the parameters for a PathKey, find any pre-existing matching
47 : * pathkey in the query's list of "canonical" pathkeys. Make a new
48 : * entry if there's not one already.
49 : *
50 : * Note that this function must not be used until after we have completed
51 : * merging EquivalenceClasses.
52 : */
53 : PathKey *
54 1629346 : make_canonical_pathkey(PlannerInfo *root,
55 : EquivalenceClass *eclass, Oid opfamily,
56 : int strategy, bool nulls_first)
57 : {
58 : PathKey *pk;
59 : ListCell *lc;
60 : MemoryContext oldcontext;
61 :
62 : /* Can't make canonical pathkeys if the set of ECs might still change */
63 1629346 : if (!root->ec_merging_done)
64 0 : elog(ERROR, "too soon to build canonical pathkeys");
65 :
66 : /* The passed eclass might be non-canonical, so chase up to the top */
67 1629346 : while (eclass->ec_merged)
68 0 : eclass = eclass->ec_merged;
69 :
70 8067854 : foreach(lc, root->canon_pathkeys)
71 : {
72 7612306 : pk = (PathKey *) lfirst(lc);
73 7612306 : if (eclass == pk->pk_eclass &&
74 1560034 : opfamily == pk->pk_opfamily &&
75 1560034 : strategy == pk->pk_strategy &&
76 1173852 : nulls_first == pk->pk_nulls_first)
77 1173798 : return pk;
78 : }
79 :
80 : /*
81 : * Be sure canonical pathkeys are allocated in the main planning context.
82 : * Not an issue in normal planning, but it is for GEQO.
83 : */
84 455548 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
85 :
86 455548 : pk = makeNode(PathKey);
87 455548 : pk->pk_eclass = eclass;
88 455548 : pk->pk_opfamily = opfamily;
89 455548 : pk->pk_strategy = strategy;
90 455548 : pk->pk_nulls_first = nulls_first;
91 :
92 455548 : root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
93 :
94 455548 : MemoryContextSwitchTo(oldcontext);
95 :
96 455548 : return pk;
97 : }
98 :
99 : /*
100 : * append_pathkeys
101 : * Append all non-redundant PathKeys in 'source' onto 'target' and
102 : * returns the updated 'target' list.
103 : */
104 : List *
105 1414 : append_pathkeys(List *target, List *source)
106 : {
107 : ListCell *lc;
108 :
109 : Assert(target != NIL);
110 :
111 2882 : foreach(lc, source)
112 : {
113 1468 : PathKey *pk = lfirst_node(PathKey, lc);
114 :
115 1468 : if (!pathkey_is_redundant(pk, target))
116 1330 : target = lappend(target, pk);
117 : }
118 1414 : return target;
119 : }
120 :
121 : /*
122 : * pathkey_is_redundant
123 : * Is a pathkey redundant with one already in the given list?
124 : *
125 : * We detect two cases:
126 : *
127 : * 1. If the new pathkey's equivalence class contains a constant, and isn't
128 : * below an outer join, then we can disregard it as a sort key. An example:
129 : * SELECT ... WHERE x = 42 ORDER BY x, y;
130 : * We may as well just sort by y. Note that because of opfamily matching,
131 : * this is semantically correct: we know that the equality constraint is one
132 : * that actually binds the variable to a single value in the terms of any
133 : * ordering operator that might go with the eclass. This rule not only lets
134 : * us simplify (or even skip) explicit sorts, but also allows matching index
135 : * sort orders to a query when there are don't-care index columns.
136 : *
137 : * 2. If the new pathkey's equivalence class is the same as that of any
138 : * existing member of the pathkey list, then it is redundant. Some examples:
139 : * SELECT ... ORDER BY x, x;
140 : * SELECT ... ORDER BY x, x DESC;
141 : * SELECT ... WHERE x = y ORDER BY x, y;
142 : * In all these cases the second sort key cannot distinguish values that are
143 : * considered equal by the first, and so there's no point in using it.
144 : * Note in particular that we need not compare opfamily (all the opfamilies
145 : * of the EC have the same notion of equality) nor sort direction.
146 : *
147 : * Both the given pathkey and the list members must be canonical for this
148 : * to work properly, but that's okay since we no longer ever construct any
149 : * non-canonical pathkeys. (Note: the notion of a pathkey *list* being
150 : * canonical includes the additional requirement of no redundant entries,
151 : * which is exactly what we are checking for here.)
152 : *
153 : * Because the equivclass.c machinery forms only one copy of any EC per query,
154 : * pointer comparison is enough to decide whether canonical ECs are the same.
155 : */
156 : static bool
157 1730248 : pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
158 : {
159 1730248 : EquivalenceClass *new_ec = new_pathkey->pk_eclass;
160 : ListCell *lc;
161 :
162 : /* Check for EC containing a constant --- unconditionally redundant */
163 1730248 : if (EC_MUST_BE_REDUNDANT(new_ec))
164 229404 : return true;
165 :
166 : /* If same EC already used in list, then redundant */
167 1691036 : foreach(lc, pathkeys)
168 : {
169 190842 : PathKey *old_pathkey = (PathKey *) lfirst(lc);
170 :
171 190842 : if (new_ec == old_pathkey->pk_eclass)
172 650 : return true;
173 : }
174 :
175 1500194 : return false;
176 : }
177 :
178 : /*
179 : * make_pathkey_from_sortinfo
180 : * Given an expression and sort-order information, create a PathKey.
181 : * The result is always a "canonical" PathKey, but it might be redundant.
182 : *
183 : * If the PathKey is being generated from a SortGroupClause, sortref should be
184 : * the SortGroupClause's SortGroupRef; otherwise zero.
185 : *
186 : * If rel is not NULL, it identifies a specific relation we're considering
187 : * a path for, and indicates that child EC members for that relation can be
188 : * considered. Otherwise child members are ignored. (See the comments for
189 : * get_eclass_for_sort_expr.)
190 : *
191 : * create_it is true if we should create any missing EquivalenceClass
192 : * needed to represent the sort key. If it's false, we return NULL if the
193 : * sort key isn't already present in any EquivalenceClass.
194 : */
195 : static PathKey *
196 1356360 : make_pathkey_from_sortinfo(PlannerInfo *root,
197 : Expr *expr,
198 : Oid opfamily,
199 : Oid opcintype,
200 : Oid collation,
201 : bool reverse_sort,
202 : bool nulls_first,
203 : Index sortref,
204 : Relids rel,
205 : bool create_it)
206 : {
207 : int16 strategy;
208 : Oid equality_op;
209 : List *opfamilies;
210 : EquivalenceClass *eclass;
211 :
212 1356360 : strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
213 :
214 : /*
215 : * EquivalenceClasses need to contain opfamily lists based on the family
216 : * membership of mergejoinable equality operators, which could belong to
217 : * more than one opfamily. So we have to look up the opfamily's equality
218 : * operator and get its membership.
219 : */
220 1356360 : equality_op = get_opfamily_member(opfamily,
221 : opcintype,
222 : opcintype,
223 : BTEqualStrategyNumber);
224 1356360 : if (!OidIsValid(equality_op)) /* shouldn't happen */
225 0 : elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
226 : BTEqualStrategyNumber, opcintype, opcintype, opfamily);
227 1356360 : opfamilies = get_mergejoin_opfamilies(equality_op);
228 1356360 : if (!opfamilies) /* certainly should find some */
229 0 : elog(ERROR, "could not find opfamilies for equality operator %u",
230 : equality_op);
231 :
232 : /* Now find or (optionally) create a matching EquivalenceClass */
233 1356360 : eclass = get_eclass_for_sort_expr(root, expr,
234 : opfamilies, opcintype, collation,
235 : sortref, rel, create_it);
236 :
237 : /* Fail if no EC and !create_it */
238 1356360 : if (!eclass)
239 490342 : return NULL;
240 :
241 : /* And finally we can find or create a PathKey node */
242 866018 : return make_canonical_pathkey(root, eclass, opfamily,
243 : strategy, nulls_first);
244 : }
245 :
246 : /*
247 : * make_pathkey_from_sortop
248 : * Like make_pathkey_from_sortinfo, but work from a sort operator.
249 : *
250 : * This should eventually go away, but we need to restructure SortGroupClause
251 : * first.
252 : */
253 : static PathKey *
254 93836 : make_pathkey_from_sortop(PlannerInfo *root,
255 : Expr *expr,
256 : Oid ordering_op,
257 : bool nulls_first,
258 : Index sortref,
259 : bool create_it)
260 : {
261 : Oid opfamily,
262 : opcintype,
263 : collation;
264 : int16 strategy;
265 :
266 : /* Find the operator in pg_amop --- failure shouldn't happen */
267 93836 : if (!get_ordering_op_properties(ordering_op,
268 : &opfamily, &opcintype, &strategy))
269 0 : elog(ERROR, "operator %u is not a valid ordering operator",
270 : ordering_op);
271 :
272 : /* Because SortGroupClause doesn't carry collation, consult the expr */
273 93836 : collation = exprCollation((Node *) expr);
274 :
275 93836 : return make_pathkey_from_sortinfo(root,
276 : expr,
277 : opfamily,
278 : opcintype,
279 : collation,
280 : (strategy == BTGreaterStrategyNumber),
281 : nulls_first,
282 : sortref,
283 : NULL,
284 : create_it);
285 : }
286 :
287 :
288 : /****************************************************************************
289 : * PATHKEY COMPARISONS
290 : ****************************************************************************/
291 :
292 : /*
293 : * compare_pathkeys
294 : * Compare two pathkeys to see if they are equivalent, and if not whether
295 : * one is "better" than the other.
296 : *
297 : * We assume the pathkeys are canonical, and so they can be checked for
298 : * equality by simple pointer comparison.
299 : */
300 : PathKeysComparison
301 8992996 : compare_pathkeys(List *keys1, List *keys2)
302 : {
303 : ListCell *key1,
304 : *key2;
305 :
306 : /*
307 : * Fall out quickly if we are passed two identical lists. This mostly
308 : * catches the case where both are NIL, but that's common enough to
309 : * warrant the test.
310 : */
311 8992996 : if (keys1 == keys2)
312 3515690 : return PATHKEYS_EQUAL;
313 :
314 6817966 : forboth(key1, keys1, key2, keys2)
315 : {
316 1897774 : PathKey *pathkey1 = (PathKey *) lfirst(key1);
317 1897774 : PathKey *pathkey2 = (PathKey *) lfirst(key2);
318 :
319 1897774 : if (pathkey1 != pathkey2)
320 557114 : return PATHKEYS_DIFFERENT; /* no need to keep looking */
321 : }
322 :
323 : /*
324 : * If we reached the end of only one list, the other is longer and
325 : * therefore not a subset.
326 : */
327 4920192 : if (key1 != NULL)
328 3358378 : return PATHKEYS_BETTER1; /* key1 is longer */
329 1561814 : if (key2 != NULL)
330 477486 : return PATHKEYS_BETTER2; /* key2 is longer */
331 1084328 : return PATHKEYS_EQUAL;
332 : }
333 :
334 : /*
335 : * pathkeys_contained_in
336 : * Common special case of compare_pathkeys: we just want to know
337 : * if keys2 are at least as well sorted as keys1.
338 : */
339 : bool
340 3230018 : pathkeys_contained_in(List *keys1, List *keys2)
341 : {
342 3230018 : switch (compare_pathkeys(keys1, keys2))
343 : {
344 798678 : case PATHKEYS_EQUAL:
345 : case PATHKEYS_BETTER2:
346 798678 : return true;
347 2431340 : default:
348 2431340 : break;
349 : }
350 2431340 : return false;
351 : }
352 :
353 : /*
354 : * pathkeys_count_contained_in
355 : * Same as pathkeys_contained_in, but also sets length of longest
356 : * common prefix of keys1 and keys2.
357 : */
358 : bool
359 794008 : pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
360 : {
361 794008 : int n = 0;
362 : ListCell *key1,
363 : *key2;
364 :
365 : /*
366 : * See if we can avoiding looping through both lists. This optimization
367 : * gains us several percent in planning time in a worst-case test.
368 : */
369 794008 : if (keys1 == keys2)
370 : {
371 35696 : *n_common = list_length(keys1);
372 35696 : return true;
373 : }
374 758312 : else if (keys1 == NIL)
375 : {
376 28 : *n_common = 0;
377 28 : return true;
378 : }
379 758284 : else if (keys2 == NIL)
380 : {
381 63692 : *n_common = 0;
382 63692 : return false;
383 : }
384 :
385 : /*
386 : * If both lists are non-empty, iterate through both to find out how many
387 : * items are shared.
388 : */
389 920852 : forboth(key1, keys1, key2, keys2)
390 : {
391 723502 : PathKey *pathkey1 = (PathKey *) lfirst(key1);
392 723502 : PathKey *pathkey2 = (PathKey *) lfirst(key2);
393 :
394 723502 : if (pathkey1 != pathkey2)
395 : {
396 497242 : *n_common = n;
397 497242 : return false;
398 : }
399 226260 : n++;
400 : }
401 :
402 : /* If we ended with a null value, then we've processed the whole list. */
403 197350 : *n_common = n;
404 197350 : return (key1 == NULL);
405 : }
406 :
407 : /*
408 : * get_cheapest_path_for_pathkeys
409 : * Find the cheapest path (according to the specified criterion) that
410 : * satisfies the given pathkeys and parameterization, and is parallel-safe
411 : * if required.
412 : * Return NULL if no such path.
413 : *
414 : * 'paths' is a list of possible paths that all generate the same relation
415 : * 'pathkeys' represents a required ordering (in canonical form!)
416 : * 'required_outer' denotes allowable outer relations for parameterized paths
417 : * 'cost_criterion' is STARTUP_COST or TOTAL_COST
418 : * 'require_parallel_safe' causes us to consider only parallel-safe paths
419 : */
420 : Path *
421 677896 : get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
422 : Relids required_outer,
423 : CostSelector cost_criterion,
424 : bool require_parallel_safe)
425 : {
426 677896 : Path *matched_path = NULL;
427 : ListCell *l;
428 :
429 2384490 : foreach(l, paths)
430 : {
431 1706594 : Path *path = (Path *) lfirst(l);
432 :
433 : /* If required, reject paths that are not parallel-safe */
434 1706594 : if (require_parallel_safe && !path->parallel_safe)
435 264 : continue;
436 :
437 : /*
438 : * Since cost comparison is a lot cheaper than pathkey comparison, do
439 : * that first. (XXX is that still true?)
440 : */
441 1776848 : if (matched_path != NULL &&
442 70518 : compare_path_costs(matched_path, path, cost_criterion) <= 0)
443 60550 : continue;
444 :
445 2369012 : if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
446 723232 : bms_is_subset(PATH_REQ_OUTER(path), required_outer))
447 442528 : matched_path = path;
448 : }
449 677896 : return matched_path;
450 : }
451 :
452 : /*
453 : * get_cheapest_fractional_path_for_pathkeys
454 : * Find the cheapest path (for retrieving a specified fraction of all
455 : * the tuples) that satisfies the given pathkeys and parameterization.
456 : * Return NULL if no such path.
457 : *
458 : * See compare_fractional_path_costs() for the interpretation of the fraction
459 : * parameter.
460 : *
461 : * 'paths' is a list of possible paths that all generate the same relation
462 : * 'pathkeys' represents a required ordering (in canonical form!)
463 : * 'required_outer' denotes allowable outer relations for parameterized paths
464 : * 'fraction' is the fraction of the total tuples expected to be retrieved
465 : */
466 : Path *
467 1636 : get_cheapest_fractional_path_for_pathkeys(List *paths,
468 : List *pathkeys,
469 : Relids required_outer,
470 : double fraction)
471 : {
472 1636 : Path *matched_path = NULL;
473 : ListCell *l;
474 :
475 4488 : foreach(l, paths)
476 : {
477 2852 : Path *path = (Path *) lfirst(l);
478 :
479 : /*
480 : * Since cost comparison is a lot cheaper than pathkey comparison, do
481 : * that first. (XXX is that still true?)
482 : */
483 3222 : if (matched_path != NULL &&
484 370 : compare_fractional_path_costs(matched_path, path, fraction) <= 0)
485 184 : continue;
486 :
487 3784 : if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
488 1116 : bms_is_subset(PATH_REQ_OUTER(path), required_outer))
489 1076 : matched_path = path;
490 : }
491 1636 : return matched_path;
492 : }
493 :
494 :
495 : /*
496 : * get_cheapest_parallel_safe_total_inner
497 : * Find the unparameterized parallel-safe path with the least total cost.
498 : */
499 : Path *
500 47964 : get_cheapest_parallel_safe_total_inner(List *paths)
501 : {
502 : ListCell *l;
503 :
504 54286 : foreach(l, paths)
505 : {
506 53544 : Path *innerpath = (Path *) lfirst(l);
507 :
508 53544 : if (innerpath->parallel_safe &&
509 51698 : bms_is_empty(PATH_REQ_OUTER(innerpath)))
510 47222 : return innerpath;
511 : }
512 :
513 742 : return NULL;
514 : }
515 :
516 : /****************************************************************************
517 : * NEW PATHKEY FORMATION
518 : ****************************************************************************/
519 :
520 : /*
521 : * build_index_pathkeys
522 : * Build a pathkeys list that describes the ordering induced by an index
523 : * scan using the given index. (Note that an unordered index doesn't
524 : * induce any ordering, so we return NIL.)
525 : *
526 : * If 'scandir' is BackwardScanDirection, build pathkeys representing a
527 : * backwards scan of the index.
528 : *
529 : * We iterate only key columns of covering indexes, since non-key columns
530 : * don't influence index ordering. The result is canonical, meaning that
531 : * redundant pathkeys are removed; it may therefore have fewer entries than
532 : * there are key columns in the index.
533 : *
534 : * Another reason for stopping early is that we may be able to tell that
535 : * an index column's sort order is uninteresting for this query. However,
536 : * that test is just based on the existence of an EquivalenceClass and not
537 : * on position in pathkey lists, so it's not complete. Caller should call
538 : * truncate_useless_pathkeys() to possibly remove more pathkeys.
539 : */
540 : List *
541 972560 : build_index_pathkeys(PlannerInfo *root,
542 : IndexOptInfo *index,
543 : ScanDirection scandir)
544 : {
545 972560 : List *retval = NIL;
546 : ListCell *lc;
547 : int i;
548 :
549 972560 : if (index->sortopfamily == NULL)
550 0 : return NIL; /* non-orderable index */
551 :
552 972560 : i = 0;
553 1714504 : foreach(lc, index->indextlist)
554 : {
555 1217696 : TargetEntry *indextle = (TargetEntry *) lfirst(lc);
556 : Expr *indexkey;
557 : bool reverse_sort;
558 : bool nulls_first;
559 : PathKey *cpathkey;
560 :
561 : /*
562 : * INCLUDE columns are stored in index unordered, so they don't
563 : * support ordered index scan.
564 : */
565 1217696 : if (i >= index->nkeycolumns)
566 0 : break;
567 :
568 : /* We assume we don't need to make a copy of the tlist item */
569 1217696 : indexkey = indextle->expr;
570 :
571 1217696 : if (ScanDirectionIsBackward(scandir))
572 : {
573 608848 : reverse_sort = !index->reverse_sort[i];
574 608848 : nulls_first = !index->nulls_first[i];
575 : }
576 : else
577 : {
578 608848 : reverse_sort = index->reverse_sort[i];
579 608848 : nulls_first = index->nulls_first[i];
580 : }
581 :
582 : /*
583 : * OK, try to make a canonical pathkey for this sort key.
584 : */
585 1217696 : cpathkey = make_pathkey_from_sortinfo(root,
586 : indexkey,
587 1217696 : index->sortopfamily[i],
588 1217696 : index->opcintype[i],
589 1217696 : index->indexcollations[i],
590 : reverse_sort,
591 : nulls_first,
592 : 0,
593 1217696 : index->rel->relids,
594 : false);
595 :
596 1217696 : if (cpathkey)
597 : {
598 : /*
599 : * We found the sort key in an EquivalenceClass, so it's relevant
600 : * for this query. Add it to list, unless it's redundant.
601 : */
602 741836 : if (!pathkey_is_redundant(cpathkey, retval))
603 532892 : retval = lappend(retval, cpathkey);
604 : }
605 : else
606 : {
607 : /*
608 : * Boolean index keys might be redundant even if they do not
609 : * appear in an EquivalenceClass, because of our special treatment
610 : * of boolean equality conditions --- see the comment for
611 : * indexcol_is_bool_constant_for_query(). If that applies, we can
612 : * continue to examine lower-order index columns. Otherwise, the
613 : * sort key is not an interesting sort order for this query, so we
614 : * should stop considering index columns; any lower-order sort
615 : * keys won't be useful either.
616 : */
617 475860 : if (!indexcol_is_bool_constant_for_query(root, index, i))
618 475752 : break;
619 : }
620 :
621 741944 : i++;
622 : }
623 :
624 972560 : return retval;
625 : }
626 :
627 : /*
628 : * partkey_is_bool_constant_for_query
629 : *
630 : * If a partition key column is constrained to have a constant value by the
631 : * query's WHERE conditions, then it's irrelevant for sort-order
632 : * considerations. Usually that means we have a restriction clause
633 : * WHERE partkeycol = constant, which gets turned into an EquivalenceClass
634 : * containing a constant, which is recognized as redundant by
635 : * build_partition_pathkeys(). But if the partition key column is a
636 : * boolean variable (or expression), then we are not going to see such a
637 : * WHERE clause, because expression preprocessing will have simplified it
638 : * to "WHERE partkeycol" or "WHERE NOT partkeycol". So we are not going
639 : * to have a matching EquivalenceClass (unless the query also contains
640 : * "ORDER BY partkeycol"). To allow such cases to work the same as they would
641 : * for non-boolean values, this function is provided to detect whether the
642 : * specified partition key column matches a boolean restriction clause.
643 : */
644 : static bool
645 14128 : partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
646 : {
647 14128 : PartitionScheme partscheme = partrel->part_scheme;
648 : ListCell *lc;
649 :
650 : /*
651 : * If the partkey isn't boolean, we can't possibly get a match.
652 : *
653 : * Partitioning currently can only use built-in AMs, so checking for
654 : * built-in boolean opfamilies is good enough.
655 : */
656 14128 : if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
657 13792 : return false;
658 :
659 : /* Check each restriction clause for the partitioned rel */
660 456 : foreach(lc, partrel->baserestrictinfo)
661 : {
662 360 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
663 :
664 : /* Ignore pseudoconstant quals, they won't match */
665 360 : if (rinfo->pseudoconstant)
666 0 : continue;
667 :
668 : /* See if we can match the clause's expression to the partkey column */
669 360 : if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
670 240 : return true;
671 : }
672 :
673 96 : return false;
674 : }
675 :
676 : /*
677 : * matches_boolean_partition_clause
678 : * Determine if the boolean clause described by rinfo matches
679 : * partrel's partkeycol-th partition key column.
680 : *
681 : * "Matches" can be either an exact match (equivalent to partkey = true),
682 : * or a NOT above an exact match (equivalent to partkey = false).
683 : */
684 : static bool
685 360 : matches_boolean_partition_clause(RestrictInfo *rinfo,
686 : RelOptInfo *partrel, int partkeycol)
687 : {
688 360 : Node *clause = (Node *) rinfo->clause;
689 360 : Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
690 :
691 : /* Direct match? */
692 360 : if (equal(partexpr, clause))
693 120 : return true;
694 : /* NOT clause? */
695 240 : else if (is_notclause(clause))
696 : {
697 144 : Node *arg = (Node *) get_notclausearg((Expr *) clause);
698 :
699 144 : if (equal(partexpr, arg))
700 120 : return true;
701 : }
702 :
703 120 : return false;
704 : }
705 :
706 : /*
707 : * build_partition_pathkeys
708 : * Build a pathkeys list that describes the ordering induced by the
709 : * partitions of partrel, under either forward or backward scan
710 : * as per scandir.
711 : *
712 : * Caller must have checked that the partitions are properly ordered,
713 : * as detected by partitions_are_ordered().
714 : *
715 : * Sets *partialkeys to true if pathkeys were only built for a prefix of the
716 : * partition key, or false if the pathkeys include all columns of the
717 : * partition key.
718 : */
719 : List *
720 42452 : build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
721 : ScanDirection scandir, bool *partialkeys)
722 : {
723 42452 : List *retval = NIL;
724 42452 : PartitionScheme partscheme = partrel->part_scheme;
725 : int i;
726 :
727 : Assert(partscheme != NULL);
728 : Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
729 : /* For now, we can only cope with baserels */
730 : Assert(IS_SIMPLE_REL(partrel));
731 :
732 72780 : for (i = 0; i < partscheme->partnatts; i++)
733 : {
734 : PathKey *cpathkey;
735 44216 : Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
736 :
737 : /*
738 : * Try to make a canonical pathkey for this partkey.
739 : *
740 : * We assume the PartitionDesc lists any NULL partition last, so we
741 : * treat the scan like a NULLS LAST index: we have nulls_first for
742 : * backwards scan only.
743 : */
744 44216 : cpathkey = make_pathkey_from_sortinfo(root,
745 : keyCol,
746 44216 : partscheme->partopfamily[i],
747 44216 : partscheme->partopcintype[i],
748 44216 : partscheme->partcollation[i],
749 : ScanDirectionIsBackward(scandir),
750 : ScanDirectionIsBackward(scandir),
751 : 0,
752 : partrel->relids,
753 : false);
754 :
755 :
756 44216 : if (cpathkey)
757 : {
758 : /*
759 : * We found the sort key in an EquivalenceClass, so it's relevant
760 : * for this query. Add it to list, unless it's redundant.
761 : */
762 30088 : if (!pathkey_is_redundant(cpathkey, retval))
763 10720 : retval = lappend(retval, cpathkey);
764 : }
765 : else
766 : {
767 : /*
768 : * Boolean partition keys might be redundant even if they do not
769 : * appear in an EquivalenceClass, because of our special treatment
770 : * of boolean equality conditions --- see the comment for
771 : * partkey_is_bool_constant_for_query(). If that applies, we can
772 : * continue to examine lower-order partition keys. Otherwise, the
773 : * sort key is not an interesting sort order for this query, so we
774 : * should stop considering partition columns; any lower-order sort
775 : * keys won't be useful either.
776 : */
777 14128 : if (!partkey_is_bool_constant_for_query(partrel, i))
778 : {
779 13888 : *partialkeys = true;
780 13888 : return retval;
781 : }
782 : }
783 : }
784 :
785 28564 : *partialkeys = false;
786 28564 : return retval;
787 : }
788 :
789 : /*
790 : * build_expression_pathkey
791 : * Build a pathkeys list that describes an ordering by a single expression
792 : * using the given sort operator.
793 : *
794 : * expr and rel are as for make_pathkey_from_sortinfo.
795 : * We induce the other arguments assuming default sort order for the operator.
796 : *
797 : * Similarly to make_pathkey_from_sortinfo, the result is NIL if create_it
798 : * is false and the expression isn't already in some EquivalenceClass.
799 : */
800 : List *
801 612 : build_expression_pathkey(PlannerInfo *root,
802 : Expr *expr,
803 : Oid opno,
804 : Relids rel,
805 : bool create_it)
806 : {
807 : List *pathkeys;
808 : Oid opfamily,
809 : opcintype;
810 : int16 strategy;
811 : PathKey *cpathkey;
812 :
813 : /* Find the operator in pg_amop --- failure shouldn't happen */
814 612 : if (!get_ordering_op_properties(opno,
815 : &opfamily, &opcintype, &strategy))
816 0 : elog(ERROR, "operator %u is not a valid ordering operator",
817 : opno);
818 :
819 612 : cpathkey = make_pathkey_from_sortinfo(root,
820 : expr,
821 : opfamily,
822 : opcintype,
823 : exprCollation((Node *) expr),
824 : (strategy == BTGreaterStrategyNumber),
825 : (strategy == BTGreaterStrategyNumber),
826 : 0,
827 : rel,
828 : create_it);
829 :
830 612 : if (cpathkey)
831 258 : pathkeys = list_make1(cpathkey);
832 : else
833 354 : pathkeys = NIL;
834 :
835 612 : return pathkeys;
836 : }
837 :
838 : /*
839 : * convert_subquery_pathkeys
840 : * Build a pathkeys list that describes the ordering of a subquery's
841 : * result, in the terms of the outer query. This is essentially a
842 : * task of conversion.
843 : *
844 : * 'rel': outer query's RelOptInfo for the subquery relation.
845 : * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
846 : * 'subquery_tlist': the subquery's output targetlist, in its terms.
847 : *
848 : * We intentionally don't do truncate_useless_pathkeys() here, because there
849 : * are situations where seeing the raw ordering of the subquery is helpful.
850 : * For example, if it returns ORDER BY x DESC, that may prompt us to
851 : * construct a mergejoin using DESC order rather than ASC order; but the
852 : * right_merge_direction heuristic would have us throw the knowledge away.
853 : */
854 : List *
855 6996 : convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
856 : List *subquery_pathkeys,
857 : List *subquery_tlist)
858 : {
859 6996 : List *retval = NIL;
860 6996 : int retvallen = 0;
861 6996 : int outer_query_keys = list_length(root->query_pathkeys);
862 : ListCell *i;
863 :
864 7714 : foreach(i, subquery_pathkeys)
865 : {
866 1994 : PathKey *sub_pathkey = (PathKey *) lfirst(i);
867 1994 : EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
868 1994 : PathKey *best_pathkey = NULL;
869 :
870 1994 : if (sub_eclass->ec_has_volatile)
871 : {
872 : /*
873 : * If the sub_pathkey's EquivalenceClass is volatile, then it must
874 : * have come from an ORDER BY clause, and we have to match it to
875 : * that same targetlist entry.
876 : */
877 : TargetEntry *tle;
878 : Var *outer_var;
879 :
880 24 : if (sub_eclass->ec_sortref == 0) /* can't happen */
881 0 : elog(ERROR, "volatile EquivalenceClass has no sortref");
882 24 : tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
883 : Assert(tle);
884 : /* Is TLE actually available to the outer query? */
885 24 : outer_var = find_var_for_subquery_tle(rel, tle);
886 24 : if (outer_var)
887 : {
888 : /* We can represent this sub_pathkey */
889 : EquivalenceMember *sub_member;
890 : EquivalenceClass *outer_ec;
891 :
892 : Assert(list_length(sub_eclass->ec_members) == 1);
893 0 : sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
894 :
895 : /*
896 : * Note: it might look funny to be setting sortref = 0 for a
897 : * reference to a volatile sub_eclass. However, the
898 : * expression is *not* volatile in the outer query: it's just
899 : * a Var referencing whatever the subquery emitted. (IOW, the
900 : * outer query isn't going to re-execute the volatile
901 : * expression itself.) So this is okay.
902 : */
903 : outer_ec =
904 0 : get_eclass_for_sort_expr(root,
905 : (Expr *) outer_var,
906 : sub_eclass->ec_opfamilies,
907 : sub_member->em_datatype,
908 : sub_eclass->ec_collation,
909 : 0,
910 : rel->relids,
911 : false);
912 :
913 : /*
914 : * If we don't find a matching EC, sub-pathkey isn't
915 : * interesting to the outer query
916 : */
917 0 : if (outer_ec)
918 : best_pathkey =
919 0 : make_canonical_pathkey(root,
920 : outer_ec,
921 : sub_pathkey->pk_opfamily,
922 : sub_pathkey->pk_strategy,
923 0 : sub_pathkey->pk_nulls_first);
924 : }
925 : }
926 : else
927 : {
928 : /*
929 : * Otherwise, the sub_pathkey's EquivalenceClass could contain
930 : * multiple elements (representing knowledge that multiple items
931 : * are effectively equal). Each element might match none, one, or
932 : * more of the output columns that are visible to the outer query.
933 : * This means we may have multiple possible representations of the
934 : * sub_pathkey in the context of the outer query. Ideally we
935 : * would generate them all and put them all into an EC of the
936 : * outer query, thereby propagating equality knowledge up to the
937 : * outer query. Right now we cannot do so, because the outer
938 : * query's EquivalenceClasses are already frozen when this is
939 : * called. Instead we prefer the one that has the highest "score"
940 : * (number of EC peers, plus one if it matches the outer
941 : * query_pathkeys). This is the most likely to be useful in the
942 : * outer query.
943 : */
944 1970 : int best_score = -1;
945 : ListCell *j;
946 :
947 4150 : foreach(j, sub_eclass->ec_members)
948 : {
949 2180 : EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
950 2180 : Expr *sub_expr = sub_member->em_expr;
951 2180 : Oid sub_expr_type = sub_member->em_datatype;
952 2180 : Oid sub_expr_coll = sub_eclass->ec_collation;
953 : ListCell *k;
954 :
955 2180 : if (sub_member->em_is_child)
956 158 : continue; /* ignore children here */
957 :
958 13246 : foreach(k, subquery_tlist)
959 : {
960 11224 : TargetEntry *tle = (TargetEntry *) lfirst(k);
961 : Var *outer_var;
962 : Expr *tle_expr;
963 : EquivalenceClass *outer_ec;
964 : PathKey *outer_pk;
965 : int score;
966 :
967 : /* Is TLE actually available to the outer query? */
968 11224 : outer_var = find_var_for_subquery_tle(rel, tle);
969 11224 : if (!outer_var)
970 5830 : continue;
971 :
972 : /*
973 : * The targetlist entry is considered to match if it
974 : * matches after sort-key canonicalization. That is
975 : * needed since the sub_expr has been through the same
976 : * process.
977 : */
978 5394 : tle_expr = canonicalize_ec_expression(tle->expr,
979 : sub_expr_type,
980 : sub_expr_coll);
981 5394 : if (!equal(tle_expr, sub_expr))
982 4062 : continue;
983 :
984 : /* See if we have a matching EC for the TLE */
985 1332 : outer_ec = get_eclass_for_sort_expr(root,
986 : (Expr *) outer_var,
987 : sub_eclass->ec_opfamilies,
988 : sub_expr_type,
989 : sub_expr_coll,
990 : 0,
991 : rel->relids,
992 : false);
993 :
994 : /*
995 : * If we don't find a matching EC, this sub-pathkey isn't
996 : * interesting to the outer query
997 : */
998 1332 : if (!outer_ec)
999 614 : continue;
1000 :
1001 718 : outer_pk = make_canonical_pathkey(root,
1002 : outer_ec,
1003 : sub_pathkey->pk_opfamily,
1004 : sub_pathkey->pk_strategy,
1005 718 : sub_pathkey->pk_nulls_first);
1006 : /* score = # of equivalence peers */
1007 718 : score = list_length(outer_ec->ec_members) - 1;
1008 : /* +1 if it matches the proper query_pathkeys item */
1009 1280 : if (retvallen < outer_query_keys &&
1010 562 : list_nth(root->query_pathkeys, retvallen) == outer_pk)
1011 456 : score++;
1012 718 : if (score > best_score)
1013 : {
1014 718 : best_pathkey = outer_pk;
1015 718 : best_score = score;
1016 : }
1017 : }
1018 : }
1019 : }
1020 :
1021 : /*
1022 : * If we couldn't find a representation of this sub_pathkey, we're
1023 : * done (we can't use the ones to its right, either).
1024 : */
1025 1994 : if (!best_pathkey)
1026 1276 : break;
1027 :
1028 : /*
1029 : * Eliminate redundant ordering info; could happen if outer query
1030 : * equivalences subquery keys...
1031 : */
1032 718 : if (!pathkey_is_redundant(best_pathkey, retval))
1033 : {
1034 718 : retval = lappend(retval, best_pathkey);
1035 718 : retvallen++;
1036 : }
1037 : }
1038 :
1039 6996 : return retval;
1040 : }
1041 :
1042 : /*
1043 : * find_var_for_subquery_tle
1044 : *
1045 : * If the given subquery tlist entry is due to be emitted by the subquery's
1046 : * scan node, return a Var for it, else return NULL.
1047 : *
1048 : * We need this to ensure that we don't return pathkeys describing values
1049 : * that are unavailable above the level of the subquery scan.
1050 : */
1051 : static Var *
1052 11248 : find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
1053 : {
1054 : ListCell *lc;
1055 :
1056 : /* If the TLE is resjunk, it's certainly not visible to the outer query */
1057 11248 : if (tle->resjunk)
1058 0 : return NULL;
1059 :
1060 : /* Search the rel's targetlist to see what it will return */
1061 44790 : foreach(lc, rel->reltarget->exprs)
1062 : {
1063 38936 : Var *var = (Var *) lfirst(lc);
1064 :
1065 : /* Ignore placeholders */
1066 38936 : if (!IsA(var, Var))
1067 24 : continue;
1068 : Assert(var->varno == rel->relid);
1069 :
1070 : /* If we find a Var referencing this TLE, we're good */
1071 38912 : if (var->varattno == tle->resno)
1072 5394 : return copyObject(var); /* Make a copy for safety */
1073 : }
1074 5854 : return NULL;
1075 : }
1076 :
1077 : /*
1078 : * build_join_pathkeys
1079 : * Build the path keys for a join relation constructed by mergejoin or
1080 : * nestloop join. This is normally the same as the outer path's keys.
1081 : *
1082 : * EXCEPTION: in a FULL, RIGHT or RIGHT_ANTI join, we cannot treat the
1083 : * result as having the outer path's path keys, because null lefthand rows
1084 : * may be inserted at random points. It must be treated as unsorted.
1085 : *
1086 : * We truncate away any pathkeys that are uninteresting for higher joins.
1087 : *
1088 : * 'joinrel' is the join relation that paths are being formed for
1089 : * 'jointype' is the join type (inner, left, full, etc)
1090 : * 'outer_pathkeys' is the list of the current outer path's path keys
1091 : *
1092 : * Returns the list of new path keys.
1093 : */
1094 : List *
1095 1431990 : build_join_pathkeys(PlannerInfo *root,
1096 : RelOptInfo *joinrel,
1097 : JoinType jointype,
1098 : List *outer_pathkeys)
1099 : {
1100 1431990 : if (jointype == JOIN_FULL ||
1101 1184560 : jointype == JOIN_RIGHT ||
1102 : jointype == JOIN_RIGHT_ANTI)
1103 260948 : return NIL;
1104 :
1105 : /*
1106 : * This used to be quite a complex bit of code, but now that all pathkey
1107 : * sublists start out life canonicalized, we don't have to do a darn thing
1108 : * here!
1109 : *
1110 : * We do, however, need to truncate the pathkeys list, since it may
1111 : * contain pathkeys that were useful for forming this joinrel but are
1112 : * uninteresting to higher levels.
1113 : */
1114 1171042 : return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1115 : }
1116 :
1117 : /****************************************************************************
1118 : * PATHKEYS AND SORT CLAUSES
1119 : ****************************************************************************/
1120 :
1121 : /*
1122 : * make_pathkeys_for_sortclauses
1123 : * Generate a pathkeys list that represents the sort order specified
1124 : * by a list of SortGroupClauses
1125 : *
1126 : * The resulting PathKeys are always in canonical form. (Actually, there
1127 : * is no longer any code anywhere that creates non-canonical PathKeys.)
1128 : *
1129 : * 'sortclauses' is a list of SortGroupClause nodes
1130 : * 'tlist' is the targetlist to find the referenced tlist entries in
1131 : */
1132 : List *
1133 457910 : make_pathkeys_for_sortclauses(PlannerInfo *root,
1134 : List *sortclauses,
1135 : List *tlist)
1136 : {
1137 : List *result;
1138 : bool sortable;
1139 :
1140 457910 : result = make_pathkeys_for_sortclauses_extended(root,
1141 : &sortclauses,
1142 : tlist,
1143 : false,
1144 : &sortable);
1145 : /* It's caller error if not all clauses were sortable */
1146 : Assert(sortable);
1147 457910 : return result;
1148 : }
1149 :
1150 : /*
1151 : * make_pathkeys_for_sortclauses_extended
1152 : * Generate a pathkeys list that represents the sort order specified
1153 : * by a list of SortGroupClauses
1154 : *
1155 : * The comments for make_pathkeys_for_sortclauses apply here too. In addition:
1156 : *
1157 : * If remove_redundant is true, then any sort clauses that are found to
1158 : * give rise to redundant pathkeys are removed from the sortclauses list
1159 : * (which therefore must be pass-by-reference in this version).
1160 : *
1161 : * *sortable is set to true if all the sort clauses are in fact sortable.
1162 : * If any are not, they are ignored except for setting *sortable false.
1163 : * (In that case, the output pathkey list isn't really useful. However,
1164 : * we process the whole sortclauses list anyway, because it's still valid
1165 : * to remove any clauses that can be proven redundant via the eclass logic.
1166 : * Even though we'll have to hash in that case, we might as well not hash
1167 : * redundant columns.)
1168 : */
1169 : List *
1170 465844 : make_pathkeys_for_sortclauses_extended(PlannerInfo *root,
1171 : List **sortclauses,
1172 : List *tlist,
1173 : bool remove_redundant,
1174 : bool *sortable)
1175 : {
1176 465844 : List *pathkeys = NIL;
1177 : ListCell *l;
1178 :
1179 465844 : *sortable = true;
1180 559686 : foreach(l, *sortclauses)
1181 : {
1182 93842 : SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1183 : Expr *sortkey;
1184 : PathKey *pathkey;
1185 :
1186 93842 : sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1187 93842 : if (!OidIsValid(sortcl->sortop))
1188 : {
1189 6 : *sortable = false;
1190 6 : continue;
1191 : }
1192 93836 : pathkey = make_pathkey_from_sortop(root,
1193 : sortkey,
1194 : sortcl->sortop,
1195 93836 : sortcl->nulls_first,
1196 : sortcl->tleSortGroupRef,
1197 : true);
1198 :
1199 : /* Canonical form eliminates redundant ordering keys */
1200 93836 : if (!pathkey_is_redundant(pathkey, pathkeys))
1201 92406 : pathkeys = lappend(pathkeys, pathkey);
1202 1430 : else if (remove_redundant)
1203 616 : *sortclauses = foreach_delete_current(*sortclauses, l);
1204 : }
1205 465844 : return pathkeys;
1206 : }
1207 :
1208 : /****************************************************************************
1209 : * PATHKEYS AND MERGECLAUSES
1210 : ****************************************************************************/
1211 :
1212 : /*
1213 : * initialize_mergeclause_eclasses
1214 : * Set the EquivalenceClass links in a mergeclause restrictinfo.
1215 : *
1216 : * RestrictInfo contains fields in which we may cache pointers to
1217 : * EquivalenceClasses for the left and right inputs of the mergeclause.
1218 : * (If the mergeclause is a true equivalence clause these will be the
1219 : * same EquivalenceClass, otherwise not.) If the mergeclause is either
1220 : * used to generate an EquivalenceClass, or derived from an EquivalenceClass,
1221 : * then it's easy to set up the left_ec and right_ec members --- otherwise,
1222 : * this function should be called to set them up. We will generate new
1223 : * EquivalenceClauses if necessary to represent the mergeclause's left and
1224 : * right sides.
1225 : *
1226 : * Note this is called before EC merging is complete, so the links won't
1227 : * necessarily point to canonical ECs. Before they are actually used for
1228 : * anything, update_mergeclause_eclasses must be called to ensure that
1229 : * they've been updated to point to canonical ECs.
1230 : */
1231 : void
1232 49308 : initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1233 : {
1234 49308 : Expr *clause = restrictinfo->clause;
1235 : Oid lefttype,
1236 : righttype;
1237 :
1238 : /* Should be a mergeclause ... */
1239 : Assert(restrictinfo->mergeopfamilies != NIL);
1240 : /* ... with links not yet set */
1241 : Assert(restrictinfo->left_ec == NULL);
1242 : Assert(restrictinfo->right_ec == NULL);
1243 :
1244 : /* Need the declared input types of the operator */
1245 49308 : op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1246 :
1247 : /* Find or create a matching EquivalenceClass for each side */
1248 49308 : restrictinfo->left_ec =
1249 49308 : get_eclass_for_sort_expr(root,
1250 49308 : (Expr *) get_leftop(clause),
1251 : restrictinfo->mergeopfamilies,
1252 : lefttype,
1253 : ((OpExpr *) clause)->inputcollid,
1254 : 0,
1255 : NULL,
1256 : true);
1257 49308 : restrictinfo->right_ec =
1258 49308 : get_eclass_for_sort_expr(root,
1259 49308 : (Expr *) get_rightop(clause),
1260 : restrictinfo->mergeopfamilies,
1261 : righttype,
1262 : ((OpExpr *) clause)->inputcollid,
1263 : 0,
1264 : NULL,
1265 : true);
1266 49308 : }
1267 :
1268 : /*
1269 : * update_mergeclause_eclasses
1270 : * Make the cached EquivalenceClass links valid in a mergeclause
1271 : * restrictinfo.
1272 : *
1273 : * These pointers should have been set by process_equivalence or
1274 : * initialize_mergeclause_eclasses, but they might have been set to
1275 : * non-canonical ECs that got merged later. Chase up to the canonical
1276 : * merged parent if so.
1277 : */
1278 : void
1279 3702116 : update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
1280 : {
1281 : /* Should be a merge clause ... */
1282 : Assert(restrictinfo->mergeopfamilies != NIL);
1283 : /* ... with pointers already set */
1284 : Assert(restrictinfo->left_ec != NULL);
1285 : Assert(restrictinfo->right_ec != NULL);
1286 :
1287 : /* Chase up to the top as needed */
1288 3702116 : while (restrictinfo->left_ec->ec_merged)
1289 0 : restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1290 3702116 : while (restrictinfo->right_ec->ec_merged)
1291 0 : restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1292 3702116 : }
1293 :
1294 : /*
1295 : * find_mergeclauses_for_outer_pathkeys
1296 : * This routine attempts to find a list of mergeclauses that can be
1297 : * used with a specified ordering for the join's outer relation.
1298 : * If successful, it returns a list of mergeclauses.
1299 : *
1300 : * 'pathkeys' is a pathkeys list showing the ordering of an outer-rel path.
1301 : * 'restrictinfos' is a list of mergejoinable restriction clauses for the
1302 : * join relation being formed, in no particular order.
1303 : *
1304 : * The restrictinfos must be marked (via outer_is_left) to show which side
1305 : * of each clause is associated with the current outer path. (See
1306 : * select_mergejoin_clauses())
1307 : *
1308 : * The result is NIL if no merge can be done, else a maximal list of
1309 : * usable mergeclauses (represented as a list of their restrictinfo nodes).
1310 : * The list is ordered to match the pathkeys, as required for execution.
1311 : */
1312 : List *
1313 1403964 : find_mergeclauses_for_outer_pathkeys(PlannerInfo *root,
1314 : List *pathkeys,
1315 : List *restrictinfos)
1316 : {
1317 1403964 : List *mergeclauses = NIL;
1318 : ListCell *i;
1319 :
1320 : /* make sure we have eclasses cached in the clauses */
1321 2886308 : foreach(i, restrictinfos)
1322 : {
1323 1482344 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1324 :
1325 1482344 : update_mergeclause_eclasses(root, rinfo);
1326 : }
1327 :
1328 2273732 : foreach(i, pathkeys)
1329 : {
1330 1031052 : PathKey *pathkey = (PathKey *) lfirst(i);
1331 1031052 : EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1332 1031052 : List *matched_restrictinfos = NIL;
1333 : ListCell *j;
1334 :
1335 : /*----------
1336 : * A mergejoin clause matches a pathkey if it has the same EC.
1337 : * If there are multiple matching clauses, take them all. In plain
1338 : * inner-join scenarios we expect only one match, because
1339 : * equivalence-class processing will have removed any redundant
1340 : * mergeclauses. However, in outer-join scenarios there might be
1341 : * multiple matches. An example is
1342 : *
1343 : * select * from a full join b
1344 : * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1345 : *
1346 : * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1347 : * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1348 : * we *must* do so or we will be unable to form a valid plan.
1349 : *
1350 : * We expect that the given pathkeys list is canonical, which means
1351 : * no two members have the same EC, so it's not possible for this
1352 : * code to enter the same mergeclause into the result list twice.
1353 : *
1354 : * It's possible that multiple matching clauses might have different
1355 : * ECs on the other side, in which case the order we put them into our
1356 : * result makes a difference in the pathkeys required for the inner
1357 : * input rel. However this routine hasn't got any info about which
1358 : * order would be best, so we don't worry about that.
1359 : *
1360 : * It's also possible that the selected mergejoin clauses produce
1361 : * a noncanonical ordering of pathkeys for the inner side, ie, we
1362 : * might select clauses that reference b.v1, b.v2, b.v1 in that
1363 : * order. This is not harmful in itself, though it suggests that
1364 : * the clauses are partially redundant. Since the alternative is
1365 : * to omit mergejoin clauses and thereby possibly fail to generate a
1366 : * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1367 : * has to delete duplicates when it constructs the inner pathkeys
1368 : * list, and we also have to deal with such cases specially in
1369 : * create_mergejoin_plan().
1370 : *----------
1371 : */
1372 2296852 : foreach(j, restrictinfos)
1373 : {
1374 1265800 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1375 : EquivalenceClass *clause_ec;
1376 :
1377 2531600 : clause_ec = rinfo->outer_is_left ?
1378 1265800 : rinfo->left_ec : rinfo->right_ec;
1379 1265800 : if (clause_ec == pathkey_ec)
1380 869894 : matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1381 : }
1382 :
1383 : /*
1384 : * If we didn't find a mergeclause, we're done --- any additional
1385 : * sort-key positions in the pathkeys are useless. (But we can still
1386 : * mergejoin if we found at least one mergeclause.)
1387 : */
1388 1031052 : if (matched_restrictinfos == NIL)
1389 161284 : break;
1390 :
1391 : /*
1392 : * If we did find usable mergeclause(s) for this sort-key position,
1393 : * add them to result list.
1394 : */
1395 869768 : mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1396 : }
1397 :
1398 1403964 : return mergeclauses;
1399 : }
1400 :
1401 : /*
1402 : * select_outer_pathkeys_for_merge
1403 : * Builds a pathkey list representing a possible sort ordering
1404 : * that can be used with the given mergeclauses.
1405 : *
1406 : * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
1407 : * that will be used in a merge join.
1408 : * 'joinrel' is the join relation we are trying to construct.
1409 : *
1410 : * The restrictinfos must be marked (via outer_is_left) to show which side
1411 : * of each clause is associated with the current outer path. (See
1412 : * select_mergejoin_clauses())
1413 : *
1414 : * Returns a pathkeys list that can be applied to the outer relation.
1415 : *
1416 : * Since we assume here that a sort is required, there is no particular use
1417 : * in matching any available ordering of the outerrel. (joinpath.c has an
1418 : * entirely separate code path for considering sort-free mergejoins.) Rather,
1419 : * it's interesting to try to match, or match a prefix of the requested
1420 : * query_pathkeys so that a second output sort may be avoided or an
1421 : * incremental sort may be done instead. We can get away with just a prefix
1422 : * of the query_pathkeys when that prefix covers the entire join condition.
1423 : * Failing that, we try to list "more popular" keys (those with the most
1424 : * unmatched EquivalenceClass peers) earlier, in hopes of making the resulting
1425 : * ordering useful for as many higher-level mergejoins as possible.
1426 : */
1427 : List *
1428 494446 : select_outer_pathkeys_for_merge(PlannerInfo *root,
1429 : List *mergeclauses,
1430 : RelOptInfo *joinrel)
1431 : {
1432 494446 : List *pathkeys = NIL;
1433 494446 : int nClauses = list_length(mergeclauses);
1434 : EquivalenceClass **ecs;
1435 : int *scores;
1436 : int necs;
1437 : ListCell *lc;
1438 : int j;
1439 :
1440 : /* Might have no mergeclauses */
1441 494446 : if (nClauses == 0)
1442 82948 : return NIL;
1443 :
1444 : /*
1445 : * Make arrays of the ECs used by the mergeclauses (dropping any
1446 : * duplicates) and their "popularity" scores.
1447 : */
1448 411498 : ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1449 411498 : scores = (int *) palloc(nClauses * sizeof(int));
1450 411498 : necs = 0;
1451 :
1452 863790 : foreach(lc, mergeclauses)
1453 : {
1454 452292 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1455 : EquivalenceClass *oeclass;
1456 : int score;
1457 : ListCell *lc2;
1458 :
1459 : /* get the outer eclass */
1460 452292 : update_mergeclause_eclasses(root, rinfo);
1461 :
1462 452292 : if (rinfo->outer_is_left)
1463 227388 : oeclass = rinfo->left_ec;
1464 : else
1465 224904 : oeclass = rinfo->right_ec;
1466 :
1467 : /* reject duplicates */
1468 495338 : for (j = 0; j < necs; j++)
1469 : {
1470 43118 : if (ecs[j] == oeclass)
1471 72 : break;
1472 : }
1473 452292 : if (j < necs)
1474 72 : continue;
1475 :
1476 : /* compute score */
1477 452220 : score = 0;
1478 1374524 : foreach(lc2, oeclass->ec_members)
1479 : {
1480 922304 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
1481 :
1482 : /* Potential future join partner? */
1483 922304 : if (!em->em_is_const && !em->em_is_child &&
1484 799322 : !bms_overlap(em->em_relids, joinrel->relids))
1485 60154 : score++;
1486 : }
1487 :
1488 452220 : ecs[necs] = oeclass;
1489 452220 : scores[necs] = score;
1490 452220 : necs++;
1491 : }
1492 :
1493 : /*
1494 : * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1495 : * can generate a sort order that's also useful for final output. If we
1496 : * only have a prefix of the query_pathkeys, and that prefix is the entire
1497 : * join condition, then it's useful to use the prefix as the pathkeys as
1498 : * this increases the chances that an incremental sort will be able to be
1499 : * used by the upper planner.
1500 : */
1501 411498 : if (root->query_pathkeys)
1502 : {
1503 207572 : int matches = 0;
1504 :
1505 258628 : foreach(lc, root->query_pathkeys)
1506 : {
1507 246106 : PathKey *query_pathkey = (PathKey *) lfirst(lc);
1508 246106 : EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1509 :
1510 462758 : for (j = 0; j < necs; j++)
1511 : {
1512 267708 : if (ecs[j] == query_ec)
1513 51056 : break; /* found match */
1514 : }
1515 246106 : if (j >= necs)
1516 195050 : break; /* didn't find match */
1517 :
1518 51056 : matches++;
1519 : }
1520 : /* if we got to the end of the list, we have them all */
1521 207572 : if (lc == NULL)
1522 : {
1523 : /* copy query_pathkeys as starting point for our output */
1524 12522 : pathkeys = list_copy(root->query_pathkeys);
1525 : /* mark their ECs as already-emitted */
1526 25680 : foreach(lc, root->query_pathkeys)
1527 : {
1528 13158 : PathKey *query_pathkey = (PathKey *) lfirst(lc);
1529 13158 : EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1530 :
1531 13842 : for (j = 0; j < necs; j++)
1532 : {
1533 13842 : if (ecs[j] == query_ec)
1534 : {
1535 13158 : scores[j] = -1;
1536 13158 : break;
1537 : }
1538 : }
1539 : }
1540 : }
1541 :
1542 : /*
1543 : * If we didn't match to all of the query_pathkeys, but did match to
1544 : * all of the join clauses then we'll make use of these as partially
1545 : * sorted input is better than nothing for the upper planner as it may
1546 : * lead to incremental sorts instead of full sorts.
1547 : */
1548 195050 : else if (matches == nClauses)
1549 : {
1550 30856 : pathkeys = list_copy_head(root->query_pathkeys, matches);
1551 :
1552 : /* we have all of the join pathkeys, so nothing more to do */
1553 30856 : pfree(ecs);
1554 30856 : pfree(scores);
1555 :
1556 30856 : return pathkeys;
1557 : }
1558 : }
1559 :
1560 : /*
1561 : * Add remaining ECs to the list in popularity order, using a default sort
1562 : * ordering. (We could use qsort() here, but the list length is usually
1563 : * so small it's not worth it.)
1564 : */
1565 : for (;;)
1566 408194 : {
1567 : int best_j;
1568 : int best_score;
1569 : EquivalenceClass *ec;
1570 : PathKey *pathkey;
1571 :
1572 788836 : best_j = 0;
1573 788836 : best_score = scores[0];
1574 911732 : for (j = 1; j < necs; j++)
1575 : {
1576 122896 : if (scores[j] > best_score)
1577 : {
1578 40032 : best_j = j;
1579 40032 : best_score = scores[j];
1580 : }
1581 : }
1582 788836 : if (best_score < 0)
1583 380642 : break; /* all done */
1584 408194 : ec = ecs[best_j];
1585 408194 : scores[best_j] = -1;
1586 408194 : pathkey = make_canonical_pathkey(root,
1587 : ec,
1588 408194 : linitial_oid(ec->ec_opfamilies),
1589 : BTLessStrategyNumber,
1590 : false);
1591 : /* can't be redundant because no duplicate ECs */
1592 : Assert(!pathkey_is_redundant(pathkey, pathkeys));
1593 408194 : pathkeys = lappend(pathkeys, pathkey);
1594 : }
1595 :
1596 380642 : pfree(ecs);
1597 380642 : pfree(scores);
1598 :
1599 380642 : return pathkeys;
1600 : }
1601 :
1602 : /*
1603 : * make_inner_pathkeys_for_merge
1604 : * Builds a pathkey list representing the explicit sort order that
1605 : * must be applied to an inner path to make it usable with the
1606 : * given mergeclauses.
1607 : *
1608 : * 'mergeclauses' is a list of RestrictInfos for the mergejoin clauses
1609 : * that will be used in a merge join, in order.
1610 : * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
1611 : * side of the join.
1612 : *
1613 : * The restrictinfos must be marked (via outer_is_left) to show which side
1614 : * of each clause is associated with the current outer path. (See
1615 : * select_mergejoin_clauses())
1616 : *
1617 : * Returns a pathkeys list that can be applied to the inner relation.
1618 : *
1619 : * Note that it is not this routine's job to decide whether sorting is
1620 : * actually needed for a particular input path. Assume a sort is necessary;
1621 : * just make the keys, eh?
1622 : */
1623 : List *
1624 766130 : make_inner_pathkeys_for_merge(PlannerInfo *root,
1625 : List *mergeclauses,
1626 : List *outer_pathkeys)
1627 : {
1628 766130 : List *pathkeys = NIL;
1629 : EquivalenceClass *lastoeclass;
1630 : PathKey *opathkey;
1631 : ListCell *lc;
1632 : ListCell *lop;
1633 :
1634 766130 : lastoeclass = NULL;
1635 766130 : opathkey = NULL;
1636 766130 : lop = list_head(outer_pathkeys);
1637 :
1638 1628432 : foreach(lc, mergeclauses)
1639 : {
1640 862302 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1641 : EquivalenceClass *oeclass;
1642 : EquivalenceClass *ieclass;
1643 : PathKey *pathkey;
1644 :
1645 862302 : update_mergeclause_eclasses(root, rinfo);
1646 :
1647 862302 : if (rinfo->outer_is_left)
1648 : {
1649 449496 : oeclass = rinfo->left_ec;
1650 449496 : ieclass = rinfo->right_ec;
1651 : }
1652 : else
1653 : {
1654 412806 : oeclass = rinfo->right_ec;
1655 412806 : ieclass = rinfo->left_ec;
1656 : }
1657 :
1658 : /* outer eclass should match current or next pathkeys */
1659 : /* we check this carefully for debugging reasons */
1660 862302 : if (oeclass != lastoeclass)
1661 : {
1662 862188 : if (!lop)
1663 0 : elog(ERROR, "too few pathkeys for mergeclauses");
1664 862188 : opathkey = (PathKey *) lfirst(lop);
1665 862188 : lop = lnext(outer_pathkeys, lop);
1666 862188 : lastoeclass = opathkey->pk_eclass;
1667 862188 : if (oeclass != lastoeclass)
1668 0 : elog(ERROR, "outer pathkeys do not match mergeclause");
1669 : }
1670 :
1671 : /*
1672 : * Often, we'll have same EC on both sides, in which case the outer
1673 : * pathkey is also canonical for the inner side, and we can skip a
1674 : * useless search.
1675 : */
1676 862302 : if (ieclass == oeclass)
1677 508500 : pathkey = opathkey;
1678 : else
1679 353802 : pathkey = make_canonical_pathkey(root,
1680 : ieclass,
1681 : opathkey->pk_opfamily,
1682 : opathkey->pk_strategy,
1683 353802 : opathkey->pk_nulls_first);
1684 :
1685 : /*
1686 : * Don't generate redundant pathkeys (which can happen if multiple
1687 : * mergeclauses refer to the same EC). Because we do this, the output
1688 : * pathkey list isn't necessarily ordered like the mergeclauses, which
1689 : * complicates life for create_mergejoin_plan(). But if we didn't,
1690 : * we'd have a noncanonical sort key list, which would be bad; for one
1691 : * reason, it certainly wouldn't match any available sort order for
1692 : * the input relation.
1693 : */
1694 862302 : if (!pathkey_is_redundant(pathkey, pathkeys))
1695 862128 : pathkeys = lappend(pathkeys, pathkey);
1696 : }
1697 :
1698 766130 : return pathkeys;
1699 : }
1700 :
1701 : /*
1702 : * trim_mergeclauses_for_inner_pathkeys
1703 : * This routine trims a list of mergeclauses to include just those that
1704 : * work with a specified ordering for the join's inner relation.
1705 : *
1706 : * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses for the
1707 : * join relation being formed, in an order known to work for the
1708 : * currently-considered sort ordering of the join's outer rel.
1709 : * 'pathkeys' is a pathkeys list showing the ordering of an inner-rel path;
1710 : * it should be equal to, or a truncation of, the result of
1711 : * make_inner_pathkeys_for_merge for these mergeclauses.
1712 : *
1713 : * What we return will be a prefix of the given mergeclauses list.
1714 : *
1715 : * We need this logic because make_inner_pathkeys_for_merge's result isn't
1716 : * necessarily in the same order as the mergeclauses. That means that if we
1717 : * consider an inner-rel pathkey list that is a truncation of that result,
1718 : * we might need to drop mergeclauses even though they match a surviving inner
1719 : * pathkey. This happens when they are to the right of a mergeclause that
1720 : * matches a removed inner pathkey.
1721 : *
1722 : * The mergeclauses must be marked (via outer_is_left) to show which side
1723 : * of each clause is associated with the current outer path. (See
1724 : * select_mergejoin_clauses())
1725 : */
1726 : List *
1727 2390 : trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root,
1728 : List *mergeclauses,
1729 : List *pathkeys)
1730 : {
1731 2390 : List *new_mergeclauses = NIL;
1732 : PathKey *pathkey;
1733 : EquivalenceClass *pathkey_ec;
1734 : bool matched_pathkey;
1735 : ListCell *lip;
1736 : ListCell *i;
1737 :
1738 : /* No pathkeys => no mergeclauses (though we don't expect this case) */
1739 2390 : if (pathkeys == NIL)
1740 0 : return NIL;
1741 : /* Initialize to consider first pathkey */
1742 2390 : lip = list_head(pathkeys);
1743 2390 : pathkey = (PathKey *) lfirst(lip);
1744 2390 : pathkey_ec = pathkey->pk_eclass;
1745 2390 : lip = lnext(pathkeys, lip);
1746 2390 : matched_pathkey = false;
1747 :
1748 : /* Scan mergeclauses to see how many we can use */
1749 4780 : foreach(i, mergeclauses)
1750 : {
1751 4780 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1752 : EquivalenceClass *clause_ec;
1753 :
1754 : /* Assume we needn't do update_mergeclause_eclasses again here */
1755 :
1756 : /* Check clause's inner-rel EC against current pathkey */
1757 9560 : clause_ec = rinfo->outer_is_left ?
1758 4780 : rinfo->right_ec : rinfo->left_ec;
1759 :
1760 : /* If we don't have a match, attempt to advance to next pathkey */
1761 4780 : if (clause_ec != pathkey_ec)
1762 : {
1763 : /* If we had no clauses matching this inner pathkey, must stop */
1764 2390 : if (!matched_pathkey)
1765 0 : break;
1766 :
1767 : /* Advance to next inner pathkey, if any */
1768 2390 : if (lip == NULL)
1769 2390 : break;
1770 0 : pathkey = (PathKey *) lfirst(lip);
1771 0 : pathkey_ec = pathkey->pk_eclass;
1772 0 : lip = lnext(pathkeys, lip);
1773 0 : matched_pathkey = false;
1774 : }
1775 :
1776 : /* If mergeclause matches current inner pathkey, we can use it */
1777 2390 : if (clause_ec == pathkey_ec)
1778 : {
1779 2390 : new_mergeclauses = lappend(new_mergeclauses, rinfo);
1780 2390 : matched_pathkey = true;
1781 : }
1782 : else
1783 : {
1784 : /* Else, no hope of adding any more mergeclauses */
1785 0 : break;
1786 : }
1787 : }
1788 :
1789 2390 : return new_mergeclauses;
1790 : }
1791 :
1792 :
1793 : /****************************************************************************
1794 : * PATHKEY USEFULNESS CHECKS
1795 : *
1796 : * We only want to remember as many of the pathkeys of a path as have some
1797 : * potential use, either for subsequent mergejoins or for meeting the query's
1798 : * requested output ordering. This ensures that add_path() won't consider
1799 : * a path to have a usefully different ordering unless it really is useful.
1800 : * These routines check for usefulness of given pathkeys.
1801 : ****************************************************************************/
1802 :
1803 : /*
1804 : * pathkeys_useful_for_merging
1805 : * Count the number of pathkeys that may be useful for mergejoins
1806 : * above the given relation.
1807 : *
1808 : * We consider a pathkey potentially useful if it corresponds to the merge
1809 : * ordering of either side of any joinclause for the rel. This might be
1810 : * overoptimistic, since joinclauses that require different other relations
1811 : * might never be usable at the same time, but trying to be exact is likely
1812 : * to be more trouble than it's worth.
1813 : *
1814 : * To avoid doubling the number of mergejoin paths considered, we would like
1815 : * to consider only one of the two scan directions (ASC or DESC) as useful
1816 : * for merging for any given target column. The choice is arbitrary unless
1817 : * one of the directions happens to match an ORDER BY key, in which case
1818 : * that direction should be preferred, in hopes of avoiding a final sort step.
1819 : * right_merge_direction() implements this heuristic.
1820 : */
1821 : static int
1822 2143602 : pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
1823 : {
1824 2143602 : int useful = 0;
1825 : ListCell *i;
1826 :
1827 2633720 : foreach(i, pathkeys)
1828 : {
1829 1286262 : PathKey *pathkey = (PathKey *) lfirst(i);
1830 1286262 : bool matched = false;
1831 : ListCell *j;
1832 :
1833 : /* If "wrong" direction, not useful for merging */
1834 1286262 : if (!right_merge_direction(root, pathkey))
1835 241278 : break;
1836 :
1837 : /*
1838 : * First look into the EquivalenceClass of the pathkey, to see if
1839 : * there are any members not yet joined to the rel. If so, it's
1840 : * surely possible to generate a mergejoin clause using them.
1841 : */
1842 1598402 : if (rel->has_eclass_joins &&
1843 553418 : eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
1844 314070 : matched = true;
1845 : else
1846 : {
1847 : /*
1848 : * Otherwise search the rel's joininfo list, which contains
1849 : * non-EquivalenceClass-derivable join clauses that might
1850 : * nonetheless be mergejoinable.
1851 : */
1852 1126772 : foreach(j, rel->joininfo)
1853 : {
1854 571906 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1855 :
1856 571906 : if (restrictinfo->mergeopfamilies == NIL)
1857 127644 : continue;
1858 444262 : update_mergeclause_eclasses(root, restrictinfo);
1859 :
1860 444262 : if (pathkey->pk_eclass == restrictinfo->left_ec ||
1861 361630 : pathkey->pk_eclass == restrictinfo->right_ec)
1862 : {
1863 176048 : matched = true;
1864 176048 : break;
1865 : }
1866 : }
1867 : }
1868 :
1869 : /*
1870 : * If we didn't find a mergeclause, we're done --- any additional
1871 : * sort-key positions in the pathkeys are useless. (But we can still
1872 : * mergejoin if we found at least one mergeclause.)
1873 : */
1874 1044984 : if (matched)
1875 490118 : useful++;
1876 : else
1877 554866 : break;
1878 : }
1879 :
1880 2143602 : return useful;
1881 : }
1882 :
1883 : /*
1884 : * right_merge_direction
1885 : * Check whether the pathkey embodies the preferred sort direction
1886 : * for merging its target column.
1887 : */
1888 : static bool
1889 1286262 : right_merge_direction(PlannerInfo *root, PathKey *pathkey)
1890 : {
1891 : ListCell *l;
1892 :
1893 2118822 : foreach(l, root->query_pathkeys)
1894 : {
1895 1092606 : PathKey *query_pathkey = (PathKey *) lfirst(l);
1896 :
1897 1092606 : if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
1898 260046 : pathkey->pk_opfamily == query_pathkey->pk_opfamily)
1899 : {
1900 : /*
1901 : * Found a matching query sort column. Prefer this pathkey's
1902 : * direction iff it matches. Note that we ignore pk_nulls_first,
1903 : * which means that a sort might be needed anyway ... but we still
1904 : * want to prefer only one of the two possible directions, and we
1905 : * might as well use this one.
1906 : */
1907 260046 : return (pathkey->pk_strategy == query_pathkey->pk_strategy);
1908 : }
1909 : }
1910 :
1911 : /* If no matching ORDER BY request, prefer the ASC direction */
1912 1026216 : return (pathkey->pk_strategy == BTLessStrategyNumber);
1913 : }
1914 :
1915 : /*
1916 : * pathkeys_useful_for_ordering
1917 : * Count the number of pathkeys that are useful for meeting the
1918 : * query's requested output ordering.
1919 : *
1920 : * Because we the have the possibility of incremental sort, a prefix list of
1921 : * keys is potentially useful for improving the performance of the requested
1922 : * ordering. Thus we return 0, if no valuable keys are found, or the number
1923 : * of leading keys shared by the list and the requested ordering..
1924 : */
1925 : static int
1926 2143602 : pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
1927 : {
1928 : int n_common_pathkeys;
1929 :
1930 2143602 : if (root->query_pathkeys == NIL)
1931 1095720 : return 0; /* no special ordering requested */
1932 :
1933 1047882 : if (pathkeys == NIL)
1934 386420 : return 0; /* unordered path */
1935 :
1936 661462 : (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
1937 : &n_common_pathkeys);
1938 :
1939 661462 : return n_common_pathkeys;
1940 : }
1941 :
1942 : /*
1943 : * truncate_useless_pathkeys
1944 : * Shorten the given pathkey list to just the useful pathkeys.
1945 : */
1946 : List *
1947 2143602 : truncate_useless_pathkeys(PlannerInfo *root,
1948 : RelOptInfo *rel,
1949 : List *pathkeys)
1950 : {
1951 : int nuseful;
1952 : int nuseful2;
1953 :
1954 2143602 : nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1955 2143602 : nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1956 2143602 : if (nuseful2 > nuseful)
1957 105526 : nuseful = nuseful2;
1958 :
1959 : /*
1960 : * Note: not safe to modify input list destructively, but we can avoid
1961 : * copying the list if we're not actually going to change it
1962 : */
1963 2143602 : if (nuseful == 0)
1964 1592874 : return NIL;
1965 550728 : else if (nuseful == list_length(pathkeys))
1966 525282 : return pathkeys;
1967 : else
1968 25446 : return list_copy_head(pathkeys, nuseful);
1969 : }
1970 :
1971 : /*
1972 : * has_useful_pathkeys
1973 : * Detect whether the specified rel could have any pathkeys that are
1974 : * useful according to truncate_useless_pathkeys().
1975 : *
1976 : * This is a cheap test that lets us skip building pathkeys at all in very
1977 : * simple queries. It's OK to err in the direction of returning "true" when
1978 : * there really aren't any usable pathkeys, but erring in the other direction
1979 : * is bad --- so keep this in sync with the routines above!
1980 : *
1981 : * We could make the test more complex, for example checking to see if any of
1982 : * the joinclauses are really mergejoinable, but that likely wouldn't win
1983 : * often enough to repay the extra cycles. Queries with neither a join nor
1984 : * a sort are reasonably common, though, so this much work seems worthwhile.
1985 : */
1986 : bool
1987 702766 : has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
1988 : {
1989 702766 : if (rel->joininfo != NIL || rel->has_eclass_joins)
1990 438670 : return true; /* might be able to use pathkeys for merging */
1991 264096 : if (root->query_pathkeys != NIL)
1992 64790 : return true; /* might be able to use them for ordering */
1993 199306 : return false; /* definitely useless */
1994 : }
|
