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