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