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