1
/*-------------------------------------------------------------------------
4
* Routines to determine which indices are usable for scanning a
5
* given relation, and create IndexPaths accordingly.
7
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
8
* Portions Copyright (c) 1994, Regents of the University of California
12
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.167.4.2 2005-04-20 21:48:12 tgl Exp $
14
*-------------------------------------------------------------------------
20
#include "access/nbtree.h"
21
#include "catalog/pg_amop.h"
22
#include "catalog/pg_namespace.h"
23
#include "catalog/pg_opclass.h"
24
#include "catalog/pg_operator.h"
25
#include "catalog/pg_proc.h"
26
#include "catalog/pg_type.h"
27
#include "executor/executor.h"
28
#include "nodes/makefuncs.h"
29
#include "optimizer/clauses.h"
30
#include "optimizer/cost.h"
31
#include "optimizer/pathnode.h"
32
#include "optimizer/paths.h"
33
#include "optimizer/restrictinfo.h"
34
#include "optimizer/var.h"
35
#include "parser/parse_expr.h"
36
#include "rewrite/rewriteManip.h"
37
#include "utils/builtins.h"
38
#include "utils/catcache.h"
39
#include "utils/lsyscache.h"
40
#include "utils/pg_locale.h"
41
#include "utils/selfuncs.h"
42
#include "utils/syscache.h"
46
* DoneMatchingIndexKeys() - MACRO
48
#define DoneMatchingIndexKeys(classes) (classes[0] == InvalidOid)
50
#define is_indexable_operator(clause,opclass,indexkey_on_left) \
51
(indexable_operator(clause,opclass,indexkey_on_left) != InvalidOid)
54
static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index);
55
static List *group_clauses_by_indexkey_for_join(Query *root,
56
RelOptInfo *rel, IndexOptInfo *index,
58
JoinType jointype, bool isouterjoin);
59
static bool match_clause_to_indexcol(RelOptInfo *rel, IndexOptInfo *index,
60
int indexcol, Oid opclass,
62
static bool match_join_clause_to_indexcol(RelOptInfo *rel, IndexOptInfo *index,
63
int indexcol, Oid opclass,
65
static Oid indexable_operator(Expr *clause, Oid opclass,
66
bool indexkey_on_left);
67
static bool pred_test_restrict_list(Expr *predicate, List *restrictinfo_list);
68
static bool pred_test_recurse_restrict(Expr *predicate, Node *clause);
69
static bool pred_test_recurse_pred(Expr *predicate, Node *clause);
70
static bool pred_test_simple_clause(Expr *predicate, Node *clause);
71
static Relids indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index);
72
static Path *make_innerjoin_index_path(Query *root,
73
RelOptInfo *rel, IndexOptInfo *index,
75
static bool match_index_to_operand(Node *operand, int indexcol,
76
RelOptInfo *rel, IndexOptInfo *index);
77
static bool match_special_index_operator(Expr *clause, Oid opclass,
78
bool indexkey_on_left);
79
static List *expand_indexqual_condition(RestrictInfo *rinfo, Oid opclass);
80
static List *prefix_quals(Node *leftop, Oid opclass,
81
Const *prefix, Pattern_Prefix_Status pstatus);
82
static List *network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass,
84
static Datum string_to_datum(const char *str, Oid datatype);
85
static Const *string_to_const(const char *str, Oid datatype);
89
* create_index_paths()
90
* Generate all interesting index paths for the given relation.
91
* Candidate paths are added to the rel's pathlist (using add_path).
93
* To be considered for an index scan, an index must match one or more
94
* restriction clauses or join clauses from the query's qual condition,
95
* or match the query's ORDER BY condition.
97
* There are two basic kinds of index scans. A "plain" index scan uses
98
* only restriction clauses (possibly none at all) in its indexqual,
99
* so it can be applied in any context. An "innerjoin" index scan uses
100
* join clauses (plus restriction clauses, if available) in its indexqual.
101
* Therefore it can only be used as the inner relation of a nestloop
102
* join against an outer rel that includes all the other rels mentioned
103
* in its join clauses. In that context, values for the other rels'
104
* attributes are available and fixed during any one scan of the indexpath.
106
* An IndexPath is generated and submitted to add_path() for each plain index
107
* scan this routine deems potentially interesting for the current query.
109
* We also determine the set of other relids that participate in join
110
* clauses that could be used with each index. The actually best innerjoin
111
* path will be generated for each outer relation later on, but knowing the
112
* set of potential otherrels allows us to identify equivalent outer relations
113
* and avoid repeated computation.
115
* 'rel' is the relation for which we want to generate index paths
117
* Note: check_partial_indexes() must have been run previously.
120
create_index_paths(Query *root, RelOptInfo *rel)
122
Relids all_join_outerrelids = NULL;
125
foreach(ilist, rel->indexlist)
127
IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
128
List *restrictclauses;
129
List *index_pathkeys;
130
List *useful_pathkeys;
131
bool index_is_ordered;
132
Relids join_outerrelids;
134
/* Ignore partial indexes that do not match the query */
135
if (index->indpred != NIL && !index->predOK)
139
* 1. Match the index against non-OR restriction clauses. (OR
140
* clauses will be considered later by orindxpath.c.)
142
restrictclauses = group_clauses_by_indexkey(rel, index);
145
* 2. Compute pathkeys describing index's ordering, if any, then
146
* see how many of them are actually useful for this query.
148
index_is_ordered = OidIsValid(index->ordering[0]);
149
if (index_is_ordered)
151
index_pathkeys = build_index_pathkeys(root, rel, index,
152
ForwardScanDirection);
153
useful_pathkeys = truncate_useless_pathkeys(root, rel,
157
useful_pathkeys = NIL;
160
* 3. Generate an indexscan path if there are relevant restriction
161
* clauses OR the index ordering is potentially useful for later
162
* merging or final output ordering.
164
* If there is a predicate, consider it anyway since the index
165
* predicate has already been found to match the query. The
166
* selectivity of the predicate might alone make the index useful.
168
* Note: not all index AMs support scans with no restriction clauses.
169
* We assume here that the AM does so if and only if it supports
170
* ordered scans. (It would probably be better if there were a
171
* specific flag for this in pg_am, but there's not.)
173
if (restrictclauses != NIL ||
174
useful_pathkeys != NIL ||
175
(index->indpred != NIL && index_is_ordered))
176
add_path(rel, (Path *)
177
create_index_path(root, rel, index,
181
ForwardScanDirection :
182
NoMovementScanDirection));
185
* 4. If the index is ordered, a backwards scan might be
186
* interesting. Currently this is only possible for a DESC query
189
if (index_is_ordered)
191
index_pathkeys = build_index_pathkeys(root, rel, index,
192
BackwardScanDirection);
193
useful_pathkeys = truncate_useless_pathkeys(root, rel,
195
if (useful_pathkeys != NIL)
196
add_path(rel, (Path *)
197
create_index_path(root, rel, index,
200
BackwardScanDirection));
204
* 5. Examine join clauses to see which ones are potentially
205
* usable with this index, and generate the set of all other
206
* relids that participate in such join clauses. We'll use this
207
* set later to recognize outer rels that are equivalent for
208
* joining purposes. We compute both per-index and
209
* overall-for-relation sets.
211
join_outerrelids = indexable_outerrelids(rel, index);
212
index->outer_relids = join_outerrelids;
213
all_join_outerrelids = bms_add_members(all_join_outerrelids,
217
rel->index_outer_relids = all_join_outerrelids;
221
/****************************************************************************
222
* ---- ROUTINES TO CHECK RESTRICTIONS ----
223
****************************************************************************/
227
* group_clauses_by_indexkey
228
* Find restriction clauses that can be used with an index.
230
* 'rel' is the node of the relation itself.
231
* 'index' is a index on 'rel'.
233
* Returns a list of sublists of RestrictInfo nodes for clauses that can be
234
* used with this index. Each sublist contains clauses that can be used
235
* with one index key (in no particular order); the top list is ordered by
236
* index key. (This is depended on by expand_indexqual_conditions().)
238
* Note that in a multi-key index, we stop if we find a key that cannot be
239
* used with any clause. For example, given an index on (A,B,C), we might
240
* return ((C1 C2) (C3 C4)) if we find that clauses C1 and C2 use column A,
241
* clauses C3 and C4 use column B, and no clauses use column C. But if
242
* no clauses match B we will return ((C1 C2)), whether or not there are
243
* clauses matching column C, because the executor couldn't use them anyway.
244
* Therefore, there are no empty sublists in the result.
247
group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index)
249
List *clausegroup_list = NIL;
250
List *restrictinfo_list = rel->baserestrictinfo;
252
Oid *classes = index->classlist;
254
if (restrictinfo_list == NIL)
259
Oid curClass = classes[0];
260
List *clausegroup = NIL;
263
foreach(l, restrictinfo_list)
265
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
267
if (match_clause_to_indexcol(rel,
272
clausegroup = lappend(clausegroup, rinfo);
276
* If no clauses match this key, we're done; we don't want to look
277
* at keys to its right.
279
if (clausegroup == NIL)
282
clausegroup_list = lappend(clausegroup_list, clausegroup);
287
} while (!DoneMatchingIndexKeys(classes));
289
return clausegroup_list;
293
* group_clauses_by_indexkey_for_join
294
* Generate a list of sublists of clauses that can be used with an index
295
* to scan the inner side of a nestloop join.
297
* This is much like group_clauses_by_indexkey(), but we consider both
298
* join and restriction clauses. Any joinclause that uses only otherrels
299
* in the specified outer_relids is fair game. But there must be at least
300
* one such joinclause in the final list, otherwise we return NIL indicating
301
* that this index isn't interesting as an inner indexscan. (A scan using
302
* only restriction clauses shouldn't be created here, because a regular Path
303
* will already have been generated for it.)
306
group_clauses_by_indexkey_for_join(Query *root,
307
RelOptInfo *rel, IndexOptInfo *index,
309
JoinType jointype, bool isouterjoin)
311
List *clausegroup_list = NIL;
314
Oid *classes = index->classlist;
318
Oid curClass = classes[0];
319
List *clausegroup = NIL;
324
* We can always use plain restriction clauses for the rel. We
325
* scan these first because we want them first in the clausegroup
326
* list for the convenience of remove_redundant_join_clauses,
327
* which can never remove non-join clauses and hence won't be able
328
* to get rid of a non-join clause if it appears after a join
329
* clause it is redundant with.
331
foreach(l, rel->baserestrictinfo)
333
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
335
/* Can't use pushed-down clauses in outer join */
336
if (isouterjoin && rinfo->is_pushed_down)
339
if (match_clause_to_indexcol(rel,
344
clausegroup = lappend(clausegroup, rinfo);
347
/* found anything in base restrict list? */
348
numsources = (clausegroup != NIL) ? 1 : 0;
350
/* Look for joinclauses that are usable with given outer_relids */
351
foreach(l, rel->joininfo)
353
JoinInfo *joininfo = (JoinInfo *) lfirst(l);
354
bool jfoundhere = false;
357
if (!bms_is_subset(joininfo->unjoined_relids, outer_relids))
360
foreach(j, joininfo->jinfo_restrictinfo)
362
RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
364
/* Can't use pushed-down clauses in outer join */
365
if (isouterjoin && rinfo->is_pushed_down)
368
if (match_join_clause_to_indexcol(rel,
374
clausegroup = lappend(clausegroup, rinfo);
386
* If we found clauses in more than one list, we may now have
387
* clauses that are known redundant. Get rid of 'em.
391
clausegroup = remove_redundant_join_clauses(root,
397
* If no clauses match this key, we're done; we don't want to look
398
* at keys to its right.
400
if (clausegroup == NIL)
403
clausegroup_list = lappend(clausegroup_list, clausegroup);
408
} while (!DoneMatchingIndexKeys(classes));
410
/* if no join clause was matched then forget it, per comments above */
414
return clausegroup_list;
419
* group_clauses_by_indexkey_for_or
420
* Generate a list of sublists of clauses that can be used with an index
421
* to find rows matching an OR subclause.
423
* This is essentially just like group_clauses_by_indexkey() except that
424
* we can use the given clause (or any AND subclauses of it) as well as
425
* top-level restriction clauses of the relation. Furthermore, we demand
426
* that at least one such use be made, otherwise we fail and return NIL.
427
* (Any path we made without such a use would be redundant with non-OR
428
* indexscans. Compare also group_clauses_by_indexkey_for_join.)
430
* XXX When we generate an indexqual list that uses both the OR subclause
431
* and top-level restriction clauses, we end up with a slightly inefficient
432
* plan because create_indexscan_plan is not very bright about figuring out
433
* which restriction clauses are implied by the generated indexqual condition.
434
* Currently we'll end up rechecking both the OR clause and the top-level
435
* restriction clause as qpquals. FIXME someday.
438
group_clauses_by_indexkey_for_or(RelOptInfo *rel,
442
List *clausegroup_list = NIL;
443
bool matched = false;
445
Oid *classes = index->classlist;
449
Oid curClass = classes[0];
450
List *clausegroup = NIL;
453
/* Try to match the OR subclause to the index key */
454
if (IsA(orsubclause, RestrictInfo))
456
if (match_clause_to_indexcol(rel, index,
458
(RestrictInfo *) orsubclause))
460
clausegroup = lappend(clausegroup, orsubclause);
464
else if (and_clause((Node *) orsubclause))
466
foreach(item, ((BoolExpr *) orsubclause)->args)
468
RestrictInfo *subsubclause = (RestrictInfo *) lfirst(item);
470
if (IsA(subsubclause, RestrictInfo) &&
471
match_clause_to_indexcol(rel, index,
475
clausegroup = lappend(clausegroup, subsubclause);
482
* If we found no clauses for this indexkey in the OR subclause
483
* itself, try looking in the rel's top-level restriction list.
485
* XXX should we always search the top-level list? Slower but could
486
* sometimes yield a better plan.
488
if (clausegroup == NIL)
490
foreach(item, rel->baserestrictinfo)
492
RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
494
if (match_clause_to_indexcol(rel, index,
497
clausegroup = lappend(clausegroup, rinfo);
502
* If still no clauses match this key, we're done; we don't want
503
* to look at keys to its right.
505
if (clausegroup == NIL)
508
clausegroup_list = lappend(clausegroup_list, clausegroup);
512
} while (!DoneMatchingIndexKeys(classes));
514
/* if OR clause was not used then forget it, per comments above */
518
return clausegroup_list;
523
* match_clause_to_indexcol()
524
* Determines whether a restriction clause matches a column of an index.
526
* To match, the clause:
528
* (1) must be in the form (indexkey op const) or (const op indexkey);
530
* (2) must contain an operator which is in the same class as the index
531
* operator for this column, or is a "special" operator as recognized
532
* by match_special_index_operator().
534
* Presently, the executor can only deal with indexquals that have the
535
* indexkey on the left, so we can only use clauses that have the indexkey
536
* on the right if we can commute the clause to put the key on the left.
537
* We do not actually do the commuting here, but we check whether a
538
* suitable commutator operator is available.
540
* 'rel' is the relation of interest.
541
* 'index' is an index on 'rel'.
542
* 'indexcol' is a column number of 'index' (counting from 0).
543
* 'opclass' is the corresponding operator class.
544
* 'rinfo' is the clause to be tested (as a RestrictInfo node).
546
* Returns true if the clause can be used with this index key.
548
* NOTE: returns false if clause is an OR or AND clause; it is the
549
* responsibility of higher-level routines to cope with those.
552
match_clause_to_indexcol(RelOptInfo *rel,
558
Expr *clause = rinfo->clause;
562
/* Clause must be a binary opclause. */
563
if (!is_opclause(clause))
565
leftop = get_leftop(clause);
566
rightop = get_rightop(clause);
567
if (!leftop || !rightop)
571
* Check for clauses of the form: (indexkey operator constant) or
572
* (constant operator indexkey). Anything that is a "pseudo constant"
573
* expression will do.
575
if (match_index_to_operand(leftop, indexcol, rel, index) &&
576
is_pseudo_constant_clause_relids(rightop, rinfo->right_relids))
578
if (is_indexable_operator(clause, opclass, true))
582
* If we didn't find a member of the index's opclass, see whether
583
* it is a "special" indexable operator.
585
if (match_special_index_operator(clause, opclass, true))
590
if (match_index_to_operand(rightop, indexcol, rel, index) &&
591
is_pseudo_constant_clause_relids(leftop, rinfo->left_relids))
593
if (is_indexable_operator(clause, opclass, false))
597
* If we didn't find a member of the index's opclass, see whether
598
* it is a "special" indexable operator.
600
if (match_special_index_operator(clause, opclass, false))
609
* match_join_clause_to_indexcol()
610
* Determines whether a join clause matches a column of an index.
612
* To match, the clause:
614
* (1) must be in the form (indexkey op others) or (others op indexkey),
615
* where others is an expression involving only vars of the other
617
* (2) must contain an operator which is in the same class as the index
618
* operator for this column, or is a "special" operator as recognized
619
* by match_special_index_operator().
621
* As above, we must be able to commute the clause to put the indexkey
624
* Note that we already know that the clause as a whole uses vars from
625
* the interesting set of relations. But we need to defend against
626
* expressions like (a.f1 OP (b.f2 OP a.f3)); that's not processable by
627
* an indexscan nestloop join, whereas (a.f1 OP (b.f2 OP c.f3)) is.
629
* 'rel' is the relation of interest.
630
* 'index' is an index on 'rel'.
631
* 'indexcol' is a column number of 'index' (counting from 0).
632
* 'opclass' is the corresponding operator class.
633
* 'rinfo' is the clause to be tested (as a RestrictInfo node).
635
* Returns true if the clause can be used with this index key.
637
* NOTE: returns false if clause is an OR or AND clause; it is the
638
* responsibility of higher-level routines to cope with those.
641
match_join_clause_to_indexcol(RelOptInfo *rel,
647
Expr *clause = rinfo->clause;
651
/* Clause must be a binary opclause. */
652
if (!is_opclause(clause))
654
leftop = get_leftop(clause);
655
rightop = get_rightop(clause);
656
if (!leftop || !rightop)
660
* Check for an indexqual that could be handled by a nestloop join. We
661
* need the index key to be compared against an expression that uses
662
* none of the indexed relation's vars and contains no volatile
665
if (match_index_to_operand(leftop, indexcol, rel, index))
667
Relids othervarnos = rinfo->right_relids;
671
!bms_overlap(rel->relids, othervarnos) &&
672
!contain_volatile_functions(rightop) &&
673
is_indexable_operator(clause, opclass, true);
677
if (match_index_to_operand(rightop, indexcol, rel, index))
679
Relids othervarnos = rinfo->left_relids;
683
!bms_overlap(rel->relids, othervarnos) &&
684
!contain_volatile_functions(leftop) &&
685
is_indexable_operator(clause, opclass, false);
694
* Does a binary opclause contain an operator matching the index opclass?
696
* If the indexkey is on the right, what we actually want to know
697
* is whether the operator has a commutator operator that matches
698
* the index's opclass.
700
* Returns the OID of the matching operator, or InvalidOid if no match.
701
* (Formerly, this routine might return a binary-compatible operator
702
* rather than the original one, but that kluge is history.)
705
indexable_operator(Expr *clause, Oid opclass, bool indexkey_on_left)
707
Oid expr_op = ((OpExpr *) clause)->opno;
710
/* Get the commuted operator if necessary */
711
if (indexkey_on_left)
712
commuted_op = expr_op;
714
commuted_op = get_commutator(expr_op);
715
if (commuted_op == InvalidOid)
718
/* OK if the (commuted) operator is a member of the index's opclass */
719
if (op_in_opclass(commuted_op, opclass))
725
/****************************************************************************
726
* ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ----
727
****************************************************************************/
730
* check_partial_indexes
731
* Check each partial index of the relation, and mark it predOK or not
732
* depending on whether the predicate is satisfied for this query.
735
check_partial_indexes(Query *root, RelOptInfo *rel)
737
List *restrictinfo_list = rel->baserestrictinfo;
740
foreach(ilist, rel->indexlist)
742
IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
745
* If this is a partial index, we can only use it if it passes the
748
if (index->indpred == NIL)
749
continue; /* ignore non-partial indexes */
751
index->predOK = pred_test(index->indpred, restrictinfo_list);
757
* Does the "predicate inclusion test" for partial indexes.
759
* Recursively checks whether the clauses in restrictinfo_list imply
760
* that the given predicate is true.
762
* This routine (together with the routines it calls) iterates over
763
* ANDs in the predicate first, then breaks down the restriction list
764
* to its constituent AND/OR elements, and iterates over ORs
765
* in the predicate last. This order is important to make the test
766
* succeed whenever possible. --Nels, Jan '93
768
* For example, a restriction (a OR b) certainly implies a predicate
769
* (a OR b OR c), but no one element of the predicate is individually
770
* implied by the restriction. By expanding the predicate ORs last
771
* we are able to prove that the whole predicate is implied by each arm
772
* of the restriction. Conversely consider predicate (a AND b) with
773
* restriction (a AND b AND c). This should be implied but we will
774
* fail to prove it if we dissect the restriction first.
776
* The top-level List structure of each list corresponds to an AND list.
777
* We assume that canonicalize_qual() has been applied and so there
778
* are no explicit ANDs immediately below the top-level List structure.
779
* (If this is not true we might fail to prove an implication that is
780
* valid, but no worse consequences will ensue.)
783
pred_test(List *predicate_list, List *restrictinfo_list)
788
* Note: if Postgres tried to optimize queries by forming equivalence
789
* classes over equi-joined attributes (i.e., if it recognized that a
790
* qualification such as "where a.b=c.d and a.b=5" could make use of
791
* an index on c.d), then we could use that equivalence class info
792
* here with joininfo_list to do more complete tests for the usability
793
* of a partial index. For now, the test only uses restriction
794
* clauses (those in restrictinfo_list). --Nels, Dec '92
796
* XXX as of 7.1, equivalence class info *is* available. Consider
797
* improving this code as foreseen by Nels.
800
if (predicate_list == NIL)
801
return true; /* no predicate: the index is usable */
802
if (restrictinfo_list == NIL)
803
return false; /* no restriction clauses: the test must
806
/* Take care of the AND semantics of the top-level predicate list */
807
foreach(pred, predicate_list)
810
* if any clause is not implied, the whole predicate is not
813
if (!pred_test_restrict_list(lfirst(pred), restrictinfo_list))
821
* pred_test_restrict_list
822
* Does the "predicate inclusion test" for one AND clause of a predicate
823
* expression. Here we take care of the AND semantics of the top-level
827
pred_test_restrict_list(Expr *predicate, List *restrictinfo_list)
831
foreach(item, restrictinfo_list)
833
/* if any clause implies the predicate, return true */
834
if (pred_test_recurse_restrict(predicate,
835
(Node *) lfirst(item)))
843
* pred_test_recurse_restrict
844
* Does the "predicate inclusion test" for one AND clause of a predicate
845
* expression. Here we recursively deal with the possibility that the
846
* restriction-list element is itself an AND or OR structure; also,
847
* we strip off RestrictInfo nodes to find bare qualifier expressions.
850
pred_test_recurse_restrict(Expr *predicate, Node *clause)
855
Assert(clause != NULL);
856
if (IsA(clause, RestrictInfo))
858
RestrictInfo *restrictinfo = (RestrictInfo *) clause;
860
return pred_test_recurse_restrict(predicate,
861
(Node *) restrictinfo->clause);
863
else if (or_clause(clause))
865
items = ((BoolExpr *) clause)->args;
868
/* if any OR item doesn't imply the predicate, clause doesn't */
869
if (!pred_test_recurse_restrict(predicate, lfirst(item)))
874
else if (and_clause(clause))
876
items = ((BoolExpr *) clause)->args;
880
* if any AND item implies the predicate, the whole clause
883
if (pred_test_recurse_restrict(predicate, lfirst(item)))
889
return pred_test_recurse_pred(predicate, clause);
894
* pred_test_recurse_pred
895
* Does the "predicate inclusion test" for one conjunct of a predicate
896
* expression. Here we recursively deal with the possibility that the
897
* predicate conjunct is itself an AND or OR structure.
900
pred_test_recurse_pred(Expr *predicate, Node *clause)
905
Assert(predicate != NULL);
906
if (or_clause((Node *) predicate))
908
items = ((BoolExpr *) predicate)->args;
911
/* if any item is implied, the whole predicate is implied */
912
if (pred_test_recurse_pred(lfirst(item), clause))
917
else if (and_clause((Node *) predicate))
919
items = ((BoolExpr *) predicate)->args;
923
* if any item is not implied, the whole predicate is not
926
if (!pred_test_recurse_pred(lfirst(item), clause))
932
return pred_test_simple_clause(predicate, clause);
937
* Define an "operator implication table" for btree operators ("strategies").
939
* The strategy numbers defined by btree indexes (see access/skey.h) are:
940
* (1) < (2) <= (3) = (4) >= (5) >
941
* and in addition we use (6) to represent <>. <> is not a btree-indexable
942
* operator, but we assume here that if the equality operator of a btree
943
* opclass has a negator operator, the negator behaves as <> for the opclass.
945
* The interpretation of:
947
* test_op = BT_implic_table[given_op-1][target_op-1]
949
* where test_op, given_op and target_op are strategy numbers (from 1 to 6)
950
* of btree operators, is as follows:
952
* If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
953
* want to determine whether "ATTR target_op CONST2" must also be true, then
954
* you can use "CONST2 test_op CONST1" as a test. If this test returns true,
955
* then the target expression must be true; if the test returns false, then
956
* the target expression may be false.
958
* An entry where test_op == 0 means the implication cannot be determined,
959
* i.e., this test should always be considered false.
962
#define BTLT BTLessStrategyNumber
963
#define BTLE BTLessEqualStrategyNumber
964
#define BTEQ BTEqualStrategyNumber
965
#define BTGE BTGreaterEqualStrategyNumber
966
#define BTGT BTGreaterStrategyNumber
969
static const StrategyNumber
970
BT_implic_table[6][6] = {
972
* The target operator:
976
{BTGE, BTGE, 0, 0, 0, BTGE}, /* LT */
977
{BTGT, BTGE, 0, 0, 0, BTGT}, /* LE */
978
{BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
979
{0, 0, 0, BTLE, BTLT, BTLT}, /* GE */
980
{0, 0, 0, BTLE, BTLE, BTLE}, /* GT */
981
{0, 0, 0, 0, 0, BTEQ} /* NE */
986
* pred_test_simple_clause
987
* Does the "predicate inclusion test" for a "simple clause" predicate
988
* and a "simple clause" restriction.
990
* We have three strategies for determining whether one simple clause
993
* A simple and general way is to see if they are equal(); this works for any
994
* kind of expression. (Actually, there is an implied assumption that the
995
* functions in the expression are immutable, ie dependent only on their input
996
* arguments --- but this was checked for the predicate by CheckPredicate().)
998
* When the predicate is of the form "foo IS NOT NULL", we can conclude that
999
* the predicate is implied if the clause is a strict operator or function
1000
* that has "foo" as an input. In this case the clause must yield NULL when
1001
* "foo" is NULL, which we can take as equivalent to FALSE because we know
1002
* we are within an AND/OR subtree of a WHERE clause. (Again, "foo" is
1003
* already known immutable, so the clause will certainly always fail.)
1005
* Our other way works only for binary boolean opclauses of the form
1006
* "foo op constant", where "foo" is the same in both clauses. The operators
1007
* and constants can be different but the operators must be in the same btree
1008
* operator class. We use the above operator implication table to be able to
1009
* derive implications between nonidentical clauses. (Note: "foo" is known
1010
* immutable, and constants are surely immutable, but we have to check that
1011
* the operators are too. As of 8.0 it's possible for opclasses to contain
1012
* operators that are merely stable, and we dare not make deductions with
1015
* Eventually, rtree operators could also be handled by defining an
1016
* appropriate "RT_implic_table" array.
1020
pred_test_simple_clause(Expr *predicate, Node *clause)
1028
bool pred_var_on_left,
1035
test_op = InvalidOid;
1038
StrategyNumber pred_strategy,
1043
ExprState *test_exprstate;
1049
MemoryContext oldcontext;
1051
/* First try the equal() test */
1052
if (equal((Node *) predicate, clause))
1055
/* Next try the IS NOT NULL case */
1056
if (predicate && IsA(predicate, NullTest) &&
1057
((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
1059
Expr *nonnullarg = ((NullTest *) predicate)->arg;
1061
if (is_opclause(clause) &&
1062
list_member(((OpExpr *) clause)->args, nonnullarg) &&
1063
op_strict(((OpExpr *) clause)->opno))
1065
if (is_funcclause(clause) &&
1066
list_member(((FuncExpr *) clause)->args, nonnullarg) &&
1067
func_strict(((FuncExpr *) clause)->funcid))
1069
return false; /* we can't succeed below... */
1073
* Can't do anything more unless they are both binary opclauses with a
1074
* Const on one side, and identical subexpressions on the other sides.
1075
* Note we don't have to think about binary relabeling of the Const
1076
* node, since that would have been folded right into the Const.
1078
* If either Const is null, we also fail right away; this assumes that
1079
* the test operator will always be strict.
1081
if (!is_opclause(predicate))
1083
leftop = get_leftop(predicate);
1084
rightop = get_rightop(predicate);
1085
if (rightop == NULL)
1086
return false; /* not a binary opclause */
1087
if (IsA(rightop, Const))
1090
pred_const = (Const *) rightop;
1091
pred_var_on_left = true;
1093
else if (IsA(leftop, Const))
1096
pred_const = (Const *) leftop;
1097
pred_var_on_left = false;
1100
return false; /* no Const to be found */
1101
if (pred_const->constisnull)
1104
if (!is_opclause(clause))
1106
leftop = get_leftop((Expr *) clause);
1107
rightop = get_rightop((Expr *) clause);
1108
if (rightop == NULL)
1109
return false; /* not a binary opclause */
1110
if (IsA(rightop, Const))
1112
clause_var = leftop;
1113
clause_const = (Const *) rightop;
1114
clause_var_on_left = true;
1116
else if (IsA(leftop, Const))
1118
clause_var = rightop;
1119
clause_const = (Const *) leftop;
1120
clause_var_on_left = false;
1123
return false; /* no Const to be found */
1124
if (clause_const->constisnull)
1128
* Check for matching subexpressions on the non-Const sides. We used
1129
* to only allow a simple Var, but it's about as easy to allow any
1130
* expression. Remember we already know that the pred expression does
1131
* not contain any non-immutable functions, so identical expressions
1132
* should yield identical results.
1134
if (!equal(pred_var, clause_var))
1138
* Okay, get the operators in the two clauses we're comparing. Commute
1139
* them if needed so that we can assume the variables are on the left.
1141
pred_op = ((OpExpr *) predicate)->opno;
1142
if (!pred_var_on_left)
1144
pred_op = get_commutator(pred_op);
1145
if (!OidIsValid(pred_op))
1149
clause_op = ((OpExpr *) clause)->opno;
1150
if (!clause_var_on_left)
1152
clause_op = get_commutator(clause_op);
1153
if (!OidIsValid(clause_op))
1158
* Try to find a btree opclass containing the needed operators.
1160
* We must find a btree opclass that contains both operators, else the
1161
* implication can't be determined. Also, the pred_op has to be of
1162
* default subtype (implying left and right input datatypes are the
1163
* same); otherwise it's unsafe to put the pred_const on the left side
1164
* of the test. Also, the opclass must contain a suitable test
1165
* operator matching the clause_const's type (which we take to mean
1166
* that it has the same subtype as the original clause_operator).
1168
* If there are multiple matching opclasses, assume we can use any one to
1169
* determine the logical relationship of the two operators and the
1170
* correct corresponding test operator. This should work for any
1171
* logically consistent opclasses.
1173
catlist = SearchSysCacheList(AMOPOPID, 1,
1174
ObjectIdGetDatum(pred_op),
1178
* If we couldn't find any opclass containing the pred_op, perhaps it
1179
* is a <> operator. See if it has a negator that is in an opclass.
1181
pred_op_negated = false;
1182
if (catlist->n_members == 0)
1184
pred_op_negator = get_negator(pred_op);
1185
if (OidIsValid(pred_op_negator))
1187
pred_op_negated = true;
1188
ReleaseSysCacheList(catlist);
1189
catlist = SearchSysCacheList(AMOPOPID, 1,
1190
ObjectIdGetDatum(pred_op_negator),
1195
/* Also may need the clause_op's negator */
1196
clause_op_negator = get_negator(clause_op);
1198
/* Now search the opclasses */
1199
for (i = 0; i < catlist->n_members; i++)
1201
HeapTuple pred_tuple = &catlist->members[i]->tuple;
1202
Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
1203
HeapTuple clause_tuple;
1205
opclass_id = pred_form->amopclaid;
1208
if (!opclass_is_btree(opclass_id))
1210
/* predicate operator must be default within this opclass */
1211
if (pred_form->amopsubtype != InvalidOid)
1214
/* Get the predicate operator's btree strategy number */
1215
pred_strategy = (StrategyNumber) pred_form->amopstrategy;
1216
Assert(pred_strategy >= 1 && pred_strategy <= 5);
1218
if (pred_op_negated)
1220
/* Only consider negators that are = */
1221
if (pred_strategy != BTEqualStrategyNumber)
1223
pred_strategy = BTNE;
1227
* From the same opclass, find a strategy number for the
1228
* clause_op, if possible
1230
clause_tuple = SearchSysCache(AMOPOPID,
1231
ObjectIdGetDatum(clause_op),
1232
ObjectIdGetDatum(opclass_id),
1234
if (HeapTupleIsValid(clause_tuple))
1236
Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
1238
/* Get the restriction clause operator's strategy/subtype */
1239
clause_strategy = (StrategyNumber) clause_form->amopstrategy;
1240
Assert(clause_strategy >= 1 && clause_strategy <= 5);
1241
clause_subtype = clause_form->amopsubtype;
1242
ReleaseSysCache(clause_tuple);
1244
else if (OidIsValid(clause_op_negator))
1246
clause_tuple = SearchSysCache(AMOPOPID,
1247
ObjectIdGetDatum(clause_op_negator),
1248
ObjectIdGetDatum(opclass_id),
1250
if (HeapTupleIsValid(clause_tuple))
1252
Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
1254
/* Get the restriction clause operator's strategy/subtype */
1255
clause_strategy = (StrategyNumber) clause_form->amopstrategy;
1256
Assert(clause_strategy >= 1 && clause_strategy <= 5);
1257
clause_subtype = clause_form->amopsubtype;
1258
ReleaseSysCache(clause_tuple);
1260
/* Only consider negators that are = */
1261
if (clause_strategy != BTEqualStrategyNumber)
1263
clause_strategy = BTNE;
1272
* Look up the "test" strategy number in the implication table
1274
test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1275
if (test_strategy == 0)
1277
/* Can't determine implication using this interpretation */
1282
* See if opclass has an operator for the test strategy and the
1285
if (test_strategy == BTNE)
1287
test_op = get_opclass_member(opclass_id, clause_subtype,
1288
BTEqualStrategyNumber);
1289
if (OidIsValid(test_op))
1290
test_op = get_negator(test_op);
1294
test_op = get_opclass_member(opclass_id, clause_subtype,
1297
if (OidIsValid(test_op))
1300
* Last check: test_op must be immutable.
1302
* Note that we require only the test_op to be immutable, not the
1303
* original clause_op. (pred_op must be immutable, else it
1304
* would not be allowed in an index predicate.) Essentially
1305
* we are assuming that the opclass is consistent even if it
1306
* contains operators that are merely stable.
1308
if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
1316
ReleaseSysCacheList(catlist);
1320
/* couldn't find a btree opclass to interpret the operators */
1325
* Evaluate the test. For this we need an EState.
1327
estate = CreateExecutorState();
1329
/* We can use the estate's working context to avoid memory leaks. */
1330
oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1332
/* Build expression tree */
1333
test_expr = make_opclause(test_op,
1336
(Expr *) pred_const,
1337
(Expr *) clause_const);
1339
/* Prepare it for execution */
1340
test_exprstate = ExecPrepareExpr(test_expr, estate);
1342
/* And execute it. */
1343
test_result = ExecEvalExprSwitchContext(test_exprstate,
1344
GetPerTupleExprContext(estate),
1347
/* Get back to outer memory context */
1348
MemoryContextSwitchTo(oldcontext);
1350
/* Release all the junk we just created */
1351
FreeExecutorState(estate);
1355
/* Treat a null result as false ... but it's a tad fishy ... */
1356
elog(DEBUG2, "null predicate test result");
1359
return DatumGetBool(test_result);
1363
/****************************************************************************
1364
* ---- ROUTINES TO CHECK JOIN CLAUSES ----
1365
****************************************************************************/
1368
* indexable_outerrelids
1369
* Finds all other relids that participate in any indexable join clause
1370
* for the specified index. Returns a set of relids.
1372
* 'rel' is the relation for which 'index' is defined
1375
indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index)
1377
Relids outer_relids = NULL;
1380
foreach(l, rel->joininfo)
1382
JoinInfo *joininfo = (JoinInfo *) lfirst(l);
1383
bool match_found = false;
1387
* Examine each joinclause in the JoinInfo node's list to see if
1388
* it matches any key of the index. If so, add the JoinInfo's
1389
* otherrels to the result. We can skip examining other
1390
* joinclauses in the same list as soon as we find a match (since
1391
* by definition they all have the same otherrels).
1393
foreach(j, joininfo->jinfo_restrictinfo)
1395
RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1397
Oid *classes = index->classlist;
1401
Oid curClass = classes[0];
1403
if (match_join_clause_to_indexcol(rel,
1416
} while (!DoneMatchingIndexKeys(classes));
1424
outer_relids = bms_add_members(outer_relids,
1425
joininfo->unjoined_relids);
1429
return outer_relids;
1433
* best_inner_indexscan
1434
* Finds the best available inner indexscan for a nestloop join
1435
* with the given rel on the inside and the given outer_relids outside.
1436
* May return NULL if there are no possible inner indexscans.
1438
* We ignore ordering considerations (since a nestloop's inner scan's order
1439
* is uninteresting). Also, we consider only total cost when deciding which
1440
* of two possible paths is better --- this assumes that all indexpaths have
1441
* negligible startup cost. (True today, but someday we might have to think
1442
* harder.) Therefore, there is only one dimension of comparison and so it's
1443
* sufficient to return a single "best" path.
1446
best_inner_indexscan(Query *root, RelOptInfo *rel,
1447
Relids outer_relids, JoinType jointype)
1449
Path *cheapest = NULL;
1453
InnerIndexscanInfo *info;
1454
MemoryContext oldcontext;
1457
* Nestloop only supports inner, left, and IN joins.
1463
case JOIN_UNIQUE_OUTER:
1464
isouterjoin = false;
1474
* If there are no indexable joinclauses for this rel, exit quickly.
1476
if (bms_is_empty(rel->index_outer_relids))
1480
* Otherwise, we have to do path selection in the memory context of
1481
* the given rel, so that any created path can be safely attached to
1482
* the rel's cache of best inner paths. (This is not currently an
1483
* issue for normal planning, but it is an issue for GEQO planning.)
1485
oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1488
* Intersect the given outer_relids with index_outer_relids to find
1489
* the set of outer relids actually relevant for this index. If there
1490
* are none, again we can fail immediately.
1492
outer_relids = bms_intersect(rel->index_outer_relids, outer_relids);
1493
if (bms_is_empty(outer_relids))
1495
bms_free(outer_relids);
1496
MemoryContextSwitchTo(oldcontext);
1501
* Look to see if we already computed the result for this set of
1502
* relevant outerrels. (We include the isouterjoin status in the
1503
* cache lookup key for safety. In practice I suspect this is not
1504
* necessary because it should always be the same for a given
1507
foreach(jlist, rel->index_inner_paths)
1509
info = (InnerIndexscanInfo *) lfirst(jlist);
1510
if (bms_equal(info->other_relids, outer_relids) &&
1511
info->isouterjoin == isouterjoin)
1513
bms_free(outer_relids);
1514
MemoryContextSwitchTo(oldcontext);
1515
return info->best_innerpath;
1520
* For each index of the rel, find the best path; then choose the best
1521
* overall. We cache the per-index results as well as the overall
1522
* result. (This is useful because different indexes may have
1523
* different relevant outerrel sets, so different overall outerrel
1524
* sets might still map to the same computation for a given index.)
1526
foreach(ilist, rel->indexlist)
1528
IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
1529
Relids index_outer_relids;
1532
/* identify set of relevant outer relids for this index */
1533
index_outer_relids = bms_intersect(index->outer_relids, outer_relids);
1535
if (bms_is_empty(index_outer_relids))
1537
bms_free(index_outer_relids);
1542
* Look to see if we already computed the result for this index.
1544
foreach(jlist, index->inner_paths)
1546
info = (InnerIndexscanInfo *) lfirst(jlist);
1547
if (bms_equal(info->other_relids, index_outer_relids) &&
1548
info->isouterjoin == isouterjoin)
1550
path = info->best_innerpath;
1551
bms_free(index_outer_relids); /* not needed anymore */
1556
if (jlist == NULL) /* failed to find a match? */
1560
/* find useful clauses for this index and outerjoin set */
1561
clausegroups = group_clauses_by_indexkey_for_join(root,
1570
path = make_innerjoin_index_path(root, rel, index,
1574
/* Cache the result --- whether positive or negative */
1575
info = makeNode(InnerIndexscanInfo);
1576
info->other_relids = index_outer_relids;
1577
info->isouterjoin = isouterjoin;
1578
info->best_innerpath = path;
1579
index->inner_paths = lcons(info, index->inner_paths);
1583
(cheapest == NULL ||
1584
compare_path_costs(path, cheapest, TOTAL_COST) < 0))
1588
/* Cache the result --- whether positive or negative */
1589
info = makeNode(InnerIndexscanInfo);
1590
info->other_relids = outer_relids;
1591
info->isouterjoin = isouterjoin;
1592
info->best_innerpath = cheapest;
1593
rel->index_inner_paths = lcons(info, rel->index_inner_paths);
1595
MemoryContextSwitchTo(oldcontext);
1600
/****************************************************************************
1601
* ---- PATH CREATION UTILITIES ----
1602
****************************************************************************/
1605
* make_innerjoin_index_path
1606
* Create an index path node for a path to be used as an inner
1607
* relation in a nestloop join.
1609
* 'rel' is the relation for which 'index' is defined
1610
* 'clausegroups' is a list of lists of RestrictInfos that can use 'index'
1613
make_innerjoin_index_path(Query *root,
1614
RelOptInfo *rel, IndexOptInfo *index,
1617
IndexPath *pathnode = makeNode(IndexPath);
1621
/* XXX perhaps this code should be merged with create_index_path? */
1623
pathnode->path.pathtype = T_IndexScan;
1624
pathnode->path.parent = rel;
1627
* There's no point in marking the path with any pathkeys, since it
1628
* will only ever be used as the inner path of a nestloop, and so its
1629
* ordering does not matter.
1631
pathnode->path.pathkeys = NIL;
1633
/* Convert clauses to indexquals the executor can handle */
1634
indexquals = expand_indexqual_conditions(index, clausegroups);
1636
/* Flatten the clausegroups list to produce indexclauses list */
1637
allclauses = flatten_clausegroups_list(clausegroups);
1640
* Note that we are making a pathnode for a single-scan indexscan;
1641
* therefore, indexinfo etc should be single-element lists.
1643
pathnode->indexinfo = list_make1(index);
1644
pathnode->indexclauses = list_make1(allclauses);
1645
pathnode->indexquals = list_make1(indexquals);
1647
pathnode->isjoininner = true;
1649
/* We don't actually care what order the index scans in ... */
1650
pathnode->indexscandir = NoMovementScanDirection;
1653
* We must compute the estimated number of output rows for the
1654
* indexscan. This is less than rel->rows because of the additional
1655
* selectivity of the join clauses. Since clausegroups may contain
1656
* both restriction and join clauses, we have to do a set union to get
1657
* the full set of clauses that must be considered to compute the
1658
* correct selectivity. (Without the union operation, we might have
1659
* some restriction clauses appearing twice, which'd mislead
1660
* clauselist_selectivity into double-counting their selectivity.
1661
* However, since RestrictInfo nodes aren't copied when linking them
1662
* into different lists, it should be sufficient to use pointer
1663
* comparison to remove duplicates.)
1665
* Always assume the join type is JOIN_INNER; even if some of the join
1666
* clauses come from other contexts, that's not our problem.
1668
allclauses = list_union_ptr(rel->baserestrictinfo, allclauses);
1669
pathnode->rows = rel->tuples *
1670
clauselist_selectivity(root,
1672
rel->relid, /* do not use 0! */
1674
/* Like costsize.c, force estimate to be at least one row */
1675
pathnode->rows = clamp_row_est(pathnode->rows);
1677
cost_index(&pathnode->path, root, rel, index, indexquals, true);
1679
return (Path *) pathnode;
1683
* flatten_clausegroups_list
1684
* Given a list of lists of RestrictInfos, flatten it to a list
1687
* This is used to flatten out the result of group_clauses_by_indexkey()
1688
* or one of its sibling routines, to produce an indexclauses list.
1691
flatten_clausegroups_list(List *clausegroups)
1693
List *allclauses = NIL;
1696
foreach(l, clausegroups)
1697
allclauses = list_concat(allclauses, list_copy((List *) lfirst(l)));
1702
* make_expr_from_indexclauses()
1703
* Given an indexclauses structure, produce an ordinary boolean expression.
1705
* This consists of stripping out the RestrictInfo nodes and inserting
1706
* explicit AND and OR nodes as needed. There's not much to it, but
1707
* the functionality is needed in a few places, so centralize the logic.
1710
make_expr_from_indexclauses(List *indexclauses)
1712
List *orclauses = NIL;
1715
/* There's no such thing as an indexpath with zero scans */
1716
Assert(indexclauses != NIL);
1718
foreach(orlist, indexclauses)
1720
List *andlist = (List *) lfirst(orlist);
1722
/* Strip RestrictInfos */
1723
andlist = get_actual_clauses(andlist);
1724
/* Insert AND node if needed, and add to orclauses list */
1725
orclauses = lappend(orclauses, make_ands_explicit(andlist));
1728
if (list_length(orclauses) > 1)
1729
return make_orclause(orclauses);
1731
return (Expr *) linitial(orclauses);
1735
/****************************************************************************
1736
* ---- ROUTINES TO CHECK OPERANDS ----
1737
****************************************************************************/
1740
* match_index_to_operand()
1741
* Generalized test for a match between an index's key
1742
* and the operand on one side of a restriction or join clause.
1744
* operand: the nodetree to be compared to the index
1745
* indexcol: the column number of the index (counting from 0)
1746
* rel: the parent relation
1747
* index: the index of interest
1750
match_index_to_operand(Node *operand,
1753
IndexOptInfo *index)
1758
* Ignore any RelabelType node above the operand. This is needed to
1759
* be able to apply indexscanning in binary-compatible-operator cases.
1760
* Note: we can assume there is at most one RelabelType node;
1761
* eval_const_expressions() will have simplified if more than one.
1763
if (operand && IsA(operand, RelabelType))
1764
operand = (Node *) ((RelabelType *) operand)->arg;
1766
indkey = index->indexkeys[indexcol];
1770
* Simple index column; operand must be a matching Var.
1772
if (operand && IsA(operand, Var) &&
1773
rel->relid == ((Var *) operand)->varno &&
1774
indkey == ((Var *) operand)->varattno)
1780
* Index expression; find the correct expression. (This search
1781
* could be avoided, at the cost of complicating all the callers
1782
* of this routine; doesn't seem worth it.)
1784
ListCell *indexpr_item;
1788
indexpr_item = list_head(index->indexprs);
1789
for (i = 0; i < indexcol; i++)
1791
if (index->indexkeys[i] == 0)
1793
if (indexpr_item == NULL)
1794
elog(ERROR, "wrong number of index expressions");
1795
indexpr_item = lnext(indexpr_item);
1798
if (indexpr_item == NULL)
1799
elog(ERROR, "wrong number of index expressions");
1800
indexkey = (Node *) lfirst(indexpr_item);
1803
* Does it match the operand? Again, strip any relabeling.
1805
if (indexkey && IsA(indexkey, RelabelType))
1806
indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1808
if (equal(indexkey, operand))
1815
/****************************************************************************
1816
* ---- ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS ----
1817
****************************************************************************/
1820
* These routines handle special optimization of operators that can be
1821
* used with index scans even though they are not known to the executor's
1822
* indexscan machinery. The key idea is that these operators allow us
1823
* to derive approximate indexscan qual clauses, such that any tuples
1824
* that pass the operator clause itself must also satisfy the simpler
1825
* indexscan condition(s). Then we can use the indexscan machinery
1826
* to avoid scanning as much of the table as we'd otherwise have to,
1827
* while applying the original operator as a qpqual condition to ensure
1828
* we deliver only the tuples we want. (In essence, we're using a regular
1829
* index as if it were a lossy index.)
1831
* An example of what we're doing is
1832
* textfield LIKE 'abc%'
1833
* from which we can generate the indexscanable conditions
1834
* textfield >= 'abc' AND textfield < 'abd'
1835
* which allow efficient scanning of an index on textfield.
1836
* (In reality, character set and collation issues make the transformation
1837
* from LIKE to indexscan limits rather harder than one might think ...
1838
* but that's the basic idea.)
1840
* Two routines are provided here, match_special_index_operator() and
1841
* expand_indexqual_conditions(). match_special_index_operator() is
1842
* just an auxiliary function for match_clause_to_indexcol(); after
1843
* the latter fails to recognize a restriction opclause's operator
1844
* as a member of an index's opclass, it asks match_special_index_operator()
1845
* whether the clause should be considered an indexqual anyway.
1846
* expand_indexqual_conditions() converts a list of lists of RestrictInfo
1847
* nodes (with implicit AND semantics across list elements) into
1848
* a list of clauses that the executor can actually handle. For operators
1849
* that are members of the index's opclass this transformation is a no-op,
1850
* but operators recognized by match_special_index_operator() must be
1851
* converted into one or more "regular" indexqual conditions.
1856
* match_special_index_operator
1857
* Recognize restriction clauses that can be used to generate
1858
* additional indexscanable qualifications.
1860
* The given clause is already known to be a binary opclause having
1861
* the form (indexkey OP pseudoconst) or (pseudoconst OP indexkey),
1862
* but the OP proved not to be one of the index's opclass operators.
1863
* Return 'true' if we can do something with it anyway.
1866
match_special_index_operator(Expr *clause, Oid opclass,
1867
bool indexkey_on_left)
1869
bool isIndexable = false;
1873
Const *prefix = NULL;
1877
* Currently, all known special operators require the indexkey on the
1878
* left, but this test could be pushed into the switch statement if
1879
* some are added that do not...
1881
if (!indexkey_on_left)
1884
/* we know these will succeed */
1885
rightop = get_rightop(clause);
1886
expr_op = ((OpExpr *) clause)->opno;
1888
/* again, required for all current special ops: */
1889
if (!IsA(rightop, Const) ||
1890
((Const *) rightop)->constisnull)
1892
patt = (Const *) rightop;
1896
case OID_TEXT_LIKE_OP:
1897
case OID_BPCHAR_LIKE_OP:
1898
case OID_NAME_LIKE_OP:
1899
/* the right-hand const is type text for all of these */
1900
isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
1901
&prefix, &rest) != Pattern_Prefix_None;
1904
case OID_BYTEA_LIKE_OP:
1905
isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
1906
&prefix, &rest) != Pattern_Prefix_None;
1909
case OID_TEXT_ICLIKE_OP:
1910
case OID_BPCHAR_ICLIKE_OP:
1911
case OID_NAME_ICLIKE_OP:
1912
/* the right-hand const is type text for all of these */
1913
isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
1914
&prefix, &rest) != Pattern_Prefix_None;
1917
case OID_TEXT_REGEXEQ_OP:
1918
case OID_BPCHAR_REGEXEQ_OP:
1919
case OID_NAME_REGEXEQ_OP:
1920
/* the right-hand const is type text for all of these */
1921
isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex,
1922
&prefix, &rest) != Pattern_Prefix_None;
1925
case OID_TEXT_ICREGEXEQ_OP:
1926
case OID_BPCHAR_ICREGEXEQ_OP:
1927
case OID_NAME_ICREGEXEQ_OP:
1928
/* the right-hand const is type text for all of these */
1929
isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
1930
&prefix, &rest) != Pattern_Prefix_None;
1933
case OID_INET_SUB_OP:
1934
case OID_INET_SUBEQ_OP:
1935
case OID_CIDR_SUB_OP:
1936
case OID_CIDR_SUBEQ_OP:
1943
pfree(DatumGetPointer(prefix->constvalue));
1947
/* done if the expression doesn't look indexable */
1952
* Must also check that index's opclass supports the operators we will
1953
* want to apply. (A hash index, for example, will not support ">=".)
1954
* Currently, only btree supports the operators we need.
1956
* We insist on the opclass being the specific one we expect, else we'd
1957
* do the wrong thing if someone were to make a reverse-sort opclass
1958
* with the same operators.
1962
case OID_TEXT_LIKE_OP:
1963
case OID_TEXT_ICLIKE_OP:
1964
case OID_TEXT_REGEXEQ_OP:
1965
case OID_TEXT_ICREGEXEQ_OP:
1966
/* text operators will be used for varchar inputs, too */
1968
(opclass == TEXT_PATTERN_BTREE_OPS_OID) ||
1969
(opclass == TEXT_BTREE_OPS_OID && lc_collate_is_c()) ||
1970
(opclass == VARCHAR_PATTERN_BTREE_OPS_OID) ||
1971
(opclass == VARCHAR_BTREE_OPS_OID && lc_collate_is_c());
1974
case OID_BPCHAR_LIKE_OP:
1975
case OID_BPCHAR_ICLIKE_OP:
1976
case OID_BPCHAR_REGEXEQ_OP:
1977
case OID_BPCHAR_ICREGEXEQ_OP:
1979
(opclass == BPCHAR_PATTERN_BTREE_OPS_OID) ||
1980
(opclass == BPCHAR_BTREE_OPS_OID && lc_collate_is_c());
1983
case OID_NAME_LIKE_OP:
1984
case OID_NAME_ICLIKE_OP:
1985
case OID_NAME_REGEXEQ_OP:
1986
case OID_NAME_ICREGEXEQ_OP:
1988
(opclass == NAME_PATTERN_BTREE_OPS_OID) ||
1989
(opclass == NAME_BTREE_OPS_OID && lc_collate_is_c());
1992
case OID_BYTEA_LIKE_OP:
1993
isIndexable = (opclass == BYTEA_BTREE_OPS_OID);
1996
case OID_INET_SUB_OP:
1997
case OID_INET_SUBEQ_OP:
1998
isIndexable = (opclass == INET_BTREE_OPS_OID);
2001
case OID_CIDR_SUB_OP:
2002
case OID_CIDR_SUBEQ_OP:
2003
isIndexable = (opclass == CIDR_BTREE_OPS_OID);
2011
* expand_indexqual_conditions
2012
* Given a list of sublists of RestrictInfo nodes, produce a flat list
2013
* of index qual clauses. Standard qual clauses (those in the index's
2014
* opclass) are passed through unchanged. "Special" index operators
2015
* are expanded into clauses that the indexscan machinery will know
2018
* The input list is ordered by index key, and so the output list is too.
2019
* (The latter is not depended on by any part of the planner, so far as I can
2020
* tell; but some parts of the executor do assume that the indxqual list
2021
* ultimately delivered to the executor is so ordered. One such place is
2022
* _bt_preprocess_keys() in the btree support. Perhaps that ought to be fixed
2023
* someday --- tgl 7/00)
2026
expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups)
2028
List *resultquals = NIL;
2029
ListCell *clausegroup_item;
2030
Oid *classes = index->classlist;
2032
if (clausegroups == NIL)
2035
clausegroup_item = list_head(clausegroups);
2038
Oid curClass = classes[0];
2041
foreach(l, (List *) lfirst(clausegroup_item))
2043
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2045
resultquals = list_concat(resultquals,
2046
expand_indexqual_condition(rinfo,
2050
clausegroup_item = lnext(clausegroup_item);
2052
} while (clausegroup_item != NULL && !DoneMatchingIndexKeys(classes));
2054
Assert(clausegroup_item == NULL); /* else more groups than indexkeys */
2060
* expand_indexqual_condition --- expand a single indexqual condition
2062
* The input is a single RestrictInfo, the output a list of RestrictInfos
2065
expand_indexqual_condition(RestrictInfo *rinfo, Oid opclass)
2067
Expr *clause = rinfo->clause;
2069
/* we know these will succeed */
2070
Node *leftop = get_leftop(clause);
2071
Node *rightop = get_rightop(clause);
2072
Oid expr_op = ((OpExpr *) clause)->opno;
2073
Const *patt = (Const *) rightop;
2074
Const *prefix = NULL;
2076
Pattern_Prefix_Status pstatus;
2082
* LIKE and regex operators are not members of any index
2083
* opclass, so if we find one in an indexqual list we can
2084
* assume that it was accepted by
2085
* match_special_index_operator().
2087
case OID_TEXT_LIKE_OP:
2088
case OID_BPCHAR_LIKE_OP:
2089
case OID_NAME_LIKE_OP:
2090
case OID_BYTEA_LIKE_OP:
2091
pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
2093
result = prefix_quals(leftop, opclass, prefix, pstatus);
2096
case OID_TEXT_ICLIKE_OP:
2097
case OID_BPCHAR_ICLIKE_OP:
2098
case OID_NAME_ICLIKE_OP:
2099
/* the right-hand const is type text for all of these */
2100
pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
2102
result = prefix_quals(leftop, opclass, prefix, pstatus);
2105
case OID_TEXT_REGEXEQ_OP:
2106
case OID_BPCHAR_REGEXEQ_OP:
2107
case OID_NAME_REGEXEQ_OP:
2108
/* the right-hand const is type text for all of these */
2109
pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
2111
result = prefix_quals(leftop, opclass, prefix, pstatus);
2114
case OID_TEXT_ICREGEXEQ_OP:
2115
case OID_BPCHAR_ICREGEXEQ_OP:
2116
case OID_NAME_ICREGEXEQ_OP:
2117
/* the right-hand const is type text for all of these */
2118
pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
2120
result = prefix_quals(leftop, opclass, prefix, pstatus);
2123
case OID_INET_SUB_OP:
2124
case OID_INET_SUBEQ_OP:
2125
case OID_CIDR_SUB_OP:
2126
case OID_CIDR_SUBEQ_OP:
2127
result = network_prefix_quals(leftop, expr_op, opclass,
2132
result = list_make1(rinfo);
2140
* Given a fixed prefix that all the "leftop" values must have,
2141
* generate suitable indexqual condition(s). opclass is the index
2142
* operator class; we use it to deduce the appropriate comparison
2143
* operators and operand datatypes.
2146
prefix_quals(Node *leftop, Oid opclass,
2147
Const *prefix_const, Pattern_Prefix_Status pstatus)
2155
Assert(pstatus != Pattern_Prefix_None);
2159
case TEXT_BTREE_OPS_OID:
2160
case TEXT_PATTERN_BTREE_OPS_OID:
2164
case VARCHAR_BTREE_OPS_OID:
2165
case VARCHAR_PATTERN_BTREE_OPS_OID:
2166
datatype = VARCHAROID;
2169
case BPCHAR_BTREE_OPS_OID:
2170
case BPCHAR_PATTERN_BTREE_OPS_OID:
2171
datatype = BPCHAROID;
2174
case NAME_BTREE_OPS_OID:
2175
case NAME_PATTERN_BTREE_OPS_OID:
2179
case BYTEA_BTREE_OPS_OID:
2180
datatype = BYTEAOID;
2184
/* shouldn't get here */
2185
elog(ERROR, "unexpected opclass: %u", opclass);
2190
* If necessary, coerce the prefix constant to the right type. The
2191
* given prefix constant is either text or bytea type.
2193
if (prefix_const->consttype != datatype)
2197
switch (prefix_const->consttype)
2200
prefix = DatumGetCString(DirectFunctionCall1(textout,
2201
prefix_const->constvalue));
2204
prefix = DatumGetCString(DirectFunctionCall1(byteaout,
2205
prefix_const->constvalue));
2208
elog(ERROR, "unexpected const type: %u",
2209
prefix_const->consttype);
2212
prefix_const = string_to_const(prefix, datatype);
2217
* If we found an exact-match pattern, generate an "=" indexqual.
2219
if (pstatus == Pattern_Prefix_Exact)
2221
oproid = get_opclass_member(opclass, InvalidOid,
2222
BTEqualStrategyNumber);
2223
if (oproid == InvalidOid)
2224
elog(ERROR, "no = operator for opclass %u", opclass);
2225
expr = make_opclause(oproid, BOOLOID, false,
2226
(Expr *) leftop, (Expr *) prefix_const);
2227
result = list_make1(make_restrictinfo(expr, true, true));
2232
* Otherwise, we have a nonempty required prefix of the values.
2234
* We can always say "x >= prefix".
2236
oproid = get_opclass_member(opclass, InvalidOid,
2237
BTGreaterEqualStrategyNumber);
2238
if (oproid == InvalidOid)
2239
elog(ERROR, "no >= operator for opclass %u", opclass);
2240
expr = make_opclause(oproid, BOOLOID, false,
2241
(Expr *) leftop, (Expr *) prefix_const);
2242
result = list_make1(make_restrictinfo(expr, true, true));
2245
* If we can create a string larger than the prefix, we can say
2249
greaterstr = make_greater_string(prefix_const);
2252
oproid = get_opclass_member(opclass, InvalidOid,
2253
BTLessStrategyNumber);
2254
if (oproid == InvalidOid)
2255
elog(ERROR, "no < operator for opclass %u", opclass);
2256
expr = make_opclause(oproid, BOOLOID, false,
2257
(Expr *) leftop, (Expr *) greaterstr);
2258
result = lappend(result, make_restrictinfo(expr, true, true));
2265
* Given a leftop and a rightop, and a inet-class sup/sub operator,
2266
* generate suitable indexqual condition(s). expr_op is the original
2267
* operator, and opclass is the index opclass.
2270
network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass, Datum rightop)
2283
case OID_INET_SUB_OP:
2287
case OID_INET_SUBEQ_OP:
2291
case OID_CIDR_SUB_OP:
2295
case OID_CIDR_SUBEQ_OP:
2300
elog(ERROR, "unexpected operator: %u", expr_op);
2305
* create clause "key >= network_scan_first( rightop )", or ">" if the
2306
* operator disallows equality.
2310
opr1oid = get_opclass_member(opclass, InvalidOid,
2311
BTGreaterEqualStrategyNumber);
2312
if (opr1oid == InvalidOid)
2313
elog(ERROR, "no >= operator for opclass %u", opclass);
2317
opr1oid = get_opclass_member(opclass, InvalidOid,
2318
BTGreaterStrategyNumber);
2319
if (opr1oid == InvalidOid)
2320
elog(ERROR, "no > operator for opclass %u", opclass);
2323
opr1right = network_scan_first(rightop);
2325
expr = make_opclause(opr1oid, BOOLOID, false,
2327
(Expr *) makeConst(datatype, -1, opr1right,
2329
result = list_make1(make_restrictinfo(expr, true, true));
2331
/* create clause "key <= network_scan_last( rightop )" */
2333
opr2oid = get_opclass_member(opclass, InvalidOid,
2334
BTLessEqualStrategyNumber);
2335
if (opr2oid == InvalidOid)
2336
elog(ERROR, "no <= operator for opclass %u", opclass);
2338
opr2right = network_scan_last(rightop);
2340
expr = make_opclause(opr2oid, BOOLOID, false,
2342
(Expr *) makeConst(datatype, -1, opr2right,
2344
result = lappend(result, make_restrictinfo(expr, true, true));
2350
* Handy subroutines for match_special_index_operator() and friends.
2354
* Generate a Datum of the appropriate type from a C string.
2355
* Note that all of the supported types are pass-by-ref, so the
2356
* returned value should be pfree'd if no longer needed.
2359
string_to_datum(const char *str, Oid datatype)
2362
* We cheat a little by assuming that textin() will do for bpchar and
2363
* varchar constants too...
2365
if (datatype == NAMEOID)
2366
return DirectFunctionCall1(namein, CStringGetDatum(str));
2367
else if (datatype == BYTEAOID)
2368
return DirectFunctionCall1(byteain, CStringGetDatum(str));
2370
return DirectFunctionCall1(textin, CStringGetDatum(str));
2374
* Generate a Const node of the appropriate type from a C string.
2377
string_to_const(const char *str, Oid datatype)
2379
Datum conval = string_to_datum(str, datatype);
2381
return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2382
conval, false, false);
added
removed
src/backend/optimizer/path/indxpath.c
