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