1 /*-------------------------------------------------------------------------
4 * Routines to determine which indices are usable for scanning a
5 * given relation, and create IndexPaths accordingly.
7 * Copyright (c) 1994, Regents of the University of California
11 * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.77 2000/01/22 23:50:14 tgl Exp $
13 *-------------------------------------------------------------------------
20 #include "access/heapam.h"
21 #include "access/nbtree.h"
22 #include "catalog/catname.h"
23 #include "catalog/pg_amop.h"
24 #include "catalog/pg_operator.h"
25 #include "executor/executor.h"
26 #include "mb/pg_wchar.h"
27 #include "nodes/makefuncs.h"
28 #include "nodes/nodeFuncs.h"
29 #include "optimizer/clauses.h"
30 #include "optimizer/cost.h"
31 #include "optimizer/pathnode.h"
32 #include "optimizer/paths.h"
33 #include "optimizer/plancat.h"
34 #include "optimizer/restrictinfo.h"
35 #include "optimizer/var.h"
36 #include "parser/parse_coerce.h"
37 #include "parser/parse_expr.h"
38 #include "parser/parse_oper.h"
39 #include "parser/parsetree.h"
40 #include "utils/builtins.h"
41 #include "utils/lsyscache.h"
42 #include "utils/syscache.h"
45 #define is_indexable_operator(clause,opclass,relam,indexkey_on_left) \
46 (indexable_operator(clause,opclass,relam,indexkey_on_left) != InvalidOid)
49 Prefix_None, Prefix_Partial, Prefix_Exact
52 static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index,
53 int indexkey, Oid opclass,
54 List *restrictinfo_list);
55 static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index,
56 int indexkey, Oid opclass,
58 List *other_matching_indices);
59 static bool match_or_subclause_to_indexkey(RelOptInfo *rel,
61 int indexkey, Oid opclass,
63 static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index,
64 int *indexkeys, Oid *classes,
65 List *restrictinfo_list);
66 static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel,
68 int *indexkeys, Oid *classes,
69 List *join_cinfo_list,
70 List *restr_cinfo_list);
71 static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index,
72 int indexkey, Oid opclass,
73 Expr *clause, bool join);
74 static bool pred_test(List *predicate_list, List *restrictinfo_list,
76 static bool one_pred_test(Expr *predicate, List *restrictinfo_list);
77 static bool one_pred_clause_expr_test(Expr *predicate, Node *clause);
78 static bool one_pred_clause_test(Expr *predicate, Node *clause);
79 static bool clause_pred_clause_test(Expr *predicate, Node *clause);
80 static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
81 List *joininfo_list, List *restrictinfo_list,
82 List **clausegroups, List **outerrelids);
83 static List *index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
84 List *clausegroup_list, List *outerrelids_list);
85 static bool useful_for_mergejoin(RelOptInfo *rel, IndexOptInfo *index,
87 static bool useful_for_ordering(Query *root, RelOptInfo *rel,
89 static bool match_index_to_operand(int indexkey, Var *operand,
90 RelOptInfo *rel, IndexOptInfo *index);
91 static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel,
93 static bool match_special_index_operator(Expr *clause, Oid opclass, Oid relam,
94 bool indexkey_on_left);
95 static Prefix_Status like_fixed_prefix(char *patt, char **prefix);
96 static Prefix_Status regex_fixed_prefix(char *patt, bool case_insensitive,
98 static List *prefix_quals(Var *leftop, Oid expr_op,
99 char *prefix, Prefix_Status pstatus);
100 static char *make_greater_string(const char * str, Oid datatype);
101 static Oid find_operator(const char * opname, Oid datatype);
102 static Datum string_to_datum(const char * str, Oid datatype);
103 static Const *string_to_const(const char * str, Oid datatype);
104 static bool string_lessthan(const char * str1, const char * str2,
109 * create_index_paths()
110 * Generate all interesting index paths for the given relation.
112 * To be considered for an index scan, an index must match one or more
113 * restriction clauses or join clauses from the query's qual condition,
114 * or match the query's ORDER BY condition.
116 * There are two basic kinds of index scans. A "plain" index scan uses
117 * only restriction clauses (possibly none at all) in its indexqual,
118 * so it can be applied in any context. An "innerjoin" index scan uses
119 * join clauses (plus restriction clauses, if available) in its indexqual.
120 * Therefore it can only be used as the inner relation of a nestloop
121 * join against an outer rel that includes all the other rels mentioned
122 * in its join clauses. In that context, values for the other rels'
123 * attributes are available and fixed during any one scan of the indexpath.
125 * This routine's return value is a list of plain IndexPaths for each
126 * index the routine deems potentially interesting for the current query
127 * (at most one IndexPath per index on the given relation). An innerjoin
128 * path is also generated for each interesting combination of outer join
129 * relations. The innerjoin paths are *not* in the return list, but are
130 * appended to the "innerjoin" list of the relation itself.
132 * 'rel' is the relation for which we want to generate index paths
133 * 'indices' is a list of available indexes for 'rel'
134 * 'restrictinfo_list' is a list of restrictinfo nodes for 'rel'
135 * 'joininfo_list' is a list of joininfo nodes for 'rel'
137 * Returns a list of IndexPath access path descriptors. Additional
138 * IndexPath nodes may also be added to the rel->innerjoin list.
141 create_index_paths(Query *root,
144 List *restrictinfo_list,
150 foreach(ilist, indices)
152 IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
153 List *restrictclauses;
154 List *joinclausegroups;
155 List *joinouterrelids;
158 * If this is a partial index, we can only use it if it passes
159 * the predicate test.
161 if (index->indpred != NIL)
162 if (!pred_test(index->indpred, restrictinfo_list, joininfo_list))
166 * 1. Try matching the index against subclauses of restriction 'or'
167 * clauses (ie, 'or' clauses that reference only this relation).
168 * The restrictinfo nodes for the 'or' clauses are marked with lists
169 * of the matching indices. No paths are actually created now;
170 * that will be done in orindxpath.c after all indexes for the rel
171 * have been examined. (We need to do it that way because we can
172 * potentially use a different index for each subclause of an 'or',
173 * so we can't build a path for an 'or' clause until all indexes have
174 * been matched against it.)
176 * We currently only look to match the first key of each index against
177 * 'or' subclauses. There are cases where a later key of a multi-key
178 * index could be used (if other top-level clauses match earlier keys
179 * of the index), but our poor brains are hurting already...
181 * We don't even think about special handling of 'or' clauses that
182 * involve more than one relation (ie, are join clauses).
183 * Can we do anything useful with those?
185 match_index_orclauses(rel,
192 * 2. If the keys of this index match any of the available non-'or'
193 * restriction clauses, then create a path using those clauses
196 restrictclauses = group_clauses_by_indexkey(rel,
202 if (restrictclauses != NIL)
203 retval = lappend(retval,
204 create_index_path(root, rel, index,
208 * 3. If this index can be used for a mergejoin, then create an
209 * index path for it even if there were no restriction clauses.
210 * (If there were, there is no need to make another index path.)
211 * This will allow the index to be considered as a base for a
212 * mergejoin in later processing. Similarly, if the index matches
213 * the ordering that is needed for the overall query result, make
214 * an index path for it even if there is no other reason to do so.
216 if (restrictclauses == NIL)
218 if (useful_for_mergejoin(rel, index, joininfo_list) ||
219 useful_for_ordering(root, rel, index))
220 retval = lappend(retval,
221 create_index_path(root, rel, index, NIL));
225 * 4. Create an innerjoin index path for each combination of
226 * other rels used in available join clauses. These paths will
227 * be considered as the inner side of nestloop joins against
228 * those sets of other rels. indexable_joinclauses() finds sets
229 * of clauses that can be used with each combination of outer rels,
230 * and index_innerjoin builds the paths themselves. We add the
231 * paths to the rel's innerjoin list, NOT to the result list.
233 indexable_joinclauses(rel, index,
234 joininfo_list, restrictinfo_list,
237 if (joinclausegroups != NIL)
239 rel->innerjoin = nconc(rel->innerjoin,
240 index_innerjoin(root, rel, index,
250 /****************************************************************************
251 * ---- ROUTINES TO PROCESS 'OR' CLAUSES ----
252 ****************************************************************************/
256 * match_index_orclauses
257 * Attempt to match an index against subclauses within 'or' clauses.
258 * Each subclause that does match is marked with the index's node.
260 * Essentially, this adds 'index' to the list of subclause indices in
261 * the RestrictInfo field of each of the 'or' clauses where it matches.
262 * NOTE: we can use storage in the RestrictInfo for this purpose because
263 * this processing is only done on single-relation restriction clauses.
264 * Therefore, we will never have indexes for more than one relation
265 * mentioned in the same RestrictInfo node's list.
267 * 'rel' is the node of the relation on which the index is defined.
268 * 'index' is the index node.
269 * 'indexkey' is the (single) key of the index that we will consider.
270 * 'class' is the class of the operator corresponding to 'indexkey'.
271 * 'restrictinfo_list' is the list of available restriction clauses.
274 match_index_orclauses(RelOptInfo *rel,
278 List *restrictinfo_list)
282 foreach(i, restrictinfo_list)
284 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
286 if (restriction_is_or_clause(restrictinfo))
289 * Add this index to the subclause index list for each
290 * subclause that it matches.
292 restrictinfo->subclauseindices =
293 match_index_orclause(rel, index,
295 restrictinfo->clause->args,
296 restrictinfo->subclauseindices);
302 * match_index_orclause
303 * Attempts to match an index against the subclauses of an 'or' clause.
305 * A match means that:
306 * (1) the operator within the subclause can be used with the
307 * index's specified operator class, and
308 * (2) one operand of the subclause matches the index key.
310 * 'or_clauses' is the list of subclauses within the 'or' clause
311 * 'other_matching_indices' is the list of information on other indices
312 * that have already been matched to subclauses within this
313 * particular 'or' clause (i.e., a list previously generated by
314 * this routine), or NIL if this routine has not previously been
315 * run for this 'or' clause.
317 * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
318 * a,b,c are nodes of indices that match the first subclause in
319 * 'or-clauses', d,e,f match the second subclause, no indices
320 * match the third, g,h match the fourth, etc.
323 match_index_orclause(RelOptInfo *rel,
328 List *other_matching_indices)
330 List *matching_indices;
334 /* first time through, we create list of same length as OR clause,
335 * containing an empty sublist for each subclause.
337 if (!other_matching_indices)
339 matching_indices = NIL;
340 foreach(clist, or_clauses)
341 matching_indices = lcons(NIL, matching_indices);
344 matching_indices = other_matching_indices;
346 index_list = matching_indices;
348 foreach(clist, or_clauses)
350 Expr *clause = lfirst(clist);
352 if (match_or_subclause_to_indexkey(rel, index, indexkey, opclass,
355 /* OK to add this index to sublist for this subclause */
356 lfirst(matching_indices) = lcons(index,
357 lfirst(matching_indices));
360 matching_indices = lnext(matching_indices);
367 * See if a subclause of an OR clause matches an index.
369 * We accept the subclause if it is an operator clause that matches the
370 * index, or if it is an AND clause all of whose members are operators
371 * that match the index. (XXX Would accepting a single match be useful?)
374 match_or_subclause_to_indexkey(RelOptInfo *rel,
380 if (and_clause((Node *) clause))
384 foreach(item, clause->args)
386 if (! match_clause_to_indexkey(rel, index, indexkey, opclass,
387 lfirst(item), false))
393 return match_clause_to_indexkey(rel, index, indexkey, opclass,
398 /****************************************************************************
399 * ---- ROUTINES TO CHECK RESTRICTIONS ----
400 ****************************************************************************/
404 * DoneMatchingIndexKeys() - MACRO
406 * Determine whether we should continue matching index keys in a clause.
407 * Depends on if there are more to match or if this is a functional index.
408 * In the latter case we stop after the first match since the there can
409 * be only key (i.e. the function's return value) and the attributes in
410 * keys list represent the arguments to the function. -mer 3 Oct. 1991
412 #define DoneMatchingIndexKeys(indexkeys, index) \
413 (indexkeys[0] == 0 || \
414 (index->indproc != InvalidOid))
417 * group_clauses_by_indexkey
418 * Generates a list of restriction clauses that can be used with an index.
420 * 'rel' is the node of the relation itself.
421 * 'index' is a index on 'rel'.
422 * 'indexkeys' are the index keys to be matched.
423 * 'classes' are the classes of the index operators on those keys.
424 * 'restrictinfo_list' is the list of available restriction clauses for 'rel'.
426 * Returns a list of all the RestrictInfo nodes for clauses that can be
427 * used with this index.
429 * The list is ordered by index key (but as far as I can tell, this is
430 * an implementation artifact of this routine, and is not depended on by
431 * any user of the returned list --- tgl 7/99).
433 * Note that in a multi-key index, we stop if we find a key that cannot be
434 * used with any clause. For example, given an index on (A,B,C), we might
435 * return (C1 C2 C3 C4) if we find that clauses C1 and C2 use column A,
436 * clauses C3 and C4 use column B, and no clauses use column C. But if
437 * no clauses match B we will return (C1 C2), whether or not there are
438 * clauses matching column C, because the executor couldn't use them anyway.
441 group_clauses_by_indexkey(RelOptInfo *rel,
445 List *restrictinfo_list)
447 List *clausegroup_list = NIL;
449 if (restrictinfo_list == NIL || indexkeys[0] == 0)
454 int curIndxKey = indexkeys[0];
455 Oid curClass = classes[0];
456 List *clausegroup = NIL;
459 foreach(curCinfo, restrictinfo_list)
461 RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
463 if (match_clause_to_indexkey(rel,
469 clausegroup = lappend(clausegroup, rinfo);
472 /* If no clauses match this key, we're done; we don't want to
473 * look at keys to its right.
475 if (clausegroup == NIL)
478 clausegroup_list = nconc(clausegroup_list, clausegroup);
483 } while (!DoneMatchingIndexKeys(indexkeys, index));
485 /* clausegroup_list holds all matched clauses ordered by indexkeys */
486 return clausegroup_list;
490 * group_clauses_by_ikey_for_joins
491 * Generates a list of join clauses that can be used with an index
492 * to scan the inner side of a nestloop join.
494 * This is much like group_clauses_by_indexkey(), but we consider both
495 * join and restriction clauses. For each indexkey in the index, we
496 * accept both join and restriction clauses that match it, since both
497 * will make useful indexquals if the index is being used to scan the
498 * inner side of a nestloop join. But there must be at least one matching
499 * join clause, or we return NIL indicating that this index isn't useful
500 * for nestloop joining.
503 group_clauses_by_ikey_for_joins(RelOptInfo *rel,
507 List *join_cinfo_list,
508 List *restr_cinfo_list)
510 List *clausegroup_list = NIL;
513 if (join_cinfo_list == NIL || indexkeys[0] == 0)
518 int curIndxKey = indexkeys[0];
519 Oid curClass = classes[0];
520 List *clausegroup = NIL;
523 foreach(curCinfo, join_cinfo_list)
525 RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
527 if (match_clause_to_indexkey(rel,
534 clausegroup = lappend(clausegroup, rinfo);
538 foreach(curCinfo, restr_cinfo_list)
540 RestrictInfo *rinfo = (RestrictInfo *) lfirst(curCinfo);
542 if (match_clause_to_indexkey(rel,
548 clausegroup = lappend(clausegroup, rinfo);
551 /* If no clauses match this key, we're done; we don't want to
552 * look at keys to its right.
554 if (clausegroup == NIL)
557 clausegroup_list = nconc(clausegroup_list, clausegroup);
562 } while (!DoneMatchingIndexKeys(indexkeys, index));
565 * if no join clause was matched then there ain't clauses for
570 freeList(clausegroup_list);
574 /* clausegroup_list holds all matched clauses ordered by indexkeys */
575 return clausegroup_list;
580 * match_clause_to_indexkey()
581 * Determines whether a restriction or join clause matches
584 * To match, the clause:
586 * (1a) for a restriction clause: must be in the form (indexkey op const)
587 * or (const op indexkey), or
588 * (1b) for a join clause: must be in the form (indexkey op others)
589 * or (others op indexkey), where others is an expression involving
590 * only vars of the other relation(s); and
591 * (2) must contain an operator which is in the same class as the index
592 * operator for this key, or is a "special" operator as recognized
593 * by match_special_index_operator().
595 * Presently, the executor can only deal with indexquals that have the
596 * indexkey on the left, so we can only use clauses that have the indexkey
597 * on the right if we can commute the clause to put the key on the left.
598 * We do not actually do the commuting here, but we check whether a
599 * suitable commutator operator is available.
601 * Note that in the join case, we already know that the clause as a
602 * whole uses vars from the interesting set of relations. But we need
603 * to defend against expressions like (a.f1 OP (b.f2 OP a.f3)); that's
604 * not processable by an indexscan nestloop join, whereas
605 * (a.f1 OP (b.f2 OP c.f3)) is.
607 * 'rel' is the relation of interest.
608 * 'index' is an index on 'rel'.
609 * 'indexkey' is a key of 'index'.
610 * 'opclass' is the corresponding operator class.
611 * 'clause' is the clause to be tested.
612 * 'join' is true if we are considering this clause for joins.
614 * Returns true if the clause can be used with this index key.
616 * NOTE: returns false if clause is an OR or AND clause; to the extent
617 * we cope with those at all, it is done by higher-level routines.
620 match_clause_to_indexkey(RelOptInfo *rel,
630 /* Clause must be a binary opclause. */
631 if (! is_opclause((Node *) clause))
633 leftop = get_leftop(clause);
634 rightop = get_rightop(clause);
635 if (! leftop || ! rightop)
641 * Not considering joins, so check for clauses of the form:
642 * (indexkey operator constant) or (constant operator indexkey).
643 * We will accept a Param as being constant.
646 if ((IsA(rightop, Const) || IsA(rightop, Param)) &&
647 match_index_to_operand(indexkey, leftop, rel, index))
649 if (is_indexable_operator(clause, opclass, index->relam, true))
652 * If we didn't find a member of the index's opclass,
653 * see whether it is a "special" indexable operator.
655 if (match_special_index_operator(clause, opclass, index->relam,
660 if ((IsA(leftop, Const) || IsA(leftop, Param)) &&
661 match_index_to_operand(indexkey, rightop, rel, index))
663 if (is_indexable_operator(clause, opclass, index->relam, false))
666 * If we didn't find a member of the index's opclass,
667 * see whether it is a "special" indexable operator.
669 if (match_special_index_operator(clause, opclass, index->relam,
678 * Check for an indexqual that could be handled by a nestloop join.
679 * We need the index key to be compared against an expression
680 * that uses none of the indexed relation's vars.
682 if (match_index_to_operand(indexkey, leftop, rel, index))
684 List *othervarnos = pull_varnos((Node *) rightop);
687 isIndexable = ! intMember(lfirsti(rel->relids), othervarnos);
688 freeList(othervarnos);
690 is_indexable_operator(clause, opclass, index->relam, true))
693 else if (match_index_to_operand(indexkey, rightop, rel, index))
695 List *othervarnos = pull_varnos((Node *) leftop);
698 isIndexable = ! intMember(lfirsti(rel->relids), othervarnos);
699 freeList(othervarnos);
701 is_indexable_operator(clause, opclass, index->relam, false))
711 * Does a binary opclause contain an operator matching the index's
714 * If the indexkey is on the right, what we actually want to know
715 * is whether the operator has a commutator operator that matches
716 * the index's access method.
718 * We try both the straightforward match and matches that rely on
719 * recognizing binary-compatible datatypes. For example, if we have
720 * an expression like "oid = 123", the operator will be oideqint4,
721 * which we need to replace with oideq in order to recognize it as
722 * matching an oid_ops index on the oid field.
724 * Returns the OID of the matching operator, or InvalidOid if no match.
725 * Note that the returned OID will be different from the one in the given
726 * expression if we used a binary-compatible substitution. Also note that
727 * if indexkey_on_left is FALSE (meaning we need to commute), the returned
728 * OID is *not* commuted; it can be plugged directly into the given clause.
731 indexable_operator(Expr *clause, Oid opclass, Oid relam,
732 bool indexkey_on_left)
734 Oid expr_op = ((Oper *) clause->oper)->opno;
739 /* Get the commuted operator if necessary */
740 if (indexkey_on_left)
741 commuted_op = expr_op;
743 commuted_op = get_commutator(expr_op);
744 if (commuted_op == InvalidOid)
747 /* Done if the (commuted) operator is a member of the index's AM */
748 if (op_class(commuted_op, opclass, relam))
752 * Maybe the index uses a binary-compatible operator set.
754 ltype = exprType((Node *) get_leftop(clause));
755 rtype = exprType((Node *) get_rightop(clause));
758 * make sure we have two different binary-compatible types...
760 if (ltype != rtype && IS_BINARY_COMPATIBLE(ltype, rtype))
762 char *opname = get_opname(expr_op);
766 return InvalidOid; /* probably shouldn't happen */
768 /* Use the datatype of the index key */
769 if (indexkey_on_left)
770 newop = oper(opname, ltype, ltype, TRUE);
772 newop = oper(opname, rtype, rtype, TRUE);
774 if (HeapTupleIsValid(newop))
776 Oid new_expr_op = oprid(newop);
778 if (new_expr_op != expr_op)
781 * OK, we found a binary-compatible operator of the same name;
782 * now does it match the index?
784 if (indexkey_on_left)
785 commuted_op = new_expr_op;
787 commuted_op = get_commutator(new_expr_op);
788 if (commuted_op == InvalidOid)
791 if (op_class(commuted_op, opclass, relam))
801 * useful_for_mergejoin
802 * Determine whether the given index can support a mergejoin based
803 * on any available join clause.
805 * We look to see whether the first indexkey of the index matches the
806 * left or right sides of any of the mergejoinable clauses and provides
807 * the ordering needed for that side. If so, the index is useful.
808 * Matching a second or later indexkey is not useful unless there is
809 * also a mergeclause for the first indexkey, so we need not consider
810 * secondary indexkeys at this stage.
812 * 'rel' is the relation for which 'index' is defined
813 * 'joininfo_list' is the list of JoinInfo nodes for 'rel'
816 useful_for_mergejoin(RelOptInfo *rel,
820 int *indexkeys = index->indexkeys;
821 Oid *ordering = index->ordering;
824 if (!indexkeys || indexkeys[0] == 0 ||
825 !ordering || ordering[0] == InvalidOid)
826 return false; /* unordered index is not useful */
828 foreach(i, joininfo_list)
830 JoinInfo *joininfo = (JoinInfo *) lfirst(i);
833 foreach(j, joininfo->jinfo_restrictinfo)
835 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
837 if (restrictinfo->mergejoinoperator)
839 if (restrictinfo->left_sortop == ordering[0] &&
840 match_index_to_operand(indexkeys[0],
841 get_leftop(restrictinfo->clause),
844 if (restrictinfo->right_sortop == ordering[0] &&
845 match_index_to_operand(indexkeys[0],
846 get_rightop(restrictinfo->clause),
856 * useful_for_ordering
857 * Determine whether the given index can produce an ordering matching
858 * the order that is wanted for the query result.
860 * We check to see whether either forward or backward scan direction can
861 * match the specified pathkeys.
863 * 'rel' is the relation for which 'index' is defined
866 useful_for_ordering(Query *root,
870 List *index_pathkeys;
872 if (root->query_pathkeys == NIL)
873 return false; /* no special ordering requested */
875 index_pathkeys = build_index_pathkeys(root, rel, index);
877 if (index_pathkeys == NIL)
878 return false; /* unordered index */
880 if (pathkeys_contained_in(root->query_pathkeys, index_pathkeys))
883 /* caution: commute_pathkeys destructively modifies its argument;
884 * safe because we just built the index_pathkeys for local use here.
886 if (commute_pathkeys(index_pathkeys))
888 if (pathkeys_contained_in(root->query_pathkeys, index_pathkeys))
889 return true; /* useful as a reverse-order path */
895 /****************************************************************************
896 * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ----
897 ****************************************************************************/
901 * Does the "predicate inclusion test" for partial indexes.
903 * Recursively checks whether the clauses in restrictinfo_list imply
904 * that the given predicate is true.
906 * This routine (together with the routines it calls) iterates over
907 * ANDs in the predicate first, then reduces the qualification
908 * clauses down to their constituent terms, and iterates over ORs
909 * in the predicate last. This order is important to make the test
910 * succeed whenever possible (assuming the predicate has been
911 * successfully cnfify()-ed). --Nels, Jan '93
914 pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list)
921 * Note: if Postgres tried to optimize queries by forming equivalence
922 * classes over equi-joined attributes (i.e., if it recognized that a
923 * qualification such as "where a.b=c.d and a.b=5" could make use of
924 * an index on c.d), then we could use that equivalence class info
925 * here with joininfo_list to do more complete tests for the usability
926 * of a partial index. For now, the test only uses restriction
927 * clauses (those in restrictinfo_list). --Nels, Dec '92
930 if (predicate_list == NULL)
931 return true; /* no predicate: the index is usable */
932 if (restrictinfo_list == NULL)
933 return false; /* no restriction clauses: the test must
936 foreach(pred, predicate_list)
940 * if any clause is not implied, the whole predicate is not
943 if (and_clause(lfirst(pred)))
945 items = ((Expr *) lfirst(pred))->args;
948 if (!one_pred_test(lfirst(item), restrictinfo_list))
952 else if (!one_pred_test(lfirst(pred), restrictinfo_list))
961 * Does the "predicate inclusion test" for one conjunct of a predicate
965 one_pred_test(Expr *predicate, List *restrictinfo_list)
967 RestrictInfo *restrictinfo;
970 Assert(predicate != NULL);
971 foreach(item, restrictinfo_list)
973 restrictinfo = (RestrictInfo *) lfirst(item);
974 /* if any clause implies the predicate, return true */
975 if (one_pred_clause_expr_test(predicate, (Node *) restrictinfo->clause))
983 * one_pred_clause_expr_test
984 * Does the "predicate inclusion test" for a general restriction-clause
988 one_pred_clause_expr_test(Expr *predicate, Node *clause)
993 if (is_opclause(clause))
994 return one_pred_clause_test(predicate, clause);
995 else if (or_clause(clause))
997 items = ((Expr *) clause)->args;
1000 /* if any OR item doesn't imply the predicate, clause doesn't */
1001 if (!one_pred_clause_expr_test(predicate, lfirst(item)))
1006 else if (and_clause(clause))
1008 items = ((Expr *) clause)->args;
1009 foreach(item, items)
1013 * if any AND item implies the predicate, the whole clause
1016 if (one_pred_clause_expr_test(predicate, lfirst(item)))
1023 /* unknown clause type never implies the predicate */
1030 * one_pred_clause_test
1031 * Does the "predicate inclusion test" for one conjunct of a predicate
1032 * expression for a simple restriction clause.
1035 one_pred_clause_test(Expr *predicate, Node *clause)
1040 if (is_opclause((Node *) predicate))
1041 return clause_pred_clause_test(predicate, clause);
1042 else if (or_clause((Node *) predicate))
1044 items = predicate->args;
1045 foreach(item, items)
1047 /* if any item is implied, the whole predicate is implied */
1048 if (one_pred_clause_test(lfirst(item), clause))
1053 else if (and_clause((Node *) predicate))
1055 items = predicate->args;
1056 foreach(item, items)
1060 * if any item is not implied, the whole predicate is not
1063 if (!one_pred_clause_test(lfirst(item), clause))
1070 elog(DEBUG, "Unsupported predicate type, index will not be used");
1077 * Define an "operator implication table" for btree operators ("strategies").
1078 * The "strategy numbers" are: (1) < (2) <= (3) = (4) >= (5) >
1080 * The interpretation of:
1082 * test_op = BT_implic_table[given_op-1][target_op-1]
1084 * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
1085 * of btree operators, is as follows:
1087 * If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
1088 * want to determine whether "ATTR target_op CONST2" must also be true, then
1089 * you can use "CONST1 test_op CONST2" as a test. If this test returns true,
1090 * then the target expression must be true; if the test returns false, then
1091 * the target expression may be false.
1093 * An entry where test_op==0 means the implication cannot be determined, i.e.,
1094 * this test should always be considered false.
1097 static StrategyNumber
1098 BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
1108 * clause_pred_clause_test
1109 * Use operator class info to check whether clause implies predicate.
1111 * Does the "predicate inclusion test" for a "simple clause" predicate
1112 * for a single "simple clause" restriction. Currently, this only handles
1113 * (binary boolean) operators that are in some btree operator class.
1114 * Eventually, rtree operators could also be handled by defining an
1115 * appropriate "RT_implic_table" array.
1118 clause_pred_clause_test(Expr *predicate, Node *clause)
1128 StrategyNumber pred_strategy,
1138 ScanKeyData entry[3];
1141 pred_var = (Var *) get_leftop(predicate);
1142 pred_const = (Const *) get_rightop(predicate);
1143 clause_var = (Var *) get_leftop((Expr *) clause);
1144 clause_const = (Const *) get_rightop((Expr *) clause);
1146 /* Check the basic form; for now, only allow the simplest case */
1147 if (!is_opclause(clause) ||
1148 !IsA(clause_var, Var) ||
1149 clause_const == NULL ||
1150 !IsA(clause_const, Const) ||
1151 !IsA(predicate->oper, Oper) ||
1152 !IsA(pred_var, Var) ||
1153 !IsA(pred_const, Const))
1157 * The implication can't be determined unless the predicate and the
1158 * clause refer to the same attribute.
1160 if (clause_var->varattno != pred_var->varattno)
1163 /* Get the operators for the two clauses we're comparing */
1164 pred_op = ((Oper *) ((Expr *) predicate)->oper)->opno;
1165 clause_op = ((Oper *) ((Expr *) clause)->oper)->opno;
1169 * 1. Find a "btree" strategy number for the pred_op
1171 ScanKeyEntryInitialize(&entry[0], 0,
1172 Anum_pg_amop_amopid,
1174 ObjectIdGetDatum(BTREE_AM_OID));
1176 ScanKeyEntryInitialize(&entry[1], 0,
1177 Anum_pg_amop_amopopr,
1179 ObjectIdGetDatum(pred_op));
1181 relation = heap_openr(AccessMethodOperatorRelationName, AccessShareLock);
1184 * The following assumes that any given operator will only be in a
1185 * single btree operator class. This is true at least for all the
1186 * pre-defined operator classes. If it isn't true, then whichever
1187 * operator class happens to be returned first for the given operator
1188 * will be used to find the associated strategy numbers for the test.
1191 scan = heap_beginscan(relation, false, SnapshotNow, 2, entry);
1192 tuple = heap_getnext(scan, 0);
1193 if (!HeapTupleIsValid(tuple))
1195 elog(DEBUG, "clause_pred_clause_test: unknown pred_op");
1197 heap_close(relation, AccessShareLock);
1200 aform = (Form_pg_amop) GETSTRUCT(tuple);
1202 /* Get the predicate operator's strategy number (1 to 5) */
1203 pred_strategy = (StrategyNumber) aform->amopstrategy;
1205 /* Remember which operator class this strategy number came from */
1206 opclass_id = aform->amopclaid;
1212 * 2. From the same opclass, find a strategy num for the clause_op
1214 ScanKeyEntryInitialize(&entry[1], 0,
1215 Anum_pg_amop_amopclaid,
1217 ObjectIdGetDatum(opclass_id));
1219 ScanKeyEntryInitialize(&entry[2], 0,
1220 Anum_pg_amop_amopopr,
1222 ObjectIdGetDatum(clause_op));
1224 scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
1225 tuple = heap_getnext(scan, 0);
1226 if (!HeapTupleIsValid(tuple))
1228 elog(DEBUG, "clause_pred_clause_test: unknown clause_op");
1230 heap_close(relation, AccessShareLock);
1233 aform = (Form_pg_amop) GETSTRUCT(tuple);
1235 /* Get the restriction clause operator's strategy number (1 to 5) */
1236 clause_strategy = (StrategyNumber) aform->amopstrategy;
1241 * 3. Look up the "test" strategy number in the implication table
1244 test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1245 if (test_strategy == 0)
1247 heap_close(relation, AccessShareLock);
1248 return false; /* the implication cannot be determined */
1252 * 4. From the same opclass, find the operator for the test strategy
1255 ScanKeyEntryInitialize(&entry[2], 0,
1256 Anum_pg_amop_amopstrategy,
1258 Int16GetDatum(test_strategy));
1260 scan = heap_beginscan(relation, false, SnapshotNow, 3, entry);
1261 tuple = heap_getnext(scan, 0);
1262 if (!HeapTupleIsValid(tuple))
1264 elog(DEBUG, "clause_pred_clause_test: unknown test_op");
1266 heap_close(relation, AccessShareLock);
1269 aform = (Form_pg_amop) GETSTRUCT(tuple);
1271 /* Get the test operator */
1272 test_op = aform->amopopr;
1276 heap_close(relation, AccessShareLock);
1279 * 5. Evaluate the test
1281 test_oper = makeOper(test_op, /* opno */
1282 InvalidOid, /* opid */
1283 BOOLOID, /* opresulttype */
1285 NULL); /* op_fcache */
1286 replace_opid(test_oper);
1288 test_expr = make_opclause(test_oper,
1289 copyObject(clause_const),
1290 copyObject(pred_const));
1292 #ifndef OMIT_PARTIAL_INDEX
1293 test_result = ExecEvalExpr((Node *) test_expr, NULL, &isNull, NULL);
1294 #endif /* OMIT_PARTIAL_INDEX */
1297 elog(DEBUG, "clause_pred_clause_test: null test result");
1304 /****************************************************************************
1305 * ---- ROUTINES TO CHECK JOIN CLAUSES ----
1306 ****************************************************************************/
1309 * indexable_joinclauses
1310 * Finds all groups of join clauses from among 'joininfo_list' that can
1311 * be used in conjunction with 'index' for the inner scan of a nestjoin.
1313 * Each clause group comes from a single joininfo node plus the current
1314 * rel's restrictinfo list. Therefore, every clause in the group references
1315 * the current rel plus the same set of other rels (except for the restrict
1316 * clauses, which only reference the current rel). Therefore, this set
1317 * of clauses could be used as an indexqual if the relation is scanned
1318 * as the inner side of a nestloop join when the outer side contains
1319 * (at least) all those "other rels".
1321 * XXX Actually, given that we are considering a join that requires an
1322 * outer rel set (A,B,C), we should use all qual clauses that reference
1323 * any subset of these rels, not just the full set or none. This is
1324 * doable with a doubly nested loop over joininfo_list; is it worth it?
1326 * Returns two parallel lists of the same length: the clause groups,
1327 * and the required outer rel set for each one.
1329 * 'rel' is the relation for which 'index' is defined
1330 * 'joininfo_list' is the list of JoinInfo nodes for 'rel'
1331 * 'restrictinfo_list' is the list of restriction clauses for 'rel'
1332 * '*clausegroups' receives a list of clause sublists
1333 * '*outerrelids' receives a list of relid lists
1336 indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
1337 List *joininfo_list, List *restrictinfo_list,
1338 List **clausegroups, List **outerrelids)
1340 List *cg_list = NIL;
1341 List *relid_list = NIL;
1344 foreach(i, joininfo_list)
1346 JoinInfo *joininfo = (JoinInfo *) lfirst(i);
1349 clausegroup = group_clauses_by_ikey_for_joins(rel,
1353 joininfo->jinfo_restrictinfo,
1356 if (clausegroup != NIL)
1358 cg_list = lappend(cg_list, clausegroup);
1359 relid_list = lappend(relid_list, joininfo->unjoined_relids);
1363 *clausegroups = cg_list;
1364 *outerrelids = relid_list;
1367 /****************************************************************************
1368 * ---- PATH CREATION UTILITIES ----
1369 ****************************************************************************/
1373 * Creates index path nodes corresponding to paths to be used as inner
1374 * relations in nestloop joins.
1376 * 'rel' is the relation for which 'index' is defined
1377 * 'clausegroup_list' is a list of lists of restrictinfo nodes which can use
1378 * 'index'. Each sublist refers to the same set of outer rels.
1379 * 'outerrelids_list' is a list of the required outer rels for each sublist
1382 * Returns a list of index pathnodes.
1385 index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
1386 List *clausegroup_list, List *outerrelids_list)
1388 List *path_list = NIL;
1391 foreach(i, clausegroup_list)
1393 List *clausegroup = lfirst(i);
1394 IndexPath *pathnode = makeNode(IndexPath);
1397 /* XXX this code ought to be merged with create_index_path? */
1399 pathnode->path.pathtype = T_IndexScan;
1400 pathnode->path.parent = rel;
1401 pathnode->path.pathkeys = build_index_pathkeys(root, rel, index);
1403 indexquals = get_actual_clauses(clausegroup);
1404 /* expand special operators to indexquals the executor can handle */
1405 indexquals = expand_indexqual_conditions(indexquals);
1407 /* Note that we are making a pathnode for a single-scan indexscan;
1408 * therefore, both indexid and indexqual should be single-element
1411 pathnode->indexid = lconsi(index->indexoid, NIL);
1412 pathnode->indexqual = lcons(indexquals, NIL);
1414 /* joinrelids saves the rels needed on the outer side of the join */
1415 pathnode->joinrelids = lfirst(outerrelids_list);
1417 pathnode->path.path_cost = cost_index(root, rel, index, indexquals,
1420 path_list = lappend(path_list, pathnode);
1421 outerrelids_list = lnext(outerrelids_list);
1426 /****************************************************************************
1427 * ---- ROUTINES TO CHECK OPERANDS ----
1428 ****************************************************************************/
1431 * match_index_to_operand()
1432 * Generalized test for a match between an index's key
1433 * and the operand on one side of a restriction or join clause.
1434 * Now check for functional indices as well.
1437 match_index_to_operand(int indexkey,
1440 IndexOptInfo *index)
1442 if (index->indproc == InvalidOid)
1447 if (IsA(operand, Var) &&
1448 lfirsti(rel->relids) == operand->varno &&
1449 indexkey == operand->varattno)
1456 * functional index check
1458 return function_index_operand((Expr *) operand, rel, index);
1462 function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index)
1464 int relvarno = lfirsti(rel->relids);
1467 int *indexKeys = index->indexkeys;
1472 * sanity check, make sure we know what we're dealing with here.
1474 if (funcOpnd == NULL || ! IsA(funcOpnd, Expr) ||
1475 funcOpnd->opType != FUNC_EXPR ||
1476 funcOpnd->oper == NULL || indexKeys == NULL)
1479 function = (Func *) funcOpnd->oper;
1480 funcargs = funcOpnd->args;
1482 if (function->funcid != index->indproc)
1486 * Check that the arguments correspond to the same arguments used to
1487 * create the functional index. To do this we must check that 1.
1488 * refer to the right relation. 2. the args have the right attr.
1489 * numbers in the right order.
1492 foreach(arg, funcargs)
1494 Var *var = (Var *) lfirst(arg);
1496 if (! IsA(var, Var))
1498 if (indexKeys[i] == 0)
1500 if (var->varno != relvarno || var->varattno != indexKeys[i])
1506 if (indexKeys[i] != 0)
1507 return false; /* not enough arguments */
1512 /****************************************************************************
1513 * ---- ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS ----
1514 ****************************************************************************/
1517 * These routines handle special optimization of operators that can be
1518 * used with index scans even though they are not known to the executor's
1519 * indexscan machinery. The key idea is that these operators allow us
1520 * to derive approximate indexscan qual clauses, such that any tuples
1521 * that pass the operator clause itself must also satisfy the simpler
1522 * indexscan condition(s). Then we can use the indexscan machinery
1523 * to avoid scanning as much of the table as we'd otherwise have to,
1524 * while applying the original operator as a qpqual condition to ensure
1525 * we deliver only the tuples we want. (In essence, we're using a regular
1526 * index as if it were a lossy index.)
1528 * An example of what we're doing is
1529 * textfield LIKE 'abc%'
1530 * from which we can generate the indexscanable conditions
1531 * textfield >= 'abc' AND textfield < 'abd'
1532 * which allow efficient scanning of an index on textfield.
1533 * (In reality, character set and collation issues make the transformation
1534 * from LIKE to indexscan limits rather harder than one might think ...
1535 * but that's the basic idea.)
1537 * Two routines are provided here, match_special_index_operator() and
1538 * expand_indexqual_conditions(). match_special_index_operator() is
1539 * just an auxiliary function for match_clause_to_indexkey(); after
1540 * the latter fails to recognize a restriction opclause's operator
1541 * as a member of an index's opclass, it asks match_special_index_operator()
1542 * whether the clause should be considered an indexqual anyway.
1543 * expand_indexqual_conditions() converts a list of "raw" indexqual
1544 * conditions (with implicit AND semantics across list elements) into
1545 * a list that the executor can actually handle. For operators that
1546 * are members of the index's opclass this transformation is a no-op,
1547 * but operators recognized by match_special_index_operator() must be
1548 * converted into one or more "regular" indexqual conditions.
1553 * match_special_index_operator
1554 * Recognize restriction clauses that can be used to generate
1555 * additional indexscanable qualifications.
1557 * The given clause is already known to be a binary opclause having
1558 * the form (indexkey OP const/param) or (const/param OP indexkey),
1559 * but the OP proved not to be one of the index's opclass operators.
1560 * Return 'true' if we can do something with it anyway.
1563 match_special_index_operator(Expr *clause, Oid opclass, Oid relam,
1564 bool indexkey_on_left)
1566 bool isIndexable = false;
1574 /* Currently, all known special operators require the indexkey
1575 * on the left, but this test could be pushed into the switch statement
1576 * if some are added that do not...
1578 if (! indexkey_on_left)
1581 /* we know these will succeed */
1582 leftop = get_leftop(clause);
1583 rightop = get_rightop(clause);
1584 expr_op = ((Oper *) clause->oper)->opno;
1586 /* again, required for all current special ops: */
1587 if (! IsA(rightop, Const) ||
1588 ((Const *) rightop)->constisnull)
1590 constvalue = ((Const *) rightop)->constvalue;
1594 case OID_TEXT_LIKE_OP:
1595 case OID_BPCHAR_LIKE_OP:
1596 case OID_VARCHAR_LIKE_OP:
1597 case OID_NAME_LIKE_OP:
1598 /* the right-hand const is type text for all of these */
1599 patt = textout((text *) DatumGetPointer(constvalue));
1600 isIndexable = like_fixed_prefix(patt, &prefix) != Prefix_None;
1601 if (prefix) pfree(prefix);
1605 case OID_TEXT_REGEXEQ_OP:
1606 case OID_BPCHAR_REGEXEQ_OP:
1607 case OID_VARCHAR_REGEXEQ_OP:
1608 case OID_NAME_REGEXEQ_OP:
1609 /* the right-hand const is type text for all of these */
1610 patt = textout((text *) DatumGetPointer(constvalue));
1611 isIndexable = regex_fixed_prefix(patt, false, &prefix) != Prefix_None;
1612 if (prefix) pfree(prefix);
1616 case OID_TEXT_ICREGEXEQ_OP:
1617 case OID_BPCHAR_ICREGEXEQ_OP:
1618 case OID_VARCHAR_ICREGEXEQ_OP:
1619 case OID_NAME_ICREGEXEQ_OP:
1620 /* the right-hand const is type text for all of these */
1621 patt = textout((text *) DatumGetPointer(constvalue));
1622 isIndexable = regex_fixed_prefix(patt, true, &prefix) != Prefix_None;
1623 if (prefix) pfree(prefix);
1628 /* done if the expression doesn't look indexable */
1633 * Must also check that index's opclass supports the operators we will
1634 * want to apply. (A hash index, for example, will not support ">=".)
1635 * We cheat a little by not checking for availability of "=" ... any
1636 * index type should support "=", methinks.
1640 case OID_TEXT_LIKE_OP:
1641 case OID_TEXT_REGEXEQ_OP:
1642 case OID_TEXT_ICREGEXEQ_OP:
1643 if (! op_class(find_operator(">=", TEXTOID), opclass, relam) ||
1644 ! op_class(find_operator("<", TEXTOID), opclass, relam))
1645 isIndexable = false;
1648 case OID_BPCHAR_LIKE_OP:
1649 case OID_BPCHAR_REGEXEQ_OP:
1650 case OID_BPCHAR_ICREGEXEQ_OP:
1651 if (! op_class(find_operator(">=", BPCHAROID), opclass, relam) ||
1652 ! op_class(find_operator("<", BPCHAROID), opclass, relam))
1653 isIndexable = false;
1656 case OID_VARCHAR_LIKE_OP:
1657 case OID_VARCHAR_REGEXEQ_OP:
1658 case OID_VARCHAR_ICREGEXEQ_OP:
1659 if (! op_class(find_operator(">=", VARCHAROID), opclass, relam) ||
1660 ! op_class(find_operator("<", VARCHAROID), opclass, relam))
1661 isIndexable = false;
1664 case OID_NAME_LIKE_OP:
1665 case OID_NAME_REGEXEQ_OP:
1666 case OID_NAME_ICREGEXEQ_OP:
1667 if (! op_class(find_operator(">=", NAMEOID), opclass, relam) ||
1668 ! op_class(find_operator("<", NAMEOID), opclass, relam))
1669 isIndexable = false;
1677 * expand_indexqual_conditions
1678 * Given a list of (implicitly ANDed) indexqual clauses,
1679 * expand any "special" index operators into clauses that the indexscan
1680 * machinery will know what to do with. Clauses that were not
1681 * recognized by match_special_index_operator() must be passed through
1685 expand_indexqual_conditions(List *indexquals)
1687 List *resultquals = NIL;
1690 foreach(q, indexquals)
1692 Expr *clause = (Expr *) lfirst(q);
1693 /* we know these will succeed */
1694 Var *leftop = get_leftop(clause);
1695 Var *rightop = get_rightop(clause);
1696 Oid expr_op = ((Oper *) clause->oper)->opno;
1700 Prefix_Status pstatus;
1705 * LIKE and regex operators are not members of any index opclass,
1706 * so if we find one in an indexqual list we can assume that
1707 * it was accepted by match_special_index_operator().
1709 case OID_TEXT_LIKE_OP:
1710 case OID_BPCHAR_LIKE_OP:
1711 case OID_VARCHAR_LIKE_OP:
1712 case OID_NAME_LIKE_OP:
1713 /* the right-hand const is type text for all of these */
1714 constvalue = ((Const *) rightop)->constvalue;
1715 patt = textout((text *) DatumGetPointer(constvalue));
1716 pstatus = like_fixed_prefix(patt, &prefix);
1717 resultquals = nconc(resultquals,
1718 prefix_quals(leftop, expr_op,
1720 if (prefix) pfree(prefix);
1724 case OID_TEXT_REGEXEQ_OP:
1725 case OID_BPCHAR_REGEXEQ_OP:
1726 case OID_VARCHAR_REGEXEQ_OP:
1727 case OID_NAME_REGEXEQ_OP:
1728 /* the right-hand const is type text for all of these */
1729 constvalue = ((Const *) rightop)->constvalue;
1730 patt = textout((text *) DatumGetPointer(constvalue));
1731 pstatus = regex_fixed_prefix(patt, false, &prefix);
1732 resultquals = nconc(resultquals,
1733 prefix_quals(leftop, expr_op,
1735 if (prefix) pfree(prefix);
1739 case OID_TEXT_ICREGEXEQ_OP:
1740 case OID_BPCHAR_ICREGEXEQ_OP:
1741 case OID_VARCHAR_ICREGEXEQ_OP:
1742 case OID_NAME_ICREGEXEQ_OP:
1743 /* the right-hand const is type text for all of these */
1744 constvalue = ((Const *) rightop)->constvalue;
1745 patt = textout((text *) DatumGetPointer(constvalue));
1746 pstatus = regex_fixed_prefix(patt, true, &prefix);
1747 resultquals = nconc(resultquals,
1748 prefix_quals(leftop, expr_op,
1750 if (prefix) pfree(prefix);
1755 resultquals = lappend(resultquals, clause);
1764 * Extract the fixed prefix, if any, for a LIKE pattern.
1765 * *prefix is set to a palloc'd prefix string,
1766 * or to NULL if no fixed prefix exists for the pattern.
1767 * The return value distinguishes no fixed prefix, a partial prefix,
1768 * or an exact-match-only pattern.
1770 static Prefix_Status
1771 like_fixed_prefix(char *patt, char **prefix)
1777 *prefix = match = palloc(strlen(patt)+1);
1780 for (pos = 0; patt[pos]; pos++)
1782 /* % and _ are wildcard characters in LIKE */
1783 if (patt[pos] == '%' ||
1786 /* Backslash quotes the next character */
1787 if (patt[pos] == '\\')
1790 if (patt[pos] == '\0')
1794 * NOTE: this code used to think that %% meant a literal %,
1795 * but textlike() itself does not think that, and the SQL92
1796 * spec doesn't say any such thing either.
1798 match[match_pos++] = patt[pos];
1801 match[match_pos] = '\0';
1803 /* in LIKE, an empty pattern is an exact match! */
1804 if (patt[pos] == '\0')
1805 return Prefix_Exact; /* reached end of pattern, so exact */
1808 return Prefix_Partial;
1813 * Extract the fixed prefix, if any, for a regex pattern.
1814 * *prefix is set to a palloc'd prefix string,
1815 * or to NULL if no fixed prefix exists for the pattern.
1816 * The return value distinguishes no fixed prefix, a partial prefix,
1817 * or an exact-match-only pattern.
1819 static Prefix_Status
1820 regex_fixed_prefix(char *patt, bool case_insensitive,
1829 /* Pattern must be anchored left */
1833 /* Cannot optimize if unquoted | { } is present in pattern */
1834 for (pos = 1; patt[pos]; pos++)
1836 if (patt[pos] == '|' ||
1840 if (patt[pos] == '\\')
1843 if (patt[pos] == '\0')
1848 /* OK, allocate space for pattern */
1849 *prefix = match = palloc(strlen(patt)+1);
1852 /* note start at pos 1 to skip leading ^ */
1853 for (pos = 1; patt[pos]; pos++)
1855 if (patt[pos] == '.' ||
1860 /* XXX I suspect isalpha() is not an adequately locale-sensitive
1861 * test for characters that can vary under case folding?
1863 (case_insensitive && isalpha(patt[pos])))
1865 if (patt[pos] == '\\')
1868 if (patt[pos] == '\0')
1871 match[match_pos++] = patt[pos];
1874 match[match_pos] = '\0';
1876 if (patt[pos] == '$' && patt[pos+1] == '\0')
1877 return Prefix_Exact; /* pattern specifies exact match */
1880 return Prefix_Partial;
1885 * Given a fixed prefix that all the "leftop" values must have,
1886 * generate suitable indexqual condition(s). expr_op is the original
1887 * LIKE or regex operator; we use it to deduce the appropriate comparison
1891 prefix_quals(Var *leftop, Oid expr_op,
1892 char *prefix, Prefix_Status pstatus)
1902 Assert(pstatus != Prefix_None);
1906 case OID_TEXT_LIKE_OP:
1907 case OID_TEXT_REGEXEQ_OP:
1908 case OID_TEXT_ICREGEXEQ_OP:
1912 case OID_BPCHAR_LIKE_OP:
1913 case OID_BPCHAR_REGEXEQ_OP:
1914 case OID_BPCHAR_ICREGEXEQ_OP:
1915 datatype = BPCHAROID;
1918 case OID_VARCHAR_LIKE_OP:
1919 case OID_VARCHAR_REGEXEQ_OP:
1920 case OID_VARCHAR_ICREGEXEQ_OP:
1921 datatype = VARCHAROID;
1924 case OID_NAME_LIKE_OP:
1925 case OID_NAME_REGEXEQ_OP:
1926 case OID_NAME_ICREGEXEQ_OP:
1931 elog(ERROR, "prefix_quals: unexpected operator %u", expr_op);
1936 * If we found an exact-match pattern, generate an "=" indexqual.
1938 if (pstatus == Prefix_Exact)
1940 oproid = find_operator("=", datatype);
1941 if (oproid == InvalidOid)
1942 elog(ERROR, "prefix_quals: no = operator for type %u", datatype);
1943 con = string_to_const(prefix, datatype);
1944 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1945 expr = make_opclause(op, leftop, (Var *) con);
1946 result = lcons(expr, NIL);
1951 * Otherwise, we have a nonempty required prefix of the values.
1953 * We can always say "x >= prefix".
1955 oproid = find_operator(">=", datatype);
1956 if (oproid == InvalidOid)
1957 elog(ERROR, "prefix_quals: no >= operator for type %u", datatype);
1958 con = string_to_const(prefix, datatype);
1959 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1960 expr = make_opclause(op, leftop, (Var *) con);
1961 result = lcons(expr, NIL);
1964 * If we can create a string larger than the prefix, say "x < greaterstr".
1966 greaterstr = make_greater_string(prefix, datatype);
1969 oproid = find_operator("<", datatype);
1970 if (oproid == InvalidOid)
1971 elog(ERROR, "prefix_quals: no < operator for type %u", datatype);
1972 con = string_to_const(greaterstr, datatype);
1973 op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
1974 expr = make_opclause(op, leftop, (Var *) con);
1975 result = lappend(result, expr);
1983 * Try to generate a string greater than the given string or any string it is
1984 * a prefix of. If successful, return a palloc'd string; else return NULL.
1986 * To work correctly in non-ASCII locales with weird collation orders,
1987 * we cannot simply increment "foo" to "fop" --- we have to check whether
1988 * we actually produced a string greater than the given one. If not,
1989 * increment the righthand byte again and repeat. If we max out the righthand
1990 * byte, truncate off the last character and start incrementing the next.
1991 * For example, if "z" were the last character in the sort order, then we
1992 * could produce "foo" as a string greater than "fonz".
1994 * This could be rather slow in the worst case, but in most cases we won't
1995 * have to try more than one or two strings before succeeding.
1997 * XXX in a sufficiently weird locale, this might produce incorrect results?
1998 * For example, in German I believe "ss" is treated specially --- if we are
1999 * given "foos" and return "foot", will this actually be greater than "fooss"?
2002 make_greater_string(const char * str, Oid datatype)
2007 /* Make a modifiable copy, which will be our return value if successful */
2008 workstr = pstrdup((char *) str);
2010 while ((len = strlen(workstr)) > 0)
2012 unsigned char *lastchar = (unsigned char *) (workstr + len - 1);
2015 * Try to generate a larger string by incrementing the last byte.
2017 while (*lastchar < (unsigned char) 255)
2020 if (string_lessthan(str, workstr, datatype))
2021 return workstr; /* Success! */
2024 * Truncate off the last character, which might be more than 1 byte
2025 * in MULTIBYTE case.
2028 len = pg_mbcliplen((const unsigned char *) workstr, len, len-1);
2029 workstr[len] = '\0';
2041 * Handy subroutines for match_special_index_operator() and friends.
2044 /* See if there is a binary op of the given name for the given datatype */
2046 find_operator(const char * opname, Oid datatype)
2050 optup = SearchSysCacheTuple(OPERNAME,
2051 PointerGetDatum(opname),
2052 ObjectIdGetDatum(datatype),
2053 ObjectIdGetDatum(datatype),
2055 if (!HeapTupleIsValid(optup))
2057 return optup->t_data->t_oid;
2061 * Generate a Datum of the appropriate type from a C string.
2062 * Note that all of the supported types are pass-by-ref, so the
2063 * returned value should be pfree'd if no longer needed.
2066 string_to_datum(const char * str, Oid datatype)
2068 /* We cheat a little by assuming that textin() will do for
2069 * bpchar and varchar constants too...
2071 if (datatype == NAMEOID)
2072 return PointerGetDatum(namein((char *) str));
2074 return PointerGetDatum(textin((char *) str));
2078 * Generate a Const node of the appropriate type from a C string.
2081 string_to_const(const char * str, Oid datatype)
2083 Datum conval = string_to_datum(str, datatype);
2085 return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2086 conval, false, false, false, false);
2090 * Test whether two strings are "<" according to the rules of the given
2091 * datatype. We do this the hard way, ie, actually calling the type's
2092 * "<" operator function, to ensure we get the right result...
2095 string_lessthan(const char * str1, const char * str2, Oid datatype)
2097 Datum datum1 = string_to_datum(str1, datatype);
2098 Datum datum2 = string_to_datum(str2, datatype);
2104 result = text_lt((text *) datum1, (text *) datum2);
2108 result = bpcharlt((char *) datum1, (char *) datum2);
2112 result = varcharlt((char *) datum1, (char *) datum2);
2116 result = namelt((NameData *) datum1, (NameData *) datum2);
2120 elog(ERROR, "string_lessthan: unexpected datatype %u", datatype);
2125 pfree(DatumGetPointer(datum1));
2126 pfree(DatumGetPointer(datum2));