Loading...
Searching...
No Matches
indxpath.c File Reference
#include "postgres.h"#include "access/stratnum.h"#include "access/sysattr.h"#include "access/transam.h"#include "catalog/pg_am.h"#include "catalog/pg_amop.h"#include "catalog/pg_operator.h"#include "catalog/pg_opfamily.h"#include "catalog/pg_type.h"#include "nodes/makefuncs.h"#include "nodes/nodeFuncs.h"#include "nodes/supportnodes.h"#include "optimizer/cost.h"#include "optimizer/optimizer.h"#include "optimizer/pathnode.h"#include "optimizer/paths.h"#include "optimizer/placeholder.h"#include "optimizer/prep.h"#include "optimizer/restrictinfo.h"#include "utils/lsyscache.h"#include "utils/selfuncs.h"
Include dependency graph for indxpath.c:
Go to the source code of this file.
Data Structures | |
| struct | IndexClauseSet |
| struct | PathClauseUsage |
| struct | ec_member_matches_arg |
| struct | OrArgIndexMatch |
Macros | |
| #define | IndexCollMatchesExprColl(idxcollation, exprcollation) ((idxcollation) == InvalidOid || (idxcollation) == (exprcollation)) |
Enumerations | |
| enum | ScanTypeControl { ST_INDEXSCAN , ST_BITMAPSCAN , ST_ANYSCAN } |
Macro Definition Documentation
◆ IndexCollMatchesExprColl
| #define IndexCollMatchesExprColl | ( | idxcollation, | |
| exprcollation | |||
| ) | ((idxcollation) == InvalidOid || (idxcollation) == (exprcollation)) |
Definition at line 41 of file indxpath.c.
45{
49} ScanTypeControl;
50
51/* Data structure for collecting qual clauses that match an index */
52typedef struct
53{
54 bool nonempty; /* True if lists are not all empty */
55 /* Lists of IndexClause nodes, one list per index column */
57} IndexClauseSet;
58
59/* Per-path data used within choose_bitmap_and() */
60typedef struct
61{
66 bool unclassifiable; /* has too many quals+preds to process? */
67} PathClauseUsage;
68
69/* Callback argument for ec_member_matches_indexcol */
70typedef struct
71{
73 int indexcol; /* index column we want to match to */
75
76
79 IndexClauseSet *rclauseset,
80 IndexClauseSet *jclauseset,
81 IndexClauseSet *eclauseset,
82 List **bitindexpaths);
85 IndexClauseSet *rclauseset,
86 IndexClauseSet *jclauseset,
87 IndexClauseSet *eclauseset,
88 List **bitindexpaths,
89 List *indexjoinclauses,
90 int considered_clauses,
91 List **considered_relids);
94 IndexClauseSet *rclauseset,
95 IndexClauseSet *jclauseset,
96 IndexClauseSet *eclauseset,
97 List **bitindexpaths,
98 Relids relids,
99 List **considered_relids);
101 List *indexjoinclauses);
104 List **bitindexpaths);
107 bool useful_predicate,
108 ScanTypeControl scantype,
109 bool *skip_nonnative_saop);
115 List *paths);
118 Path *ipath);
120 List *paths);
122 List **clauselist);
128 Index cur_relid,
129 Index outer_relid,
130 double rowcount);
134 IndexClauseSet *clauseset);
137 IndexClauseSet *clauseset,
138 List **joinorclauses);
141 IndexClauseSet *clauseset);
143 List *clauses,
145 IndexClauseSet *clauseset);
147 RestrictInfo *rinfo,
149 IndexClauseSet *clauseset);
151 RestrictInfo *rinfo,
152 int indexcol,
156 RestrictInfo *rinfo,
159 RestrictInfo *rinfo,
160 int indexcol,
163 RestrictInfo *rinfo,
164 int indexcol,
167 RestrictInfo *rinfo,
168 Oid funcid,
169 int indexarg,
170 int indexcol,
173 RestrictInfo *rinfo,
174 int indexcol,
177 RestrictInfo *rinfo,
178 int indexcol,
181 RestrictInfo *rinfo,
182 int indexcol,
185 RestrictInfo *rinfo,
186 int indexcol,
188 Oid expr_op,
189 bool var_on_left);
191 List **orderby_clauses_p,
192 List **clause_columns_p);
198
199
200/*
201 * create_index_paths()
202 * Generate all interesting index paths for the given relation.
203 * Candidate paths are added to the rel's pathlist (using add_path).
204 *
205 * To be considered for an index scan, an index must match one or more
206 * restriction clauses or join clauses from the query's qual condition,
207 * or match the query's ORDER BY condition, or have a predicate that
208 * matches the query's qual condition.
209 *
210 * There are two basic kinds of index scans. A "plain" index scan uses
211 * only restriction clauses (possibly none at all) in its indexqual,
212 * so it can be applied in any context. A "parameterized" index scan uses
213 * join clauses (plus restriction clauses, if available) in its indexqual.
214 * When joining such a scan to one of the relations supplying the other
215 * variables used in its indexqual, the parameterized scan must appear as
216 * the inner relation of a nestloop join; it can't be used on the outer side,
217 * nor in a merge or hash join. In that context, values for the other rels'
218 * attributes are available and fixed during any one scan of the indexpath.
219 *
220 * An IndexPath is generated and submitted to add_path() for each plain or
221 * parameterized index scan this routine deems potentially interesting for
222 * the current query.
223 *
224 * 'rel' is the relation for which we want to generate index paths
225 *
226 * Note: check_index_predicates() must have been run previously for this rel.
227 *
228 * Note: in cases involving LATERAL references in the relation's tlist, it's
229 * possible that rel->lateral_relids is nonempty. Currently, we include
230 * lateral_relids into the parameterization reported for each path, but don't
231 * take it into account otherwise. The fact that any such rels *must* be
232 * available as parameter sources perhaps should influence our choices of
233 * index quals ... but for now, it doesn't seem worth troubling over.
234 * In particular, comments below about "unparameterized" paths should be read
235 * as meaning "unparameterized so far as the indexquals are concerned".
236 */
237void
239{
240 List *indexpaths;
241 List *bitindexpaths;
242 List *bitjoinpaths;
243 List *joinorclauses;
244 IndexClauseSet rclauseset;
245 IndexClauseSet jclauseset;
246 IndexClauseSet eclauseset;
247 ListCell *lc;
248
249 /* Skip the whole mess if no indexes */
251 return;
252
253 /* Bitmap paths are collected and then dealt with at the end */
254 bitindexpaths = bitjoinpaths = joinorclauses = NIL;
255
256 /* Examine each index in turn */
258 {
260
261 /* Protect limited-size array in IndexClauseSets */
263
264 /*
265 * Ignore partial indexes that do not match the query.
266 * (generate_bitmap_or_paths() might be able to do something with
267 * them, but that's of no concern here.)
268 */
270 continue;
271
272 /*
273 * Identify the restriction clauses that can match the index.
274 */
277
278 /*
279 * Build index paths from the restriction clauses. These will be
280 * non-parameterized paths. Plain paths go directly to add_path(),
281 * bitmap paths are added to bitindexpaths to be handled below.
282 */
284 &bitindexpaths);
285
286 /*
287 * Identify the join clauses that can match the index. For the moment
288 * we keep them separate from the restriction clauses. Note that this
289 * step finds only "loose" join clauses that have not been merged into
290 * EquivalenceClasses. Also, collect join OR clauses for later.
291 */
294 &jclauseset, &joinorclauses);
295
296 /*
297 * Look for EquivalenceClasses that can generate joinclauses matching
298 * the index.
299 */
302 &eclauseset);
303
304 /*
305 * If we found any plain or eclass join clauses, build parameterized
306 * index paths using them.
307 */
310 &rclauseset,
311 &jclauseset,
312 &eclauseset,
313 &bitjoinpaths);
314 }
315
316 /*
317 * Generate BitmapOrPaths for any suitable OR-clauses present in the
318 * restriction list. Add these to bitindexpaths.
319 */
322 bitindexpaths = list_concat(bitindexpaths, indexpaths);
323
324 /*
325 * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
326 * the joinclause list. Add these to bitjoinpaths.
327 */
329 joinorclauses, rel->baserestrictinfo);
330 bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
331
332 /*
333 * If we found anything usable, generate a BitmapHeapPath for the most
334 * promising combination of restriction bitmap index paths. Note there
335 * will be only one such path no matter how many indexes exist. This
336 * should be sufficient since there's basically only one figure of merit
337 * (total cost) for such a path.
338 */
340 {
341 Path *bitmapqual;
342 BitmapHeapPath *bpath;
343
346 rel->lateral_relids, 1.0, 0);
348
349 /* create a partial bitmap heap path */
352 }
353
354 /*
355 * Likewise, if we found anything usable, generate BitmapHeapPaths for the
356 * most promising combinations of join bitmap index paths. Our strategy
357 * is to generate one such path for each distinct parameterization seen
358 * among the available bitmap index paths. This may look pretty
359 * expensive, but usually there won't be very many distinct
360 * parameterizations. (This logic is quite similar to that in
361 * consider_index_join_clauses, but we're working with whole paths not
362 * individual clauses.)
363 */
365 {
366 List *all_path_outers;
367
368 /* Identify each distinct parameterization seen in bitjoinpaths */
369 all_path_outers = NIL;
370 foreach(lc, bitjoinpaths)
371 {
374
375 all_path_outers = list_append_unique(all_path_outers,
376 required_outer);
377 }
378
379 /* Now, for each distinct parameterization set ... */
380 foreach(lc, all_path_outers)
381 {
383 List *this_path_set;
384 Path *bitmapqual;
385 Relids required_outer;
386 double loop_count;
387 BitmapHeapPath *bpath;
388 ListCell *lcp;
389
390 /* Identify all the bitmap join paths needing no more than that */
391 this_path_set = NIL;
392 foreach(lcp, bitjoinpaths)
393 {
395
397 this_path_set = lappend(this_path_set, path);
398 }
399
400 /*
401 * Add in restriction bitmap paths, since they can be used
402 * together with any join paths.
403 */
404 this_path_set = list_concat(this_path_set, bitindexpaths);
405
406 /* Select best AND combination for this parameterization */
408
409 /* And push that path into the mix */
410 required_outer = PATH_REQ_OUTER(bitmapqual);
413 required_outer, loop_count, 0);
415 }
416 }
417}
418
419/*
420 * consider_index_join_clauses
421 * Given sets of join clauses for an index, decide which parameterized
422 * index paths to build.
423 *
424 * Plain indexpaths are sent directly to add_path, while potential
425 * bitmap indexpaths are added to *bitindexpaths for later processing.
426 *
427 * 'rel' is the index's heap relation
428 * 'index' is the index for which we want to generate paths
429 * 'rclauseset' is the collection of indexable restriction clauses
430 * 'jclauseset' is the collection of indexable simple join clauses
431 * 'eclauseset' is the collection of indexable clauses from EquivalenceClasses
432 * '*bitindexpaths' is the list to add bitmap paths to
433 */
434static void
437 IndexClauseSet *rclauseset,
438 IndexClauseSet *jclauseset,
439 IndexClauseSet *eclauseset,
440 List **bitindexpaths)
441{
442 int considered_clauses = 0;
444 int indexcol;
445
446 /*
447 * The strategy here is to identify every potentially useful set of outer
448 * rels that can provide indexable join clauses. For each such set,
449 * select all the join clauses available from those outer rels, add on all
450 * the indexable restriction clauses, and generate plain and/or bitmap
451 * index paths for that set of clauses. This is based on the assumption
452 * that it's always better to apply a clause as an indexqual than as a
453 * filter (qpqual); which is where an available clause would end up being
454 * applied if we omit it from the indexquals.
455 *
456 * This looks expensive, but in most practical cases there won't be very
457 * many distinct sets of outer rels to consider. As a safety valve when
458 * that's not true, we use a heuristic: limit the number of outer rel sets
459 * considered to a multiple of the number of clauses considered. (We'll
460 * always consider using each individual join clause, though.)
461 *
462 * For simplicity in selecting relevant clauses, we represent each set of
463 * outer rels as a maximum set of clause_relids --- that is, the indexed
464 * relation itself is also included in the relids set. considered_relids
465 * lists all relids sets we've already tried.
466 */
468 {
469 /* Consider each applicable simple join clause */
472 rclauseset, jclauseset, eclauseset,
473 bitindexpaths,
474 jclauseset->indexclauses[indexcol],
475 considered_clauses,
476 &considered_relids);
477 /* Consider each applicable eclass join clause */
480 rclauseset, jclauseset, eclauseset,
481 bitindexpaths,
482 eclauseset->indexclauses[indexcol],
483 considered_clauses,
484 &considered_relids);
485 }
486}
487
488/*
489 * consider_index_join_outer_rels
490 * Generate parameterized paths based on clause relids in the clause list.
491 *
492 * Workhorse for consider_index_join_clauses; see notes therein for rationale.
493 *
494 * 'rel', 'index', 'rclauseset', 'jclauseset', 'eclauseset', and
495 * 'bitindexpaths' as above
496 * 'indexjoinclauses' is a list of IndexClauses for join clauses
497 * 'considered_clauses' is the total number of clauses considered (so far)
498 * '*considered_relids' is a list of all relids sets already considered
499 */
500static void
503 IndexClauseSet *rclauseset,
504 IndexClauseSet *jclauseset,
505 IndexClauseSet *eclauseset,
506 List **bitindexpaths,
507 List *indexjoinclauses,
508 int considered_clauses,
509 List **considered_relids)
510{
511 ListCell *lc;
512
513 /* Examine relids of each joinclause in the given list */
514 foreach(lc, indexjoinclauses)
515 {
519 int num_considered_relids;
520
521 /* If we already tried its relids set, no need to do so again */
523 continue;
524
525 /*
526 * Generate the union of this clause's relids set with each
527 * previously-tried set. This ensures we try this clause along with
528 * every interesting subset of previous clauses. However, to avoid
529 * exponential growth of planning time when there are many clauses,
530 * limit the number of relid sets accepted to 10 * considered_clauses.
531 *
532 * Note: get_join_index_paths appends entries to *considered_relids,
533 * but we do not need to visit such newly-added entries within this
534 * loop, so we don't use foreach() here. No real harm would be done
535 * if we did visit them, since the subset check would reject them; but
536 * it would waste some cycles.
537 */
538 num_considered_relids = list_length(*considered_relids);
539 for (int pos = 0; pos < num_considered_relids; pos++)
540 {
542
543 /*
544 * If either is a subset of the other, no new set is possible.
545 * This isn't a complete test for redundancy, but it's easy and
546 * cheap. get_join_index_paths will check more carefully if we
547 * already generated the same relids set.
548 */
550 continue;
551
552 /*
553 * If this clause was derived from an equivalence class, the
554 * clause list may contain other clauses derived from the same
555 * eclass. We should not consider that combining this clause with
556 * one of those clauses generates a usefully different
557 * parameterization; so skip if any clause derived from the same
558 * eclass would already have been included when using oldrelids.
559 */
560 if (parent_ec &&
561 eclass_already_used(parent_ec, oldrelids,
562 indexjoinclauses))
563 continue;
564
565 /*
566 * If the number of relid sets considered exceeds our heuristic
567 * limit, stop considering combinations of clauses. We'll still
568 * consider the current clause alone, though (below this loop).
569 */
571 break;
572
573 /* OK, try the union set */
575 rclauseset, jclauseset, eclauseset,
576 bitindexpaths,
577 bms_union(clause_relids, oldrelids),
578 considered_relids);
579 }
580
581 /* Also try this set of relids by itself */
583 rclauseset, jclauseset, eclauseset,
584 bitindexpaths,
585 clause_relids,
586 considered_relids);
587 }
588}
589
590/*
591 * get_join_index_paths
592 * Generate index paths using clauses from the specified outer relations.
593 * In addition to generating paths, relids is added to *considered_relids
594 * if not already present.
595 *
596 * Workhorse for consider_index_join_clauses; see notes therein for rationale.
597 *
598 * 'rel', 'index', 'rclauseset', 'jclauseset', 'eclauseset',
599 * 'bitindexpaths', 'considered_relids' as above
600 * 'relids' is the current set of relids to consider (the target rel plus
601 * one or more outer rels)
602 */
603static void
606 IndexClauseSet *rclauseset,
607 IndexClauseSet *jclauseset,
608 IndexClauseSet *eclauseset,
609 List **bitindexpaths,
610 Relids relids,
611 List **considered_relids)
612{
613 IndexClauseSet clauseset;
614 int indexcol;
615
616 /* If we already considered this relids set, don't repeat the work */
618 return;
619
620 /* Identify indexclauses usable with this relids set */
622
624 {
625 ListCell *lc;
626
627 /* First find applicable simple join clauses */
629 {
631
633 clauseset.indexclauses[indexcol] =
635 }
636
637 /*
638 * Add applicable eclass join clauses. The clauses generated for each
639 * column are redundant (cf generate_implied_equalities_for_column),
640 * so we need at most one. This is the only exception to the general
641 * rule of using all available index clauses.
642 */
644 {
646
648 {
649 clauseset.indexclauses[indexcol] =
651 break;
652 }
653 }
654
655 /* Add restriction clauses */
656 clauseset.indexclauses[indexcol] =
658 rclauseset->indexclauses[indexcol]);
659
662 }
663
664 /* We should have found something, else caller passed silly relids */
666
667 /* Build index path(s) using the collected set of clauses */
669
670 /*
671 * Remember we considered paths for this set of relids.
672 */
673 *considered_relids = lappend(*considered_relids, relids);
674}
675
676/*
677 * eclass_already_used
678 * True if any join clause usable with oldrelids was generated from
679 * the specified equivalence class.
680 */
681static bool
683 List *indexjoinclauses)
684{
685 ListCell *lc;
686
687 foreach(lc, indexjoinclauses)
688 {
691
692 if (rinfo->parent_ec == parent_ec &&
693 bms_is_subset(rinfo->clause_relids, oldrelids))
694 return true;
695 }
696 return false;
697}
698
699
700/*
701 * get_index_paths
702 * Given an index and a set of index clauses for it, construct IndexPaths.
703 *
704 * Plain indexpaths are sent directly to add_path, while potential
705 * bitmap indexpaths are added to *bitindexpaths for later processing.
706 *
707 * This is a fairly simple frontend to build_index_paths(). Its reason for
708 * existence is mainly to handle ScalarArrayOpExpr quals properly. If the
709 * index AM supports them natively, we should just include them in simple
710 * index paths. If not, we should exclude them while building simple index
711 * paths, and then make a separate attempt to include them in bitmap paths.
712 */
713static void
716 List **bitindexpaths)
717{
718 List *indexpaths;
719 bool skip_nonnative_saop = false;
720 ListCell *lc;
721
722 /*
723 * Build simple index paths using the clauses. Allow ScalarArrayOpExpr
724 * clauses only if the index AM supports them natively.
725 */
727 index, clauses,
728 index->predOK,
729 ST_ANYSCAN,
730 &skip_nonnative_saop);
731
732 /*
733 * Submit all the ones that can form plain IndexScan plans to add_path. (A
734 * plain IndexPath can represent either a plain IndexScan or an
735 * IndexOnlyScan, but for our purposes here that distinction does not
736 * matter. However, some of the indexes might support only bitmap scans,
737 * and those we mustn't submit to add_path here.)
738 *
739 * Also, pick out the ones that are usable as bitmap scans. For that, we
740 * must discard indexes that don't support bitmap scans, and we also are
741 * only interested in paths that have some selectivity; we should discard
742 * anything that was generated solely for ordering purposes.
743 */
744 foreach(lc, indexpaths)
745 {
747
750
753 ipath->indexselectivity < 1.0))
754 *bitindexpaths = lappend(*bitindexpaths, ipath);
755 }
756
757 /*
758 * If there were ScalarArrayOpExpr clauses that the index can't handle
759 * natively, generate bitmap scan paths relying on executor-managed
760 * ScalarArrayOpExpr.
761 */
762 if (skip_nonnative_saop)
763 {
765 index, clauses,
766 false,
767 ST_BITMAPSCAN,
768 NULL);
769 *bitindexpaths = list_concat(*bitindexpaths, indexpaths);
770 }
771}
772
773/*
774 * build_index_paths
775 * Given an index and a set of index clauses for it, construct zero
776 * or more IndexPaths. It also constructs zero or more partial IndexPaths.
777 *
778 * We return a list of paths because (1) this routine checks some cases
779 * that should cause us to not generate any IndexPath, and (2) in some
780 * cases we want to consider both a forward and a backward scan, so as
781 * to obtain both sort orders. Note that the paths are just returned
782 * to the caller and not immediately fed to add_path().
783 *
784 * At top level, useful_predicate should be exactly the index's predOK flag
785 * (ie, true if it has a predicate that was proven from the restriction
786 * clauses). When working on an arm of an OR clause, useful_predicate
787 * should be true if the predicate required the current OR list to be proven.
788 * Note that this routine should never be called at all if the index has an
789 * unprovable predicate.
790 *
791 * scantype indicates whether we want to create plain indexscans, bitmap
792 * indexscans, or both. When it's ST_BITMAPSCAN, we will not consider
793 * index ordering while deciding if a Path is worth generating.
794 *
795 * If skip_nonnative_saop is non-NULL, we ignore ScalarArrayOpExpr clauses
796 * unless the index AM supports them directly, and we set *skip_nonnative_saop
797 * to true if we found any such clauses (caller must initialize the variable
798 * to false). If it's NULL, we do not ignore ScalarArrayOpExpr clauses.
799 *
800 * 'rel' is the index's heap relation
801 * 'index' is the index for which we want to generate paths
802 * 'clauses' is the collection of indexable clauses (IndexClause nodes)
803 * 'useful_predicate' indicates whether the index has a useful predicate
804 * 'scantype' indicates whether we need plain or bitmap scan support
805 * 'skip_nonnative_saop' indicates whether to accept SAOP if index AM doesn't
806 */
810 bool useful_predicate,
811 ScanTypeControl scantype,
812 bool *skip_nonnative_saop)
813{
815 IndexPath *ipath;
816 List *index_clauses;
817 Relids outer_relids;
818 double loop_count;
819 List *orderbyclauses;
820 List *orderbyclausecols;
821 List *index_pathkeys;
822 List *useful_pathkeys;
823 bool pathkeys_possibly_useful;
824 bool index_is_ordered;
825 bool index_only_scan;
826 int indexcol;
827
829
830 /*
831 * Check that index supports the desired scan type(s)
832 */
833 switch (scantype)
834 {
838 break;
842 break;
844 /* either or both are OK */
845 break;
846 }
847
848 /*
849 * 1. Combine the per-column IndexClause lists into an overall list.
850 *
851 * In the resulting list, clauses are ordered by index key, so that the
852 * column numbers form a nondecreasing sequence. (This order is depended
853 * on by btree and possibly other places.) The list can be empty, if the
854 * index AM allows that.
855 *
856 * We also build a Relids set showing which outer rels are required by the
857 * selected clauses. Any lateral_relids are included in that, but not
858 * otherwise accounted for.
859 */
860 index_clauses = NIL;
863 {
864 ListCell *lc;
865
867 {
870
873 {
874 /*
875 * Caller asked us to generate IndexPaths that omit any
876 * ScalarArrayOpExpr clauses when the underlying index AM
877 * lacks native support.
878 *
879 * We must omit this clause (and tell caller about it).
880 */
881 *skip_nonnative_saop = true;
882 continue;
883 }
884
885 /* OK to include this clause */
886 index_clauses = lappend(index_clauses, iclause);
887 outer_relids = bms_add_members(outer_relids,
888 rinfo->clause_relids);
889 }
890
891 /*
892 * If no clauses match the first index column, check for amoptionalkey
893 * restriction. We can't generate a scan over an index with
894 * amoptionalkey = false unless there's at least one index clause.
895 * (When working on columns after the first, this test cannot fail. It
896 * is always okay for columns after the first to not have any
897 * clauses.)
898 */
901 }
902
903 /* We do not want the index's rel itself listed in outer_relids */
905
906 /* Compute loop_count for cost estimation purposes */
908
909 /*
910 * 2. Compute pathkeys describing index's ordering, if any, then see how
911 * many of them are actually useful for this query. This is not relevant
912 * if we are only trying to build bitmap indexscans.
913 */
914 pathkeys_possibly_useful = (scantype != ST_BITMAPSCAN &&
916 index_is_ordered = (index->sortopfamily != NULL);
917 if (index_is_ordered && pathkeys_possibly_useful)
918 {
920 ForwardScanDirection);
922 index_pathkeys);
923 orderbyclauses = NIL;
924 orderbyclausecols = NIL;
925 }
927 {
928 /*
929 * See if we can generate ordering operators for query_pathkeys or at
930 * least some prefix thereof. Matching to just a prefix of the
931 * query_pathkeys will allow an incremental sort to be considered on
932 * the index's partially sorted results.
933 */
935 &orderbyclauses,
936 &orderbyclausecols);
938 useful_pathkeys = root->query_pathkeys;
939 else
941 list_length(orderbyclauses));
942 }
943 else
944 {
945 useful_pathkeys = NIL;
946 orderbyclauses = NIL;
947 orderbyclausecols = NIL;
948 }
949
950 /*
951 * 3. Check if an index-only scan is possible. If we're not building
952 * plain indexscans, this isn't relevant since bitmap scans don't support
953 * index data retrieval anyway.
954 */
955 index_only_scan = (scantype != ST_BITMAPSCAN &&
957
958 /*
959 * 4. Generate an indexscan path if there are relevant restriction clauses
960 * in the current clauses, OR the index ordering is potentially useful for
961 * later merging or final output ordering, OR the index has a useful
962 * predicate, OR an index-only scan is possible.
963 */
965 index_only_scan)
966 {
968 index_clauses,
969 orderbyclauses,
970 orderbyclausecols,
971 useful_pathkeys,
972 ForwardScanDirection,
973 index_only_scan,
974 outer_relids,
975 loop_count,
976 false);
978
979 /*
980 * If appropriate, consider parallel index scan. We don't allow
981 * parallel index scan for bitmap index scans.
982 */
984 rel->consider_parallel && outer_relids == NULL &&
985 scantype != ST_BITMAPSCAN)
986 {
988 index_clauses,
989 orderbyclauses,
990 orderbyclausecols,
991 useful_pathkeys,
992 ForwardScanDirection,
993 index_only_scan,
994 outer_relids,
995 loop_count,
996 true);
997
998 /*
999 * if, after costing the path, we find that it's not worth using
1000 * parallel workers, just free it.
1001 */
1004 else
1005 pfree(ipath);
1006 }
1007 }
1008
1009 /*
1010 * 5. If the index is ordered, a backwards scan might be interesting.
1011 */
1012 if (index_is_ordered && pathkeys_possibly_useful)
1013 {
1015 BackwardScanDirection);
1017 index_pathkeys);
1019 {
1021 index_clauses,
1022 NIL,
1023 NIL,
1024 useful_pathkeys,
1025 BackwardScanDirection,
1026 index_only_scan,
1027 outer_relids,
1028 loop_count,
1029 false);
1031
1032 /* If appropriate, consider parallel index scan */
1034 rel->consider_parallel && outer_relids == NULL &&
1035 scantype != ST_BITMAPSCAN)
1036 {
1038 index_clauses,
1039 NIL,
1040 NIL,
1041 useful_pathkeys,
1042 BackwardScanDirection,
1043 index_only_scan,
1044 outer_relids,
1045 loop_count,
1046 true);
1047
1048 /*
1049 * if, after costing the path, we find that it's not worth
1050 * using parallel workers, just free it.
1051 */
1054 else
1055 pfree(ipath);
1056 }
1057 }
1058 }
1059
1061}
1062
1063/*
1064 * build_paths_for_OR
1065 * Given a list of restriction clauses from one arm of an OR clause,
1066 * construct all matching IndexPaths for the relation.
1067 *
1068 * Here we must scan all indexes of the relation, since a bitmap OR tree
1069 * can use multiple indexes.
1070 *
1071 * The caller actually supplies two lists of restriction clauses: some
1072 * "current" ones and some "other" ones. Both lists can be used freely
1073 * to match keys of the index, but an index must use at least one of the
1074 * "current" clauses to be considered usable. The motivation for this is
1075 * examples like
1076 * WHERE (x = 42) AND (... OR (y = 52 AND z = 77) OR ....)
1077 * While we are considering the y/z subclause of the OR, we can use "x = 42"
1078 * as one of the available index conditions; but we shouldn't match the
1079 * subclause to any index on x alone, because such a Path would already have
1080 * been generated at the upper level. So we could use an index on x,y,z
1081 * or an index on x,y for the OR subclause, but not an index on just x.
1082 * When dealing with a partial index, a match of the index predicate to
1083 * one of the "current" clauses also makes the index usable.
1084 *
1085 * 'rel' is the relation for which we want to generate index paths
1086 * 'clauses' is the current list of clauses (RestrictInfo nodes)
1087 * 'other_clauses' is the list of additional upper-level clauses
1088 */
1092{
1095 ListCell *lc;
1096
1098 {
1100 IndexClauseSet clauseset;
1101 List *indexpaths;
1102 bool useful_predicate;
1103
1104 /* Ignore index if it doesn't support bitmap scans */
1106 continue;
1107
1108 /*
1109 * Ignore partial indexes that do not match the query. If a partial
1110 * index is marked predOK then we know it's OK. Otherwise, we have to
1111 * test whether the added clauses are sufficient to imply the
1112 * predicate. If so, we can use the index in the current context.
1113 *
1114 * We set useful_predicate to true iff the predicate was proven using
1115 * the current set of clauses. This is needed to prevent matching a
1116 * predOK index to an arm of an OR, which would be a legal but
1117 * pointlessly inefficient plan. (A better plan will be generated by
1118 * just scanning the predOK index alone, no OR.)
1119 */
1120 useful_predicate = false;
1122 {
1124 {
1125 /* Usable, but don't set useful_predicate */
1126 }
1127 else
1128 {
1129 /* Form all_clauses if not done already */
1131 all_clauses = list_concat_copy(clauses, other_clauses);
1132
1134 continue; /* can't use it at all */
1135
1137 useful_predicate = true;
1138 }
1139 }
1140
1141 /*
1142 * Identify the restriction clauses that can match the index.
1143 */
1146
1147 /*
1148 * If no matches so far, and the index predicate isn't useful, we
1149 * don't want it.
1150 */
1152 continue;
1153
1154 /*
1155 * Add "other" restriction clauses to the clauseset.
1156 */
1158
1159 /*
1160 * Construct paths if possible.
1161 */
1163 index, &clauseset,
1164 useful_predicate,
1165 ST_BITMAPSCAN,
1166 NULL);
1168 }
1169
1171}
1172
1173/*
1174 * Utility structure used to group similar OR-clause arguments in
1175 * group_similar_or_args(). It represents information about the OR-clause
1176 * argument and its matching index key.
1177 */
1178typedef struct
1179{
1180 int indexnum; /* index of the matching index, or -1 if no
1181 * matching index */
1182 int colnum; /* index of the matching column, or -1 if no
1183 * matching index */
1185 * if not an OpExpr */
1187 int argindex; /* index of the clause in the list of
1188 * arguments */
1189 int groupindex; /* value of argindex for the fist clause in
1190 * the group of similar clauses */
1191} OrArgIndexMatch;
1192
1193/*
1194 * Comparison function for OrArgIndexMatch which provides sort order placing
1195 * similar OR-clause arguments together.
1196 */
1197static int
1199{
1202
1204 return -1;
1206 return 1;
1207
1209 return -1;
1211 return 1;
1212
1214 return -1;
1216 return 1;
1217
1219 return -1;
1221 return 1;
1222
1224 return -1;
1226 return 1;
1227
1228 return 0;
1229}
1230
1231/*
1232 * Another comparison function for OrArgIndexMatch. It sorts groups together
1233 * using groupindex. The group items are then sorted by argindex.
1234 */
1235static int
1237{
1240
1242 return -1;
1244 return 1;
1245
1247 return -1;
1249 return 1;
1250
1251 return 0;
1252}
1253
1254/*
1255 * group_similar_or_args
1256 * Transform incoming OR-restrictinfo into a list of sub-restrictinfos,
1257 * each of them containing a subset of similar OR-clause arguments from
1258 * the source rinfo.
1259 *
1260 * Similar OR-clause arguments are of the form "indexkey op constant" having
1261 * the same indexkey, operator, and collation. Constant may comprise either
1262 * Const or Param. It may be employed later, during the
1263 * match_clause_to_indexcol() to transform the whole OR-sub-rinfo to an SAOP
1264 * clause.
1265 *
1266 * Returns the processed list of OR-clause arguments.
1267 */
1270{
1271 int n;
1273 int group_start;
1274 OrArgIndexMatch *matches;
1275 bool matched = false;
1276 ListCell *lc;
1277 ListCell *lc2;
1278 List *orargs;
1281
1283 orargs = ((BoolExpr *) rinfo->orclause)->args;
1284 n = list_length(orargs);
1285
1286 /*
1287 * To avoid N^2 behavior, take utility pass along the list of OR-clause
1288 * arguments. For each argument, fill the OrArgIndexMatch structure,
1289 * which will be used to sort these arguments at the next step.
1290 */
1291 i = -1;
1293 foreach(lc, orargs)
1294 {
1296 RestrictInfo *argrinfo;
1297 OpExpr *clause;
1298 Oid opno;
1299 Node *leftop,
1300 *rightop;
1301 Node *nonConstExpr;
1302 int indexnum;
1303 int colnum;
1304
1305 i++;
1312
1314 continue;
1315
1317
1318 /* Only operator clauses can match */
1320 continue;
1321
1323 opno = clause->opno;
1324
1325 /* Only binary operators can match */
1327 continue;
1328
1329 /*
1330 * Ignore any RelabelType node above the operands. This is needed to
1331 * be able to apply indexscanning in binary-compatible-operator cases.
1332 * Note: we can assume there is at most one RelabelType node;
1333 * eval_const_expressions() will have simplified if more than one.
1334 */
1335 leftop = get_leftop(clause);
1338
1339 rightop = get_rightop(clause);
1342
1343 /*
1344 * Check for clauses of the form: (indexkey operator constant) or
1345 * (constant operator indexkey). But we don't know a particular index
1346 * yet. Therefore, we try to distinguish the potential index key and
1347 * constant first, then search for a matching index key among all
1348 * indexes.
1349 */
1351 !bms_is_member(relid, argrinfo->left_relids) &&
1352 !contain_volatile_functions(leftop))
1353 {
1354 opno = get_commutator(opno);
1355
1357 {
1358 /* commutator doesn't exist, we can't reverse the order */
1359 continue;
1360 }
1361 nonConstExpr = rightop;
1362 }
1364 !bms_is_member(relid, argrinfo->right_relids) &&
1365 !contain_volatile_functions(rightop))
1366 {
1367 nonConstExpr = leftop;
1368 }
1369 else
1370 {
1371 continue;
1372 }
1373
1374 /*
1375 * Match non-constant part to the index key. It's possible that a
1376 * single non-constant part matches multiple index keys. It's OK, we
1377 * just stop with first matching index key. Given that this choice is
1378 * determined the same for every clause, we will group similar clauses
1379 * together anyway.
1380 */
1381 indexnum = 0;
1383 {
1385
1386 /*
1387 * Ignore index if it doesn't support bitmap scans or SAOP
1388 * clauses.
1389 */
1391 continue;
1392
1394 {
1396 {
1401 matched = true;
1402 break;
1403 }
1404 }
1405
1406 /*
1407 * Stop looping through the indexes, if we managed to match
1408 * nonConstExpr to any index column.
1409 */
1411 break;
1412 indexnum++;
1413 }
1414 }
1415
1416 /*
1417 * Fast-path check: if no clause is matching to the index column, we can
1418 * just give up at this stage and return the clause list as-is.
1419 */
1420 if (!matched)
1421 {
1422 pfree(matches);
1423 return orargs;
1424 }
1425
1426 /*
1427 * Sort clauses to make similar clauses go together. But at the same
1428 * time, we would like to change the order of clauses as little as
1429 * possible. To do so, we reorder each group of similar clauses so that
1430 * the first item of the group stays in place, and all the other items are
1431 * moved after it. So, if there are no similar clauses, the order of
1432 * clauses stays the same. When there are some groups, required
1433 * reordering happens while the rest of the clauses remain in their
1434 * places. That is achieved by assigning a 'groupindex' to each clause:
1435 * the number of the first item in the group in the original clause list.
1436 */
1438
1439 /* Assign groupindex to the sorted clauses */
1441 {
1442 /*
1443 * When two clauses are similar and should belong to the same group,
1444 * copy the 'groupindex' from the previous clause. Given we are
1445 * considering clauses in direct order, all the clauses would have a
1446 * 'groupindex' equal to the 'groupindex' of the first clause in the
1447 * group.
1448 */
1453 matches[i].indexnum != -1)
1455 }
1456
1457 /* Re-sort clauses first by groupindex then by argindex */
1459
1460 /*
1461 * Group similar clauses into single sub-restrictinfo. Side effect: the
1462 * resulting list of restrictions will be sorted by indexnum and colnum.
1463 */
1464 group_start = 0;
1466 {
1467 /* Check if it's a group boundary */
1468 if (group_start >= 0 &&
1469 (i == n ||
1470 matches[i].indexnum != matches[group_start].indexnum ||
1471 matches[i].colnum != matches[group_start].colnum ||
1472 matches[i].opno != matches[group_start].opno ||
1473 matches[i].inputcollid != matches[group_start].inputcollid ||
1474 matches[i].indexnum == -1))
1475 {
1476 /*
1477 * One clause in group: add it "as is" to the upper-level OR.
1478 */
1480 {
1482 list_nth(orargs,
1483 matches[group_start].argindex));
1484 }
1485 else
1486 {
1487 /*
1488 * Two or more clauses in a group: create a nested OR.
1489 */
1492 RestrictInfo *subrinfo;
1494
1496
1497 /* Construct the list of nested OR arguments */
1499 {
1501
1505 else
1507 }
1508
1509 /* Construct the nested OR and wrap it with RestrictInfo */
1511 make_orclause(args),
1512 make_orclause(rargs),
1513 rinfo->is_pushed_down,
1514 rinfo->has_clone,
1515 rinfo->is_clone,
1516 rinfo->pseudoconstant,
1517 rinfo->security_level,
1518 rinfo->required_relids,
1519 rinfo->incompatible_relids,
1520 rinfo->outer_relids);
1522 }
1523
1524 group_start = i;
1525 }
1526 }
1527 pfree(matches);
1529}
1530
1531/*
1532 * make_bitmap_paths_for_or_group
1533 * Generate bitmap paths for a group of similar OR-clause arguments
1534 * produced by group_similar_or_args().
1535 *
1536 * This function considers two cases: (1) matching a group of clauses to
1537 * the index as a whole, and (2) matching the individual clauses one-by-one.
1538 * (1) typically comprises an optimal solution. If not, (2) typically
1539 * comprises fair alternative.
1540 *
1541 * Ideally, we could consider all arbitrary splits of arguments into
1542 * subgroups, but that could lead to unacceptable computational complexity.
1543 * This is why we only consider two cases of above.
1544 */
1548{
1551 ListCell *lc;
1552 List *orargs;
1554 Cost jointcost = 0.0,
1555 splitcost = 0.0;
1556 Path *bitmapqual;
1557 List *indlist;
1558
1559 /*
1560 * First, try to match the whole group to the one index.
1561 */
1562 orargs = list_make1(ri);
1564 orargs,
1565 other_clauses);
1567 {
1569 jointcost = bitmapqual->total_cost;
1570 jointlist = list_make1(bitmapqual);
1571 }
1572
1573 /*
1574 * If we manage to find a bitmap scan, which uses the group of OR-clause
1575 * arguments as a whole, we can skip matching OR-clause arguments
1576 * one-by-one as long as there are no other clauses, which can bring more
1577 * efficiency to one-by-one case.
1578 */
1580 return jointlist;
1581
1582 /*
1583 * Also try to match all containing clauses one-by-one.
1584 */
1585 foreach(lc, args)
1586 {
1588
1590 orargs,
1591 other_clauses);
1592
1594 {
1595 splitlist = NIL;
1596 break;
1597 }
1598
1600 splitcost += bitmapqual->total_cost;
1601 splitlist = lappend(splitlist, bitmapqual);
1602 }
1603
1604 /*
1605 * Pick the best option.
1606 */
1608 return jointlist;
1610 return splitlist;
1611 else
1612 return (jointcost < splitcost) ? jointlist : splitlist;
1613}
1614
1615
1616/*
1617 * generate_bitmap_or_paths
1618 * Look through the list of clauses to find OR clauses, and generate
1619 * a BitmapOrPath for each one we can handle that way. Return a list
1620 * of the generated BitmapOrPaths.
1621 *
1622 * other_clauses is a list of additional clauses that can be assumed true
1623 * for the purpose of generating indexquals, but are not to be searched for
1624 * ORs. (See build_paths_for_OR() for motivation.)
1625 */
1629{
1631 List *all_clauses;
1632 ListCell *lc;
1633
1634 /*
1635 * We can use both the current and other clauses as context for
1636 * build_paths_for_OR; no need to remove ORs from the lists.
1637 */
1638 all_clauses = list_concat_copy(clauses, other_clauses);
1639
1640 foreach(lc, clauses)
1641 {
1643 List *pathlist;
1644 Path *bitmapqual;
1646 List *groupedArgs;
1648
1649 /* Ignore RestrictInfos that aren't ORs */
1651 continue;
1652
1653 /*
1654 * We must be able to match at least one index to each of the arms of
1655 * the OR, else we can't use it.
1656 */
1657 pathlist = NIL;
1658
1659 /*
1660 * Group the similar OR-clause arguments into dedicated RestrictInfos,
1661 * because each of those RestrictInfos has a chance to match the index
1662 * as a whole.
1663 */
1665
1667 {
1668 /*
1669 * Some parts of the rinfo were probably grouped. In this case,
1670 * we have a set of sub-rinfos that together are an exact
1671 * duplicate of rinfo. Thus, we need to remove the rinfo from
1672 * other clauses. match_clauses_to_index detects duplicated
1673 * iclauses by comparing pointers to original rinfos that would be
1674 * different. So, we must delete rinfo to avoid de-facto
1675 * duplicated clauses in the index clauses list.
1676 */
1678 }
1679
1681 {
1683 List *indlist;
1684
1685 /* OR arguments should be ANDs or sub-RestrictInfos */
1687 {
1689
1691 andargs,
1692 all_clauses);
1693
1694 /* Recurse in case there are sub-ORs */
1695 indlist = list_concat(indlist,
1697 andargs,
1698 all_clauses));
1699 }
1701 {
1703
1704 /*
1705 * Generate bitmap paths for the group of similar OR-clause
1706 * arguments.
1707 */
1709 rel, ri,
1710 inner_other_clauses);
1711
1713 {
1714 pathlist = NIL;
1715 break;
1716 }
1717 else
1718 {
1719 pathlist = list_concat(pathlist, indlist);
1720 continue;
1721 }
1722 }
1723 else
1724 {
1726 List *orargs;
1727
1728 orargs = list_make1(ri);
1729
1731 orargs,
1732 all_clauses);
1733 }
1734
1735 /*
1736 * If nothing matched this arm, we can't do anything with this OR
1737 * clause.
1738 */
1740 {
1741 pathlist = NIL;
1742 break;
1743 }
1744
1745 /*
1746 * OK, pick the most promising AND combination, and add it to
1747 * pathlist.
1748 */
1750 pathlist = lappend(pathlist, bitmapqual);
1751 }
1752
1754 list_free(inner_other_clauses);
1755
1756 /*
1757 * If we have a match for every arm, then turn them into a
1758 * BitmapOrPath, and add to result list.
1759 */
1761 {
1764 }
1765 }
1766
1768}
1769
1770
1771/*
1772 * choose_bitmap_and
1773 * Given a nonempty list of bitmap paths, AND them into one path.
1774 *
1775 * This is a nontrivial decision since we can legally use any subset of the
1776 * given path set. We want to choose a good tradeoff between selectivity
1777 * and cost of computing the bitmap.
1778 *
1779 * The result is either a single one of the inputs, or a BitmapAndPath
1780 * combining multiple inputs.
1781 */
1784{
1786 PathClauseUsage **pathinfoarray;
1787 PathClauseUsage *pathinfo;
1788 List *clauselist;
1790 Cost bestcost = 0;
1792 j;
1793 ListCell *l;
1794
1796 if (npaths == 1)
1798
1799 /*
1800 * In theory we should consider every nonempty subset of the given paths.
1801 * In practice that seems like overkill, given the crude nature of the
1802 * estimates, not to mention the possible effects of higher-level AND and
1803 * OR clauses. Moreover, it's completely impractical if there are a large
1804 * number of paths, since the work would grow as O(2^N).
1805 *
1806 * As a heuristic, we first check for paths using exactly the same sets of
1807 * WHERE clauses + index predicate conditions, and reject all but the
1808 * cheapest-to-scan in any such group. This primarily gets rid of indexes
1809 * that include the interesting columns but also irrelevant columns. (In
1810 * situations where the DBA has gone overboard on creating variant
1811 * indexes, this can make for a very large reduction in the number of
1812 * paths considered further.)
1813 *
1814 * We then sort the surviving paths with the cheapest-to-scan first, and
1815 * for each path, consider using that path alone as the basis for a bitmap
1816 * scan. Then we consider bitmap AND scans formed from that path plus
1817 * each subsequent (higher-cost) path, adding on a subsequent path if it
1818 * results in a reduction in the estimated total scan cost. This means we
1819 * consider about O(N^2) rather than O(2^N) path combinations, which is
1820 * quite tolerable, especially given than N is usually reasonably small
1821 * because of the prefiltering step. The cheapest of these is returned.
1822 *
1823 * We will only consider AND combinations in which no two indexes use the
1824 * same WHERE clause. This is a bit of a kluge: it's needed because
1825 * costsize.c and clausesel.c aren't very smart about redundant clauses.
1826 * They will usually double-count the redundant clauses, producing a
1827 * too-small selectivity that makes a redundant AND step look like it
1828 * reduces the total cost. Perhaps someday that code will be smarter and
1829 * we can remove this limitation. (But note that this also defends
1830 * against flat-out duplicate input paths, which can happen because
1831 * match_join_clauses_to_index will find the same OR join clauses that
1832 * extract_restriction_or_clauses has pulled OR restriction clauses out
1833 * of.)
1834 *
1835 * For the same reason, we reject AND combinations in which an index
1836 * predicate clause duplicates another clause. Here we find it necessary
1837 * to be even stricter: we'll reject a partial index if any of its
1838 * predicate clauses are implied by the set of WHERE clauses and predicate
1839 * clauses used so far. This covers cases such as a condition "x = 42"
1840 * used with a plain index, followed by a clauseless scan of a partial
1841 * index "WHERE x >= 40 AND x < 50". The partial index has been accepted
1842 * only because "x = 42" was present, and so allowing it would partially
1843 * double-count selectivity. (We could use predicate_implied_by on
1844 * regular qual clauses too, to have a more intelligent, but much more
1845 * expensive, check for redundancy --- but in most cases simple equality
1846 * seems to suffice.)
1847 */
1848
1849 /*
1850 * Extract clause usage info and detect any paths that use exactly the
1851 * same set of clauses; keep only the cheapest-to-scan of any such groups.
1852 * The surviving paths are put into an array for qsort'ing.
1853 */
1855 clauselist = NIL;
1856 npaths = 0;
1857 foreach(l, paths)
1858 {
1860
1861 pathinfo = classify_index_clause_usage(ipath, &clauselist);
1862
1863 /* If it's unclassifiable, treat it as distinct from all others */
1865 {
1866 pathinfoarray[npaths++] = pathinfo;
1867 continue;
1868 }
1869
1871 {
1874 break;
1875 }
1877 {
1878 /* duplicate clauseids, keep the cheaper one */
1879 Cost ncost;
1880 Cost ocost;
1881 Selectivity nselec;
1882 Selectivity oselec;
1883
1886 if (ncost < ocost)
1887 pathinfoarray[i] = pathinfo;
1888 }
1889 else
1890 {
1891 /* not duplicate clauseids, add to array */
1892 pathinfoarray[npaths++] = pathinfo;
1893 }
1894 }
1895
1896 /* If only one surviving path, we're done */
1897 if (npaths == 1)
1899
1900 /* Sort the surviving paths by index access cost */
1902 path_usage_comparator);
1903
1904 /*
1905 * For each surviving index, consider it as an "AND group leader", and see
1906 * whether adding on any of the later indexes results in an AND path with
1907 * cheaper total cost than before. Then take the cheapest AND group.
1908 *
1909 * Note: paths that are either clauseless or unclassifiable will have
1910 * empty clauseids, so that they will not be rejected by the clauseids
1911 * filter here, nor will they cause later paths to be rejected by it.
1912 */
1914 {
1915 Cost costsofar;
1916 List *qualsofar;
1917 Bitmapset *clauseidsofar;
1918
1919 pathinfo = pathinfoarray[i];
1924
1926 {
1927 Cost newcost;
1928
1929 pathinfo = pathinfoarray[j];
1930 /* Check for redundancy */
1932 continue; /* consider it redundant */
1934 {
1935 bool redundant = false;
1936
1937 /* we check each predicate clause separately */
1939 {
1941
1943 {
1944 redundant = true;
1945 break; /* out of inner foreach loop */
1946 }
1947 }
1948 if (redundant)
1949 continue;
1950 }
1951 /* tentatively add new path to paths, so we can estimate cost */
1954 if (newcost < costsofar)
1955 {
1956 /* keep new path in paths, update subsidiary variables */
1957 costsofar = newcost;
1960 clauseidsofar = bms_add_members(clauseidsofar,
1961 pathinfo->clauseids);
1962 }
1963 else
1964 {
1965 /* reject new path, remove it from paths list */
1967 }
1968 }
1969
1970 /* Keep the cheapest AND-group (or singleton) */
1972 {
1973 bestpaths = paths;
1974 bestcost = costsofar;
1975 }
1976
1977 /* some easy cleanup (we don't try real hard though) */
1978 list_free(qualsofar);
1979 }
1980
1984}
1985
1986/* qsort comparator to sort in increasing index access cost order */
1987static int
1989{
1992 Cost acost;
1993 Cost bcost;
1994 Selectivity aselec;
1995 Selectivity bselec;
1996
1999
2000 /*
2001 * If costs are the same, sort by selectivity.
2002 */
2003 if (acost < bcost)
2004 return -1;
2005 if (acost > bcost)
2006 return 1;
2007
2008 if (aselec < bselec)
2009 return -1;
2010 if (aselec > bselec)
2011 return 1;
2012
2013 return 0;
2014}
2015
2016/*
2017 * Estimate the cost of actually executing a bitmap scan with a single
2018 * index path (which could be a BitmapAnd or BitmapOr node).
2019 */
2022{
2023 BitmapHeapPath bpath;
2024
2025 /* Set up a dummy BitmapHeapPath */
2026 bpath.path.type = T_BitmapHeapPath;
2028 bpath.path.parent = rel;
2030 bpath.path.param_info = ipath->param_info;
2032 bpath.bitmapqual = ipath;
2033
2034 /*
2035 * Check the cost of temporary path without considering parallelism.
2036 * Parallel bitmap heap path will be considered at later stage.
2037 */
2039
2040 /* Now we can do cost_bitmap_heap_scan */
2042 bpath.path.param_info,
2043 ipath,
2045 PATH_REQ_OUTER(ipath)));
2046
2048}
2049
2050/*
2051 * Estimate the cost of actually executing a BitmapAnd scan with the given
2052 * inputs.
2053 */
2056{
2057 BitmapAndPath *apath;
2058
2059 /*
2060 * Might as well build a real BitmapAndPath here, as the work is slightly
2061 * too complicated to be worth repeating just to save one palloc.
2062 */
2064
2066}
2067
2068
2069/*
2070 * classify_index_clause_usage
2071 * Construct a PathClauseUsage struct describing the WHERE clauses and
2072 * index predicate clauses used by the given indexscan path.
2073 * We consider two clauses the same if they are equal().
2074 *
2075 * At some point we might want to migrate this info into the Path data
2076 * structure proper, but for the moment it's only needed within
2077 * choose_bitmap_and().
2078 *
2079 * *clauselist is used and expanded as needed to identify all the distinct
2080 * clauses seen across successive calls. Caller must initialize it to NIL
2081 * before first call of a set.
2082 */
2085{
2087 Bitmapset *clauseids;
2088 ListCell *lc;
2089
2091 result->path = path;
2092
2093 /* Recursively find the quals and preds used by the path */
2097
2098 /*
2099 * Some machine-generated queries have outlandish numbers of qual clauses.
2100 * To avoid getting into O(N^2) behavior even in this preliminary
2101 * classification step, we want to limit the number of entries we can
2102 * accumulate in *clauselist. Treat any path with more than 100 quals +
2103 * preds as unclassifiable, which will cause calling code to consider it
2104 * distinct from all other paths.
2105 */
2107 {
2108 result->clauseids = NULL;
2111 }
2112
2113 /* Build up a bitmapset representing the quals and preds */
2114 clauseids = NULL;
2116 {
2118
2119 clauseids = bms_add_member(clauseids,
2120 find_list_position(node, clauselist));
2121 }
2123 {
2125
2126 clauseids = bms_add_member(clauseids,
2127 find_list_position(node, clauselist));
2128 }
2129 result->clauseids = clauseids;
2131
2133}
2134
2135
2136/*
2137 * find_indexpath_quals
2138 *
2139 * Given the Path structure for a plain or bitmap indexscan, extract lists
2140 * of all the index clauses and index predicate conditions used in the Path.
2141 * These are appended to the initial contents of *quals and *preds (hence
2142 * caller should initialize those to NIL).
2143 *
2144 * Note we are not trying to produce an accurate representation of the AND/OR
2145 * semantics of the Path, but just find out all the base conditions used.
2146 *
2147 * The result lists contain pointers to the expressions used in the Path,
2148 * but all the list cells are freshly built, so it's safe to destructively
2149 * modify the lists (eg, by concat'ing with other lists).
2150 */
2151static void
2153{
2155 {
2157 ListCell *l;
2158
2160 {
2162 }
2163 }
2165 {
2167 ListCell *l;
2168
2170 {
2172 }
2173 }
2175 {
2177 ListCell *l;
2178
2180 {
2182
2184 }
2186 }
2187 else
2189}
2190
2191
2192/*
2193 * find_list_position
2194 * Return the given node's position (counting from 0) in the given
2195 * list of nodes. If it's not equal() to any existing list member,
2196 * add it at the end, and return that position.
2197 */
2198static int
2200{
2202 ListCell *lc;
2203
2204 i = 0;
2205 foreach(lc, *nodelist)
2206 {
2208
2211 i++;
2212 }
2213
2214 *nodelist = lappend(*nodelist, node);
2215
2217}
2218
2219
2220/*
2221 * check_index_only
2222 * Determine whether an index-only scan is possible for this index.
2223 */
2224static bool
2226{
2228 Bitmapset *attrs_used = NULL;
2229 Bitmapset *index_canreturn_attrs = NULL;
2230 ListCell *lc;
2232
2233 /* If we're not allowed to consider index-only scans, give up now */
2235 return false;
2236
2237 /*
2238 * Check that all needed attributes of the relation are available from the
2239 * index.
2240 */
2241
2242 /*
2243 * First, identify all the attributes needed for joins or final output.
2244 * Note: we must look at rel's targetlist, not the attr_needed data,
2245 * because attr_needed isn't computed for inheritance child rels.
2246 */
2248
2249 /*
2250 * Add all the attributes used by restriction clauses; but consider only
2251 * those clauses not implied by the index predicate, since ones that are
2252 * so implied don't need to be checked explicitly in the plan.
2253 *
2254 * Note: attributes used only in index quals would not be needed at
2255 * runtime either, if we are certain that the index is not lossy. However
2256 * it'd be complicated to account for that accurately, and it doesn't
2257 * matter in most cases, since we'd conclude that such attributes are
2258 * available from the index anyway.
2259 */
2261 {
2263
2265 }
2266
2267 /*
2268 * Construct a bitmapset of columns that the index can return back in an
2269 * index-only scan.
2270 */
2272 {
2274
2275 /*
2276 * For the moment, we just ignore index expressions. It might be nice
2277 * to do something with them, later.
2278 */
2279 if (attno == 0)
2280 continue;
2281
2283 index_canreturn_attrs =
2284 bms_add_member(index_canreturn_attrs,
2285 attno - FirstLowInvalidHeapAttributeNumber);
2286 }
2287
2288 /* Do we have all the necessary attributes? */
2290
2291 bms_free(attrs_used);
2292 bms_free(index_canreturn_attrs);
2293
2295}
2296
2297/*
2298 * get_loop_count
2299 * Choose the loop count estimate to use for costing a parameterized path
2300 * with the given set of outer relids.
2301 *
2302 * Since we produce parameterized paths before we've begun to generate join
2303 * relations, it's impossible to predict exactly how many times a parameterized
2304 * path will be iterated; we don't know the size of the relation that will be
2305 * on the outside of the nestloop. However, we should try to account for
2306 * multiple iterations somehow in costing the path. The heuristic embodied
2307 * here is to use the rowcount of the smallest other base relation needed in
2308 * the join clauses used by the path. (We could alternatively consider the
2309 * largest one, but that seems too optimistic.) This is of course the right
2310 * answer for single-other-relation cases, and it seems like a reasonable
2311 * zero-order approximation for multiway-join cases.
2312 *
2313 * In addition, we check to see if the other side of each join clause is on
2314 * the inside of some semijoin that the current relation is on the outside of.
2315 * If so, the only way that a parameterized path could be used is if the
2316 * semijoin RHS has been unique-ified, so we should use the number of unique
2317 * RHS rows rather than using the relation's raw rowcount.
2318 *
2319 * Note: for this to work, allpaths.c must establish all baserel size
2320 * estimates before it begins to compute paths, or at least before it
2321 * calls create_index_paths().
2322 */
2323static double
2325{
2327 int outer_relid;
2328
2329 /* For a non-parameterized path, just return 1.0 quickly */
2330 if (outer_relids == NULL)
2331 return 1.0;
2332
2333 result = 0.0;
2334 outer_relid = -1;
2336 {
2337 RelOptInfo *outer_rel;
2338 double rowcount;
2339
2340 /* Paranoia: ignore bogus relid indexes */
2342 continue;
2343 outer_rel = root->simple_rel_array[outer_relid];
2344 if (outer_rel == NULL)
2345 continue;
2347
2348 /* Other relation could be proven empty, if so ignore */
2350 continue;
2351
2352 /* Otherwise, rel's rows estimate should be valid by now */
2354
2355 /* Check to see if rel is on the inside of any semijoins */
2357 cur_relid,
2358 outer_relid,
2359 outer_rel->rows);
2360
2361 /* Remember smallest row count estimate among the outer rels */
2363 result = rowcount;
2364 }
2365 /* Return 1.0 if we found no valid relations (shouldn't happen) */
2367}
2368
2369/*
2370 * Check to see if outer_relid is on the inside of any semijoin that cur_relid
2371 * is on the outside of. If so, replace rowcount with the estimated number of
2372 * unique rows from the semijoin RHS (assuming that's smaller, which it might
2373 * not be). The estimate is crude but it's the best we can do at this stage
2374 * of the proceedings.
2375 */
2376static double
2378 Index cur_relid,
2379 Index outer_relid,
2380 double rowcount)
2381{
2382 ListCell *lc;
2383
2385 {
2387
2391 {
2392 /* Estimate number of unique-ified rows */
2393 double nraw;
2394 double nunique;
2395
2398 sjinfo->semi_rhs_exprs,
2399 nraw,
2400 NULL,
2401 NULL);
2402 if (rowcount > nunique)
2403 rowcount = nunique;
2404 }
2405 }
2406 return rowcount;
2407}
2408
2409/*
2410 * Make an approximate estimate of the size of a joinrel.
2411 *
2412 * We don't have enough info at this point to get a good estimate, so we
2413 * just multiply the base relation sizes together. Fortunately, this is
2414 * the right answer anyway for the most common case with a single relation
2415 * on the RHS of a semijoin. Also, estimate_num_groups() has only a weak
2416 * dependency on its input_rows argument (it basically uses it as a clamp).
2417 * So we might be able to get a fairly decent end result even with a severe
2418 * overestimate of the RHS's raw size.
2419 */
2420static double
2422{
2423 double rowcount = 1.0;
2424 int relid;
2425
2426 relid = -1;
2428 {
2429 RelOptInfo *rel;
2430
2431 /* Paranoia: ignore bogus relid indexes */
2433 continue;
2434 rel = root->simple_rel_array[relid];
2435 if (rel == NULL)
2436 continue;
2438
2439 /* Relation could be proven empty, if so ignore */
2441 continue;
2442
2443 /* Otherwise, rel's rows estimate should be valid by now */
2445
2446 /* Accumulate product */
2447 rowcount *= rel->rows;
2448 }
2449 return rowcount;
2450}
2451
2452
2453/****************************************************************************
2454 * ---- ROUTINES TO CHECK QUERY CLAUSES ----
2455 ****************************************************************************/
2456
2457/*
2458 * match_restriction_clauses_to_index
2459 * Identify restriction clauses for the rel that match the index.
2460 * Matching clauses are added to *clauseset.
2461 */
2462static void
2465 IndexClauseSet *clauseset)
2466{
2467 /* We can ignore clauses that are implied by the index predicate */
2469}
2470
2471/*
2472 * match_join_clauses_to_index
2473 * Identify join clauses for the rel that match the index.
2474 * Matching clauses are added to *clauseset.
2475 * Also, add any potentially usable join OR clauses to *joinorclauses.
2476 * They also might be processed by match_clause_to_index() as a whole.
2477 */
2478static void
2481 IndexClauseSet *clauseset,
2482 List **joinorclauses)
2483{
2484 ListCell *lc;
2485
2486 /* Scan the rel's join clauses */
2488 {
2490
2491 /* Check if clause can be moved to this rel */
2493 continue;
2494
2495 /*
2496 * Potentially usable, so see if it matches the index or is an OR. Use
2497 * list_append_unique_ptr() here to avoid possible duplicates when
2498 * processing the same clauses with different indexes.
2499 */
2501 *joinorclauses = list_append_unique_ptr(*joinorclauses, rinfo);
2502
2504 }
2505}
2506
2507/*
2508 * match_eclass_clauses_to_index
2509 * Identify EquivalenceClass join clauses for the rel that match the index.
2510 * Matching clauses are added to *clauseset.
2511 */
2512static void
2514 IndexClauseSet *clauseset)
2515{
2516 int indexcol;
2517
2518 /* No work if rel is not in any such ECs */
2520 return;
2521
2523 {
2525 List *clauses;
2526
2527 /* Generate clauses, skipping any that join to lateral_referencers */
2529 arg.indexcol = indexcol;
2531 index->rel,
2533 &arg,
2534 index->rel->lateral_referencers);
2535
2536 /*
2537 * We have to check whether the results actually do match the index,
2538 * since for non-btree indexes the EC's equality operators might not
2539 * be in the index opclass (cf ec_member_matches_indexcol).
2540 */
2542 }
2543}
2544
2545/*
2546 * match_clauses_to_index
2547 * Perform match_clause_to_index() for each clause in a list.
2548 * Matching clauses are added to *clauseset.
2549 */
2550static void
2552 List *clauses,
2554 IndexClauseSet *clauseset)
2555{
2556 ListCell *lc;
2557
2558 foreach(lc, clauses)
2559 {
2561
2563 }
2564}
2565
2566/*
2567 * match_clause_to_index
2568 * Test whether a qual clause can be used with an index.
2569 *
2570 * If the clause is usable, add an IndexClause entry for it to the appropriate
2571 * list in *clauseset. (*clauseset must be initialized to zeroes before first
2572 * call.)
2573 *
2574 * Note: in some circumstances we may find the same RestrictInfos coming from
2575 * multiple places. Defend against redundant outputs by refusing to add a
2576 * clause twice (pointer equality should be a good enough check for this).
2577 *
2578 * Note: it's possible that a badly-defined index could have multiple matching
2579 * columns. We always select the first match if so; this avoids scenarios
2580 * wherein we get an inflated idea of the index's selectivity by using the
2581 * same clause multiple times with different index columns.
2582 */
2583static void
2585 RestrictInfo *rinfo,
2587 IndexClauseSet *clauseset)
2588{
2589 int indexcol;
2590
2591 /*
2592 * Never match pseudoconstants to indexes. (Normally a match could not
2593 * happen anyway, since a pseudoconstant clause couldn't contain a Var,
2594 * but what if someone builds an expression index on a constant? It's not
2595 * totally unreasonable to do so with a partial index, either.)
2596 */
2597 if (rinfo->pseudoconstant)
2598 return;
2599
2600 /*
2601 * If clause can't be used as an indexqual because it must wait till after
2602 * some lower-security-level restriction clause, reject it.
2603 */
2605 return;
2606
2607 /* OK, check each index key column for a match */
2609 {
2610 IndexClause *iclause;
2611 ListCell *lc;
2612
2613 /* Ignore duplicates */
2615 {
2617
2619 return;
2620 }
2621
2622 /* OK, try to match the clause to the index column */
2624 rinfo,
2625 indexcol,
2626 index);
2627 if (iclause)
2628 {
2629 /* Success, so record it */
2630 clauseset->indexclauses[indexcol] =
2633 return;
2634 }
2635 }
2636}
2637
2638/*
2639 * match_clause_to_indexcol()
2640 * Determine whether a restriction clause matches a column of an index,
2641 * and if so, build an IndexClause node describing the details.
2642 *
2643 * To match an index normally, an operator clause:
2644 *
2645 * (1) must be in the form (indexkey op const) or (const op indexkey);
2646 * and
2647 * (2) must contain an operator which is in the index's operator family
2648 * for this column; and
2649 * (3) must match the collation of the index, if collation is relevant.
2650 *
2651 * Our definition of "const" is exceedingly liberal: we allow anything that
2652 * doesn't involve a volatile function or a Var of the index's relation.
2653 * In particular, Vars belonging to other relations of the query are
2654 * accepted here, since a clause of that form can be used in a
2655 * parameterized indexscan. It's the responsibility of higher code levels
2656 * to manage restriction and join clauses appropriately.
2657 *
2658 * Note: we do need to check for Vars of the index's relation on the
2659 * "const" side of the clause, since clauses like (a.f1 OP (b.f2 OP a.f3))
2660 * are not processable by a parameterized indexscan on a.f1, whereas
2661 * something like (a.f1 OP (b.f2 OP c.f3)) is.
2662 *
2663 * Presently, the executor can only deal with indexquals that have the
2664 * indexkey on the left, so we can only use clauses that have the indexkey
2665 * on the right if we can commute the clause to put the key on the left.
2666 * We handle that by generating an IndexClause with the correctly-commuted
2667 * opclause as a derived indexqual.
2668 *
2669 * If the index has a collation, the clause must have the same collation.
2670 * For collation-less indexes, we assume it doesn't matter; this is
2671 * necessary for cases like "hstore ? text", wherein hstore's operators
2672 * don't care about collation but the clause will get marked with a
2673 * collation anyway because of the text argument. (This logic is
2674 * embodied in the macro IndexCollMatchesExprColl.)
2675 *
2676 * It is also possible to match RowCompareExpr clauses to indexes (but
2677 * currently, only btree indexes handle this).
2678 *
2679 * It is also possible to match ScalarArrayOpExpr clauses to indexes, when
2680 * the clause is of the form "indexkey op ANY (arrayconst)".
2681 *
2682 * It is also possible to match a list of OR clauses if it might be
2683 * transformed into a single ScalarArrayOpExpr clause. On success,
2684 * the returning index clause will contain a transformed clause.
2685 *
2686 * For boolean indexes, it is also possible to match the clause directly
2687 * to the indexkey; or perhaps the clause is (NOT indexkey).
2688 *
2689 * And, last but not least, some operators and functions can be processed
2690 * to derive (typically lossy) indexquals from a clause that isn't in
2691 * itself indexable. If we see that any operand of an OpExpr or FuncExpr
2692 * matches the index key, and the function has a planner support function
2693 * attached to it, we'll invoke the support function to see if such an
2694 * indexqual can be built.
2695 *
2696 * 'rinfo' is the clause to be tested (as a RestrictInfo node).
2697 * 'indexcol' is a column number of 'index' (counting from 0).
2698 * 'index' is the index of interest.
2699 *
2700 * Returns an IndexClause if the clause can be used with this index key,
2701 * or NULL if not.
2702 *
2703 * NOTE: This routine always returns NULL if the clause is an AND clause.
2704 * Higher-level routines deal with OR and AND clauses. OR clause can be
2705 * matched as a whole by match_orclause_to_indexcol() though.
2706 */
2709 RestrictInfo *rinfo,
2710 int indexcol,
2712{
2713 IndexClause *iclause;
2715 Oid opfamily;
2716
2717 Assert(indexcol < index->nkeycolumns);
2718
2719 /*
2720 * Historically this code has coped with NULL clauses. That's probably
2721 * not possible anymore, but we might as well continue to cope.
2722 */
2723 if (clause == NULL)
2724 return NULL;
2725
2726 /* First check for boolean-index cases. */
2727 opfamily = index->opfamily[indexcol];
2729 {
2731 if (iclause)
2732 return iclause;
2733 }
2734
2735 /*
2736 * Clause must be an opclause, funcclause, ScalarArrayOpExpr,
2737 * RowCompareExpr, or OR-clause that could be converted to SAOP. Or, if
2738 * the index supports it, we can handle IS NULL/NOT NULL clauses.
2739 */
2741 {
2743 }
2745 {
2747 }
2749 {
2751 }
2753 {
2755 }
2757 {
2759 }
2761 {
2763
2764 if (!nt->argisrow &&
2766 {
2768 iclause->rinfo = rinfo;
2771 iclause->indexcol = indexcol;
2773 return iclause;
2774 }
2775 }
2776
2777 return NULL;
2778}
2779
2780/*
2781 * IsBooleanOpfamily
2782 * Detect whether an opfamily supports boolean equality as an operator.
2783 *
2784 * If the opfamily OID is in the range of built-in objects, we can rely
2785 * on hard-wired knowledge of which built-in opfamilies support this.
2786 * For extension opfamilies, there's no choice but to do a catcache lookup.
2787 */
2788static bool
2790{
2792 return IsBuiltinBooleanOpfamily(opfamily);
2793 else
2795}
2796
2797/*
2798 * match_boolean_index_clause
2799 * Recognize restriction clauses that can be matched to a boolean index.
2800 *
2801 * The idea here is that, for an index on a boolean column that supports the
2802 * BooleanEqualOperator, we can transform a plain reference to the indexkey
2803 * into "indexkey = true", or "NOT indexkey" into "indexkey = false", etc,
2804 * so as to make the expression indexable using the index's "=" operator.
2805 * Since Postgres 8.1, we must do this because constant simplification does
2806 * the reverse transformation; without this code there'd be no way to use
2807 * such an index at all.
2808 *
2809 * This should be called only when IsBooleanOpfamily() recognizes the
2810 * index's operator family. We check to see if the clause matches the
2811 * index's key, and if so, build a suitable IndexClause.
2812 */
2815 RestrictInfo *rinfo,
2816 int indexcol,
2818{
2820 Expr *op = NULL;
2821
2822 /* Direct match? */
2824 {
2825 /* convert to indexkey = TRUE */
2827 (Expr *) clause,
2830 }
2831 /* NOT clause? */
2833 {
2835
2837 {
2838 /* convert to indexkey = FALSE */
2843 }
2844 }
2845
2846 /*
2847 * Since we only consider clauses at top level of WHERE, we can convert
2848 * indexkey IS TRUE and indexkey IS FALSE to index searches as well. The
2849 * different meaning for NULL isn't important.
2850 */
2852 {
2855
2858 {
2859 /* convert to indexkey = TRUE */
2864 }
2867 {
2868 /* convert to indexkey = FALSE */
2873 }
2874 }
2875
2876 /*
2877 * If we successfully made an operator clause from the given qual, we must
2878 * wrap it in an IndexClause. It's not lossy.
2879 */
2880 if (op)
2881 {
2883
2884 iclause->rinfo = rinfo;
2887 iclause->indexcol = indexcol;
2889 return iclause;
2890 }
2891
2892 return NULL;
2893}
2894
2895/*
2896 * match_opclause_to_indexcol()
2897 * Handles the OpExpr case for match_clause_to_indexcol(),
2898 * which see for comments.
2899 */
2902 RestrictInfo *rinfo,
2903 int indexcol,
2905{
2906 IndexClause *iclause;
2908 Node *leftop,
2909 *rightop;
2910 Oid expr_op;
2911 Oid expr_coll;
2912 Index index_relid;
2913 Oid opfamily;
2914 Oid idxcollation;
2915
2916 /*
2917 * Only binary operators need apply. (In theory, a planner support
2918 * function could do something with a unary operator, but it seems
2919 * unlikely to be worth the cycles to check.)
2920 */
2922 return NULL;
2923
2926 expr_op = clause->opno;
2927 expr_coll = clause->inputcollid;
2928
2929 index_relid = index->rel->relid;
2930 opfamily = index->opfamily[indexcol];
2931 idxcollation = index->indexcollations[indexcol];
2932
2933 /*
2934 * Check for clauses of the form: (indexkey operator constant) or
2935 * (constant operator indexkey). See match_clause_to_indexcol's notes
2936 * about const-ness.
2937 *
2938 * Note that we don't ask the support function about clauses that don't
2939 * have one of these forms. Again, in principle it might be possible to
2940 * do something, but it seems unlikely to be worth the cycles to check.
2941 */
2943 !bms_is_member(index_relid, rinfo->right_relids) &&
2944 !contain_volatile_functions(rightop))
2945 {
2947 op_in_opfamily(expr_op, opfamily))
2948 {
2950 iclause->rinfo = rinfo;
2953 iclause->indexcol = indexcol;
2955 return iclause;
2956 }
2957
2958 /*
2959 * If we didn't find a member of the index's opfamily, try the support
2960 * function for the operator's underlying function.
2961 */
2964 rinfo,
2965 clause->opfuncid,
2966 0, /* indexarg on left */
2967 indexcol,
2968 index);
2969 }
2970
2972 !bms_is_member(index_relid, rinfo->left_relids) &&
2973 !contain_volatile_functions(leftop))
2974 {
2976 {
2978
2980 op_in_opfamily(comm_op, opfamily))
2981 {
2982 RestrictInfo *commrinfo;
2983
2984 /* Build a commuted OpExpr and RestrictInfo */
2985 commrinfo = commute_restrictinfo(rinfo, comm_op);
2986
2987 /* Make an IndexClause showing that as a derived qual */
2989 iclause->rinfo = rinfo;
2992 iclause->indexcol = indexcol;
2994 return iclause;
2995 }
2996 }
2997
2998 /*
2999 * If we didn't find a member of the index's opfamily, try the support
3000 * function for the operator's underlying function.
3001 */
3004 rinfo,
3005 clause->opfuncid,
3006 1, /* indexarg on right */
3007 indexcol,
3008 index);
3009 }
3010
3011 return NULL;
3012}
3013
3014/*
3015 * match_funcclause_to_indexcol()
3016 * Handles the FuncExpr case for match_clause_to_indexcol(),
3017 * which see for comments.
3018 */
3021 RestrictInfo *rinfo,
3022 int indexcol,
3024{
3026 int indexarg;
3027 ListCell *lc;
3028
3029 /*
3030 * We have no built-in intelligence about function clauses, but if there's
3031 * a planner support function, it might be able to do something. But, to
3032 * cut down on wasted planning cycles, only call the support function if
3033 * at least one argument matches the target index column.
3034 *
3035 * Note that we don't insist on the other arguments being pseudoconstants;
3036 * the support function has to check that. This is to allow cases where
3037 * only some of the other arguments need to be included in the indexqual.
3038 */
3039 indexarg = 0;
3040 foreach(lc, clause->args)
3041 {
3043
3045 {
3047 rinfo,
3048 clause->funcid,
3049 indexarg,
3050 indexcol,
3051 index);
3052 }
3053
3054 indexarg++;
3055 }
3056
3057 return NULL;
3058}
3059
3060/*
3061 * get_index_clause_from_support()
3062 * If the function has a planner support function, try to construct
3063 * an IndexClause using indexquals created by the support function.
3064 */
3067 RestrictInfo *rinfo,
3068 Oid funcid,
3069 int indexarg,
3070 int indexcol,
3072{
3074 SupportRequestIndexCondition req;
3075 List *sresult;
3076
3078 return NULL;
3079
3080 req.type = T_SupportRequestIndexCondition;
3082 req.funcid = funcid;
3084 req.indexarg = indexarg;
3086 req.indexcol = indexcol;
3089
3091
3092 sresult = (List *)
3094 PointerGetDatum(&req)));
3095
3097 {
3100 ListCell *lc;
3101
3102 /*
3103 * The support function API says it should just give back bare
3104 * clauses, so here we must wrap each one in a RestrictInfo.
3105 */
3106 foreach(lc, sresult)
3107 {
3109
3110 indexquals = lappend(indexquals,
3112 }
3113
3114 iclause->rinfo = rinfo;
3115 iclause->indexquals = indexquals;
3117 iclause->indexcol = indexcol;
3119
3120 return iclause;
3121 }
3122
3123 return NULL;
3124}
3125
3126/*
3127 * match_saopclause_to_indexcol()
3128 * Handles the ScalarArrayOpExpr case for match_clause_to_indexcol(),
3129 * which see for comments.
3130 */
3133 RestrictInfo *rinfo,
3134 int indexcol,
3136{
3138 Node *leftop,
3139 *rightop;
3140 Relids right_relids;
3141 Oid expr_op;
3142 Oid expr_coll;
3143 Index index_relid;
3144 Oid opfamily;
3145 Oid idxcollation;
3146
3147 /* We only accept ANY clauses, not ALL */
3148 if (!saop->useOr)
3149 return NULL;
3153 expr_op = saop->opno;
3154 expr_coll = saop->inputcollid;
3155
3156 index_relid = index->rel->relid;
3157 opfamily = index->opfamily[indexcol];
3158 idxcollation = index->indexcollations[indexcol];
3159
3160 /*
3161 * We must have indexkey on the left and a pseudo-constant array argument.
3162 */
3164 !bms_is_member(index_relid, right_relids) &&
3165 !contain_volatile_functions(rightop))
3166 {
3168 op_in_opfamily(expr_op, opfamily))
3169 {
3171
3172 iclause->rinfo = rinfo;
3175 iclause->indexcol = indexcol;
3177 return iclause;
3178 }
3179
3180 /*
3181 * We do not currently ask support functions about ScalarArrayOpExprs,
3182 * though in principle we could.
3183 */
3184 }
3185
3186 return NULL;
3187}
3188
3189/*
3190 * match_rowcompare_to_indexcol()
3191 * Handles the RowCompareExpr case for match_clause_to_indexcol(),
3192 * which see for comments.
3193 *
3194 * In this routine we check whether the first column of the row comparison
3195 * matches the target index column. This is sufficient to guarantee that some
3196 * index condition can be constructed from the RowCompareExpr --- the rest
3197 * is handled by expand_indexqual_rowcompare().
3198 */
3201 RestrictInfo *rinfo,
3202 int indexcol,
3204{
3206 Index index_relid;
3207 Oid opfamily;
3208 Oid idxcollation;
3209 Node *leftop,
3210 *rightop;
3211 bool var_on_left;
3212 Oid expr_op;
3213 Oid expr_coll;
3214
3215 /* Forget it if we're not dealing with a btree index */
3217 return NULL;
3218
3219 index_relid = index->rel->relid;
3220 opfamily = index->opfamily[indexcol];
3221 idxcollation = index->indexcollations[indexcol];
3222
3223 /*
3224 * We could do the matching on the basis of insisting that the opfamily
3225 * shown in the RowCompareExpr be the same as the index column's opfamily,
3226 * but that could fail in the presence of reverse-sort opfamilies: it'd be
3227 * a matter of chance whether RowCompareExpr had picked the forward or
3228 * reverse-sort family. So look only at the operator, and match if it is
3229 * a member of the index's opfamily (after commutation, if the indexkey is
3230 * on the right). We'll worry later about whether any additional
3231 * operators are matchable to the index.
3232 */
3235 expr_op = linitial_oid(clause->opnos);
3236 expr_coll = linitial_oid(clause->inputcollids);
3237
3238 /* Collations must match, if relevant */
3240 return NULL;
3241
3242 /*
3243 * These syntactic tests are the same as in match_opclause_to_indexcol()
3244 */
3247 !contain_volatile_functions(rightop))
3248 {
3249 /* OK, indexkey is on left */
3250 var_on_left = true;
3251 }
3254 !contain_volatile_functions(leftop))
3255 {
3256 /* indexkey is on right, so commute the operator */
3257 expr_op = get_commutator(expr_op);
3259 return NULL;
3260 var_on_left = false;
3261 }
3262 else
3263 return NULL;
3264
3265 /* We're good if the operator is the right type of opfamily member */
3267 {
3273 rinfo,
3274 indexcol,
3275 index,
3276 expr_op,
3277 var_on_left);
3278 }
3279
3280 return NULL;
3281}
3282
3283/*
3284 * match_orclause_to_indexcol()
3285 * Handles the OR-expr case for match_clause_to_indexcol() in the case
3286 * when it could be transformed to ScalarArrayOpExpr.
3287 *
3288 * In this routine, we attempt to transform a list of OR-clause args into a
3289 * single SAOP expression matching the target index column. On success,
3290 * return an IndexClause containing the transformed expression.
3291 * Return NULL if the transformation fails.
3292 */
3295 RestrictInfo *rinfo,
3296 int indexcol,
3298{
3301 Node *indexExpr = NULL;
3306 bool firstTime = true;
3307 bool haveNonConst = false;
3309 ScalarArrayOpExpr *saopexpr;
3310 IndexClause *iclause;
3311 ListCell *lc;
3312
3313 /* Forget it if index doesn't support SAOP clauses */
3315 return NULL;
3316
3317 /*
3318 * Try to convert a list of OR-clauses to a single SAOP expression. Each
3319 * OR entry must be in the form: (indexkey operator constant) or (constant
3320 * operator indexkey). Operators of all the entries must match. On
3321 * discovery of anything unsupported, we give up by breaking out of the
3322 * loop immediately and returning NULL.
3323 */
3324 foreach(lc, orclause->args)
3325 {
3327 OpExpr *subClause;
3328 Oid opno;
3329 Node *leftop,
3330 *rightop;
3331 Node *constExpr;
3332
3333 /* If it's not a RestrictInfo (i.e. it's a sub-AND), we can't use it */
3335 break;
3336
3337 /* Only operator clauses can match */
3339 break;
3340
3342 opno = subClause->opno;
3343
3344 /* Only binary operators can match */
3346 break;
3347
3348 /*
3349 * Check for clauses of the form: (indexkey operator constant) or
3350 * (constant operator indexkey). These tests should agree with
3351 * match_opclause_to_indexcol.
3352 */
3356 !bms_is_member(indexRelid, subRinfo->right_relids) &&
3357 !contain_volatile_functions(rightop))
3358 {
3359 indexExpr = leftop;
3360 constExpr = rightop;
3361 }
3363 !bms_is_member(indexRelid, subRinfo->left_relids) &&
3364 !contain_volatile_functions(leftop))
3365 {
3366 opno = get_commutator(opno);
3368 {
3369 /* commutator doesn't exist, we can't reverse the order */
3370 break;
3371 }
3372 indexExpr = rightop;
3373 constExpr = leftop;
3374 }
3375 else
3376 {
3377 break;
3378 }
3379
3380 /*
3381 * Save information about the operator, type, and collation for the
3382 * first matching qual. Then, check that subsequent quals match the
3383 * first.
3384 */
3385 if (firstTime)
3386 {
3387 matchOpno = opno;
3388 consttype = exprType(constExpr);
3389 arraytype = get_array_type(consttype);
3390 inputcollid = subClause->inputcollid;
3391
3392 /*
3393 * Check that the operator is presented in the opfamily and that
3394 * the expression collation matches the index collation. Also,
3395 * there must be an array type to construct an array later.
3396 */
3398 inputcollid) ||
3400 !OidIsValid(arraytype))
3401 break;
3402
3403 /*
3404 * Disallow if either type is RECORD, mainly because we can't be
3405 * positive that all the RHS expressions are the same record type.
3406 */
3408 break;
3409
3410 firstTime = false;
3411 }
3412 else
3413 {
3414 if (matchOpno != opno ||
3415 inputcollid != subClause->inputcollid ||
3416 consttype != exprType(constExpr))
3417 break;
3418 }
3419
3420 /*
3421 * The righthand inputs don't necessarily have to be plain Consts, but
3422 * make_SAOP_expr needs to know if any are not.
3423 */
3425 haveNonConst = true;
3426
3427 consts = lappend(consts, constExpr);
3428 }
3429
3430 /*
3431 * Handle failed conversion from breaking out of the loop because of an
3432 * unsupported qual. Also check that we have an indexExpr, just in case
3433 * the OR list was somehow empty (it shouldn't be). Return NULL to
3434 * indicate the conversion failed.
3435 */
3436 if (lc != NULL || indexExpr == NULL)
3437 {
3439 return NULL;
3440 }
3441
3442 /*
3443 * Build the new SAOP node. We use the indexExpr from the last OR arm;
3444 * since all the arms passed match_index_to_operand, it shouldn't matter
3445 * which one we use. But using "inputcollid" twice is a bit of a cheat:
3446 * we might end up with an array Const node that is labeled with a
3447 * collation despite its elements being of a noncollatable type. But
3448 * nothing is likely to complain about that, so we don't bother being more
3449 * accurate.
3450 */
3451 saopexpr = make_SAOP_expr(matchOpno, indexExpr, consttype, inputcollid,
3452 inputcollid, consts, haveNonConst);
3453 Assert(saopexpr != NULL);
3454
3455 /*
3456 * Finally, build an IndexClause based on the SAOP node. It's not lossy.
3457 */
3459 iclause->rinfo = rinfo;
3461 (Expr *) saopexpr));
3463 iclause->indexcol = indexcol;
3465 return iclause;
3466}
3467
3468/*
3469 * expand_indexqual_rowcompare --- expand a single indexqual condition
3470 * that is a RowCompareExpr
3471 *
3472 * It's already known that the first column of the row comparison matches
3473 * the specified column of the index. We can use additional columns of the
3474 * row comparison as index qualifications, so long as they match the index
3475 * in the "same direction", ie, the indexkeys are all on the same side of the
3476 * clause and the operators are all the same-type members of the opfamilies.
3477 *
3478 * If all the columns of the RowCompareExpr match in this way, we just use it
3479 * as-is, except for possibly commuting it to put the indexkeys on the left.
3480 *
3481 * Otherwise, we build a shortened RowCompareExpr (if more than one
3482 * column matches) or a simple OpExpr (if the first-column match is all
3483 * there is). In these cases the modified clause is always "<=" or ">="
3484 * even when the original was "<" or ">" --- this is necessary to match all
3485 * the rows that could match the original. (We are building a lossy version
3486 * of the row comparison when we do this, so we set lossy = true.)
3487 *
3488 * Note: this is really just the last half of match_rowcompare_to_indexcol,
3489 * but we split it out for comprehensibility.
3490 */
3493 RestrictInfo *rinfo,
3494 int indexcol,
3496 Oid expr_op,
3497 bool var_on_left)
3498{
3501 int op_strategy;
3502 Oid op_lefttype;
3503 Oid op_righttype;
3504 int matching_cols;
3505 List *expr_ops;
3506 List *opfamilies;
3507 List *lefttypes;
3508 List *righttypes;
3509 List *new_ops;
3510 List *var_args;
3511 List *non_var_args;
3512
3513 iclause->rinfo = rinfo;
3514 iclause->indexcol = indexcol;
3515
3516 if (var_on_left)
3517 {
3518 var_args = clause->largs;
3519 non_var_args = clause->rargs;
3520 }
3521 else
3522 {
3523 var_args = clause->rargs;
3524 non_var_args = clause->largs;
3525 }
3526
3528 &op_strategy,
3529 &op_lefttype,
3530 &op_righttype);
3531
3532 /* Initialize returned list of which index columns are used */
3534
3535 /* Build lists of ops, opfamilies and operator datatypes in case needed */
3536 expr_ops = list_make1_oid(expr_op);
3538 lefttypes = list_make1_oid(op_lefttype);
3539 righttypes = list_make1_oid(op_righttype);
3540
3541 /*
3542 * See how many of the remaining columns match some index column in the
3543 * same way. As in match_clause_to_indexcol(), the "other" side of any
3544 * potential index condition is OK as long as it doesn't use Vars from the
3545 * indexed relation.
3546 */
3547 matching_cols = 1;
3548
3550 {
3554
3555 expr_op = list_nth_oid(clause->opnos, matching_cols);
3556 if (!var_on_left)
3557 {
3558 /* indexkey is on right, so commute the operator */
3559 expr_op = get_commutator(expr_op);
3561 break; /* operator is not usable */
3562 }
3564 break; /* no good, Var on wrong side */
3566 break; /* no good, volatile comparison value */
3567
3568 /*
3569 * The Var side can match any key column of the index.
3570 */
3572 {
3574 get_op_opfamily_strategy(expr_op,
3577 list_nth_oid(clause->inputcollids,
3578 matching_cols)))
3579 break;
3580 }
3582 break; /* no match found */
3583
3584 /* Add column number to returned list */
3586
3587 /* Add operator info to lists */
3589 &op_strategy,
3590 &op_lefttype,
3591 &op_righttype);
3592 expr_ops = lappend_oid(expr_ops, expr_op);
3594 lefttypes = lappend_oid(lefttypes, op_lefttype);
3595 righttypes = lappend_oid(righttypes, op_righttype);
3596
3597 /* This column matches, keep scanning */
3598 matching_cols++;
3599 }
3600
3601 /* Result is non-lossy if all columns are usable as index quals */
3603
3604 /*
3605 * We can use rinfo->clause as-is if we have var on left and it's all
3606 * usable as index quals.
3607 */
3610 else
3611 {
3612 /*
3613 * We have to generate a modified rowcompare (possibly just one
3614 * OpExpr). The painful part of this is changing < to <= or > to >=,
3615 * so deal with that first.
3616 */
3618 {
3619 /* very easy, just use the commuted operators */
3620 new_ops = expr_ops;
3621 }
3623 op_strategy == BTGreaterEqualStrategyNumber)
3624 {
3625 /* easy, just use the same (possibly commuted) operators */
3626 new_ops = list_truncate(expr_ops, matching_cols);
3627 }
3628 else
3629 {
3630 ListCell *opfamilies_cell;
3631 ListCell *lefttypes_cell;
3632 ListCell *righttypes_cell;
3633
3635 op_strategy = BTLessEqualStrategyNumber;
3637 op_strategy = BTGreaterEqualStrategyNumber;
3638 else
3640 new_ops = NIL;
3641 forthree(opfamilies_cell, opfamilies,
3642 lefttypes_cell, lefttypes,
3643 righttypes_cell, righttypes)
3644 {
3648
3649 expr_op = get_opfamily_member(opfam, lefttype, righttype,
3650 op_strategy);
3653 op_strategy, lefttype, righttype, opfam);
3654 new_ops = lappend_oid(new_ops, expr_op);
3655 }
3656 }
3657
3658 /* If we have more than one matching col, create a subset rowcompare */
3659 if (matching_cols > 1)
3660 {
3662
3664 rc->opnos = new_ops;
3665 rc->opfamilies = list_copy_head(clause->opfamilies,
3666 matching_cols);
3667 rc->inputcollids = list_copy_head(clause->inputcollids,
3668 matching_cols);
3672 (Expr *) rc));
3673 }
3674 else
3675 {
3676 Expr *op;
3677
3678 /* We don't report an index column list in this case */
3680
3684 InvalidOid,
3685 linitial_oid(clause->inputcollids));
3687 }
3688 }
3689
3690 return iclause;
3691}
3692
3693
3694/****************************************************************************
3695 * ---- ROUTINES TO CHECK ORDERING OPERATORS ----
3696 ****************************************************************************/
3697
3698/*
3699 * match_pathkeys_to_index
3700 * For the given 'index' and 'pathkeys', output a list of suitable ORDER
3701 * BY expressions, each of the form "indexedcol operator pseudoconstant",
3702 * along with an integer list of the index column numbers (zero based)
3703 * that each clause would be used with.
3704 *
3705 * This attempts to find an ORDER BY and index column number for all items in
3706 * the pathkey list, however, if we're unable to match any given pathkey to an
3707 * index column, we return just the ones matched by the function so far. This
3708 * allows callers who are interested in partial matches to get them. Callers
3709 * can determine a partial match vs a full match by checking the outputted
3710 * list lengths. A full match will have one item in the output lists for each
3711 * item in the given 'pathkeys' list.
3712 */
3713static void
3715 List **orderby_clauses_p,
3716 List **clause_columns_p)
3717{
3718 ListCell *lc1;
3719
3721 *clause_columns_p = NIL;
3722
3723 /* Only indexes with the amcanorderbyop property are interesting here */
3725 return;
3726
3727 foreach(lc1, pathkeys)
3728 {
3730 bool found = false;
3731 EquivalenceMemberIterator it;
3732 EquivalenceMember *member;
3733
3734
3735 /* Pathkey must request default sort order for the target opfamily */
3737 return;
3738
3739 /* If eclass is volatile, no hope of using an indexscan */
3740 if (pathkey->pk_eclass->ec_has_volatile)
3741 return;
3742
3743 /*
3744 * Try to match eclass member expression(s) to index. Note that child
3745 * EC members are considered, but only when they belong to the target
3746 * relation. (Unlike regular members, the same expression could be a
3747 * child member of more than one EC. Therefore, the same index could
3748 * be considered to match more than one pathkey list, which is OK
3749 * here. See also get_eclass_for_sort_expr.)
3750 */
3751 setup_eclass_member_iterator(&it, pathkey->pk_eclass,
3752 index->rel->relids);
3754 {
3755 int indexcol;
3756
3757 /* No possibility of match if it references other relations */
3759 continue;
3760
3761 /*
3762 * We allow any column of the index to match each pathkey; they
3763 * don't have to match left-to-right as you might expect. This is
3764 * correct for GiST, and it doesn't matter for SP-GiST because
3765 * that doesn't handle multiple columns anyway, and no other
3766 * existing AMs support amcanorderbyop. We might need different
3767 * logic in future for other implementations.
3768 */
3770 {
3771 Expr *expr;
3772
3774 indexcol,
3775 member->em_expr,
3776 pathkey->pk_opfamily);
3777 if (expr)
3778 {
3779 *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
3780 *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
3781 found = true;
3782 break;
3783 }
3784 }
3785
3786 if (found) /* don't want to look at remaining members */
3787 break;
3788 }
3789
3790 /*
3791 * Return the matches found so far when this pathkey couldn't be
3792 * matched to the index.
3793 */
3794 if (!found)
3795 return;
3796 }
3797}
3798
3799/*
3800 * match_clause_to_ordering_op
3801 * Determines whether an ordering operator expression matches an
3802 * index column.
3803 *
3804 * This is similar to, but simpler than, match_clause_to_indexcol.
3805 * We only care about simple OpExpr cases. The input is a bare
3806 * expression that is being ordered by, which must be of the form
3807 * (indexkey op const) or (const op indexkey) where op is an ordering
3808 * operator for the column's opfamily.
3809 *
3810 * 'index' is the index of interest.
3811 * 'indexcol' is a column number of 'index' (counting from 0).
3812 * 'clause' is the ordering expression to be tested.
3813 * 'pk_opfamily' is the btree opfamily describing the required sort order.
3814 *
3815 * Note that we currently do not consider the collation of the ordering
3816 * operator's result. In practical cases the result type will be numeric
3817 * and thus have no collation, and it's not very clear what to match to
3818 * if it did have a collation. The index's collation should match the
3819 * ordering operator's input collation, not its result.
3820 *
3821 * If successful, return 'clause' as-is if the indexkey is on the left,
3822 * otherwise a commuted copy of 'clause'. If no match, return NULL.
3823 */
3826 int indexcol,
3827 Expr *clause,
3828 Oid pk_opfamily)
3829{
3830 Oid opfamily;
3831 Oid idxcollation;
3832 Node *leftop,
3833 *rightop;
3834 Oid expr_op;
3835 Oid expr_coll;
3836 Oid sortfamily;
3837 bool commuted;
3838
3839 Assert(indexcol < index->nkeycolumns);
3840
3841 opfamily = index->opfamily[indexcol];
3842 idxcollation = index->indexcollations[indexcol];
3843
3844 /*
3845 * Clause must be a binary opclause.
3846 */
3848 return NULL;
3849 leftop = get_leftop(clause);
3850 rightop = get_rightop(clause);
3851 if (!leftop || !rightop)
3852 return NULL;
3853 expr_op = ((OpExpr *) clause)->opno;
3854 expr_coll = ((OpExpr *) clause)->inputcollid;
3855
3856 /*
3857 * We can forget the whole thing right away if wrong collation.
3858 */
3860 return NULL;
3861
3862 /*
3863 * Check for clauses of the form: (indexkey operator constant) or
3864 * (constant operator indexkey).
3865 */
3867 !contain_var_clause(rightop) &&
3868 !contain_volatile_functions(rightop))
3869 {
3870 commuted = false;
3871 }
3873 !contain_var_clause(leftop) &&
3874 !contain_volatile_functions(leftop))
3875 {
3876 /* Might match, but we need a commuted operator */
3877 expr_op = get_commutator(expr_op);
3879 return NULL;
3880 commuted = true;
3881 }
3882 else
3883 return NULL;
3884
3885 /*
3886 * Is the (commuted) operator an ordering operator for the opfamily? And
3887 * if so, does it yield the right sorting semantics?
3888 */
3889 sortfamily = get_op_opfamily_sortfamily(expr_op, opfamily);
3890 if (sortfamily != pk_opfamily)
3891 return NULL;
3892
3893 /* We have a match. Return clause or a commuted version thereof. */
3894 if (commuted)
3895 {
3897
3898 /* flat-copy all the fields of clause */
3900
3901 /* commute it */
3902 newclause->opno = expr_op;
3903 newclause->opfuncid = InvalidOid;
3905
3906 clause = (Expr *) newclause;
3907 }
3908
3909 return clause;
3910}
3911
3912
3913/****************************************************************************
3914 * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ----
3915 ****************************************************************************/
3916
3917/*
3918 * check_index_predicates
3919 * Set the predicate-derived IndexOptInfo fields for each index
3920 * of the specified relation.
3921 *
3922 * predOK is set true if the index is partial and its predicate is satisfied
3923 * for this query, ie the query's WHERE clauses imply the predicate.
3924 *
3925 * indrestrictinfo is set to the relation's baserestrictinfo list less any
3926 * conditions that are implied by the index's predicate. (Obviously, for a
3927 * non-partial index, this is the same as baserestrictinfo.) Such conditions
3928 * can be dropped from the plan when using the index, in certain cases.
3929 *
3930 * At one time it was possible for this to get re-run after adding more
3931 * restrictions to the rel, thus possibly letting us prove more indexes OK.
3932 * That doesn't happen any more (at least not in the core code's usage),
3933 * but this code still supports it in case extensions want to mess with the
3934 * baserestrictinfo list. We assume that adding more restrictions can't make
3935 * an index not predOK. We must recompute indrestrictinfo each time, though,
3936 * to make sure any newly-added restrictions get into it if needed.
3937 */
3938void
3940{
3941 List *clauselist;
3942 bool have_partial;
3943 bool is_target_rel;
3944 Relids otherrels;
3945 ListCell *lc;
3946
3947 /* Indexes are available only on base or "other" member relations. */
3949
3950 /*
3951 * Initialize the indrestrictinfo lists to be identical to
3952 * baserestrictinfo, and check whether there are any partial indexes. If
3953 * not, this is all we need to do.
3954 */
3955 have_partial = false;
3957 {
3959
3962 have_partial = true;
3963 }
3964 if (!have_partial)
3965 return;
3966
3967 /*
3968 * Construct a list of clauses that we can assume true for the purpose of
3969 * proving the index(es) usable. Restriction clauses for the rel are
3970 * always usable, and so are any join clauses that are "movable to" this
3971 * rel. Also, we can consider any EC-derivable join clauses (which must
3972 * be "movable to" this rel, by definition).
3973 */
3975
3976 /* Scan the rel's join clauses */
3978 {
3980
3981 /* Check if clause can be moved to this rel */
3983 continue;
3984
3985 clauselist = lappend(clauselist, rinfo);
3986 }
3987
3988 /*
3989 * Add on any equivalence-derivable join clauses. Computing the correct
3990 * relid sets for generate_join_implied_equalities is slightly tricky
3991 * because the rel could be a child rel rather than a true baserel, and in
3992 * that case we must subtract its parents' relid(s) from all_query_rels.
3993 * Additionally, we mustn't consider clauses that are only computable
3994 * after outer joins that can null the rel.
3995 */
3999 else
4002
4004 clauselist =
4005 list_concat(clauselist,
4008 otherrels),
4009 otherrels,
4010 rel,
4011 NULL));
4012
4013 /*
4014 * Normally we remove quals that are implied by a partial index's
4015 * predicate from indrestrictinfo, indicating that they need not be
4016 * checked explicitly by an indexscan plan using this index. However, if
4017 * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
4018 * we cannot remove such quals from the plan, because they need to be in
4019 * the plan so that they will be properly rechecked by EvalPlanQual
4020 * testing. Some day we might want to remove such quals from the main
4021 * plan anyway and pass them through to EvalPlanQual via a side channel;
4022 * but for now, we just don't remove implied quals at all for target
4023 * relations.
4024 */
4027
4028 /*
4029 * Now try to prove each index predicate true, and compute the
4030 * indrestrictinfo lists for partial indexes. Note that we compute the
4031 * indrestrictinfo list even for non-predOK indexes; this might seem
4032 * wasteful, but we may be able to use such indexes in OR clauses, cf
4033 * generate_bitmap_or_paths().
4034 */
4036 {
4038 ListCell *lcr;
4039
4041 continue; /* ignore non-partial indexes here */
4042
4045 false);
4046
4047 /* If rel is an update target, leave indrestrictinfo as set above */
4048 if (is_target_rel)
4049 continue;
4050
4051 /*
4052 * If index is !amoptionalkey, also leave indrestrictinfo as set
4053 * above. Otherwise we risk removing all quals for the first index
4054 * key and then not being able to generate an indexscan at all. It
4055 * would be better to be more selective, but we've not yet identified
4056 * which if any of the quals match the first index key.
4057 */
4059 continue;
4060
4061 /* Else compute indrestrictinfo as the non-implied quals */
4064 {
4066
4067 /* predicate_implied_by() assumes first arg is immutable */
4072 }
4073 }
4074}
4075
4076/****************************************************************************
4077 * ---- ROUTINES TO CHECK EXTERNALLY-VISIBLE CONDITIONS ----
4078 ****************************************************************************/
4079
4080/*
4081 * ec_member_matches_indexcol
4082 * Test whether an EquivalenceClass member matches an index column.
4083 *
4084 * This is a callback for use by generate_implied_equalities_for_column.
4085 */
4086static bool
4090{
4093 Oid curFamily;
4094 Oid curCollation;
4095
4096 Assert(indexcol < index->nkeycolumns);
4097
4098 curFamily = index->opfamily[indexcol];
4099 curCollation = index->indexcollations[indexcol];
4100
4101 /*
4102 * If it's a btree index, we can reject it if its opfamily isn't
4103 * compatible with the EC, since no clause generated from the EC could be
4104 * used with the index. For non-btree indexes, we can't easily tell
4105 * whether clauses generated from the EC could be used with the index, so
4106 * don't check the opfamily. This might mean we return "true" for a
4107 * useless EC, so we have to recheck the results of
4108 * generate_implied_equalities_for_column; see
4109 * match_eclass_clauses_to_index.
4110 */
4113 return false;
4114
4115 /* We insist on collation match for all index types, though */
4117 return false;
4118
4120}
4121
4122/*
4123 * relation_has_unique_index_for
4124 * Determine whether the relation provably has at most one row satisfying
4125 * a set of equality conditions, because the conditions constrain all
4126 * columns of some unique index.
4127 *
4128 * The conditions are provided as a list of RestrictInfo nodes, where the
4129 * caller has already determined that each condition is a mergejoinable
4130 * equality with an expression in this relation on one side, and an
4131 * expression not involving this relation on the other. The transient
4132 * outer_is_left flag is used to identify which side we should look at:
4133 * left side if outer_is_left is false, right side if it is true.
4134 *
4135 * The caller need only supply equality conditions arising from joins;
4136 * this routine automatically adds in any usable baserestrictinfo clauses.
4137 * (Note that the passed-in restrictlist will be destructively modified!)
4138 *
4139 * If extra_clauses isn't NULL, return baserestrictinfo clauses which were used
4140 * to derive uniqueness.
4141 */
4142bool
4145{
4146 ListCell *ic;
4147
4148 /* Short-circuit if no indexes... */
4150 return false;
4151
4152 /*
4153 * Examine the rel's restriction clauses for usable var = const clauses
4154 * that we can add to the restrictlist.
4155 */
4157 {
4159
4160 /*
4161 * Note: can_join won't be set for a restriction clause, but
4162 * mergeopfamilies will be if it has a mergejoinable operator and
4163 * doesn't contain volatile functions.
4164 */
4166 continue; /* not mergejoinable */
4167
4168 /*
4169 * The clause certainly doesn't refer to anything but the given rel.
4170 * If either side is pseudoconstant then we can use it.
4171 */
4173 {
4174 /* righthand side is inner */
4175 restrictinfo->outer_is_left = true;
4176 }
4178 {
4179 /* lefthand side is inner */
4180 restrictinfo->outer_is_left = false;
4181 }
4182 else
4183 continue;
4184
4185 /* OK, add to list */
4186 restrictlist = lappend(restrictlist, restrictinfo);
4187 }
4188
4189 /* Short-circuit the easy case */
4191 return false;
4192
4193 /* Examine each index of the relation ... */
4195 {
4199
4200 /*
4201 * If the index is not unique, or not immediately enforced, or if it's
4202 * a partial index, it's useless here. We're unable to make use of
4203 * predOK partial unique indexes due to the fact that
4204 * check_index_predicates() also makes use of join predicates to
4205 * determine if the partial index is usable. Here we need proofs that
4206 * hold true before any joins are evaluated.
4207 */
4209 continue;
4210
4211 /*
4212 * Try to find each index column in the list of conditions. This is
4213 * O(N^2) or worse, but we expect all the lists to be short.
4214 */
4216 {
4217 ListCell *lc;
4218
4219 foreach(lc, restrictlist)
4220 {
4222 Node *rexpr;
4223
4224 /*
4225 * The condition's equality operator must be a member of the
4226 * index opfamily, else it is not asserting the right kind of
4227 * equality behavior for this index. We check this first
4228 * since it's probably cheaper than match_index_to_operand().
4229 */
4231 continue;
4232
4233 /*
4234 * XXX at some point we may need to check collations here too.
4235 * For the moment we assume all collations reduce to the same
4236 * notion of equality.
4237 */
4238
4239 /* OK, see if the condition operand matches the index key */
4240 if (rinfo->outer_is_left)
4242 else
4244
4246 {
4248 {
4249 MemoryContext oldMemCtx =
4251
4252 /*
4253 * Add filter clause into a list allowing caller to
4254 * know if uniqueness have made not only by join
4255 * clauses.
4256 */
4258 bms_is_empty(rinfo->right_relids));
4259 if (extra_clauses)
4260 exprs = lappend(exprs, rinfo);
4261 MemoryContextSwitchTo(oldMemCtx);
4262 }
4263
4264 break; /* found a match; column is unique */
4265 }
4266 }
4267
4268 if (lc == NULL)
4269 break; /* no match; this index doesn't help us */
4270 }
4271
4272 /* Matched all key columns of this index? */
4274 {
4275 if (extra_clauses)
4276 *extra_clauses = exprs;
4277 return true;
4278 }
4279 }
4280
4281 return false;
4282}
4283
4284/*
4285 * indexcol_is_bool_constant_for_query
4286 *
4287 * If an index column is constrained to have a constant value by the query's
4288 * WHERE conditions, then it's irrelevant for sort-order considerations.
4289 * Usually that means we have a restriction clause WHERE indexcol = constant,
4290 * which gets turned into an EquivalenceClass containing a constant, which
4291 * is recognized as redundant by build_index_pathkeys(). But if the index
4292 * column is a boolean variable (or expression), then we are not going to
4293 * see WHERE indexcol = constant, because expression preprocessing will have
4294 * simplified that to "WHERE indexcol" or "WHERE NOT indexcol". So we are not
4295 * going to have a matching EquivalenceClass (unless the query also contains
4296 * "ORDER BY indexcol"). To allow such cases to work the same as they would
4297 * for non-boolean values, this function is provided to detect whether the
4298 * specified index column matches a boolean restriction clause.
4299 */
4300bool
4303 int indexcol)
4304{
4305 ListCell *lc;
4306
4307 /* If the index isn't boolean, we can't possibly get a match */
4309 return false;
4310
4311 /* Check each restriction clause for the index's rel */
4313 {
4315
4316 /*
4317 * As in match_clause_to_indexcol, never match pseudoconstants to
4318 * indexes. (It might be semantically okay to do so here, but the
4319 * odds of getting a match are negligible, so don't waste the cycles.)
4320 */
4321 if (rinfo->pseudoconstant)
4322 continue;
4323
4324 /* See if we can match the clause's expression to the index column */
4326 return true;
4327 }
4328
4329 return false;
4330}
4331
4332
4333/****************************************************************************
4334 * ---- ROUTINES TO CHECK OPERANDS ----
4335 ****************************************************************************/
4336
4337/*
4338 * match_index_to_operand()
4339 * Generalized test for a match between an index's key
4340 * and the operand on one side of a restriction or join clause.
4341 *
4342 * operand: the nodetree to be compared to the index
4343 * indexcol: the column number of the index (counting from 0)
4344 * index: the index of interest
4345 *
4346 * Note that we aren't interested in collations here; the caller must check
4347 * for a collation match, if it's dealing with an operator where that matters.
4348 *
4349 * This is exported for use in selfuncs.c.
4350 */
4351bool
4353 int indexcol,
4355{
4356 int indkey;
4357
4358 /*
4359 * Ignore any PlaceHolderVar node contained in the operand. This is
4360 * needed to be able to apply indexscanning in cases where the operand (or
4361 * a subtree) has been wrapped in PlaceHolderVars to enforce separate
4362 * identity or as a result of outer joins.
4363 */
4364 operand = strip_noop_phvs(operand);
4365
4366 /*
4367 * Ignore any RelabelType node above the operand. This is needed to be
4368 * able to apply indexscanning in binary-compatible-operator cases.
4369 *
4370 * Note: we must handle nested RelabelType nodes here. While
4371 * eval_const_expressions() will have simplified them to at most one
4372 * layer, our prior stripping of PlaceHolderVars may have brought separate
4373 * RelabelTypes into adjacency.
4374 */
4377
4378 indkey = index->indexkeys[indexcol];
4379 if (indkey != 0)
4380 {
4381 /*
4382 * Simple index column; operand must be a matching Var.
4383 */
4386 indkey == ((Var *) operand)->varattno &&
4387 ((Var *) operand)->varnullingrels == NULL)
4388 return true;
4389 }
4390 else
4391 {
4392 /*
4393 * Index expression; find the correct expression. (This search could
4394 * be avoided, at the cost of complicating all the callers of this
4395 * routine; doesn't seem worth it.)
4396 */
4397 ListCell *indexpr_item;
4399 Node *indexkey;
4400
4403 {
4405 {
4406 if (indexpr_item == NULL)
4409 }
4410 }
4411 if (indexpr_item == NULL)
4414
4415 /*
4416 * Does it match the operand? Again, strip any relabeling.
4417 */
4420
4422 return true;
4423 }
4424
4425 return false;
4426}
4427
4428/*
4429 * is_pseudo_constant_for_index()
4430 * Test whether the given expression can be used as an indexscan
4431 * comparison value.
4432 *
4433 * An indexscan comparison value must not contain any volatile functions,
4434 * and it can't contain any Vars of the index's own table. Vars of
4435 * other tables are okay, though; in that case we'd be producing an
4436 * indexqual usable in a parameterized indexscan. This is, therefore,
4437 * a weaker condition than is_pseudo_constant_clause().
4438 *
4439 * This function is exported for use by planner support functions,
4440 * which will have available the IndexOptInfo, but not any RestrictInfo
4441 * infrastructure. It is making the same test made by functions above
4442 * such as match_opclause_to_indexcol(), but those rely where possible
4443 * on RestrictInfo information about variable membership.
4444 *
4445 * expr: the nodetree to be checked
4446 * index: the index of interest
4447 */
4448bool
4450{
4451 /* pull_varnos is cheaper than volatility check, so do that first */
4453 return false; /* no good, contains Var of table */
4455 return false; /* no good, volatile comparison value */
4456 return true;
4457}
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition allpaths.c:4758
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:346
BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:445
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:1145
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:901
memcpy(sums, checksumBaseOffsets, sizeof(checksumBaseOffsets))
ScalarArrayOpExpr * make_SAOP_expr(Oid oper, Node *leftexpr, Oid coltype, Oid arraycollid, Oid inputcollid, List *exprs, bool haveNonConst)
Definition clauses.c:6244
void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
Definition costsize.c:1115
void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, Path *bitmapqual, double loop_count)
Definition costsize.c:1012
void setup_eclass_member_iterator(EquivalenceMemberIterator *it, EquivalenceClass *ec, Relids child_relids)
Definition equivclass.c:3155
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition equivclass.c:3238
EquivalenceMember * eclass_member_iterator_next(EquivalenceMemberIterator *it)
Definition equivclass.c:3174
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition equivclass.c:1549
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition indxpath.c:1784
static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition indxpath.c:2056
static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds)
Definition indxpath.c:2153
static void get_join_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths, Relids relids, List **considered_relids)
Definition indxpath.c:605
static int or_arg_index_match_cmp(const void *a, const void *b)
Definition indxpath.c:1199
static void match_clause_to_index(PlannerInfo *root, RestrictInfo *rinfo, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition indxpath.c:2585
bool is_pseudo_constant_for_index(PlannerInfo *root, Node *expr, IndexOptInfo *index)
Definition indxpath.c:4450
static bool eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids, List *indexjoinclauses)
Definition indxpath.c:683
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition indxpath.c:2480
static IndexClause * match_saopclause_to_indexcol(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:3133
static bool check_index_only(RelOptInfo *rel, IndexOptInfo *index)
Definition indxpath.c:2226
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition indxpath.c:2514
static PathClauseUsage * classify_index_clause_usage(Path *path, List **clauselist)
Definition indxpath.c:2085
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition indxpath.c:715
void check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
Definition indxpath.c:3940
static List * build_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, bool useful_predicate, ScanTypeControl scantype, bool *skip_nonnative_saop)
Definition indxpath.c:809
static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys, List **orderby_clauses_p, List **clause_columns_p)
Definition indxpath.c:3715
static int find_list_position(Node *node, List **nodelist)
Definition indxpath.c:2200
static void match_clauses_to_index(PlannerInfo *root, List *clauses, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition indxpath.c:2552
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids)
Definition indxpath.c:2325
static void consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths, List *indexjoinclauses, int considered_clauses, List **considered_relids)
Definition indxpath.c:502
void create_index_paths(PlannerInfo *root, RelOptInfo *rel)
Definition indxpath.c:239
static double adjust_rowcount_for_semijoins(PlannerInfo *root, Index cur_relid, Index outer_relid, double rowcount)
Definition indxpath.c:2378
static IndexClause * match_clause_to_indexcol(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:2709
static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition indxpath.c:4088
static IndexClause * get_index_clause_from_support(PlannerInfo *root, RestrictInfo *rinfo, Oid funcid, int indexarg, int indexcol, IndexOptInfo *index)
Definition indxpath.c:3067
#define IndexCollMatchesExprColl(idxcollation, exprcollation)
Definition indxpath.c:41
static IndexClause * match_orclause_to_indexcol(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:3295
static IndexClause * match_opclause_to_indexcol(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:2902
static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel, Path *ipath)
Definition indxpath.c:2022
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition indxpath.c:4353
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:2815
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition indxpath.c:436
static int or_arg_index_match_cmp_group(const void *a, const void *b)
Definition indxpath.c:1237
static IndexClause * expand_indexqual_rowcompare(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index, Oid expr_op, bool var_on_left)
Definition indxpath.c:3493
static void match_restriction_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition indxpath.c:2464
static IndexClause * match_rowcompare_to_indexcol(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:3201
static List * build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition indxpath.c:1091
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition indxpath.c:4302
static IndexClause * match_funcclause_to_indexcol(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition indxpath.c:3021
static int path_usage_comparator(const void *a, const void *b)
Definition indxpath.c:1989
static List * group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
Definition indxpath.c:1270
static double approximate_joinrel_size(PlannerInfo *root, Relids relids)
Definition indxpath.c:2422
static Expr * match_clause_to_ordering_op(IndexOptInfo *index, int indexcol, Expr *clause, Oid pk_opfamily)
Definition indxpath.c:3826
bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List **extra_clauses)
Definition indxpath.c:4144
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition indxpath.c:1628
static List * make_bitmap_paths_for_or_group(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *ri, List *other_clauses)
Definition indxpath.c:1547
void get_op_opfamily_properties(Oid opno, Oid opfamily, bool ordering_op, int *strategy, Oid *lefttype, Oid *righttype)
Definition lsyscache.c:140
Oid get_op_opfamily_sortfamily(Oid opno, Oid opfamily)
Definition lsyscache.c:112
int get_op_opfamily_strategy(Oid opno, Oid opfamily)
Definition lsyscache.c:87
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition lsyscache.c:170
Expr * make_opclause(Oid opno, Oid opresulttype, bool opretset, Expr *leftop, Expr *rightop, Oid opcollid, Oid inputcollid)
Definition makefuncs.c:701
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition palloc.h:124
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition pathkeys.c:2200
bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel)
Definition pathkeys.c:2291
List * build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
Definition pathkeys.c:740
BitmapAndPath * create_bitmap_and_path(PlannerInfo *root, RelOptInfo *rel, List *bitmapquals)
Definition pathnode.c:1182
IndexPath * create_index_path(PlannerInfo *root, IndexOptInfo *index, List *indexclauses, List *indexorderbys, List *indexorderbycols, List *pathkeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, double loop_count, bool partial_path)
Definition pathnode.c:1092
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition pathnode.c:793
BitmapOrPath * create_bitmap_or_path(PlannerInfo *root, RelOptInfo *rel, List *bitmapquals)
Definition pathnode.c:1234
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition pathnode.c:1149
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition predtest.c:154
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition preptlist.c:528
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition relnode.c:1668
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition restrictinfo.c:407
bool restriction_is_securely_promotable(RestrictInfo *restrictinfo, RelOptInfo *rel)
Definition restrictinfo.c:422
RestrictInfo * make_plain_restrictinfo(PlannerInfo *root, Expr *clause, Expr *orclause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids)
Definition restrictinfo.c:103
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition restrictinfo.c:575
RestrictInfo * commute_restrictinfo(RestrictInfo *rinfo, Oid comm_op)
Definition restrictinfo.c:350
double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset, EstimationInfo *estinfo)
Definition selfuncs.c:3800
Definition pathnodes.h:2141
Definition pathnodes.h:2129
Definition pathnodes.h:2154
Definition bitmapset.h:50
Definition primnodes.h:968
Definition primnodes.h:2008
Definition primnodes.h:325
Definition pathnodes.h:1654
Definition pathnodes.h:1780
Definition pathnodes.h:1715
Definition primnodes.h:190
Definition primnodes.h:780
Definition indxpath.c:54
Definition pathnodes.h:2100
Definition pathnodes.h:1347
Definition pathnodes.h:2054
Definition pg_list.h:54
Definition memnodes.h:118
Definition nodes.h:135
Definition primnodes.h:1984
Definition primnodes.h:847
Definition indxpath.c:1180
Definition indxpath.c:62
Definition pathnodes.h:1807
Definition pathnodes.h:1965
Definition pathnodes.h:303
Definition pathnodes.h:1010
Definition primnodes.h:1217
Definition pathnodes.h:2895
Definition primnodes.h:1491
Definition primnodes.h:927
Definition pathnodes.h:3222
Definition primnodes.h:263
Definition indxpath.c:72
Definition preproc-array_of_struct.c:43
Definition pg_list.h:46
void pull_varattnos(Node *node, Index varno, Bitmapset **varattnos)
Definition var.c:296
Enumeration Type Documentation
◆ ScanTypeControl
| enum ScanTypeControl |
| Enumerator | |
|---|---|
| ST_INDEXSCAN | |
| ST_BITMAPSCAN | |
| ST_ANYSCAN | |
Definition at line 45 of file indxpath.c.
46{
50} ScanTypeControl;
Function Documentation
◆ adjust_rowcount_for_semijoins()
|
static |
Definition at line 2378 of file indxpath.c.
2382{
2383 ListCell *lc;
2384
2386 {
2388
2392 {
2393 /* Estimate number of unique-ified rows */
2394 double nraw;
2395 double nunique;
2396
2399 sjinfo->semi_rhs_exprs,
2400 nraw,
2401 NULL,
2402 NULL);
2403 if (rowcount > nunique)
2404 rowcount = nunique;
2405 }
2406 }
2407 return rowcount;
2408}
References approximate_joinrel_size(), bms_is_member(), estimate_num_groups(), JOIN_SEMI, SpecialJoinInfo::jointype, lfirst, root, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.
Referenced by get_loop_count().
◆ approximate_joinrel_size()
|
static |
Definition at line 2422 of file indxpath.c.
2423{
2424 double rowcount = 1.0;
2425 int relid;
2426
2427 relid = -1;
2429 {
2430 RelOptInfo *rel;
2431
2432 /* Paranoia: ignore bogus relid indexes */
2434 continue;
2435 rel = root->simple_rel_array[relid];
2436 if (rel == NULL)
2437 continue;
2439
2440 /* Relation could be proven empty, if so ignore */
2442 continue;
2443
2444 /* Otherwise, rel's rows estimate should be valid by now */
2446
2447 /* Accumulate product */
2448 rowcount *= rel->rows;
2449 }
2450 return rowcount;
2451}
References Assert, bms_next_member(), IS_DUMMY_REL, RelOptInfo::relid, root, and RelOptInfo::rows.
Referenced by adjust_rowcount_for_semijoins().
◆ bitmap_and_cost_est()
|
static |
Definition at line 2056 of file indxpath.c.
2057{
2058 BitmapAndPath *apath;
2059
2060 /*
2061 * Might as well build a real BitmapAndPath here, as the work is slightly
2062 * too complicated to be worth repeating just to save one palloc.
2063 */
2065
2067}
References bitmap_scan_cost_est(), create_bitmap_and_path(), and root.
Referenced by choose_bitmap_and().
◆ bitmap_scan_cost_est()
|
static |
Definition at line 2022 of file indxpath.c.
2023{
2024 BitmapHeapPath bpath;
2025
2026 /* Set up a dummy BitmapHeapPath */
2027 bpath.path.type = T_BitmapHeapPath;
2029 bpath.path.parent = rel;
2031 bpath.path.param_info = ipath->param_info;
2033 bpath.bitmapqual = ipath;
2034
2035 /*
2036 * Check the cost of temporary path without considering parallelism.
2037 * Parallel bitmap heap path will be considered at later stage.
2038 */
2040
2041 /* Now we can do cost_bitmap_heap_scan */
2043 bpath.path.param_info,
2044 ipath,
2046 PATH_REQ_OUTER(ipath)));
2047
2049}
References BitmapHeapPath::bitmapqual, cost_bitmap_heap_scan(), get_loop_count(), NIL, Path::parallel_workers, BitmapHeapPath::path, PATH_REQ_OUTER, Path::pathkeys, Path::pathtype, RelOptInfo::relid, RelOptInfo::reltarget, root, and Path::total_cost.
Referenced by bitmap_and_cost_est(), and choose_bitmap_and().
◆ build_index_paths()
|
static |
Definition at line 809 of file indxpath.c.
814{
816 IndexPath *ipath;
817 List *index_clauses;
818 Relids outer_relids;
819 double loop_count;
820 List *orderbyclauses;
821 List *orderbyclausecols;
822 List *index_pathkeys;
823 List *useful_pathkeys;
824 bool pathkeys_possibly_useful;
825 bool index_is_ordered;
826 bool index_only_scan;
827 int indexcol;
828
830
831 /*
832 * Check that index supports the desired scan type(s)
833 */
834 switch (scantype)
835 {
839 break;
843 break;
845 /* either or both are OK */
846 break;
847 }
848
849 /*
850 * 1. Combine the per-column IndexClause lists into an overall list.
851 *
852 * In the resulting list, clauses are ordered by index key, so that the
853 * column numbers form a nondecreasing sequence. (This order is depended
854 * on by btree and possibly other places.) The list can be empty, if the
855 * index AM allows that.
856 *
857 * We also build a Relids set showing which outer rels are required by the
858 * selected clauses. Any lateral_relids are included in that, but not
859 * otherwise accounted for.
860 */
861 index_clauses = NIL;
864 {
865 ListCell *lc;
866
868 {
871
874 {
875 /*
876 * Caller asked us to generate IndexPaths that omit any
877 * ScalarArrayOpExpr clauses when the underlying index AM
878 * lacks native support.
879 *
880 * We must omit this clause (and tell caller about it).
881 */
882 *skip_nonnative_saop = true;
883 continue;
884 }
885
886 /* OK to include this clause */
887 index_clauses = lappend(index_clauses, iclause);
888 outer_relids = bms_add_members(outer_relids,
889 rinfo->clause_relids);
890 }
891
892 /*
893 * If no clauses match the first index column, check for amoptionalkey
894 * restriction. We can't generate a scan over an index with
895 * amoptionalkey = false unless there's at least one index clause.
896 * (When working on columns after the first, this test cannot fail. It
897 * is always okay for columns after the first to not have any
898 * clauses.)
899 */
902 }
903
904 /* We do not want the index's rel itself listed in outer_relids */
906
907 /* Compute loop_count for cost estimation purposes */
909
910 /*
911 * 2. Compute pathkeys describing index's ordering, if any, then see how
912 * many of them are actually useful for this query. This is not relevant
913 * if we are only trying to build bitmap indexscans.
914 */
915 pathkeys_possibly_useful = (scantype != ST_BITMAPSCAN &&
917 index_is_ordered = (index->sortopfamily != NULL);
918 if (index_is_ordered && pathkeys_possibly_useful)
919 {
921 ForwardScanDirection);
923 index_pathkeys);
924 orderbyclauses = NIL;
925 orderbyclausecols = NIL;
926 }
928 {
929 /*
930 * See if we can generate ordering operators for query_pathkeys or at
931 * least some prefix thereof. Matching to just a prefix of the
932 * query_pathkeys will allow an incremental sort to be considered on
933 * the index's partially sorted results.
934 */
936 &orderbyclauses,
937 &orderbyclausecols);
939 useful_pathkeys = root->query_pathkeys;
940 else
942 list_length(orderbyclauses));
943 }
944 else
945 {
946 useful_pathkeys = NIL;
947 orderbyclauses = NIL;
948 orderbyclausecols = NIL;
949 }
950
951 /*
952 * 3. Check if an index-only scan is possible. If we're not building
953 * plain indexscans, this isn't relevant since bitmap scans don't support
954 * index data retrieval anyway.
955 */
956 index_only_scan = (scantype != ST_BITMAPSCAN &&
958
959 /*
960 * 4. Generate an indexscan path if there are relevant restriction clauses
961 * in the current clauses, OR the index ordering is potentially useful for
962 * later merging or final output ordering, OR the index has a useful
963 * predicate, OR an index-only scan is possible.
964 */
966 index_only_scan)
967 {
969 index_clauses,
970 orderbyclauses,
971 orderbyclausecols,
972 useful_pathkeys,
973 ForwardScanDirection,
974 index_only_scan,
975 outer_relids,
976 loop_count,
977 false);
979
980 /*
981 * If appropriate, consider parallel index scan. We don't allow
982 * parallel index scan for bitmap index scans.
983 */
985 rel->consider_parallel && outer_relids == NULL &&
986 scantype != ST_BITMAPSCAN)
987 {
989 index_clauses,
990 orderbyclauses,
991 orderbyclausecols,
992 useful_pathkeys,
993 ForwardScanDirection,
994 index_only_scan,
995 outer_relids,
996 loop_count,
997 true);
998
999 /*
1000 * if, after costing the path, we find that it's not worth using
1001 * parallel workers, just free it.
1002 */
1005 else
1006 pfree(ipath);
1007 }
1008 }
1009
1010 /*
1011 * 5. If the index is ordered, a backwards scan might be interesting.
1012 */
1013 if (index_is_ordered && pathkeys_possibly_useful)
1014 {
1016 BackwardScanDirection);
1018 index_pathkeys);
1020 {
1022 index_clauses,
1023 NIL,
1024 NIL,
1025 useful_pathkeys,
1026 BackwardScanDirection,
1027 index_only_scan,
1028 outer_relids,
1029 loop_count,
1030 false);
1032
1033 /* If appropriate, consider parallel index scan */
1035 rel->consider_parallel && outer_relids == NULL &&
1036 scantype != ST_BITMAPSCAN)
1037 {
1039 index_clauses,
1040 NIL,
1041 NIL,
1042 useful_pathkeys,
1043 BackwardScanDirection,
1044 index_only_scan,
1045 outer_relids,
1046 loop_count,
1047 true);
1048
1049 /*
1050 * if, after costing the path, we find that it's not worth
1051 * using parallel workers, just free it.
1052 */
1055 else
1056 pfree(ipath);
1057 }
1058 }
1059 }
1060
1062}
References add_partial_path(), Assert, BackwardScanDirection, bms_add_members(), bms_copy(), bms_del_member(), build_index_pathkeys(), check_index_only(), RestrictInfo::clause, RelOptInfo::consider_parallel, create_index_path(), ForwardScanDirection, get_loop_count(), has_useful_pathkeys(), IndexClauseSet::indexclauses, IsA, lappend(), RelOptInfo::lateral_relids, lfirst, list_copy_head(), list_length(), match_pathkeys_to_index(), NIL, Path::parallel_workers, IndexPath::path, pfree(), RelOptInfo::relid, result, IndexClause::rinfo, root, ST_ANYSCAN, ST_BITMAPSCAN, ST_INDEXSCAN, and truncate_useless_pathkeys().
Referenced by build_paths_for_OR(), and get_index_paths().
◆ build_paths_for_OR()
|
static |
Definition at line 1091 of file indxpath.c.
1093{
1096 ListCell *lc;
1097
1099 {
1101 IndexClauseSet clauseset;
1102 List *indexpaths;
1103 bool useful_predicate;
1104
1105 /* Ignore index if it doesn't support bitmap scans */
1107 continue;
1108
1109 /*
1110 * Ignore partial indexes that do not match the query. If a partial
1111 * index is marked predOK then we know it's OK. Otherwise, we have to
1112 * test whether the added clauses are sufficient to imply the
1113 * predicate. If so, we can use the index in the current context.
1114 *
1115 * We set useful_predicate to true iff the predicate was proven using
1116 * the current set of clauses. This is needed to prevent matching a
1117 * predOK index to an arm of an OR, which would be a legal but
1118 * pointlessly inefficient plan. (A better plan will be generated by
1119 * just scanning the predOK index alone, no OR.)
1120 */
1121 useful_predicate = false;
1123 {
1125 {
1126 /* Usable, but don't set useful_predicate */
1127 }
1128 else
1129 {
1130 /* Form all_clauses if not done already */
1132 all_clauses = list_concat_copy(clauses, other_clauses);
1133
1135 continue; /* can't use it at all */
1136
1138 useful_predicate = true;
1139 }
1140 }
1141
1142 /*
1143 * Identify the restriction clauses that can match the index.
1144 */
1147
1148 /*
1149 * If no matches so far, and the index predicate isn't useful, we
1150 * don't want it.
1151 */
1153 continue;
1154
1155 /*
1156 * Add "other" restriction clauses to the clauseset.
1157 */
1159
1160 /*
1161 * Construct paths if possible.
1162 */
1164 index, &clauseset,
1165 useful_predicate,
1166 ST_BITMAPSCAN,
1167 NULL);
1169 }
1170
1172}
References build_index_paths(), RelOptInfo::indexlist, lfirst, list_concat(), list_concat_copy(), match_clauses_to_index(), MemSet, NIL, IndexClauseSet::nonempty, predicate_implied_by(), result, root, and ST_BITMAPSCAN.
Referenced by generate_bitmap_or_paths(), and make_bitmap_paths_for_or_group().
◆ check_index_only()
|
static |
Definition at line 2226 of file indxpath.c.
2227{
2229 Bitmapset *attrs_used = NULL;
2230 Bitmapset *index_canreturn_attrs = NULL;
2231 ListCell *lc;
2233
2234 /* If we're not allowed to consider index-only scans, give up now */
2236 return false;
2237
2238 /*
2239 * Check that all needed attributes of the relation are available from the
2240 * index.
2241 */
2242
2243 /*
2244 * First, identify all the attributes needed for joins or final output.
2245 * Note: we must look at rel's targetlist, not the attr_needed data,
2246 * because attr_needed isn't computed for inheritance child rels.
2247 */
2249
2250 /*
2251 * Add all the attributes used by restriction clauses; but consider only
2252 * those clauses not implied by the index predicate, since ones that are
2253 * so implied don't need to be checked explicitly in the plan.
2254 *
2255 * Note: attributes used only in index quals would not be needed at
2256 * runtime either, if we are certain that the index is not lossy. However
2257 * it'd be complicated to account for that accurately, and it doesn't
2258 * matter in most cases, since we'd conclude that such attributes are
2259 * available from the index anyway.
2260 */
2262 {
2264
2266 }
2267
2268 /*
2269 * Construct a bitmapset of columns that the index can return back in an
2270 * index-only scan.
2271 */
2273 {
2275
2276 /*
2277 * For the moment, we just ignore index expressions. It might be nice
2278 * to do something with them, later.
2279 */
2280 if (attno == 0)
2281 continue;
2282
2284 index_canreturn_attrs =
2285 bms_add_member(index_canreturn_attrs,
2286 attno - FirstLowInvalidHeapAttributeNumber);
2287 }
2288
2289 /* Do we have all the necessary attributes? */
2291
2292 bms_free(attrs_used);
2293 bms_free(index_canreturn_attrs);
2294
2296}
References bms_add_member(), bms_free(), bms_is_subset(), RestrictInfo::clause, PathTarget::exprs, FirstLowInvalidHeapAttributeNumber, i, lfirst, PGS_CONSIDER_INDEXONLY, RelOptInfo::pgs_mask, pull_varattnos(), RelOptInfo::relid, RelOptInfo::reltarget, and result.
Referenced by build_index_paths().
◆ check_index_predicates()
| void check_index_predicates | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 3940 of file indxpath.c.
3941{
3942 List *clauselist;
3943 bool have_partial;
3944 bool is_target_rel;
3945 Relids otherrels;
3946 ListCell *lc;
3947
3948 /* Indexes are available only on base or "other" member relations. */
3950
3951 /*
3952 * Initialize the indrestrictinfo lists to be identical to
3953 * baserestrictinfo, and check whether there are any partial indexes. If
3954 * not, this is all we need to do.
3955 */
3956 have_partial = false;
3958 {
3960
3963 have_partial = true;
3964 }
3965 if (!have_partial)
3966 return;
3967
3968 /*
3969 * Construct a list of clauses that we can assume true for the purpose of
3970 * proving the index(es) usable. Restriction clauses for the rel are
3971 * always usable, and so are any join clauses that are "movable to" this
3972 * rel. Also, we can consider any EC-derivable join clauses (which must
3973 * be "movable to" this rel, by definition).
3974 */
3976
3977 /* Scan the rel's join clauses */
3979 {
3981
3982 /* Check if clause can be moved to this rel */
3984 continue;
3985
3986 clauselist = lappend(clauselist, rinfo);
3987 }
3988
3989 /*
3990 * Add on any equivalence-derivable join clauses. Computing the correct
3991 * relid sets for generate_join_implied_equalities is slightly tricky
3992 * because the rel could be a child rel rather than a true baserel, and in
3993 * that case we must subtract its parents' relid(s) from all_query_rels.
3994 * Additionally, we mustn't consider clauses that are only computable
3995 * after outer joins that can null the rel.
3996 */
4000 else
4003
4005 clauselist =
4006 list_concat(clauselist,
4009 otherrels),
4010 otherrels,
4011 rel,
4012 NULL));
4013
4014 /*
4015 * Normally we remove quals that are implied by a partial index's
4016 * predicate from indrestrictinfo, indicating that they need not be
4017 * checked explicitly by an indexscan plan using this index. However, if
4018 * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
4019 * we cannot remove such quals from the plan, because they need to be in
4020 * the plan so that they will be properly rechecked by EvalPlanQual
4021 * testing. Some day we might want to remove such quals from the main
4022 * plan anyway and pass them through to EvalPlanQual via a side channel;
4023 * but for now, we just don't remove implied quals at all for target
4024 * relations.
4025 */
4028
4029 /*
4030 * Now try to prove each index predicate true, and compute the
4031 * indrestrictinfo lists for partial indexes. Note that we compute the
4032 * indrestrictinfo list even for non-predOK indexes; this might seem
4033 * wasteful, but we may be able to use such indexes in OR clauses, cf
4034 * generate_bitmap_or_paths().
4035 */
4037 {
4039 ListCell *lcr;
4040
4042 continue; /* ignore non-partial indexes here */
4043
4046 false);
4047
4048 /* If rel is an update target, leave indrestrictinfo as set above */
4049 if (is_target_rel)
4050 continue;
4051
4052 /*
4053 * If index is !amoptionalkey, also leave indrestrictinfo as set
4054 * above. Otherwise we risk removing all quals for the first index
4055 * key and then not being able to generate an indexscan at all. It
4056 * would be better to be more selective, but we've not yet identified
4057 * which if any of the quals match the first index key.
4058 */
4060 continue;
4061
4062 /* Else compute indrestrictinfo as the non-implied quals */
4065 {
4067
4068 /* predicate_implied_by() assumes first arg is immutable */
4073 }
4074 }
4075}
References Assert, RelOptInfo::baserestrictinfo, bms_del_members(), bms_difference(), bms_is_empty, bms_is_member(), bms_union(), RestrictInfo::clause, contain_mutable_functions(), find_childrel_parents(), generate_join_implied_equalities(), get_plan_rowmark(), RelOptInfo::indexlist, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, RelOptInfo::nulling_relids, predicate_implied_by(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and root.
Referenced by set_plain_rel_size(), and set_tablesample_rel_size().
◆ choose_bitmap_and()
|
static |
Definition at line 1784 of file indxpath.c.
1785{
1787 PathClauseUsage **pathinfoarray;
1788 PathClauseUsage *pathinfo;
1789 List *clauselist;
1791 Cost bestcost = 0;
1793 j;
1794 ListCell *l;
1795
1797 if (npaths == 1)
1799
1800 /*
1801 * In theory we should consider every nonempty subset of the given paths.
1802 * In practice that seems like overkill, given the crude nature of the
1803 * estimates, not to mention the possible effects of higher-level AND and
1804 * OR clauses. Moreover, it's completely impractical if there are a large
1805 * number of paths, since the work would grow as O(2^N).
1806 *
1807 * As a heuristic, we first check for paths using exactly the same sets of
1808 * WHERE clauses + index predicate conditions, and reject all but the
1809 * cheapest-to-scan in any such group. This primarily gets rid of indexes
1810 * that include the interesting columns but also irrelevant columns. (In
1811 * situations where the DBA has gone overboard on creating variant
1812 * indexes, this can make for a very large reduction in the number of
1813 * paths considered further.)
1814 *
1815 * We then sort the surviving paths with the cheapest-to-scan first, and
1816 * for each path, consider using that path alone as the basis for a bitmap
1817 * scan. Then we consider bitmap AND scans formed from that path plus
1818 * each subsequent (higher-cost) path, adding on a subsequent path if it
1819 * results in a reduction in the estimated total scan cost. This means we
1820 * consider about O(N^2) rather than O(2^N) path combinations, which is
1821 * quite tolerable, especially given than N is usually reasonably small
1822 * because of the prefiltering step. The cheapest of these is returned.
1823 *
1824 * We will only consider AND combinations in which no two indexes use the
1825 * same WHERE clause. This is a bit of a kluge: it's needed because
1826 * costsize.c and clausesel.c aren't very smart about redundant clauses.
1827 * They will usually double-count the redundant clauses, producing a
1828 * too-small selectivity that makes a redundant AND step look like it
1829 * reduces the total cost. Perhaps someday that code will be smarter and
1830 * we can remove this limitation. (But note that this also defends
1831 * against flat-out duplicate input paths, which can happen because
1832 * match_join_clauses_to_index will find the same OR join clauses that
1833 * extract_restriction_or_clauses has pulled OR restriction clauses out
1834 * of.)
1835 *
1836 * For the same reason, we reject AND combinations in which an index
1837 * predicate clause duplicates another clause. Here we find it necessary
1838 * to be even stricter: we'll reject a partial index if any of its
1839 * predicate clauses are implied by the set of WHERE clauses and predicate
1840 * clauses used so far. This covers cases such as a condition "x = 42"
1841 * used with a plain index, followed by a clauseless scan of a partial
1842 * index "WHERE x >= 40 AND x < 50". The partial index has been accepted
1843 * only because "x = 42" was present, and so allowing it would partially
1844 * double-count selectivity. (We could use predicate_implied_by on
1845 * regular qual clauses too, to have a more intelligent, but much more
1846 * expensive, check for redundancy --- but in most cases simple equality
1847 * seems to suffice.)
1848 */
1849
1850 /*
1851 * Extract clause usage info and detect any paths that use exactly the
1852 * same set of clauses; keep only the cheapest-to-scan of any such groups.
1853 * The surviving paths are put into an array for qsort'ing.
1854 */
1856 clauselist = NIL;
1857 npaths = 0;
1858 foreach(l, paths)
1859 {
1861
1862 pathinfo = classify_index_clause_usage(ipath, &clauselist);
1863
1864 /* If it's unclassifiable, treat it as distinct from all others */
1866 {
1867 pathinfoarray[npaths++] = pathinfo;
1868 continue;
1869 }
1870
1872 {
1875 break;
1876 }
1878 {
1879 /* duplicate clauseids, keep the cheaper one */
1880 Cost ncost;
1881 Cost ocost;
1882 Selectivity nselec;
1883 Selectivity oselec;
1884
1887 if (ncost < ocost)
1888 pathinfoarray[i] = pathinfo;
1889 }
1890 else
1891 {
1892 /* not duplicate clauseids, add to array */
1893 pathinfoarray[npaths++] = pathinfo;
1894 }
1895 }
1896
1897 /* If only one surviving path, we're done */
1898 if (npaths == 1)
1900
1901 /* Sort the surviving paths by index access cost */
1903 path_usage_comparator);
1904
1905 /*
1906 * For each surviving index, consider it as an "AND group leader", and see
1907 * whether adding on any of the later indexes results in an AND path with
1908 * cheaper total cost than before. Then take the cheapest AND group.
1909 *
1910 * Note: paths that are either clauseless or unclassifiable will have
1911 * empty clauseids, so that they will not be rejected by the clauseids
1912 * filter here, nor will they cause later paths to be rejected by it.
1913 */
1915 {
1916 Cost costsofar;
1917 List *qualsofar;
1918 Bitmapset *clauseidsofar;
1919
1920 pathinfo = pathinfoarray[i];
1925
1927 {
1928 Cost newcost;
1929
1930 pathinfo = pathinfoarray[j];
1931 /* Check for redundancy */
1933 continue; /* consider it redundant */
1935 {
1936 bool redundant = false;
1937
1938 /* we check each predicate clause separately */
1940 {
1942
1944 {
1945 redundant = true;
1946 break; /* out of inner foreach loop */
1947 }
1948 }
1949 if (redundant)
1950 continue;
1951 }
1952 /* tentatively add new path to paths, so we can estimate cost */
1955 if (newcost < costsofar)
1956 {
1957 /* keep new path in paths, update subsidiary variables */
1958 costsofar = newcost;
1961 clauseidsofar = bms_add_members(clauseidsofar,
1962 pathinfo->clauseids);
1963 }
1964 else
1965 {
1966 /* reject new path, remove it from paths list */
1968 }
1969 }
1970
1971 /* Keep the cheapest AND-group (or singleton) */
1973 {
1974 bestpaths = paths;
1975 bestcost = costsofar;
1976 }
1977
1978 /* some easy cleanup (we don't try real hard though) */
1979 list_free(qualsofar);
1980 }
1981
1985}
References Assert, bitmap_and_cost_est(), bitmap_scan_cost_est(), bms_add_members(), bms_copy(), bms_equal(), bms_overlap(), classify_index_clause_usage(), PathClauseUsage::clauseids, cost_bitmap_tree_node(), create_bitmap_and_path(), i, j, lappend(), lfirst, linitial, list_concat(), list_concat_copy(), list_free(), list_length(), list_make1, list_truncate(), NIL, palloc_array, PathClauseUsage::path, path_usage_comparator(), predicate_implied_by(), PathClauseUsage::preds, qsort, PathClauseUsage::quals, root, and PathClauseUsage::unclassifiable.
Referenced by create_index_paths(), generate_bitmap_or_paths(), and make_bitmap_paths_for_or_group().
◆ classify_index_clause_usage()
|
static |
Definition at line 2085 of file indxpath.c.
2086{
2088 Bitmapset *clauseids;
2089 ListCell *lc;
2090
2092 result->path = path;
2093
2094 /* Recursively find the quals and preds used by the path */
2098
2099 /*
2100 * Some machine-generated queries have outlandish numbers of qual clauses.
2101 * To avoid getting into O(N^2) behavior even in this preliminary
2102 * classification step, we want to limit the number of entries we can
2103 * accumulate in *clauselist. Treat any path with more than 100 quals +
2104 * preds as unclassifiable, which will cause calling code to consider it
2105 * distinct from all other paths.
2106 */
2108 {
2109 result->clauseids = NULL;
2112 }
2113
2114 /* Build up a bitmapset representing the quals and preds */
2115 clauseids = NULL;
2117 {
2119
2120 clauseids = bms_add_member(clauseids,
2121 find_list_position(node, clauselist));
2122 }
2124 {
2126
2127 clauseids = bms_add_member(clauseids,
2128 find_list_position(node, clauselist));
2129 }
2130 result->clauseids = clauseids;
2132
2134}
References bms_add_member(), find_indexpath_quals(), find_list_position(), lfirst, list_length(), NIL, palloc_object, and result.
Referenced by choose_bitmap_and().
◆ consider_index_join_clauses()
|
static |
Definition at line 436 of file indxpath.c.
442{
443 int considered_clauses = 0;
445 int indexcol;
446
447 /*
448 * The strategy here is to identify every potentially useful set of outer
449 * rels that can provide indexable join clauses. For each such set,
450 * select all the join clauses available from those outer rels, add on all
451 * the indexable restriction clauses, and generate plain and/or bitmap
452 * index paths for that set of clauses. This is based on the assumption
453 * that it's always better to apply a clause as an indexqual than as a
454 * filter (qpqual); which is where an available clause would end up being
455 * applied if we omit it from the indexquals.
456 *
457 * This looks expensive, but in most practical cases there won't be very
458 * many distinct sets of outer rels to consider. As a safety valve when
459 * that's not true, we use a heuristic: limit the number of outer rel sets
460 * considered to a multiple of the number of clauses considered. (We'll
461 * always consider using each individual join clause, though.)
462 *
463 * For simplicity in selecting relevant clauses, we represent each set of
464 * outer rels as a maximum set of clause_relids --- that is, the indexed
465 * relation itself is also included in the relids set. considered_relids
466 * lists all relids sets we've already tried.
467 */
469 {
470 /* Consider each applicable simple join clause */
473 rclauseset, jclauseset, eclauseset,
474 bitindexpaths,
475 jclauseset->indexclauses[indexcol],
476 considered_clauses,
477 &considered_relids);
478 /* Consider each applicable eclass join clause */
481 rclauseset, jclauseset, eclauseset,
482 bitindexpaths,
483 eclauseset->indexclauses[indexcol],
484 considered_clauses,
485 &considered_relids);
486 }
487}
References consider_index_join_outer_rels(), IndexClauseSet::indexclauses, list_length(), NIL, and root.
Referenced by create_index_paths().
◆ consider_index_join_outer_rels()
|
static |
Definition at line 502 of file indxpath.c.
511{
512 ListCell *lc;
513
514 /* Examine relids of each joinclause in the given list */
515 foreach(lc, indexjoinclauses)
516 {
520 int num_considered_relids;
521
522 /* If we already tried its relids set, no need to do so again */
524 continue;
525
526 /*
527 * Generate the union of this clause's relids set with each
528 * previously-tried set. This ensures we try this clause along with
529 * every interesting subset of previous clauses. However, to avoid
530 * exponential growth of planning time when there are many clauses,
531 * limit the number of relid sets accepted to 10 * considered_clauses.
532 *
533 * Note: get_join_index_paths appends entries to *considered_relids,
534 * but we do not need to visit such newly-added entries within this
535 * loop, so we don't use foreach() here. No real harm would be done
536 * if we did visit them, since the subset check would reject them; but
537 * it would waste some cycles.
538 */
539 num_considered_relids = list_length(*considered_relids);
540 for (int pos = 0; pos < num_considered_relids; pos++)
541 {
543
544 /*
545 * If either is a subset of the other, no new set is possible.
546 * This isn't a complete test for redundancy, but it's easy and
547 * cheap. get_join_index_paths will check more carefully if we
548 * already generated the same relids set.
549 */
551 continue;
552
553 /*
554 * If this clause was derived from an equivalence class, the
555 * clause list may contain other clauses derived from the same
556 * eclass. We should not consider that combining this clause with
557 * one of those clauses generates a usefully different
558 * parameterization; so skip if any clause derived from the same
559 * eclass would already have been included when using oldrelids.
560 */
561 if (parent_ec &&
562 eclass_already_used(parent_ec, oldrelids,
563 indexjoinclauses))
564 continue;
565
566 /*
567 * If the number of relid sets considered exceeds our heuristic
568 * limit, stop considering combinations of clauses. We'll still
569 * consider the current clause alone, though (below this loop).
570 */
572 break;
573
574 /* OK, try the union set */
576 rclauseset, jclauseset, eclauseset,
577 bitindexpaths,
578 bms_union(clause_relids, oldrelids),
579 considered_relids);
580 }
581
582 /* Also try this set of relids by itself */
584 rclauseset, jclauseset, eclauseset,
585 bitindexpaths,
586 clause_relids,
587 considered_relids);
588 }
589}
References BMS_DIFFERENT, bms_subset_compare(), bms_union(), eclass_already_used(), get_join_index_paths(), lfirst, list_length(), list_member(), list_nth(), IndexClause::rinfo, and root.
Referenced by consider_index_join_clauses().
◆ create_index_paths()
| void create_index_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 239 of file indxpath.c.
240{
241 List *indexpaths;
242 List *bitindexpaths;
243 List *bitjoinpaths;
244 List *joinorclauses;
245 IndexClauseSet rclauseset;
246 IndexClauseSet jclauseset;
247 IndexClauseSet eclauseset;
248 ListCell *lc;
249
250 /* Skip the whole mess if no indexes */
252 return;
253
254 /* Bitmap paths are collected and then dealt with at the end */
255 bitindexpaths = bitjoinpaths = joinorclauses = NIL;
256
257 /* Examine each index in turn */
259 {
261
262 /* Protect limited-size array in IndexClauseSets */
264
265 /*
266 * Ignore partial indexes that do not match the query.
267 * (generate_bitmap_or_paths() might be able to do something with
268 * them, but that's of no concern here.)
269 */
271 continue;
272
273 /*
274 * Identify the restriction clauses that can match the index.
275 */
278
279 /*
280 * Build index paths from the restriction clauses. These will be
281 * non-parameterized paths. Plain paths go directly to add_path(),
282 * bitmap paths are added to bitindexpaths to be handled below.
283 */
285 &bitindexpaths);
286
287 /*
288 * Identify the join clauses that can match the index. For the moment
289 * we keep them separate from the restriction clauses. Note that this
290 * step finds only "loose" join clauses that have not been merged into
291 * EquivalenceClasses. Also, collect join OR clauses for later.
292 */
295 &jclauseset, &joinorclauses);
296
297 /*
298 * Look for EquivalenceClasses that can generate joinclauses matching
299 * the index.
300 */
303 &eclauseset);
304
305 /*
306 * If we found any plain or eclass join clauses, build parameterized
307 * index paths using them.
308 */
311 &rclauseset,
312 &jclauseset,
313 &eclauseset,
314 &bitjoinpaths);
315 }
316
317 /*
318 * Generate BitmapOrPaths for any suitable OR-clauses present in the
319 * restriction list. Add these to bitindexpaths.
320 */
323 bitindexpaths = list_concat(bitindexpaths, indexpaths);
324
325 /*
326 * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
327 * the joinclause list. Add these to bitjoinpaths.
328 */
330 joinorclauses, rel->baserestrictinfo);
331 bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
332
333 /*
334 * If we found anything usable, generate a BitmapHeapPath for the most
335 * promising combination of restriction bitmap index paths. Note there
336 * will be only one such path no matter how many indexes exist. This
337 * should be sufficient since there's basically only one figure of merit
338 * (total cost) for such a path.
339 */
341 {
342 Path *bitmapqual;
343 BitmapHeapPath *bpath;
344
347 rel->lateral_relids, 1.0, 0);
349
350 /* create a partial bitmap heap path */
353 }
354
355 /*
356 * Likewise, if we found anything usable, generate BitmapHeapPaths for the
357 * most promising combinations of join bitmap index paths. Our strategy
358 * is to generate one such path for each distinct parameterization seen
359 * among the available bitmap index paths. This may look pretty
360 * expensive, but usually there won't be very many distinct
361 * parameterizations. (This logic is quite similar to that in
362 * consider_index_join_clauses, but we're working with whole paths not
363 * individual clauses.)
364 */
366 {
367 List *all_path_outers;
368
369 /* Identify each distinct parameterization seen in bitjoinpaths */
370 all_path_outers = NIL;
371 foreach(lc, bitjoinpaths)
372 {
375
376 all_path_outers = list_append_unique(all_path_outers,
377 required_outer);
378 }
379
380 /* Now, for each distinct parameterization set ... */
381 foreach(lc, all_path_outers)
382 {
384 List *this_path_set;
385 Path *bitmapqual;
386 Relids required_outer;
387 double loop_count;
388 BitmapHeapPath *bpath;
389 ListCell *lcp;
390
391 /* Identify all the bitmap join paths needing no more than that */
392 this_path_set = NIL;
393 foreach(lcp, bitjoinpaths)
394 {
396
398 this_path_set = lappend(this_path_set, path);
399 }
400
401 /*
402 * Add in restriction bitmap paths, since they can be used
403 * together with any join paths.
404 */
405 this_path_set = list_concat(this_path_set, bitindexpaths);
406
407 /* Select best AND combination for this parameterization */
409
410 /* And push that path into the mix */
411 required_outer = PATH_REQ_OUTER(bitmapqual);
414 required_outer, loop_count, 0);
416 }
417 }
418}
References add_path(), Assert, RelOptInfo::baserestrictinfo, bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), generate_bitmap_or_paths(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, lappend(), RelOptInfo::lateral_relids, lfirst, list_append_unique(), list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, NIL, IndexClauseSet::nonempty, PATH_REQ_OUTER, RelOptInfo::relid, and root.
Referenced by set_plain_rel_pathlist().
◆ ec_member_matches_indexcol()
|
static |
Definition at line 4088 of file indxpath.c.
4091{
4094 Oid curFamily;
4095 Oid curCollation;
4096
4097 Assert(indexcol < index->nkeycolumns);
4098
4099 curFamily = index->opfamily[indexcol];
4100 curCollation = index->indexcollations[indexcol];
4101
4102 /*
4103 * If it's a btree index, we can reject it if its opfamily isn't
4104 * compatible with the EC, since no clause generated from the EC could be
4105 * used with the index. For non-btree indexes, we can't easily tell
4106 * whether clauses generated from the EC could be used with the index, so
4107 * don't check the opfamily. This might mean we return "true" for a
4108 * useless EC, so we have to recheck the results of
4109 * generate_implied_equalities_for_column; see
4110 * match_eclass_clauses_to_index.
4111 */
4114 return false;
4115
4116 /* We insist on collation match for all index types, though */
4118 return false;
4119
4121}
References arg, Assert, EquivalenceClass::ec_collation, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_expr, IndexCollMatchesExprColl, list_member_oid(), and match_index_to_operand().
Referenced by match_eclass_clauses_to_index().
◆ eclass_already_used()
|
static |
Definition at line 683 of file indxpath.c.
685{
686 ListCell *lc;
687
688 foreach(lc, indexjoinclauses)
689 {
692
693 if (rinfo->parent_ec == parent_ec &&
694 bms_is_subset(rinfo->clause_relids, oldrelids))
695 return true;
696 }
697 return false;
698}
References bms_is_subset(), lfirst, and IndexClause::rinfo.
Referenced by consider_index_join_outer_rels().
◆ expand_indexqual_rowcompare()
|
static |
Definition at line 3493 of file indxpath.c.
3499{
3502 int op_strategy;
3503 Oid op_lefttype;
3504 Oid op_righttype;
3505 int matching_cols;
3506 List *expr_ops;
3507 List *opfamilies;
3508 List *lefttypes;
3509 List *righttypes;
3510 List *new_ops;
3511 List *var_args;
3512 List *non_var_args;
3513
3514 iclause->rinfo = rinfo;
3515 iclause->indexcol = indexcol;
3516
3517 if (var_on_left)
3518 {
3519 var_args = clause->largs;
3520 non_var_args = clause->rargs;
3521 }
3522 else
3523 {
3524 var_args = clause->rargs;
3525 non_var_args = clause->largs;
3526 }
3527
3529 &op_strategy,
3530 &op_lefttype,
3531 &op_righttype);
3532
3533 /* Initialize returned list of which index columns are used */
3534 iclause->indexcols = list_make1_int(indexcol);
3535
3536 /* Build lists of ops, opfamilies and operator datatypes in case needed */
3537 expr_ops = list_make1_oid(expr_op);
3539 lefttypes = list_make1_oid(op_lefttype);
3540 righttypes = list_make1_oid(op_righttype);
3541
3542 /*
3543 * See how many of the remaining columns match some index column in the
3544 * same way. As in match_clause_to_indexcol(), the "other" side of any
3545 * potential index condition is OK as long as it doesn't use Vars from the
3546 * indexed relation.
3547 */
3548 matching_cols = 1;
3549
3551 {
3555
3556 expr_op = list_nth_oid(clause->opnos, matching_cols);
3557 if (!var_on_left)
3558 {
3559 /* indexkey is on right, so commute the operator */
3560 expr_op = get_commutator(expr_op);
3562 break; /* operator is not usable */
3563 }
3565 break; /* no good, Var on wrong side */
3567 break; /* no good, volatile comparison value */
3568
3569 /*
3570 * The Var side can match any key column of the index.
3571 */
3573 {
3575 get_op_opfamily_strategy(expr_op,
3578 list_nth_oid(clause->inputcollids,
3579 matching_cols)))
3580 break;
3581 }
3583 break; /* no match found */
3584
3585 /* Add column number to returned list */
3587
3588 /* Add operator info to lists */
3590 &op_strategy,
3591 &op_lefttype,
3592 &op_righttype);
3593 expr_ops = lappend_oid(expr_ops, expr_op);
3595 lefttypes = lappend_oid(lefttypes, op_lefttype);
3596 righttypes = lappend_oid(righttypes, op_righttype);
3597
3598 /* This column matches, keep scanning */
3599 matching_cols++;
3600 }
3601
3602 /* Result is non-lossy if all columns are usable as index quals */
3603 iclause->lossy = (matching_cols != list_length(clause->opnos));
3604
3605 /*
3606 * We can use rinfo->clause as-is if we have var on left and it's all
3607 * usable as index quals.
3608 */
3609 if (var_on_left && !iclause->lossy)
3610 iclause->indexquals = list_make1(rinfo);
3611 else
3612 {
3613 /*
3614 * We have to generate a modified rowcompare (possibly just one
3615 * OpExpr). The painful part of this is changing < to <= or > to >=,
3616 * so deal with that first.
3617 */
3618 if (!iclause->lossy)
3619 {
3620 /* very easy, just use the commuted operators */
3621 new_ops = expr_ops;
3622 }
3624 op_strategy == BTGreaterEqualStrategyNumber)
3625 {
3626 /* easy, just use the same (possibly commuted) operators */
3627 new_ops = list_truncate(expr_ops, matching_cols);
3628 }
3629 else
3630 {
3631 ListCell *opfamilies_cell;
3632 ListCell *lefttypes_cell;
3633 ListCell *righttypes_cell;
3634
3636 op_strategy = BTLessEqualStrategyNumber;
3638 op_strategy = BTGreaterEqualStrategyNumber;
3639 else
3641 new_ops = NIL;
3642 forthree(opfamilies_cell, opfamilies,
3643 lefttypes_cell, lefttypes,
3644 righttypes_cell, righttypes)
3645 {
3649
3650 expr_op = get_opfamily_member(opfam, lefttype, righttype,
3651 op_strategy);
3654 op_strategy, lefttype, righttype, opfam);
3655 new_ops = lappend_oid(new_ops, expr_op);
3656 }
3657 }
3658
3659 /* If we have more than one matching col, create a subset rowcompare */
3660 if (matching_cols > 1)
3661 {
3663
3665 rc->opnos = new_ops;
3666 rc->opfamilies = list_copy_head(clause->opfamilies,
3667 matching_cols);
3668 rc->inputcollids = list_copy_head(clause->inputcollids,
3669 matching_cols);
3673 (Expr *) rc));
3674 }
3675 else
3676 {
3677 Expr *op;
3678
3679 /* We don't report an index column list in this case */
3680 iclause->indexcols = NIL;
3681
3685 InvalidOid,
3686 linitial_oid(clause->inputcollids));
3688 }
3689 }
3690
3691 return iclause;
3692}
References bms_is_member(), BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, RowCompareExpr::cmptype, contain_volatile_functions(), copyObject, elog, ERROR, forthree, get_commutator(), get_op_opfamily_properties(), get_op_opfamily_strategy(), get_opfamily_member(), i, IndexClause::indexcol, IndexCollMatchesExprColl, IndexClause::indexcols, IndexClause::indexquals, InvalidOid, lappend_int(), lappend_oid(), RowCompareExpr::largs, lfirst_oid, linitial, linitial_oid, list_copy_head(), list_length(), list_make1, list_make1_int, list_make1_oid, list_nth(), list_nth_oid(), list_truncate(), IndexClause::lossy, make_opclause(), make_simple_restrictinfo, makeNode, match_index_to_operand(), NIL, OidIsValid, pull_varnos(), RowCompareExpr::rargs, IndexClause::rinfo, and root.
Referenced by match_rowcompare_to_indexcol().
◆ find_indexpath_quals()
Definition at line 2153 of file indxpath.c.
2154{
2156 {
2158 ListCell *l;
2159
2161 {
2163 }
2164 }
2166 {
2168 ListCell *l;
2169
2171 {
2173 }
2174 }
2176 {
2178 ListCell *l;
2179
2181 {
2183
2185 }
2187 }
2188 else
2190}
References BitmapAndPath::bitmapquals, BitmapOrPath::bitmapquals, RestrictInfo::clause, elog, ERROR, find_indexpath_quals(), IndexPath::indexclauses, IndexPath::indexinfo, IndexOptInfo::indpred, IsA, lappend(), lfirst, list_concat(), nodeTag, and IndexClause::rinfo.
Referenced by classify_index_clause_usage(), and find_indexpath_quals().
◆ find_list_position()
◆ generate_bitmap_or_paths()
|
static |
Definition at line 1628 of file indxpath.c.
1630{
1632 List *all_clauses;
1633 ListCell *lc;
1634
1635 /*
1636 * We can use both the current and other clauses as context for
1637 * build_paths_for_OR; no need to remove ORs from the lists.
1638 */
1639 all_clauses = list_concat_copy(clauses, other_clauses);
1640
1641 foreach(lc, clauses)
1642 {
1644 List *pathlist;
1645 Path *bitmapqual;
1647 List *groupedArgs;
1649
1650 /* Ignore RestrictInfos that aren't ORs */
1652 continue;
1653
1654 /*
1655 * We must be able to match at least one index to each of the arms of
1656 * the OR, else we can't use it.
1657 */
1658 pathlist = NIL;
1659
1660 /*
1661 * Group the similar OR-clause arguments into dedicated RestrictInfos,
1662 * because each of those RestrictInfos has a chance to match the index
1663 * as a whole.
1664 */
1666
1668 {
1669 /*
1670 * Some parts of the rinfo were probably grouped. In this case,
1671 * we have a set of sub-rinfos that together are an exact
1672 * duplicate of rinfo. Thus, we need to remove the rinfo from
1673 * other clauses. match_clauses_to_index detects duplicated
1674 * iclauses by comparing pointers to original rinfos that would be
1675 * different. So, we must delete rinfo to avoid de-facto
1676 * duplicated clauses in the index clauses list.
1677 */
1679 }
1680
1682 {
1684 List *indlist;
1685
1686 /* OR arguments should be ANDs or sub-RestrictInfos */
1688 {
1690
1692 andargs,
1693 all_clauses);
1694
1695 /* Recurse in case there are sub-ORs */
1696 indlist = list_concat(indlist,
1698 andargs,
1699 all_clauses));
1700 }
1702 {
1704
1705 /*
1706 * Generate bitmap paths for the group of similar OR-clause
1707 * arguments.
1708 */
1710 rel, ri,
1711 inner_other_clauses);
1712
1714 {
1715 pathlist = NIL;
1716 break;
1717 }
1718 else
1719 {
1720 pathlist = list_concat(pathlist, indlist);
1721 continue;
1722 }
1723 }
1724 else
1725 {
1727 List *orargs;
1728
1729 orargs = list_make1(ri);
1730
1732 orargs,
1733 all_clauses);
1734 }
1735
1736 /*
1737 * If nothing matched this arm, we can't do anything with this OR
1738 * clause.
1739 */
1741 {
1742 pathlist = NIL;
1743 break;
1744 }
1745
1746 /*
1747 * OK, pick the most promising AND combination, and add it to
1748 * pathlist.
1749 */
1751 pathlist = lappend(pathlist, bitmapqual);
1752 }
1753
1755 list_free(inner_other_clauses);
1756
1757 /*
1758 * If we have a match for every arm, then turn them into a
1759 * BitmapOrPath, and add to result list.
1760 */
1762 {
1765 }
1766 }
1767
1769}
References build_paths_for_OR(), castNode, choose_bitmap_and(), create_bitmap_or_path(), generate_bitmap_or_paths(), group_similar_or_args(), is_andclause(), j, lappend(), lfirst, lfirst_node, list_concat(), list_concat_copy(), list_copy(), list_delete(), list_free(), list_make1, make_bitmap_paths_for_or_group(), NIL, restriction_is_or_clause(), result, and root.
Referenced by create_index_paths(), and generate_bitmap_or_paths().
◆ get_index_clause_from_support()
|
static |
Definition at line 3067 of file indxpath.c.
3073{
3075 SupportRequestIndexCondition req;
3076 List *sresult;
3077
3079 return NULL;
3080
3081 req.type = T_SupportRequestIndexCondition;
3083 req.funcid = funcid;
3085 req.indexarg = indexarg;
3087 req.indexcol = indexcol;
3090
3092
3093 sresult = (List *)
3095 PointerGetDatum(&req)));
3096
3098 {
3101 ListCell *lc;
3102
3103 /*
3104 * The support function API says it should just give back bare
3105 * clauses, so here we must wrap each one in a RestrictInfo.
3106 */
3107 foreach(lc, sresult)
3108 {
3110
3111 indexquals = lappend(indexquals,
3113 }
3114
3115 iclause->rinfo = rinfo;
3116 iclause->indexquals = indexquals;
3118 iclause->indexcol = indexcol;
3120
3121 return iclause;
3122 }
3123
3124 return NULL;
3125}
References RestrictInfo::clause, DatumGetPointer(), SupportRequestIndexCondition::funcid, get_func_support(), SupportRequestIndexCondition::index, SupportRequestIndexCondition::indexarg, IndexClause::indexcol, SupportRequestIndexCondition::indexcol, SupportRequestIndexCondition::indexcollation, IndexClause::indexcols, IndexClause::indexquals, lappend(), lfirst, IndexClause::lossy, SupportRequestIndexCondition::lossy, make_simple_restrictinfo, makeNode, NIL, SupportRequestIndexCondition::node, OidFunctionCall1, OidIsValid, SupportRequestIndexCondition::opfamily, PointerGetDatum(), IndexClause::rinfo, root, SupportRequestIndexCondition::root, and SupportRequestIndexCondition::type.
Referenced by match_funcclause_to_indexcol(), and match_opclause_to_indexcol().
◆ get_index_paths()
|
static |
Definition at line 715 of file indxpath.c.
718{
719 List *indexpaths;
720 bool skip_nonnative_saop = false;
721 ListCell *lc;
722
723 /*
724 * Build simple index paths using the clauses. Allow ScalarArrayOpExpr
725 * clauses only if the index AM supports them natively.
726 */
728 index, clauses,
729 index->predOK,
730 ST_ANYSCAN,
731 &skip_nonnative_saop);
732
733 /*
734 * Submit all the ones that can form plain IndexScan plans to add_path. (A
735 * plain IndexPath can represent either a plain IndexScan or an
736 * IndexOnlyScan, but for our purposes here that distinction does not
737 * matter. However, some of the indexes might support only bitmap scans,
738 * and those we mustn't submit to add_path here.)
739 *
740 * Also, pick out the ones that are usable as bitmap scans. For that, we
741 * must discard indexes that don't support bitmap scans, and we also are
742 * only interested in paths that have some selectivity; we should discard
743 * anything that was generated solely for ordering purposes.
744 */
745 foreach(lc, indexpaths)
746 {
748
751
754 ipath->indexselectivity < 1.0))
755 *bitindexpaths = lappend(*bitindexpaths, ipath);
756 }
757
758 /*
759 * If there were ScalarArrayOpExpr clauses that the index can't handle
760 * natively, generate bitmap scan paths relying on executor-managed
761 * ScalarArrayOpExpr.
762 */
763 if (skip_nonnative_saop)
764 {
766 index, clauses,
767 false,
768 ST_BITMAPSCAN,
769 NULL);
770 *bitindexpaths = list_concat(*bitindexpaths, indexpaths);
771 }
772}
References add_path(), build_index_paths(), IndexPath::indexselectivity, lappend(), lfirst, list_concat(), NIL, IndexPath::path, Path::pathkeys, root, ST_ANYSCAN, and ST_BITMAPSCAN.
Referenced by create_index_paths(), and get_join_index_paths().
◆ get_join_index_paths()
|
static |
Definition at line 605 of file indxpath.c.
613{
614 IndexClauseSet clauseset;
615 int indexcol;
616
617 /* If we already considered this relids set, don't repeat the work */
619 return;
620
621 /* Identify indexclauses usable with this relids set */
623
625 {
626 ListCell *lc;
627
628 /* First find applicable simple join clauses */
630 {
632
634 clauseset.indexclauses[indexcol] =
636 }
637
638 /*
639 * Add applicable eclass join clauses. The clauses generated for each
640 * column are redundant (cf generate_implied_equalities_for_column),
641 * so we need at most one. This is the only exception to the general
642 * rule of using all available index clauses.
643 */
645 {
647
649 {
650 clauseset.indexclauses[indexcol] =
652 break;
653 }
654 }
655
656 /* Add restriction clauses */
657 clauseset.indexclauses[indexcol] =
659 rclauseset->indexclauses[indexcol]);
660
663 }
664
665 /* We should have found something, else caller passed silly relids */
667
668 /* Build index path(s) using the collected set of clauses */
670
671 /*
672 * Remember we considered paths for this set of relids.
673 */
674 *considered_relids = lappend(*considered_relids, relids);
675}
References Assert, bms_is_subset(), get_index_paths(), IndexClauseSet::indexclauses, lappend(), lfirst, list_concat(), list_member(), MemSet, NIL, IndexClauseSet::nonempty, IndexClause::rinfo, and root.
Referenced by consider_index_join_outer_rels().
◆ get_loop_count()
|
static |
Definition at line 2325 of file indxpath.c.
2326{
2328 int outer_relid;
2329
2330 /* For a non-parameterized path, just return 1.0 quickly */
2331 if (outer_relids == NULL)
2332 return 1.0;
2333
2334 result = 0.0;
2335 outer_relid = -1;
2337 {
2338 RelOptInfo *outer_rel;
2339 double rowcount;
2340
2341 /* Paranoia: ignore bogus relid indexes */
2343 continue;
2344 outer_rel = root->simple_rel_array[outer_relid];
2345 if (outer_rel == NULL)
2346 continue;
2348
2349 /* Other relation could be proven empty, if so ignore */
2351 continue;
2352
2353 /* Otherwise, rel's rows estimate should be valid by now */
2355
2356 /* Check to see if rel is on the inside of any semijoins */
2358 cur_relid,
2359 outer_relid,
2360 outer_rel->rows);
2361
2362 /* Remember smallest row count estimate among the outer rels */
2364 result = rowcount;
2365 }
2366 /* Return 1.0 if we found no valid relations (shouldn't happen) */
2368}
References adjust_rowcount_for_semijoins(), Assert, bms_next_member(), IS_DUMMY_REL, RelOptInfo::relid, result, root, and RelOptInfo::rows.
Referenced by bitmap_scan_cost_est(), build_index_paths(), and create_index_paths().
◆ group_similar_or_args()
|
static |
Definition at line 1270 of file indxpath.c.
1271{
1272 int n;
1274 int group_start;
1275 OrArgIndexMatch *matches;
1276 bool matched = false;
1277 ListCell *lc;
1278 ListCell *lc2;
1279 List *orargs;
1282
1284 orargs = ((BoolExpr *) rinfo->orclause)->args;
1285 n = list_length(orargs);
1286
1287 /*
1288 * To avoid N^2 behavior, take utility pass along the list of OR-clause
1289 * arguments. For each argument, fill the OrArgIndexMatch structure,
1290 * which will be used to sort these arguments at the next step.
1291 */
1292 i = -1;
1294 foreach(lc, orargs)
1295 {
1297 RestrictInfo *argrinfo;
1298 OpExpr *clause;
1299 Oid opno;
1300 Node *leftop,
1301 *rightop;
1302 Node *nonConstExpr;
1303 int indexnum;
1304 int colnum;
1305
1306 i++;
1313
1315 continue;
1316
1318
1319 /* Only operator clauses can match */
1321 continue;
1322
1324 opno = clause->opno;
1325
1326 /* Only binary operators can match */
1328 continue;
1329
1330 /*
1331 * Ignore any RelabelType node above the operands. This is needed to
1332 * be able to apply indexscanning in binary-compatible-operator cases.
1333 * Note: we can assume there is at most one RelabelType node;
1334 * eval_const_expressions() will have simplified if more than one.
1335 */
1336 leftop = get_leftop(clause);
1339
1340 rightop = get_rightop(clause);
1343
1344 /*
1345 * Check for clauses of the form: (indexkey operator constant) or
1346 * (constant operator indexkey). But we don't know a particular index
1347 * yet. Therefore, we try to distinguish the potential index key and
1348 * constant first, then search for a matching index key among all
1349 * indexes.
1350 */
1352 !bms_is_member(relid, argrinfo->left_relids) &&
1353 !contain_volatile_functions(leftop))
1354 {
1355 opno = get_commutator(opno);
1356
1358 {
1359 /* commutator doesn't exist, we can't reverse the order */
1360 continue;
1361 }
1362 nonConstExpr = rightop;
1363 }
1365 !bms_is_member(relid, argrinfo->right_relids) &&
1366 !contain_volatile_functions(rightop))
1367 {
1368 nonConstExpr = leftop;
1369 }
1370 else
1371 {
1372 continue;
1373 }
1374
1375 /*
1376 * Match non-constant part to the index key. It's possible that a
1377 * single non-constant part matches multiple index keys. It's OK, we
1378 * just stop with first matching index key. Given that this choice is
1379 * determined the same for every clause, we will group similar clauses
1380 * together anyway.
1381 */
1382 indexnum = 0;
1384 {
1386
1387 /*
1388 * Ignore index if it doesn't support bitmap scans or SAOP
1389 * clauses.
1390 */
1392 continue;
1393
1395 {
1397 {
1402 matched = true;
1403 break;
1404 }
1405 }
1406
1407 /*
1408 * Stop looping through the indexes, if we managed to match
1409 * nonConstExpr to any index column.
1410 */
1412 break;
1413 indexnum++;
1414 }
1415 }
1416
1417 /*
1418 * Fast-path check: if no clause is matching to the index column, we can
1419 * just give up at this stage and return the clause list as-is.
1420 */
1421 if (!matched)
1422 {
1423 pfree(matches);
1424 return orargs;
1425 }
1426
1427 /*
1428 * Sort clauses to make similar clauses go together. But at the same
1429 * time, we would like to change the order of clauses as little as
1430 * possible. To do so, we reorder each group of similar clauses so that
1431 * the first item of the group stays in place, and all the other items are
1432 * moved after it. So, if there are no similar clauses, the order of
1433 * clauses stays the same. When there are some groups, required
1434 * reordering happens while the rest of the clauses remain in their
1435 * places. That is achieved by assigning a 'groupindex' to each clause:
1436 * the number of the first item in the group in the original clause list.
1437 */
1439
1440 /* Assign groupindex to the sorted clauses */
1442 {
1443 /*
1444 * When two clauses are similar and should belong to the same group,
1445 * copy the 'groupindex' from the previous clause. Given we are
1446 * considering clauses in direct order, all the clauses would have a
1447 * 'groupindex' equal to the 'groupindex' of the first clause in the
1448 * group.
1449 */
1454 matches[i].indexnum != -1)
1456 }
1457
1458 /* Re-sort clauses first by groupindex then by argindex */
1460
1461 /*
1462 * Group similar clauses into single sub-restrictinfo. Side effect: the
1463 * resulting list of restrictions will be sorted by indexnum and colnum.
1464 */
1465 group_start = 0;
1467 {
1468 /* Check if it's a group boundary */
1469 if (group_start >= 0 &&
1470 (i == n ||
1471 matches[i].indexnum != matches[group_start].indexnum ||
1472 matches[i].colnum != matches[group_start].colnum ||
1473 matches[i].opno != matches[group_start].opno ||
1474 matches[i].inputcollid != matches[group_start].inputcollid ||
1475 matches[i].indexnum == -1))
1476 {
1477 /*
1478 * One clause in group: add it "as is" to the upper-level OR.
1479 */
1481 {
1483 list_nth(orargs,
1484 matches[group_start].argindex));
1485 }
1486 else
1487 {
1488 /*
1489 * Two or more clauses in a group: create a nested OR.
1490 */
1493 RestrictInfo *subrinfo;
1495
1497
1498 /* Construct the list of nested OR arguments */
1500 {
1502
1506 else
1508 }
1509
1510 /* Construct the nested OR and wrap it with RestrictInfo */
1512 make_orclause(args),
1513 make_orclause(rargs),
1514 rinfo->is_pushed_down,
1515 rinfo->has_clone,
1516 rinfo->is_clone,
1517 rinfo->pseudoconstant,
1518 rinfo->security_level,
1519 rinfo->required_relids,
1520 rinfo->incompatible_relids,
1521 rinfo->outer_relids);
1523 }
1524
1525 group_start = i;
1526 }
1527 }
1528 pfree(matches);
1530}
References arg, OrArgIndexMatch::argindex, OpExpr::args, Assert, bms_is_member(), castNode, RestrictInfo::clause, OrArgIndexMatch::colnum, contain_volatile_functions(), get_commutator(), get_leftop(), get_rightop(), OrArgIndexMatch::groupindex, RestrictInfo::has_clone, i, RestrictInfo::incompatible_relids, RelOptInfo::indexlist, OrArgIndexMatch::indexnum, OrArgIndexMatch::inputcollid, InvalidOid, RestrictInfo::is_clone, RestrictInfo::is_pushed_down, IsA, j, lappend(), lfirst, list_length(), list_nth(), make_orclause(), make_plain_restrictinfo(), match_index_to_operand(), NIL, OidIsValid, OrArgIndexMatch::opno, OpExpr::opno, or_arg_index_match_cmp(), or_arg_index_match_cmp_group(), RestrictInfo::outer_relids, palloc_array, pfree(), qsort, RelOptInfo::relid, RestrictInfo::required_relids, result, root, and RestrictInfo::security_level.
Referenced by generate_bitmap_or_paths().
◆ indexcol_is_bool_constant_for_query()
| bool indexcol_is_bool_constant_for_query | ( | PlannerInfo * | root, |
| IndexOptInfo * | index, | ||
| int | indexcol | ||
| ) |
Definition at line 4302 of file indxpath.c.
4305{
4306 ListCell *lc;
4307
4308 /* If the index isn't boolean, we can't possibly get a match */
4310 return false;
4311
4312 /* Check each restriction clause for the index's rel */
4314 {
4316
4317 /*
4318 * As in match_clause_to_indexcol, never match pseudoconstants to
4319 * indexes. (It might be semantically okay to do so here, but the
4320 * odds of getting a match are negligible, so don't waste the cycles.)
4321 */
4322 if (rinfo->pseudoconstant)
4323 continue;
4324
4325 /* See if we can match the clause's expression to the index column */
4327 return true;
4328 }
4329
4330 return false;
4331}
References IsBooleanOpfamily(), lfirst, match_boolean_index_clause(), and root.
Referenced by build_index_pathkeys().
◆ is_pseudo_constant_for_index()
| bool is_pseudo_constant_for_index | ( | PlannerInfo * | root, |
| Node * | expr, | ||
| IndexOptInfo * | index | ||
| ) |
Definition at line 4450 of file indxpath.c.
4451{
4452 /* pull_varnos is cheaper than volatility check, so do that first */
4454 return false; /* no good, contains Var of table */
4456 return false; /* no good, volatile comparison value */
4457 return true;
4458}
References bms_is_member(), contain_volatile_functions(), pull_varnos(), and root.
◆ IsBooleanOpfamily()
|
static |
Definition at line 2790 of file indxpath.c.
2791{
2793 return IsBuiltinBooleanOpfamily(opfamily);
2794 else
2796}
References FirstNormalObjectId, and op_in_opfamily().
Referenced by indexcol_is_bool_constant_for_query(), and match_clause_to_indexcol().
◆ make_bitmap_paths_for_or_group()
|
static |
Definition at line 1547 of file indxpath.c.
1549{
1552 ListCell *lc;
1553 List *orargs;
1555 Cost jointcost = 0.0,
1556 splitcost = 0.0;
1557 Path *bitmapqual;
1558 List *indlist;
1559
1560 /*
1561 * First, try to match the whole group to the one index.
1562 */
1563 orargs = list_make1(ri);
1565 orargs,
1566 other_clauses);
1568 {
1570 jointcost = bitmapqual->total_cost;
1571 jointlist = list_make1(bitmapqual);
1572 }
1573
1574 /*
1575 * If we manage to find a bitmap scan, which uses the group of OR-clause
1576 * arguments as a whole, we can skip matching OR-clause arguments
1577 * one-by-one as long as there are no other clauses, which can bring more
1578 * efficiency to one-by-one case.
1579 */
1581 return jointlist;
1582
1583 /*
1584 * Also try to match all containing clauses one-by-one.
1585 */
1586 foreach(lc, args)
1587 {
1589
1591 orargs,
1592 other_clauses);
1593
1595 {
1596 splitlist = NIL;
1597 break;
1598 }
1599
1601 splitcost += bitmapqual->total_cost;
1602 splitlist = lappend(splitlist, bitmapqual);
1603 }
1604
1605 /*
1606 * Pick the best option.
1607 */
1609 return jointlist;
1611 return splitlist;
1612 else
1613 return (jointcost < splitcost) ? jointlist : splitlist;
1614}
References build_paths_for_OR(), choose_bitmap_and(), lappend(), lfirst, list_make1, NIL, root, and Path::total_cost.
Referenced by generate_bitmap_or_paths().
◆ match_boolean_index_clause()
|
static |
Definition at line 2815 of file indxpath.c.
2819{
2821 Expr *op = NULL;
2822
2823 /* Direct match? */
2825 {
2826 /* convert to indexkey = TRUE */
2828 (Expr *) clause,
2831 }
2832 /* NOT clause? */
2834 {
2836
2838 {
2839 /* convert to indexkey = FALSE */
2844 }
2845 }
2846
2847 /*
2848 * Since we only consider clauses at top level of WHERE, we can convert
2849 * indexkey IS TRUE and indexkey IS FALSE to index searches as well. The
2850 * different meaning for NULL isn't important.
2851 */
2853 {
2856
2859 {
2860 /* convert to indexkey = TRUE */
2865 }
2868 {
2869 /* convert to indexkey = FALSE */
2874 }
2875 }
2876
2877 /*
2878 * If we successfully made an operator clause from the given qual, we must
2879 * wrap it in an IndexClause. It's not lossy.
2880 */
2881 if (op)
2882 {
2884
2885 iclause->rinfo = rinfo;
2888 iclause->indexcol = indexcol;
2890 return iclause;
2891 }
2892
2893 return NULL;
2894}
References arg, BooleanTest::arg, BooleanTest::booltesttype, RestrictInfo::clause, get_notclausearg(), IndexClause::indexcol, IndexClause::indexcols, IndexClause::indexquals, InvalidOid, IS_FALSE, is_notclause(), IS_TRUE, IsA, list_make1, IndexClause::lossy, make_opclause(), make_simple_restrictinfo, makeBoolConst(), makeNode, match_index_to_operand(), NIL, IndexClause::rinfo, and root.
Referenced by indexcol_is_bool_constant_for_query(), and match_clause_to_indexcol().
◆ match_clause_to_index()
|
static |
Definition at line 2585 of file indxpath.c.
2589{
2590 int indexcol;
2591
2592 /*
2593 * Never match pseudoconstants to indexes. (Normally a match could not
2594 * happen anyway, since a pseudoconstant clause couldn't contain a Var,
2595 * but what if someone builds an expression index on a constant? It's not
2596 * totally unreasonable to do so with a partial index, either.)
2597 */
2598 if (rinfo->pseudoconstant)
2599 return;
2600
2601 /*
2602 * If clause can't be used as an indexqual because it must wait till after
2603 * some lower-security-level restriction clause, reject it.
2604 */
2606 return;
2607
2608 /* OK, check each index key column for a match */
2610 {
2611 IndexClause *iclause;
2612 ListCell *lc;
2613
2614 /* Ignore duplicates */
2616 {
2618
2620 return;
2621 }
2622
2623 /* OK, try to match the clause to the index column */
2625 rinfo,
2626 indexcol,
2627 index);
2628 if (iclause)
2629 {
2630 /* Success, so record it */
2631 clauseset->indexclauses[indexcol] =
2634 return;
2635 }
2636 }
2637}
References IndexClauseSet::indexclauses, lappend(), lfirst, match_clause_to_indexcol(), IndexClauseSet::nonempty, restriction_is_securely_promotable(), IndexClause::rinfo, and root.
Referenced by match_clauses_to_index(), and match_join_clauses_to_index().
◆ match_clause_to_indexcol()
|
static |
Definition at line 2709 of file indxpath.c.
2713{
2714 IndexClause *iclause;
2716 Oid opfamily;
2717
2718 Assert(indexcol < index->nkeycolumns);
2719
2720 /*
2721 * Historically this code has coped with NULL clauses. That's probably
2722 * not possible anymore, but we might as well continue to cope.
2723 */
2724 if (clause == NULL)
2725 return NULL;
2726
2727 /* First check for boolean-index cases. */
2728 opfamily = index->opfamily[indexcol];
2730 {
2732 if (iclause)
2733 return iclause;
2734 }
2735
2736 /*
2737 * Clause must be an opclause, funcclause, ScalarArrayOpExpr,
2738 * RowCompareExpr, or OR-clause that could be converted to SAOP. Or, if
2739 * the index supports it, we can handle IS NULL/NOT NULL clauses.
2740 */
2742 {
2744 }
2746 {
2748 }
2750 {
2752 }
2754 {
2756 }
2758 {
2760 }
2762 {
2764
2765 if (!nt->argisrow &&
2767 {
2769 iclause->rinfo = rinfo;
2772 iclause->indexcol = indexcol;
2774 return iclause;
2775 }
2776 }
2777
2778 return NULL;
2779}
References NullTest::arg, Assert, RestrictInfo::clause, IndexClause::indexcol, IndexClause::indexcols, IndexClause::indexquals, IsA, IsBooleanOpfamily(), list_make1, IndexClause::lossy, makeNode, match_boolean_index_clause(), match_funcclause_to_indexcol(), match_index_to_operand(), match_opclause_to_indexcol(), match_orclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), NIL, restriction_is_or_clause(), IndexClause::rinfo, and root.
Referenced by match_clause_to_index().
◆ match_clause_to_ordering_op()
|
static |
Definition at line 3826 of file indxpath.c.
3830{
3831 Oid opfamily;
3832 Oid idxcollation;
3833 Node *leftop,
3834 *rightop;
3835 Oid expr_op;
3836 Oid expr_coll;
3837 Oid sortfamily;
3838 bool commuted;
3839
3840 Assert(indexcol < index->nkeycolumns);
3841
3842 opfamily = index->opfamily[indexcol];
3843 idxcollation = index->indexcollations[indexcol];
3844
3845 /*
3846 * Clause must be a binary opclause.
3847 */
3849 return NULL;
3850 leftop = get_leftop(clause);
3851 rightop = get_rightop(clause);
3852 if (!leftop || !rightop)
3853 return NULL;
3854 expr_op = ((OpExpr *) clause)->opno;
3855 expr_coll = ((OpExpr *) clause)->inputcollid;
3856
3857 /*
3858 * We can forget the whole thing right away if wrong collation.
3859 */
3861 return NULL;
3862
3863 /*
3864 * Check for clauses of the form: (indexkey operator constant) or
3865 * (constant operator indexkey).
3866 */
3868 !contain_var_clause(rightop) &&
3869 !contain_volatile_functions(rightop))
3870 {
3871 commuted = false;
3872 }
3874 !contain_var_clause(leftop) &&
3875 !contain_volatile_functions(leftop))
3876 {
3877 /* Might match, but we need a commuted operator */
3878 expr_op = get_commutator(expr_op);
3880 return NULL;
3881 commuted = true;
3882 }
3883 else
3884 return NULL;
3885
3886 /*
3887 * Is the (commuted) operator an ordering operator for the opfamily? And
3888 * if so, does it yield the right sorting semantics?
3889 */
3890 sortfamily = get_op_opfamily_sortfamily(expr_op, opfamily);
3891 if (sortfamily != pk_opfamily)
3892 return NULL;
3893
3894 /* We have a match. Return clause or a commuted version thereof. */
3895 if (commuted)
3896 {
3898
3899 /* flat-copy all the fields of clause */
3901
3902 /* commute it */
3903 newclause->opno = expr_op;
3904 newclause->opfuncid = InvalidOid;
3906
3907 clause = (Expr *) newclause;
3908 }
3909
3910 return clause;
3911}
References OpExpr::args, Assert, contain_var_clause(), contain_volatile_functions(), get_commutator(), get_leftop(), get_op_opfamily_sortfamily(), get_rightop(), IndexCollMatchesExprColl, InvalidOid, is_opclause(), list_make2, makeNode, match_index_to_operand(), memcpy(), and OpExpr::opno.
Referenced by match_pathkeys_to_index().
◆ match_clauses_to_index()
|
static |
Definition at line 2552 of file indxpath.c.
References lfirst_node, match_clause_to_index(), and root.
Referenced by build_paths_for_OR(), match_eclass_clauses_to_index(), and match_restriction_clauses_to_index().
◆ match_eclass_clauses_to_index()
|
static |
Definition at line 2514 of file indxpath.c.
2516{
2517 int indexcol;
2518
2519 /* No work if rel is not in any such ECs */
2521 return;
2522
2524 {
2526 List *clauses;
2527
2528 /* Generate clauses, skipping any that join to lateral_referencers */
2530 arg.indexcol = indexcol;
2532 index->rel,
2534 &arg,
2535 index->rel->lateral_referencers);
2536
2537 /*
2538 * We have to check whether the results actually do match the index,
2539 * since for non-btree indexes the EC's equality operators might not
2540 * be in the index opclass (cf ec_member_matches_indexcol).
2541 */
2543 }
2544}
References arg, ec_member_matches_indexcol(), generate_implied_equalities_for_column(), match_clauses_to_index(), and root.
Referenced by create_index_paths().
◆ match_funcclause_to_indexcol()
|
static |
Definition at line 3021 of file indxpath.c.
3025{
3027 int indexarg;
3028 ListCell *lc;
3029
3030 /*
3031 * We have no built-in intelligence about function clauses, but if there's
3032 * a planner support function, it might be able to do something. But, to
3033 * cut down on wasted planning cycles, only call the support function if
3034 * at least one argument matches the target index column.
3035 *
3036 * Note that we don't insist on the other arguments being pseudoconstants;
3037 * the support function has to check that. This is to allow cases where
3038 * only some of the other arguments need to be included in the indexqual.
3039 */
3040 indexarg = 0;
3041 foreach(lc, clause->args)
3042 {
3044
3046 {
3048 rinfo,
3049 clause->funcid,
3050 indexarg,
3051 indexcol,
3052 index);
3053 }
3054
3055 indexarg++;
3056 }
3057
3058 return NULL;
3059}
References FuncExpr::args, RestrictInfo::clause, FuncExpr::funcid, get_index_clause_from_support(), lfirst, match_index_to_operand(), and root.
Referenced by match_clause_to_indexcol().
◆ match_index_to_operand()
| bool match_index_to_operand | ( | Node * | operand, |
| int | indexcol, | ||
| IndexOptInfo * | index | ||
| ) |
Definition at line 4353 of file indxpath.c.
4356{
4357 int indkey;
4358
4359 /*
4360 * Ignore any PlaceHolderVar node contained in the operand. This is
4361 * needed to be able to apply indexscanning in cases where the operand (or
4362 * a subtree) has been wrapped in PlaceHolderVars to enforce separate
4363 * identity or as a result of outer joins.
4364 */
4365 operand = strip_noop_phvs(operand);
4366
4367 /*
4368 * Ignore any RelabelType node above the operand. This is needed to be
4369 * able to apply indexscanning in binary-compatible-operator cases.
4370 *
4371 * Note: we must handle nested RelabelType nodes here. While
4372 * eval_const_expressions() will have simplified them to at most one
4373 * layer, our prior stripping of PlaceHolderVars may have brought separate
4374 * RelabelTypes into adjacency.
4375 */
4378
4379 indkey = index->indexkeys[indexcol];
4380 if (indkey != 0)
4381 {
4382 /*
4383 * Simple index column; operand must be a matching Var.
4384 */
4387 indkey == ((Var *) operand)->varattno &&
4388 ((Var *) operand)->varnullingrels == NULL)
4389 return true;
4390 }
4391 else
4392 {
4393 /*
4394 * Index expression; find the correct expression. (This search could
4395 * be avoided, at the cost of complicating all the callers of this
4396 * routine; doesn't seem worth it.)
4397 */
4398 ListCell *indexpr_item;
4400 Node *indexkey;
4401
4404 {
4406 {
4407 if (indexpr_item == NULL)
4410 }
4411 }
4412 if (indexpr_item == NULL)
4415
4416 /*
4417 * Does it match the operand? Again, strip any relabeling.
4418 */
4421
4423 return true;
4424 }
4425
4426 return false;
4427}
References arg, elog, equal(), ERROR, i, IsA, lfirst, list_head(), lnext(), and strip_noop_phvs().
Referenced by ec_member_matches_indexcol(), expand_indexqual_rowcompare(), get_actual_variable_range(), group_similar_or_args(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_funcclause_to_indexcol(), match_opclause_to_indexcol(), match_orclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), and relation_has_unique_index_for().
◆ match_join_clauses_to_index()
|
static |
Definition at line 2480 of file indxpath.c.
2484{
2485 ListCell *lc;
2486
2487 /* Scan the rel's join clauses */
2489 {
2491
2492 /* Check if clause can be moved to this rel */
2494 continue;
2495
2496 /*
2497 * Potentially usable, so see if it matches the index or is an OR. Use
2498 * list_append_unique_ptr() here to avoid possible duplicates when
2499 * processing the same clauses with different indexes.
2500 */
2502 *joinorclauses = list_append_unique_ptr(*joinorclauses, rinfo);
2503
2505 }
2506}
References join_clause_is_movable_to(), RelOptInfo::joininfo, lfirst, list_append_unique_ptr(), match_clause_to_index(), restriction_is_or_clause(), and root.
Referenced by create_index_paths().
◆ match_opclause_to_indexcol()
|
static |
Definition at line 2902 of file indxpath.c.
2906{
2907 IndexClause *iclause;
2909 Node *leftop,
2910 *rightop;
2911 Oid expr_op;
2912 Oid expr_coll;
2913 Index index_relid;
2914 Oid opfamily;
2915 Oid idxcollation;
2916
2917 /*
2918 * Only binary operators need apply. (In theory, a planner support
2919 * function could do something with a unary operator, but it seems
2920 * unlikely to be worth the cycles to check.)
2921 */
2923 return NULL;
2924
2927 expr_op = clause->opno;
2928 expr_coll = clause->inputcollid;
2929
2930 index_relid = index->rel->relid;
2931 opfamily = index->opfamily[indexcol];
2932 idxcollation = index->indexcollations[indexcol];
2933
2934 /*
2935 * Check for clauses of the form: (indexkey operator constant) or
2936 * (constant operator indexkey). See match_clause_to_indexcol's notes
2937 * about const-ness.
2938 *
2939 * Note that we don't ask the support function about clauses that don't
2940 * have one of these forms. Again, in principle it might be possible to
2941 * do something, but it seems unlikely to be worth the cycles to check.
2942 */
2944 !bms_is_member(index_relid, rinfo->right_relids) &&
2945 !contain_volatile_functions(rightop))
2946 {
2948 op_in_opfamily(expr_op, opfamily))
2949 {
2951 iclause->rinfo = rinfo;
2952 iclause->indexquals = list_make1(rinfo);
2953 iclause->lossy = false;
2954 iclause->indexcol = indexcol;
2955 iclause->indexcols = NIL;
2956 return iclause;
2957 }
2958
2959 /*
2960 * If we didn't find a member of the index's opfamily, try the support
2961 * function for the operator's underlying function.
2962 */
2965 rinfo,
2966 clause->opfuncid,
2967 0, /* indexarg on left */
2968 indexcol,
2969 index);
2970 }
2971
2973 !bms_is_member(index_relid, rinfo->left_relids) &&
2974 !contain_volatile_functions(leftop))
2975 {
2977 {
2979
2981 op_in_opfamily(comm_op, opfamily))
2982 {
2983 RestrictInfo *commrinfo;
2984
2985 /* Build a commuted OpExpr and RestrictInfo */
2986 commrinfo = commute_restrictinfo(rinfo, comm_op);
2987
2988 /* Make an IndexClause showing that as a derived qual */
2990 iclause->rinfo = rinfo;
2991 iclause->indexquals = list_make1(commrinfo);
2992 iclause->lossy = false;
2993 iclause->indexcol = indexcol;
2994 iclause->indexcols = NIL;
2995 return iclause;
2996 }
2997 }
2998
2999 /*
3000 * If we didn't find a member of the index's opfamily, try the support
3001 * function for the operator's underlying function.
3002 */
3005 rinfo,
3006 clause->opfuncid,
3007 1, /* indexarg on right */
3008 indexcol,
3009 index);
3010 }
3011
3012 return NULL;
3013}
References OpExpr::args, bms_is_member(), RestrictInfo::clause, commute_restrictinfo(), contain_volatile_functions(), get_commutator(), get_index_clause_from_support(), IndexClause::indexcol, IndexCollMatchesExprColl, IndexClause::indexcols, IndexClause::indexquals, linitial, list_length(), list_make1, IndexClause::lossy, lsecond, makeNode, match_index_to_operand(), NIL, OidIsValid, op_in_opfamily(), OpExpr::opno, IndexClause::rinfo, root, and set_opfuncid().
Referenced by match_clause_to_indexcol().
◆ match_orclause_to_indexcol()
|
static |
Definition at line 3295 of file indxpath.c.
3299{
3302 Node *indexExpr = NULL;
3307 bool firstTime = true;
3308 bool haveNonConst = false;
3310 ScalarArrayOpExpr *saopexpr;
3311 IndexClause *iclause;
3312 ListCell *lc;
3313
3314 /* Forget it if index doesn't support SAOP clauses */
3316 return NULL;
3317
3318 /*
3319 * Try to convert a list of OR-clauses to a single SAOP expression. Each
3320 * OR entry must be in the form: (indexkey operator constant) or (constant
3321 * operator indexkey). Operators of all the entries must match. On
3322 * discovery of anything unsupported, we give up by breaking out of the
3323 * loop immediately and returning NULL.
3324 */
3325 foreach(lc, orclause->args)
3326 {
3328 OpExpr *subClause;
3329 Oid opno;
3330 Node *leftop,
3331 *rightop;
3332 Node *constExpr;
3333
3334 /* If it's not a RestrictInfo (i.e. it's a sub-AND), we can't use it */
3336 break;
3337
3338 /* Only operator clauses can match */
3340 break;
3341
3343 opno = subClause->opno;
3344
3345 /* Only binary operators can match */
3347 break;
3348
3349 /*
3350 * Check for clauses of the form: (indexkey operator constant) or
3351 * (constant operator indexkey). These tests should agree with
3352 * match_opclause_to_indexcol.
3353 */
3357 !bms_is_member(indexRelid, subRinfo->right_relids) &&
3358 !contain_volatile_functions(rightop))
3359 {
3360 indexExpr = leftop;
3361 constExpr = rightop;
3362 }
3364 !bms_is_member(indexRelid, subRinfo->left_relids) &&
3365 !contain_volatile_functions(leftop))
3366 {
3367 opno = get_commutator(opno);
3369 {
3370 /* commutator doesn't exist, we can't reverse the order */
3371 break;
3372 }
3373 indexExpr = rightop;
3374 constExpr = leftop;
3375 }
3376 else
3377 {
3378 break;
3379 }
3380
3381 /*
3382 * Save information about the operator, type, and collation for the
3383 * first matching qual. Then, check that subsequent quals match the
3384 * first.
3385 */
3386 if (firstTime)
3387 {
3388 matchOpno = opno;
3389 consttype = exprType(constExpr);
3390 arraytype = get_array_type(consttype);
3391 inputcollid = subClause->inputcollid;
3392
3393 /*
3394 * Check that the operator is presented in the opfamily and that
3395 * the expression collation matches the index collation. Also,
3396 * there must be an array type to construct an array later.
3397 */
3399 inputcollid) ||
3401 !OidIsValid(arraytype))
3402 break;
3403
3404 /*
3405 * Disallow if either type is RECORD, mainly because we can't be
3406 * positive that all the RHS expressions are the same record type.
3407 */
3409 break;
3410
3411 firstTime = false;
3412 }
3413 else
3414 {
3415 if (matchOpno != opno ||
3416 inputcollid != subClause->inputcollid ||
3417 consttype != exprType(constExpr))
3418 break;
3419 }
3420
3421 /*
3422 * The righthand inputs don't necessarily have to be plain Consts, but
3423 * make_SAOP_expr needs to know if any are not.
3424 */
3426 haveNonConst = true;
3427
3428 consts = lappend(consts, constExpr);
3429 }
3430
3431 /*
3432 * Handle failed conversion from breaking out of the loop because of an
3433 * unsupported qual. Also check that we have an indexExpr, just in case
3434 * the OR list was somehow empty (it shouldn't be). Return NULL to
3435 * indicate the conversion failed.
3436 */
3437 if (lc != NULL || indexExpr == NULL)
3438 {
3440 return NULL;
3441 }
3442
3443 /*
3444 * Build the new SAOP node. We use the indexExpr from the last OR arm;
3445 * since all the arms passed match_index_to_operand, it shouldn't matter
3446 * which one we use. But using "inputcollid" twice is a bit of a cheat:
3447 * we might end up with an array Const node that is labeled with a
3448 * collation despite its elements being of a noncollatable type. But
3449 * nothing is likely to complain about that, so we don't bother being more
3450 * accurate.
3451 */
3452 saopexpr = make_SAOP_expr(matchOpno, indexExpr, consttype, inputcollid,
3453 inputcollid, consts, haveNonConst);
3454 Assert(saopexpr != NULL);
3455
3456 /*
3457 * Finally, build an IndexClause based on the SAOP node. It's not lossy.
3458 */
3460 iclause->rinfo = rinfo;
3462 (Expr *) saopexpr));
3464 iclause->indexcol = indexcol;
3466 return iclause;
3467}
References OpExpr::args, BoolExpr::args, Assert, bms_is_member(), RestrictInfo::clause, contain_volatile_functions(), exprType(), get_array_type(), get_commutator(), IndexClause::indexcol, IndexCollMatchesExprColl, IndexClause::indexcols, IndexClause::indexquals, InvalidOid, IsA, lappend(), lfirst, linitial, list_free(), list_length(), list_make1, IndexClause::lossy, lsecond, make_SAOP_expr(), make_simple_restrictinfo, makeNode, match_index_to_operand(), NIL, OidIsValid, op_in_opfamily(), OpExpr::opno, IndexClause::rinfo, and root.
Referenced by match_clause_to_indexcol().
◆ match_pathkeys_to_index()
|
static |
Definition at line 3715 of file indxpath.c.
3718{
3719 ListCell *lc1;
3720
3722 *clause_columns_p = NIL;
3723
3724 /* Only indexes with the amcanorderbyop property are interesting here */
3726 return;
3727
3728 foreach(lc1, pathkeys)
3729 {
3731 bool found = false;
3732 EquivalenceMemberIterator it;
3733 EquivalenceMember *member;
3734
3735
3736 /* Pathkey must request default sort order for the target opfamily */
3738 return;
3739
3740 /* If eclass is volatile, no hope of using an indexscan */
3741 if (pathkey->pk_eclass->ec_has_volatile)
3742 return;
3743
3744 /*
3745 * Try to match eclass member expression(s) to index. Note that child
3746 * EC members are considered, but only when they belong to the target
3747 * relation. (Unlike regular members, the same expression could be a
3748 * child member of more than one EC. Therefore, the same index could
3749 * be considered to match more than one pathkey list, which is OK
3750 * here. See also get_eclass_for_sort_expr.)
3751 */
3752 setup_eclass_member_iterator(&it, pathkey->pk_eclass,
3753 index->rel->relids);
3755 {
3756 int indexcol;
3757
3758 /* No possibility of match if it references other relations */
3760 continue;
3761
3762 /*
3763 * We allow any column of the index to match each pathkey; they
3764 * don't have to match left-to-right as you might expect. This is
3765 * correct for GiST, and it doesn't matter for SP-GiST because
3766 * that doesn't handle multiple columns anyway, and no other
3767 * existing AMs support amcanorderbyop. We might need different
3768 * logic in future for other implementations.
3769 */
3771 {
3772 Expr *expr;
3773
3775 indexcol,
3776 member->em_expr,
3777 pathkey->pk_opfamily);
3778 if (expr)
3779 {
3780 *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
3781 *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
3782 found = true;
3783 break;
3784 }
3785 }
3786
3787 if (found) /* don't want to look at remaining members */
3788 break;
3789 }
3790
3791 /*
3792 * Return the matches found so far when this pathkey couldn't be
3793 * matched to the index.
3794 */
3795 if (!found)
3796 return;
3797 }
3798}
References bms_equal(), COMPARE_LT, eclass_member_iterator_next(), EquivalenceMember::em_expr, EquivalenceMember::em_relids, lappend(), lappend_int(), lfirst, match_clause_to_ordering_op(), NIL, PathKey::pk_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, and setup_eclass_member_iterator().
Referenced by build_index_paths().
◆ match_restriction_clauses_to_index()
|
static |
Definition at line 2464 of file indxpath.c.
2467{
2468 /* We can ignore clauses that are implied by the index predicate */
2470}
References match_clauses_to_index(), and root.
Referenced by create_index_paths().
◆ match_rowcompare_to_indexcol()
|
static |
Definition at line 3201 of file indxpath.c.
3205{
3207 Index index_relid;
3208 Oid opfamily;
3209 Oid idxcollation;
3210 Node *leftop,
3211 *rightop;
3212 bool var_on_left;
3213 Oid expr_op;
3214 Oid expr_coll;
3215
3216 /* Forget it if we're not dealing with a btree index */
3218 return NULL;
3219
3220 index_relid = index->rel->relid;
3221 opfamily = index->opfamily[indexcol];
3222 idxcollation = index->indexcollations[indexcol];
3223
3224 /*
3225 * We could do the matching on the basis of insisting that the opfamily
3226 * shown in the RowCompareExpr be the same as the index column's opfamily,
3227 * but that could fail in the presence of reverse-sort opfamilies: it'd be
3228 * a matter of chance whether RowCompareExpr had picked the forward or
3229 * reverse-sort family. So look only at the operator, and match if it is
3230 * a member of the index's opfamily (after commutation, if the indexkey is
3231 * on the right). We'll worry later about whether any additional
3232 * operators are matchable to the index.
3233 */
3236 expr_op = linitial_oid(clause->opnos);
3237 expr_coll = linitial_oid(clause->inputcollids);
3238
3239 /* Collations must match, if relevant */
3241 return NULL;
3242
3243 /*
3244 * These syntactic tests are the same as in match_opclause_to_indexcol()
3245 */
3248 !contain_volatile_functions(rightop))
3249 {
3250 /* OK, indexkey is on left */
3251 var_on_left = true;
3252 }
3255 !contain_volatile_functions(leftop))
3256 {
3257 /* indexkey is on right, so commute the operator */
3258 expr_op = get_commutator(expr_op);
3260 return NULL;
3261 var_on_left = false;
3262 }
3263 else
3264 return NULL;
3265
3266 /* We're good if the operator is the right type of opfamily member */
3268 {
3274 rinfo,
3275 indexcol,
3276 index,
3277 expr_op,
3278 var_on_left);
3279 }
3280
3281 return NULL;
3282}
References bms_is_member(), BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, RestrictInfo::clause, contain_volatile_functions(), expand_indexqual_rowcompare(), get_commutator(), get_op_opfamily_strategy(), IndexCollMatchesExprColl, InvalidOid, RowCompareExpr::largs, linitial, linitial_oid, match_index_to_operand(), pull_varnos(), RowCompareExpr::rargs, and root.
Referenced by match_clause_to_indexcol().
◆ match_saopclause_to_indexcol()
|
static |
Definition at line 3133 of file indxpath.c.
3137{
3139 Node *leftop,
3140 *rightop;
3141 Relids right_relids;
3142 Oid expr_op;
3143 Oid expr_coll;
3144 Index index_relid;
3145 Oid opfamily;
3146 Oid idxcollation;
3147
3148 /* We only accept ANY clauses, not ALL */
3149 if (!saop->useOr)
3150 return NULL;
3154 expr_op = saop->opno;
3155 expr_coll = saop->inputcollid;
3156
3157 index_relid = index->rel->relid;
3158 opfamily = index->opfamily[indexcol];
3159 idxcollation = index->indexcollations[indexcol];
3160
3161 /*
3162 * We must have indexkey on the left and a pseudo-constant array argument.
3163 */
3165 !bms_is_member(index_relid, right_relids) &&
3166 !contain_volatile_functions(rightop))
3167 {
3169 op_in_opfamily(expr_op, opfamily))
3170 {
3172
3173 iclause->rinfo = rinfo;
3176 iclause->indexcol = indexcol;
3178 return iclause;
3179 }
3180
3181 /*
3182 * We do not currently ask support functions about ScalarArrayOpExprs,
3183 * though in principle we could.
3184 */
3185 }
3186
3187 return NULL;
3188}
References ScalarArrayOpExpr::args, bms_is_member(), RestrictInfo::clause, contain_volatile_functions(), IndexClause::indexcol, IndexCollMatchesExprColl, IndexClause::indexcols, IndexClause::indexquals, linitial, list_make1, IndexClause::lossy, lsecond, makeNode, match_index_to_operand(), NIL, op_in_opfamily(), ScalarArrayOpExpr::opno, pull_varnos(), IndexClause::rinfo, root, and ScalarArrayOpExpr::useOr.
Referenced by match_clause_to_indexcol().
◆ or_arg_index_match_cmp()
|
static |
Definition at line 1199 of file indxpath.c.
1200{
1203
1205 return -1;
1207 return 1;
1208
1210 return -1;
1212 return 1;
1213
1215 return -1;
1217 return 1;
1218
1220 return -1;
1222 return 1;
1223
1225 return -1;
1227 return 1;
1228
1229 return 0;
1230}
References a, OrArgIndexMatch::argindex, b, OrArgIndexMatch::colnum, OrArgIndexMatch::indexnum, OrArgIndexMatch::inputcollid, and OrArgIndexMatch::opno.
Referenced by group_similar_or_args().
◆ or_arg_index_match_cmp_group()
|
static |
Definition at line 1237 of file indxpath.c.
1238{
1241
1243 return -1;
1245 return 1;
1246
1248 return -1;
1250 return 1;
1251
1252 return 0;
1253}
References a, OrArgIndexMatch::argindex, b, and OrArgIndexMatch::groupindex.
Referenced by group_similar_or_args().
◆ path_usage_comparator()
|
static |
Definition at line 1989 of file indxpath.c.
1990{
1993 Cost acost;
1994 Cost bcost;
1995 Selectivity aselec;
1996 Selectivity bselec;
1997
2000
2001 /*
2002 * If costs are the same, sort by selectivity.
2003 */
2004 if (acost < bcost)
2005 return -1;
2006 if (acost > bcost)
2007 return 1;
2008
2009 if (aselec < bselec)
2010 return -1;
2011 if (aselec > bselec)
2012 return 1;
2013
2014 return 0;
2015}
References a, b, cost_bitmap_tree_node(), and PathClauseUsage::path.
Referenced by choose_bitmap_and().
◆ relation_has_unique_index_for()
| bool relation_has_unique_index_for | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | restrictlist, | ||
| List ** | extra_clauses | ||
| ) |
Definition at line 4144 of file indxpath.c.
4146{
4147 ListCell *ic;
4148
4149 /* Short-circuit if no indexes... */
4151 return false;
4152
4153 /*
4154 * Examine the rel's restriction clauses for usable var = const clauses
4155 * that we can add to the restrictlist.
4156 */
4158 {
4160
4161 /*
4162 * Note: can_join won't be set for a restriction clause, but
4163 * mergeopfamilies will be if it has a mergejoinable operator and
4164 * doesn't contain volatile functions.
4165 */
4167 continue; /* not mergejoinable */
4168
4169 /*
4170 * The clause certainly doesn't refer to anything but the given rel.
4171 * If either side is pseudoconstant then we can use it.
4172 */
4174 {
4175 /* righthand side is inner */
4176 restrictinfo->outer_is_left = true;
4177 }
4179 {
4180 /* lefthand side is inner */
4181 restrictinfo->outer_is_left = false;
4182 }
4183 else
4184 continue;
4185
4186 /* OK, add to list */
4187 restrictlist = lappend(restrictlist, restrictinfo);
4188 }
4189
4190 /* Short-circuit the easy case */
4192 return false;
4193
4194 /* Examine each index of the relation ... */
4196 {
4200
4201 /*
4202 * If the index is not unique, or not immediately enforced, or if it's
4203 * a partial index, it's useless here. We're unable to make use of
4204 * predOK partial unique indexes due to the fact that
4205 * check_index_predicates() also makes use of join predicates to
4206 * determine if the partial index is usable. Here we need proofs that
4207 * hold true before any joins are evaluated.
4208 */
4210 continue;
4211
4212 /*
4213 * Try to find each index column in the list of conditions. This is
4214 * O(N^2) or worse, but we expect all the lists to be short.
4215 */
4217 {
4218 ListCell *lc;
4219
4220 foreach(lc, restrictlist)
4221 {
4223 Node *rexpr;
4224
4225 /*
4226 * The condition's equality operator must be a member of the
4227 * index opfamily, else it is not asserting the right kind of
4228 * equality behavior for this index. We check this first
4229 * since it's probably cheaper than match_index_to_operand().
4230 */
4232 continue;
4233
4234 /*
4235 * XXX at some point we may need to check collations here too.
4236 * For the moment we assume all collations reduce to the same
4237 * notion of equality.
4238 */
4239
4240 /* OK, see if the condition operand matches the index key */
4241 if (rinfo->outer_is_left)
4243 else
4245
4247 {
4249 {
4250 MemoryContext oldMemCtx =
4252
4253 /*
4254 * Add filter clause into a list allowing caller to
4255 * know if uniqueness have made not only by join
4256 * clauses.
4257 */
4259 bms_is_empty(rinfo->right_relids));
4260 if (extra_clauses)
4261 exprs = lappend(exprs, rinfo);
4262 MemoryContextSwitchTo(oldMemCtx);
4263 }
4264
4265 break; /* found a match; column is unique */
4266 }
4267 }
4268
4269 if (lc == NULL)
4270 break; /* no match; this index doesn't help us */
4271 }
4272
4273 /* Matched all key columns of this index? */
4275 {
4276 if (extra_clauses)
4277 *extra_clauses = exprs;
4278 return true;
4279 }
4280 }
4281
4282 return false;
4283}
References Assert, RelOptInfo::baserestrictinfo, bms_is_empty, bms_membership(), BMS_SINGLETON, RestrictInfo::clause, get_leftop(), get_rightop(), RelOptInfo::indexlist, lappend(), lfirst, list_member_oid(), match_index_to_operand(), MemoryContextSwitchTo(), NIL, and root.
Referenced by rel_is_distinct_for().
