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