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