indxpath.c 66.9 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * indxpath.c
4
 *	  Routines to determine which indices are usable for scanning a
5
 *	  given relation, and create IndexPaths accordingly.
6
 *
Bruce Momjian's avatar
Bruce Momjian committed
7
 * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
8
 * Portions Copyright (c) 1994, Regents of the University of California
9 10 11
 *
 *
 * IDENTIFICATION
12
 *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.130 2002/12/16 21:30:29 tgl Exp $
13 14 15 16
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"
Bruce Momjian's avatar
Bruce Momjian committed
17

18 19
#include <math.h>

20 21
#include "access/heapam.h"
#include "access/nbtree.h"
Bruce Momjian's avatar
Bruce Momjian committed
22 23
#include "catalog/catname.h"
#include "catalog/pg_amop.h"
24
#include "catalog/pg_namespace.h"
25
#include "catalog/pg_operator.h"
Bruce Momjian's avatar
Bruce Momjian committed
26
#include "executor/executor.h"
27 28 29 30
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
Bruce Momjian's avatar
Bruce Momjian committed
31
#include "optimizer/pathnode.h"
Bruce Momjian's avatar
Bruce Momjian committed
32
#include "optimizer/paths.h"
Bruce Momjian's avatar
Bruce Momjian committed
33
#include "optimizer/restrictinfo.h"
34
#include "optimizer/var.h"
Bruce Momjian's avatar
Bruce Momjian committed
35
#include "parser/parse_coerce.h"
Bruce Momjian's avatar
Bruce Momjian committed
36 37
#include "parser/parse_expr.h"
#include "parser/parse_oper.h"
38
#include "rewrite/rewriteManip.h"
39
#include "utils/builtins.h"
40
#include "utils/fmgroids.h"
Bruce Momjian's avatar
Bruce Momjian committed
41
#include "utils/lsyscache.h"
42
#include "utils/selfuncs.h"
43
#include "utils/syscache.h"
44

45

46 47 48
/*
 * DoneMatchingIndexKeys() - MACRO
 *
49 50
 * Formerly this looked at indexkeys, but that's the wrong thing for a
 * functional index.
51
 */
52 53
#define DoneMatchingIndexKeys(indexkeys, classes) \
	(classes[0] == InvalidOid)
54

55 56
#define is_indexable_operator(clause,opclass,indexkey_on_left) \
	(indexable_operator(clause,opclass,indexkey_on_left) != InvalidOid)
57

58

59
static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index,
60
					  List *restrictinfo_list);
61
static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index,
62 63
					 List *or_clauses,
					 List *other_matching_indices);
64
static bool match_or_subclause_to_indexkey(RelOptInfo *rel,
65 66
							   IndexOptInfo *index,
							   Expr *clause);
67 68
static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index);
static List *group_clauses_by_indexkey_for_join(RelOptInfo *rel,
69
								IndexOptInfo *index,
70 71
								Relids outer_relids,
								bool isouterjoin);
72
static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index,
73 74 75
									 int indexkey, Oid opclass, Expr *clause);
static bool match_join_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index,
						 int indexkey, Oid opclass, Expr *clause);
76 77
static Oid indexable_operator(Expr *clause, Oid opclass,
				   bool indexkey_on_left);
78
static bool pred_test(List *predicate_list, List *restrictinfo_list,
79
		  List *joininfo_list, int relvarno);
80 81 82 83
static bool pred_test_restrict_list(Expr *predicate, List *restrictinfo_list);
static bool pred_test_recurse_clause(Expr *predicate, Node *clause);
static bool pred_test_recurse_pred(Expr *predicate, Node *clause);
static bool pred_test_simple_clause(Expr *predicate, Node *clause);
84 85 86 87
static Relids indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index);
static Path *make_innerjoin_index_path(Query *root,
									   RelOptInfo *rel, IndexOptInfo *index,
									   List *clausegroup);
88
static bool match_index_to_operand(int indexkey, Var *operand,
89
					   RelOptInfo *rel, IndexOptInfo *index);
90
static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel,
91
					   IndexOptInfo *index);
92
static bool match_special_index_operator(Expr *clause, Oid opclass,
93
							 bool indexkey_on_left);
94
static List *prefix_quals(Var *leftop, Oid expr_op,
95
			 Const *prefix, Pattern_Prefix_Status pstatus);
96
static List *network_prefix_quals(Var *leftop, Oid expr_op, Datum rightop);
97 98 99
static Oid	find_operator(const char *opname, Oid datatype);
static Datum string_to_datum(const char *str, Oid datatype);
static Const *string_to_const(const char *str, Oid datatype);
100 101


102 103 104
/*
 * create_index_paths()
 *	  Generate all interesting index paths for the given relation.
105
 *	  Candidate paths are added to the rel's pathlist (using add_path).
106
 *
107
 * To be considered for an index scan, an index must match one or more
108 109
 * restriction clauses or join clauses from the query's qual condition,
 * or match the query's ORDER BY condition.
110
 *
111 112 113 114 115 116 117 118 119
 * There are two basic kinds of index scans.  A "plain" index scan uses
 * only restriction clauses (possibly none at all) in its indexqual,
 * so it can be applied in any context.  An "innerjoin" index scan uses
 * join clauses (plus restriction clauses, if available) in its indexqual.
 * Therefore it can only be used as the inner relation of a nestloop
 * join against an outer rel that includes all the other rels mentioned
 * in its join clauses.  In that context, values for the other rels'
 * attributes are available and fixed during any one scan of the indexpath.
 *
120 121 122 123 124 125 126 127
 * An IndexPath is generated and submitted to add_path() for each plain index
 * scan this routine deems potentially interesting for the current query.
 *
 * We also determine the set of other relids that participate in join
 * clauses that could be used with each index.  The actually best innerjoin
 * path will be generated for each outer relation later on, but knowing the
 * set of potential otherrels allows us to identify equivalent outer relations
 * and avoid repeated computation.
128
 *
129
 * 'rel' is the relation for which we want to generate index paths
130
 */
131
void
132
create_index_paths(Query *root, RelOptInfo *rel)
133
{
134 135
	List	   *restrictinfo_list = rel->baserestrictinfo;
	List	   *joininfo_list = rel->joininfo;
136
	Relids		all_join_outerrelids = NIL;
137
	List	   *ilist;
138

139
	foreach(ilist, rel->indexlist)
140
	{
141
		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
142
		List	   *restrictclauses;
143 144 145
		List	   *index_pathkeys;
		List	   *useful_pathkeys;
		bool		index_is_ordered;
146
		Relids		join_outerrelids;
147

148
		/*
149 150
		 * If this is a partial index, we can only use it if it passes the
		 * predicate test.
151
		 */
152
		if (index->indpred != NIL)
153 154
			if (!pred_test(index->indpred, restrictinfo_list, joininfo_list,
						   lfirsti(rel->relids)))
155
				continue;
156

157
		/*
158 159 160 161 162 163 164 165 166
		 * 1. Try matching the index against subclauses of restriction
		 * 'or' clauses (ie, 'or' clauses that reference only this
		 * relation). The restrictinfo nodes for the 'or' clauses are
		 * marked with lists of the matching indices.  No paths are
		 * actually created now; that will be done in orindxpath.c after
		 * all indexes for the rel have been examined.	(We need to do it
		 * that way because we can potentially use a different index for
		 * each subclause of an 'or', so we can't build a path for an 'or'
		 * clause until all indexes have been matched against it.)
167 168
		 *
		 * We don't even think about special handling of 'or' clauses that
169 170
		 * involve more than one relation (ie, are join clauses). Can we
		 * do anything useful with those?
171
		 */
172
		match_index_orclauses(rel, index, restrictinfo_list);
173

174
		/*
175
		 * 2. Match the index against non-'or' restriction clauses.
176
		 */
177
		restrictclauses = group_clauses_by_indexkey(rel, index);
178

179
		/*
180 181
		 * 3. Compute pathkeys describing index's ordering, if any, then
		 * see how many of them are actually useful for this query.
182
		 */
183 184 185 186 187
		index_pathkeys = build_index_pathkeys(root, rel, index,
											  ForwardScanDirection);
		index_is_ordered = (index_pathkeys != NIL);
		useful_pathkeys = truncate_useless_pathkeys(root, rel,
													index_pathkeys);
188

189
		/*
190 191 192
		 * 4. Generate an indexscan path if there are relevant restriction
		 * clauses OR the index ordering is potentially useful for later
		 * merging or final output ordering.
193 194
		 *
		 * If there is a predicate, consider it anyway since the index
195 196
		 * predicate has already been found to match the query.  The
		 * selectivity of the predicate might alone make the index useful.
197
		 */
198 199 200
		if (restrictclauses != NIL ||
			useful_pathkeys != NIL ||
			index->indpred != NIL)
201 202
			add_path(rel, (Path *)
					 create_index_path(root, rel, index,
203
									   restrictclauses,
204 205 206 207 208 209
									   useful_pathkeys,
									   index_is_ordered ?
									   ForwardScanDirection :
									   NoMovementScanDirection));

		/*
210 211 212
		 * 5. If the index is ordered, a backwards scan might be
		 * interesting. Currently this is only possible for a DESC query
		 * result ordering.
213 214 215 216 217 218 219 220 221 222 223 224 225 226
		 */
		if (index_is_ordered)
		{
			index_pathkeys = build_index_pathkeys(root, rel, index,
												  BackwardScanDirection);
			useful_pathkeys = truncate_useless_pathkeys(root, rel,
														index_pathkeys);
			if (useful_pathkeys != NIL)
				add_path(rel, (Path *)
						 create_index_path(root, rel, index,
										   restrictclauses,
										   useful_pathkeys,
										   BackwardScanDirection));
		}
227 228

		/*
229 230 231 232 233
		 * 6. Examine join clauses to see which ones are potentially
		 * usable with this index, and generate a list of all other relids
		 * that participate in such join clauses.  We'll use this list later
		 * to recognize outer rels that are equivalent for joining purposes.
		 * We compute both per-index and overall-for-relation lists.
234
		 */
235 236 237 238
		join_outerrelids = indexable_outerrelids(rel, index);
		index->outer_relids = join_outerrelids;
		all_join_outerrelids = set_unioni(all_join_outerrelids,
										  join_outerrelids);
239
	}
240 241

	rel->index_outer_relids = all_join_outerrelids;
242 243 244 245
}


/****************************************************************************
246
 *		----  ROUTINES TO PROCESS 'OR' CLAUSES	----
247 248 249
 ****************************************************************************/


250
/*
251
 * match_index_orclauses
252
 *	  Attempt to match an index against subclauses within 'or' clauses.
253
 *	  Each subclause that does match is marked with the index's node.
254
 *
255 256 257 258 259 260
 *	  Essentially, this adds 'index' to the list of subclause indices in
 *	  the RestrictInfo field of each of the 'or' clauses where it matches.
 *	  NOTE: we can use storage in the RestrictInfo for this purpose because
 *	  this processing is only done on single-relation restriction clauses.
 *	  Therefore, we will never have indexes for more than one relation
 *	  mentioned in the same RestrictInfo node's list.
261
 *
262 263
 * 'rel' is the node of the relation on which the index is defined.
 * 'index' is the index node.
264
 * 'restrictinfo_list' is the list of available restriction clauses.
265 266
 */
static void
267
match_index_orclauses(RelOptInfo *rel,
268
					  IndexOptInfo *index,
269
					  List *restrictinfo_list)
270
{
271
	List	   *i;
272

273
	foreach(i, restrictinfo_list)
274
	{
275 276
		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);

277
		if (restriction_is_or_clause(restrictinfo))
278 279
		{
			/*
280 281
			 * Add this index to the subclause index list for each
			 * subclause that it matches.
282
			 */
283
			restrictinfo->subclauseindices =
284
				match_index_orclause(rel, index,
285
									 ((BoolExpr *) restrictinfo->clause)->args,
286
									 restrictinfo->subclauseindices);
287
		}
288 289 290
	}
}

291
/*
292
 * match_index_orclause
293 294 295
 *	  Attempts to match an index against the subclauses of an 'or' clause.
 *
 *	  A match means that:
296
 *	  (1) the operator within the subclause can be used with the
297
 *		  index's specified operator class, and
298
 *	  (2) one operand of the subclause matches the index key.
299
 *
300 301 302
 *	  If a subclause is an 'and' clause, then it matches if any of its
 *	  subclauses is an opclause that matches.
 *
303
 * 'or_clauses' is the list of subclauses within the 'or' clause
304
 * 'other_matching_indices' is the list of information on other indices
305 306
 *		that have already been matched to subclauses within this
 *		particular 'or' clause (i.e., a list previously generated by
307
 *		this routine), or NIL if this routine has not previously been
308
 *		run for this 'or' clause.
309
 *
310 311 312 313 314
 * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
 * a,b,c are nodes of indices that match the first subclause in
 * 'or-clauses', d,e,f match the second subclause, no indices
 * match the third, g,h match the fourth, etc.
 */
315
static List *
316
match_index_orclause(RelOptInfo *rel,
317
					 IndexOptInfo *index,
318 319
					 List *or_clauses,
					 List *other_matching_indices)
320
{
321 322
	List	   *matching_indices;
	List	   *index_list;
323
	List	   *clist;
324

325 326
	/*
	 * first time through, we create list of same length as OR clause,
327 328
	 * containing an empty sublist for each subclause.
	 */
Bruce Momjian's avatar
Bruce Momjian committed
329 330
	if (!other_matching_indices)
	{
331
		matching_indices = NIL;
Bruce Momjian's avatar
Bruce Momjian committed
332 333 334
		foreach(clist, or_clauses)
			matching_indices = lcons(NIL, matching_indices);
	}
335 336
	else
		matching_indices = other_matching_indices;
Bruce Momjian's avatar
Bruce Momjian committed
337 338

	index_list = matching_indices;
339

340
	foreach(clist, or_clauses)
341
	{
342
		Expr	   *clause = lfirst(clist);
343

344
		if (match_or_subclause_to_indexkey(rel, index, clause))
345
		{
346 347 348
			/* OK to add this index to sublist for this subclause */
			lfirst(matching_indices) = lcons(index,
											 lfirst(matching_indices));
349
		}
350

Bruce Momjian's avatar
Bruce Momjian committed
351
		matching_indices = lnext(matching_indices);
352
	}
353

354
	return index_list;
355 356
}

357 358 359 360
/*
 * See if a subclause of an OR clause matches an index.
 *
 * We accept the subclause if it is an operator clause that matches the
361 362 363
 * index, or if it is an AND clause any of whose members is an opclause
 * that matches the index.
 *
364 365 366 367 368
 * For multi-key indexes, we only look for matches to the first key;
 * without such a match the index is useless.  If the clause is an AND
 * then we may be able to extract additional subclauses to use with the
 * later indexkeys, but we need not worry about that until
 * extract_or_indexqual_conditions() is called (if it ever is).
369 370 371
 */
static bool
match_or_subclause_to_indexkey(RelOptInfo *rel,
372
							   IndexOptInfo *index,
373 374
							   Expr *clause)
{
375 376
	int			indexkey = index->indexkeys[0];
	Oid			opclass = index->classlist[0];
377

378 379 380 381
	if (and_clause((Node *) clause))
	{
		List	   *item;

382
		foreach(item, ((BoolExpr *) clause)->args)
383
		{
384
			if (match_clause_to_indexkey(rel, index, indexkey, opclass,
385
										 lfirst(item)))
386
				return true;
387
		}
388
		return false;
389 390
	}
	else
391
		return match_clause_to_indexkey(rel, index, indexkey, opclass,
392
										clause);
393 394
}

395
/*----------
396 397 398 399 400
 * Given an OR subclause that has previously been determined to match
 * the specified index, extract a list of specific opclauses that can be
 * used as indexquals.
 *
 * In the simplest case this just means making a one-element list of the
401
 * given opclause.	However, if the OR subclause is an AND, we have to
402 403
 * scan it to find the opclause(s) that match the index.  (There should
 * be at least one, if match_or_subclause_to_indexkey succeeded, but there
404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
 * could be more.)
 *
 * Also, we can look at other restriction clauses of the rel to discover
 * additional candidate indexquals: for example, consider
 *			... where (a = 11 or a = 12) and b = 42;
 * If we are dealing with an index on (a,b) then we can include the clause
 * b = 42 in the indexqual list generated for each of the OR subclauses.
 * Essentially, we are making an index-specific transformation from CNF to
 * DNF.  (NOTE: when we do this, we end up with a slightly inefficient plan
 * because create_indexscan_plan is not very bright about figuring out which
 * restriction clauses are implied by the generated indexqual condition.
 * Currently we'll end up rechecking both the OR clause and the transferred
 * restriction clause as qpquals.  FIXME someday.)
 *
 * Also, we apply expand_indexqual_conditions() to convert any special
 * matching opclauses to indexable operators.
420 421
 *
 * The passed-in clause is not changed.
422
 *----------
423 424 425 426 427 428
 */
List *
extract_or_indexqual_conditions(RelOptInfo *rel,
								IndexOptInfo *index,
								Expr *orsubclause)
{
429
	List	   *quals = NIL;
430 431
	int		   *indexkeys = index->indexkeys;
	Oid		   *classes = index->classlist;
432

433
	/*
434 435 436 437
	 * Extract relevant indexclauses in indexkey order.  This is
	 * essentially just like group_clauses_by_indexkey() except that the
	 * input and output are lists of bare clauses, not of RestrictInfo
	 * nodes.
438 439
	 */
	do
440
	{
441 442 443 444
		int			curIndxKey = indexkeys[0];
		Oid			curClass = classes[0];
		List	   *clausegroup = NIL;
		List	   *item;
445

446 447
		if (and_clause((Node *) orsubclause))
		{
448
			foreach(item, ((BoolExpr *) orsubclause)->args)
449
			{
450
				Expr	   *subsubclause = (Expr *) lfirst(item);
451

452 453
				if (match_clause_to_indexkey(rel, index,
											 curIndxKey, curClass,
454
											 subsubclause))
455 456 457 458 459
					clausegroup = lappend(clausegroup, subsubclause);
			}
		}
		else if (match_clause_to_indexkey(rel, index,
										  curIndxKey, curClass,
460
										  orsubclause))
461
			clausegroup = makeList1(orsubclause);
462

463 464 465 466 467 468 469
		/*
		 * If we found no clauses for this indexkey in the OR subclause
		 * itself, try looking in the rel's top-level restriction list.
		 */
		if (clausegroup == NIL)
		{
			foreach(item, rel->baserestrictinfo)
470
			{
471 472
				RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);

473 474
				if (match_clause_to_indexkey(rel, index,
											 curIndxKey, curClass,
475
											 rinfo->clause))
476
					clausegroup = lappend(clausegroup, rinfo->clause);
477
			}
478
		}
479

480
		/*
481 482
		 * If still no clauses match this key, we're done; we don't want
		 * to look at keys to its right.
483 484 485
		 */
		if (clausegroup == NIL)
			break;
486

487
		quals = nconc(quals, clausegroup);
488

489 490
		indexkeys++;
		classes++;
491 492

	} while (!DoneMatchingIndexKeys(indexkeys, classes));
493

494 495
	if (quals == NIL)
		elog(ERROR, "extract_or_indexqual_conditions: no matching clause");
496 497 498 499

	return expand_indexqual_conditions(quals);
}

500

501
/****************************************************************************
502
 *				----  ROUTINES TO CHECK RESTRICTIONS  ----
503 504 505
 ****************************************************************************/


506
/*
507
 * group_clauses_by_indexkey
508
 *	  Generates a list of restriction clauses that can be used with an index.
509
 *
510 511
 * 'rel' is the node of the relation itself.
 * 'index' is a index on 'rel'.
512
 *
513
 * Returns a list of all the RestrictInfo nodes for clauses that can be
514 515
 * used with this index.
 *
Tom Lane's avatar
Tom Lane committed
516
 * The list is ordered by index key.  (This is not depended on by any part
517
 * of the planner, so far as I can tell; but some parts of the executor
Tom Lane's avatar
Tom Lane committed
518 519 520
 * do assume that the indxqual list ultimately delivered to the executor
 * is so ordered.  One such place is _bt_orderkeys() in the btree support.
 * Perhaps that ought to be fixed someday --- tgl 7/00)
521
 *
522 523
 * Note that in a multi-key index, we stop if we find a key that cannot be
 * used with any clause.  For example, given an index on (A,B,C), we might
524 525 526
 * return (C1 C2 C3 C4) if we find that clauses C1 and C2 use column A,
 * clauses C3 and C4 use column B, and no clauses use column C.  But if
 * no clauses match B we will return (C1 C2), whether or not there are
527
 * clauses matching column C, because the executor couldn't use them anyway.
528
 */
529
static List *
530
group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index)
531
{
532
	List	   *clausegroup_list = NIL;
533 534 535
	List	   *restrictinfo_list = rel->baserestrictinfo;
	int		   *indexkeys = index->indexkeys;
	Oid		   *classes = index->classlist;
536

537
	if (restrictinfo_list == NIL)
538
		return NIL;
539

540
	do
541
	{
542 543 544
		int			curIndxKey = indexkeys[0];
		Oid			curClass = classes[0];
		List	   *clausegroup = NIL;
545
		List	   *i;
546

547
		foreach(i, restrictinfo_list)
548
		{
549
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
550 551 552 553 554

			if (match_clause_to_indexkey(rel,
										 index,
										 curIndxKey,
										 curClass,
555
										 rinfo->clause))
556
				clausegroup = lappend(clausegroup, rinfo);
557
		}
558

559 560 561
		/*
		 * If no clauses match this key, we're done; we don't want to look
		 * at keys to its right.
562 563
		 */
		if (clausegroup == NIL)
564
			break;
565

566
		clausegroup_list = nconc(clausegroup_list, clausegroup);
567 568 569 570

		indexkeys++;
		classes++;

571
	} while (!DoneMatchingIndexKeys(indexkeys, classes));
572

573
	/* clausegroup_list holds all matched clauses ordered by indexkeys */
574
	return clausegroup_list;
575 576
}

577
/*
578 579
 * group_clauses_by_indexkey_for_join
 *	  Generates a list of clauses that can be used with an index
580
 *	  to scan the inner side of a nestloop join.
581
 *
582
 * This is much like group_clauses_by_indexkey(), but we consider both
583 584 585 586 587 588
 * join and restriction clauses.  Any joinclause that uses only otherrels
 * in the specified outer_relids is fair game.  But there must be at least
 * one such joinclause in the final list, otherwise we return NIL indicating
 * that this index isn't interesting as an inner indexscan.  (A scan using
 * only restriction clauses shouldn't be created here, because a regular Path
 * will already have been generated for it.)
589
 */
590
static List *
591 592
group_clauses_by_indexkey_for_join(RelOptInfo *rel, IndexOptInfo *index,
								   Relids outer_relids, bool isouterjoin)
593
{
594
	List	   *clausegroup_list = NIL;
595
	bool		jfound = false;
596 597
	int		   *indexkeys = index->indexkeys;
	Oid		   *classes = index->classlist;
598

599
	do
600
	{
601 602 603
		int			curIndxKey = indexkeys[0];
		Oid			curClass = classes[0];
		List	   *clausegroup = NIL;
604
		List	   *i;
605

606 607
		/* Look for joinclauses that are usable with given outer_relids */
		foreach(i, rel->joininfo)
608
		{
609 610
			JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
			List	   *j;
611

612 613 614 615
			if (!is_subseti(joininfo->unjoined_relids, outer_relids))
				continue;

			foreach(j, joininfo->jinfo_restrictinfo)
616
			{
617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
				RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);

				/* Can't use pushed-down clauses in outer join */
				if (isouterjoin && rinfo->ispusheddown)
					continue;

				if (match_join_clause_to_indexkey(rel,
												  index,
												  curIndxKey,
												  curClass,
												  rinfo->clause))
				{
					clausegroup = lappend(clausegroup, rinfo);
					jfound = true;
				}
632
			}
633
		}
634 635 636

		/* We can also use plain restriction clauses for the rel */
		foreach(i, rel->baserestrictinfo)
637
		{
638 639 640 641 642
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);

			/* Can't use pushed-down clauses in outer join */
			if (isouterjoin && rinfo->ispusheddown)
				continue;
643 644 645 646 647

			if (match_clause_to_indexkey(rel,
										 index,
										 curIndxKey,
										 curClass,
648
										 rinfo->clause))
649
				clausegroup = lappend(clausegroup, rinfo);
650
		}
651

652 653 654
		/*
		 * If no clauses match this key, we're done; we don't want to look
		 * at keys to its right.
655 656
		 */
		if (clausegroup == NIL)
657 658
			break;

659
		clausegroup_list = nconc(clausegroup_list, clausegroup);
660 661 662

		indexkeys++;
		classes++;
663

664
	} while (!DoneMatchingIndexKeys(indexkeys, classes));
665

666
	/*
667
	 * if no join clause was matched then forget it, per comments above.
668 669
	 */
	if (!jfound)
670
	{
671 672
		freeList(clausegroup_list);
		return NIL;
673
	}
674 675 676

	/* clausegroup_list holds all matched clauses ordered by indexkeys */
	return clausegroup_list;
677 678
}

679

680
/*
681
 * match_clause_to_indexkey()
682
 *	  Determines whether a restriction clause matches a key of an index.
683
 *
684
 *	  To match, the clause:
685
 *
686 687
 *	  (1)  must be in the form (indexkey op const) or (const op indexkey);
 *		   and
688 689 690
 *	  (2)  must contain an operator which is in the same class as the index
 *		   operator for this key, or is a "special" operator as recognized
 *		   by match_special_index_operator().
691
 *
692 693 694 695 696
 *	  Presently, the executor can only deal with indexquals that have the
 *	  indexkey on the left, so we can only use clauses that have the indexkey
 *	  on the right if we can commute the clause to put the key on the left.
 *	  We do not actually do the commuting here, but we check whether a
 *	  suitable commutator operator is available.
697
 *
698 699 700
 * 'rel' is the relation of interest.
 * 'index' is an index on 'rel'.
 * 'indexkey' is a key of 'index'.
701
 * 'opclass' is the corresponding operator class.
702
 * 'clause' is the clause to be tested.
703
 *
704 705
 * Returns true if the clause can be used with this index key.
 *
706 707
 * NOTE:  returns false if clause is an OR or AND clause; it is the
 * responsibility of higher-level routines to cope with those.
708
 */
709
static bool
710
match_clause_to_indexkey(RelOptInfo *rel,
711
						 IndexOptInfo *index,
712
						 int indexkey,
713
						 Oid opclass,
714
						 Expr *clause)
715
{
716 717
	Var		   *leftop,
			   *rightop;
718

719
	/* Clause must be a binary opclause. */
720
	if (!is_opclause(clause))
721
		return false;
722 723
	leftop = get_leftop(clause);
	rightop = get_rightop(clause);
724
	if (!leftop || !rightop)
725
		return false;
726

727 728 729 730 731 732 733
	/*
	 * Check for clauses of the form:
	 *		(indexkey operator constant) or (constant operator indexkey).
	 * Anything that is a "pseudo constant" expression will do.
	 */
	if (match_index_to_operand(indexkey, leftop, rel, index) &&
		is_pseudo_constant_clause((Node *) rightop))
734
	{
735 736 737
		if (is_indexable_operator(clause, opclass, true))
			return true;

738
		/*
739 740
		 * If we didn't find a member of the index's opclass, see
		 * whether it is a "special" indexable operator.
741
		 */
742 743 744 745
		if (match_special_index_operator(clause, opclass, true))
			return true;
		return false;
	}
Bruce Momjian's avatar
Bruce Momjian committed
746

747 748 749 750 751
	if (match_index_to_operand(indexkey, rightop, rel, index) &&
		is_pseudo_constant_clause((Node *) leftop))
	{
		if (is_indexable_operator(clause, opclass, false))
			return true;
752

753 754 755 756 757 758 759 760
		/*
		 * If we didn't find a member of the index's opclass, see
		 * whether it is a "special" indexable operator.
		 */
		if (match_special_index_operator(clause, opclass, false))
			return true;
		return false;
	}
761

762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807
	return false;
}

/*
 * match_join_clause_to_indexkey()
 *	  Determines whether a join clause matches a key of an index.
 *
 *	  To match, the clause:
 *
 *	  (1)  must be in the form (indexkey op others) or (others op indexkey),
 *		   where others is an expression involving only vars of the other
 *		   relation(s); and
 *	  (2)  must contain an operator which is in the same class as the index
 *		   operator for this key, or is a "special" operator as recognized
 *		   by match_special_index_operator().
 *
 *	  As above, we must be able to commute the clause to put the indexkey
 *	  on the left.
 *
 *	  Note that we already know that the clause as a whole uses vars from
 *	  the interesting set of relations.  But we need to defend against
 *	  expressions like (a.f1 OP (b.f2 OP a.f3)); that's not processable by
 *	  an indexscan nestloop join, whereas (a.f1 OP (b.f2 OP c.f3)) is.
 *
 * 'rel' is the relation of interest.
 * 'index' is an index on 'rel'.
 * 'indexkey' is a key of 'index'.
 * 'opclass' is the corresponding operator class.
 * 'clause' is the clause to be tested.
 *
 * Returns true if the clause can be used with this index key.
 *
 * NOTE:  returns false if clause is an OR or AND clause; it is the
 * responsibility of higher-level routines to cope with those.
 */
static bool
match_join_clause_to_indexkey(RelOptInfo *rel,
							  IndexOptInfo *index,
							  int indexkey,
							  Oid opclass,
							  Expr *clause)
{
	Var		   *leftop,
			   *rightop;

	/* Clause must be a binary opclause. */
808
	if (!is_opclause(clause))
809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
		return false;
	leftop = get_leftop(clause);
	rightop = get_rightop(clause);
	if (!leftop || !rightop)
		return false;

	/*
	 * Check for an indexqual that could be handled by a nestloop
	 * join. We need the index key to be compared against an
	 * expression that uses none of the indexed relation's vars and
	 * contains no volatile functions.
	 */
	if (match_index_to_operand(indexkey, leftop, rel, index))
	{
		List	   *othervarnos = pull_varnos((Node *) rightop);
		bool		isIndexable;

		isIndexable =
			!intMember(lfirsti(rel->relids), othervarnos) &&
			!contain_volatile_functions((Node *) rightop) &&
			is_indexable_operator(clause, opclass, true);
		freeList(othervarnos);
		return isIndexable;
832
	}
833 834

	if (match_index_to_operand(indexkey, rightop, rel, index))
835
	{
836 837 838 839 840 841 842 843 844
		List	   *othervarnos = pull_varnos((Node *) leftop);
		bool		isIndexable;

		isIndexable =
			!intMember(lfirsti(rel->relids), othervarnos) &&
			!contain_volatile_functions((Node *) leftop) &&
			is_indexable_operator(clause, opclass, false);
		freeList(othervarnos);
		return isIndexable;
845
	}
846

847 848
	return false;
}
849

850 851
/*
 * indexable_operator
852
 *	  Does a binary opclause contain an operator matching the index opclass?
853
 *
854 855
 * If the indexkey is on the right, what we actually want to know
 * is whether the operator has a commutator operator that matches
856
 * the index's opclass.
857
 *
858
 * Returns the OID of the matching operator, or InvalidOid if no match.
859 860
 * (Formerly, this routine might return a binary-compatible operator
 * rather than the original one, but that kluge is history.)
861
 */
862
static Oid
863
indexable_operator(Expr *clause, Oid opclass, bool indexkey_on_left)
864
{
865
	Oid			expr_op = ((OpExpr *) clause)->opno;
866
	Oid			commuted_op;
867 868 869 870 871 872 873

	/* Get the commuted operator if necessary */
	if (indexkey_on_left)
		commuted_op = expr_op;
	else
		commuted_op = get_commutator(expr_op);
	if (commuted_op == InvalidOid)
874
		return InvalidOid;
875

876
	/* OK if the (commuted) operator is a member of the index's opclass */
877
	if (op_in_opclass(commuted_op, opclass))
878
		return expr_op;
879

880
	return InvalidOid;
881 882 883
}

/****************************************************************************
884
 *				----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS	----
885 886
 ****************************************************************************/

887
/*
888
 * pred_test
889
 *	  Does the "predicate inclusion test" for partial indexes.
890
 *
891
 *	  Recursively checks whether the clauses in restrictinfo_list imply
892
 *	  that the given predicate is true.
893
 *
894 895 896 897
 *	  This routine (together with the routines it calls) iterates over
 *	  ANDs in the predicate first, then reduces the qualification
 *	  clauses down to their constituent terms, and iterates over ORs
 *	  in the predicate last.  This order is important to make the test
898 899
 *	  succeed whenever possible (assuming the predicate has been converted
 *	  to CNF format). --Nels, Jan '93
900
 */
901
static bool
902 903
pred_test(List *predicate_list, List *restrictinfo_list, List *joininfo_list,
		  int relvarno)
904
{
905
	List	   *pred;
906 907 908 909 910 911 912 913

	/*
	 * Note: if Postgres tried to optimize queries by forming equivalence
	 * classes over equi-joined attributes (i.e., if it recognized that a
	 * qualification such as "where a.b=c.d and a.b=5" could make use of
	 * an index on c.d), then we could use that equivalence class info
	 * here with joininfo_list to do more complete tests for the usability
	 * of a partial index.	For now, the test only uses restriction
914
	 * clauses (those in restrictinfo_list). --Nels, Dec '92
915 916 917
	 *
	 * XXX as of 7.1, equivalence class info *is* available.  Consider
	 * improving this code as foreseen by Nels.
918 919
	 */

920
	if (predicate_list == NIL)
921
		return true;			/* no predicate: the index is usable */
922
	if (restrictinfo_list == NIL)
923 924 925
		return false;			/* no restriction clauses: the test must
								 * fail */

926 927 928 929 930 931 932 933 934 935 936 937
	/*
	 * The predicate as stored in the index definition will use varno 1
	 * for its Vars referencing the indexed relation.  If the indexed
	 * relation isn't varno 1 in the query, we must adjust the predicate
	 * to make the Vars match, else equal() won't work.
	 */
	if (relvarno != 1)
	{
		predicate_list = copyObject(predicate_list);
		ChangeVarNodes((Node *) predicate_list, 1, relvarno, 0);
	}

938 939 940 941
	foreach(pred, predicate_list)
	{
		/*
		 * if any clause is not implied, the whole predicate is not
942 943
		 * implied.  Note we assume that any sub-ANDs have been flattened
		 * when the predicate was fed through canonicalize_qual().
944
		 */
945
		if (!pred_test_restrict_list(lfirst(pred), restrictinfo_list))
946
			return false;
947
	}
948
	return true;
949 950 951
}


952
/*
953
 * pred_test_restrict_list
954 955
 *	  Does the "predicate inclusion test" for one conjunct of a predicate
 *	  expression.
956
 */
957
static bool
958
pred_test_restrict_list(Expr *predicate, List *restrictinfo_list)
959
{
960
	List	   *item;
961

962
	foreach(item, restrictinfo_list)
963
	{
964 965
		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(item);

966
		/* if any clause implies the predicate, return true */
967 968
		if (pred_test_recurse_clause(predicate,
									 (Node *) restrictinfo->clause))
969 970 971
			return true;
	}
	return false;
972 973 974
}


975
/*
976
 * pred_test_recurse_clause
977
 *	  Does the "predicate inclusion test" for a general restriction-clause
978 979
 *	  expression.  Here we recursively deal with the possibility that the
 *	  restriction clause is itself an AND or OR structure.
980
 */
981
static bool
982
pred_test_recurse_clause(Expr *predicate, Node *clause)
983
{
984 985
	List	   *items,
			   *item;
986

987 988
	Assert(clause != NULL);
	if (or_clause(clause))
989
	{
990
		items = ((BoolExpr *) clause)->args;
991 992 993
		foreach(item, items)
		{
			/* if any OR item doesn't imply the predicate, clause doesn't */
994
			if (!pred_test_recurse_clause(predicate, lfirst(item)))
995 996 997 998 999 1000
				return false;
		}
		return true;
	}
	else if (and_clause(clause))
	{
1001
		items = ((BoolExpr *) clause)->args;
1002 1003 1004 1005 1006 1007
		foreach(item, items)
		{
			/*
			 * if any AND item implies the predicate, the whole clause
			 * does
			 */
1008
			if (pred_test_recurse_clause(predicate, lfirst(item)))
1009 1010
				return true;
		}
1011 1012
		return false;
	}
1013
	else
1014
		return pred_test_recurse_pred(predicate, clause);
1015 1016 1017
}


1018
/*
1019
 * pred_test_recurse_pred
1020
 *	  Does the "predicate inclusion test" for one conjunct of a predicate
1021 1022 1023
 *	  expression for a simple restriction clause.  Here we recursively deal
 *	  with the possibility that the predicate conjunct is itself an AND or
 *	  OR structure.
1024
 */
1025
static bool
1026
pred_test_recurse_pred(Expr *predicate, Node *clause)
1027
{
1028 1029
	List	   *items,
			   *item;
1030

1031 1032
	Assert(predicate != NULL);
	if (or_clause((Node *) predicate))
1033
	{
1034
		items = ((BoolExpr *) predicate)->args;
1035 1036 1037
		foreach(item, items)
		{
			/* if any item is implied, the whole predicate is implied */
1038
			if (pred_test_recurse_pred(lfirst(item), clause))
1039 1040 1041 1042 1043 1044
				return true;
		}
		return false;
	}
	else if (and_clause((Node *) predicate))
	{
1045
		items = ((BoolExpr *) predicate)->args;
1046 1047 1048 1049 1050 1051
		foreach(item, items)
		{
			/*
			 * if any item is not implied, the whole predicate is not
			 * implied
			 */
1052
			if (!pred_test_recurse_pred(lfirst(item), clause))
1053 1054
				return false;
		}
1055 1056
		return true;
	}
1057
	else
1058
		return pred_test_simple_clause(predicate, clause);
1059 1060 1061 1062 1063
}


/*
 * Define an "operator implication table" for btree operators ("strategies").
1064
 * The "strategy numbers" are:	(1) <	(2) <=	 (3) =	 (4) >=   (5) >
1065 1066 1067
 *
 * The interpretation of:
 *
1068
 *		test_op = BT_implic_table[given_op-1][target_op-1]
1069 1070 1071 1072
 *
 * where test_op, given_op and target_op are strategy numbers (from 1 to 5)
 * of btree operators, is as follows:
 *
1073 1074 1075 1076 1077
 *	 If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
 *	 want to determine whether "ATTR target_op CONST2" must also be true, then
 *	 you can use "CONST1 test_op CONST2" as a test.  If this test returns true,
 *	 then the target expression must be true; if the test returns false, then
 *	 the target expression may be false.
1078 1079 1080 1081 1082
 *
 * An entry where test_op==0 means the implication cannot be determined, i.e.,
 * this test should always be considered false.
 */

1083
static const StrategyNumber
1084
			BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
1085 1086 1087 1088 1089
	{2, 2, 0, 0, 0},
	{1, 2, 0, 0, 0},
	{1, 2, 3, 4, 5},
	{0, 0, 0, 4, 5},
	{0, 0, 0, 4, 4}
1090 1091 1092
};


1093
/*
1094
 * pred_test_simple_clause
1095
 *	  Does the "predicate inclusion test" for a "simple clause" predicate
1096 1097 1098
 *	  and a "simple clause" restriction.
 *
 *	  We have two strategies for determining whether one simple clause
1099
 *	  implies another.	A simple and general way is to see if they are
1100 1101
 *	  equal(); this works for any kind of expression.  (Actually, there
 *	  is an implied assumption that the functions in the expression are
1102
 *	  immutable, ie dependent only on their input arguments --- but this
1103 1104 1105 1106 1107 1108
 *	  was checked for the predicate by CheckPredicate().)
 *
 *	  Our other way works only for (binary boolean) operators that are
 *	  in some btree operator class.  We use the above operator implication
 *	  table to be able to derive implications between nonidentical clauses.
 *
1109 1110
 *	  Eventually, rtree operators could also be handled by defining an
 *	  appropriate "RT_implic_table" array.
1111
 */
1112
static bool
1113
pred_test_simple_clause(Expr *predicate, Node *clause)
1114
{
1115 1116 1117 1118 1119 1120 1121
	Var		   *pred_var,
			   *clause_var;
	Const	   *pred_const,
			   *clause_const;
	Oid			pred_op,
				clause_op,
				test_op;
1122 1123
	Oid			opclass_id = InvalidOid;
	StrategyNumber pred_strategy = 0,
1124 1125 1126
				clause_strategy,
				test_strategy;
	Expr	   *test_expr;
1127
	ExprState  *test_exprstate;
1128 1129
	Datum		test_result;
	bool		isNull;
1130 1131 1132
	Relation	relation;
	HeapScanDesc scan;
	HeapTuple	tuple;
1133
	ScanKeyData entry[1];
1134
	Form_pg_amop aform;
1135 1136
	EState	   *estate;
	MemoryContext oldcontext;
1137

1138 1139 1140
	/* First try the equal() test */
	if (equal((Node *) predicate, clause))
		return true;
1141

1142
	/*
1143 1144
	 * Can't do anything more unless they are both binary opclauses with a
	 * Var on the left and a Const on the right.
1145
	 */
1146
	if (!is_opclause(predicate))
1147
		return false;
1148 1149
	pred_var = (Var *) get_leftop(predicate);
	pred_const = (Const *) get_rightop(predicate);
1150 1151 1152

	if (!is_opclause(clause))
		return false;
1153 1154 1155
	clause_var = (Var *) get_leftop((Expr *) clause);
	clause_const = (Const *) get_rightop((Expr *) clause);

1156
	if (!IsA(clause_var, Var) ||
1157
		clause_const == NULL ||
1158 1159
		!IsA(clause_const, Const) ||
		!IsA(pred_var, Var) ||
1160
		pred_const == NULL ||
1161 1162
		!IsA(pred_const, Const))
		return false;
1163

1164 1165 1166 1167
	/*
	 * The implication can't be determined unless the predicate and the
	 * clause refer to the same attribute.
	 */
1168 1169
	if (clause_var->varno != pred_var->varno ||
		clause_var->varattno != pred_var->varattno)
1170
		return false;
1171

1172
	/* Get the operators for the two clauses we're comparing */
1173 1174
	pred_op = ((OpExpr *) predicate)->opno;
	clause_op = ((OpExpr *) clause)->opno;
1175

1176 1177
	/*
	 * 1. Find a "btree" strategy number for the pred_op
1178
	 *
1179 1180
	 * The following assumes that any given operator will only be in a single
	 * btree operator class.  This is true at least for all the
1181 1182 1183 1184 1185
	 * pre-defined operator classes.  If it isn't true, then whichever
	 * operator class happens to be returned first for the given operator
	 * will be used to find the associated strategy numbers for the test.
	 * --Nels, Jan '93
	 */
1186 1187 1188 1189 1190 1191
	ScanKeyEntryInitialize(&entry[0], 0x0,
						   Anum_pg_amop_amopopr,
						   F_OIDEQ,
						   ObjectIdGetDatum(pred_op));

	relation = heap_openr(AccessMethodOperatorRelationName, AccessShareLock);
1192
	scan = heap_beginscan(relation, SnapshotNow, 1, entry);
1193

1194
	while ((tuple = heap_getnext(scan, ForwardScanDirection)) != NULL)
1195
	{
1196 1197 1198 1199 1200 1201
		aform = (Form_pg_amop) GETSTRUCT(tuple);
		if (opclass_is_btree(aform->amopclaid))
		{
			/* Get the predicate operator's btree strategy number (1 to 5) */
			pred_strategy = (StrategyNumber) aform->amopstrategy;
			Assert(pred_strategy >= 1 && pred_strategy <= 5);
1202 1203 1204 1205 1206

			/*
			 * Remember which operator class this strategy number came
			 * from
			 */
1207 1208 1209
			opclass_id = aform->amopclaid;
			break;
		}
1210
	}
1211

1212
	heap_endscan(scan);
1213 1214 1215 1216 1217 1218 1219
	heap_close(relation, AccessShareLock);

	if (!OidIsValid(opclass_id))
	{
		/* predicate operator isn't btree-indexable */
		return false;
	}
1220

1221 1222 1223
	/*
	 * 2. From the same opclass, find a strategy num for the clause_op
	 */
1224 1225 1226 1227
	tuple = SearchSysCache(AMOPOPID,
						   ObjectIdGetDatum(opclass_id),
						   ObjectIdGetDatum(clause_op),
						   0, 0);
1228 1229
	if (!HeapTupleIsValid(tuple))
	{
1230
		/* clause operator isn't btree-indexable, or isn't in this opclass */
1231 1232
		return false;
	}
1233
	aform = (Form_pg_amop) GETSTRUCT(tuple);
1234

1235
	/* Get the restriction clause operator's strategy number (1 to 5) */
1236
	clause_strategy = (StrategyNumber) aform->amopstrategy;
1237
	Assert(clause_strategy >= 1 && clause_strategy <= 5);
1238

1239
	ReleaseSysCache(tuple);
1240

1241 1242 1243 1244 1245
	/*
	 * 3. Look up the "test" strategy number in the implication table
	 */
	test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
	if (test_strategy == 0)
1246
	{
1247
		return false;			/* the implication cannot be determined */
1248
	}
1249

1250 1251 1252
	/*
	 * 4. From the same opclass, find the operator for the test strategy
	 */
1253 1254 1255 1256
	tuple = SearchSysCache(AMOPSTRATEGY,
						   ObjectIdGetDatum(opclass_id),
						   Int16GetDatum(test_strategy),
						   0, 0);
1257 1258
	if (!HeapTupleIsValid(tuple))
	{
1259
		/* this probably shouldn't fail? */
1260
		elog(DEBUG1, "pred_test_simple_clause: unknown test_op");
1261 1262
		return false;
	}
1263
	aform = (Form_pg_amop) GETSTRUCT(tuple);
1264 1265

	/* Get the test operator */
1266
	test_op = aform->amopopr;
1267

1268
	ReleaseSysCache(tuple);
1269 1270

	/*
1271
	 * 5. Evaluate the test.  For this we need an EState.
1272
	 */
1273 1274 1275 1276 1277 1278
	estate = CreateExecutorState();

	/* We can use the estate's working context to avoid memory leaks. */
	oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);

	/* Build expression tree */
1279 1280 1281 1282 1283
	test_expr = make_opclause(test_op,
							  BOOLOID,
							  false,
							  (Expr *) clause_const,
							  (Expr *) pred_const);
1284

1285 1286 1287 1288 1289 1290
	/* Prepare it for execution */
	test_exprstate = ExecPrepareExpr(test_expr, estate);

	/* And execute it. */
	test_result = ExecEvalExprSwitchContext(test_exprstate,
											GetPerTupleExprContext(estate),
1291
											&isNull, NULL);
1292 1293 1294 1295 1296 1297

	/* Get back to outer memory context */
	MemoryContextSwitchTo(oldcontext);

	/* Release all the junk we just created */
	FreeExecutorState(estate);
1298

1299 1300
	if (isNull)
	{
1301
		elog(DEBUG1, "pred_test_simple_clause: null test result");
1302 1303
		return false;
	}
1304
	return DatumGetBool(test_result);
1305 1306 1307 1308
}


/****************************************************************************
1309
 *				----  ROUTINES TO CHECK JOIN CLAUSES  ----
1310 1311
 ****************************************************************************/

1312
/*
1313 1314 1315
 * indexable_outerrelids
 *	  Finds all other relids that participate in any indexable join clause
 *	  for the specified index.  Returns a list of relids.
1316
 *
1317
 * 'rel' is the relation for which 'index' is defined
1318
 */
1319 1320
static Relids
indexable_outerrelids(RelOptInfo *rel, IndexOptInfo *index)
1321
{
1322
	Relids		outer_relids = NIL;
1323
	List	   *i;
1324

1325
	foreach(i, rel->joininfo)
1326
	{
1327
		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
1328 1329
		bool		match_found = false;
		List	   *j;
1330

1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343
		/*
		 * Examine each joinclause in the JoinInfo node's list to see if
		 * it matches any key of the index.  If so, add the JoinInfo's
		 * otherrels to the result.  We can skip examining other joinclauses
		 * in the same list as soon as we find a match (since by definition
		 * they all have the same otherrels).
		 */
		foreach(j, joininfo->jinfo_restrictinfo)
		{
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
			Expr   *clause = rinfo->clause;
			int	   *indexkeys = index->indexkeys;
			Oid	   *classes = index->classlist;
1344

1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369
			do
			{
				int			curIndxKey = indexkeys[0];
				Oid			curClass = classes[0];

				if (match_join_clause_to_indexkey(rel,
												  index,
												  curIndxKey,
												  curClass,
												  clause))
				{
					match_found = true;
					break;
				}

				indexkeys++;
				classes++;

			} while (!DoneMatchingIndexKeys(indexkeys, classes));

			if (match_found)
				break;
		}

		if (match_found)
1370
		{
1371 1372
			outer_relids = set_unioni(outer_relids,
									  joininfo->unjoined_relids);
1373
		}
1374
	}
1375

1376
	return outer_relids;
1377 1378
}

1379
/*
1380 1381 1382 1383
 * best_inner_indexscan
 *	  Finds the best available inner indexscan for a nestloop join
 *	  with the given rel on the inside and the given outer_relids outside.
 *	  May return NULL if there are no possible inner indexscans.
1384
 *
1385 1386 1387 1388 1389 1390
 * We ignore ordering considerations (since a nestloop's inner scan's order
 * is uninteresting).  Also, we consider only total cost when deciding which
 * of two possible paths is better --- this assumes that all indexpaths have
 * negligible startup cost.  (True today, but someday we might have to think
 * harder.)  Therefore, there is only one dimension of comparison and so it's
 * sufficient to return a single "best" path.
1391
 */
1392 1393 1394
Path *
best_inner_indexscan(Query *root, RelOptInfo *rel,
					 Relids outer_relids, JoinType jointype)
1395
{
1396 1397 1398 1399 1400
	Path	   *cheapest = NULL;
	bool		isouterjoin;
	List	   *ilist;
	List	   *jlist;
	InnerIndexscanInfo *info;
1401
	MemoryContext oldcontext;
1402

1403 1404 1405 1406
	/*
	 * Nestloop only supports inner and left joins.
	 */
	switch (jointype)
1407
	{
1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421
		case JOIN_INNER:
			isouterjoin = false;
			break;
		case JOIN_LEFT:
			isouterjoin = true;
			break;
		default:
			return NULL;
	}
	/*
	 * If there are no indexable joinclauses for this rel, exit quickly.
	 */
	if (!rel->index_outer_relids)
		return NULL;
1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433
	/*
	 * Otherwise, we have to do path selection in the memory context of
	 * the given rel, so that any created path can be safely attached to
	 * the rel's cache of best inner paths.  (This is not currently an
	 * issue for normal planning, but it is an issue for GEQO planning.)
	 */
	oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
	/*
	 * Intersect the given outer_relids with index_outer_relids
	 * to find the set of outer relids actually relevant for this index.
	 * If there are none, again we can fail immediately.
	 */
1434 1435
	outer_relids = set_intersecti(rel->index_outer_relids, outer_relids);
	if (!outer_relids)
1436 1437
	{
		MemoryContextSwitchTo(oldcontext);
1438
		return NULL;
1439
	}
1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452
	/*
	 * Look to see if we already computed the result for this set of
	 * relevant outerrels.  (We include the isouterjoin status in the
	 * cache lookup key for safety.  In practice I suspect this is not
	 * necessary because it should always be the same for a given innerrel.)
	 */
	foreach(jlist, rel->index_inner_paths)
	{
		info = (InnerIndexscanInfo *) lfirst(jlist);
		if (sameseti(info->other_relids, outer_relids) &&
			info->isouterjoin == isouterjoin)
		{
			freeList(outer_relids);
1453
			MemoryContextSwitchTo(oldcontext);
1454 1455 1456
			return info->best_innerpath;
		}
	}
1457

1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477
	/*
	 * For each index of the rel, find the best path; then choose the
	 * best overall.  We cache the per-index results as well as the overall
	 * result.  (This is useful because different indexes may have different
	 * relevant outerrel sets, so different overall outerrel sets might still
	 * map to the same computation for a given index.)
	 */
	foreach(ilist, rel->indexlist)
	{
		IndexOptInfo  *index = (IndexOptInfo *) lfirst(ilist);
		Relids		index_outer_relids;
		Path	   *path = NULL;

		/* skip quickly if index has no useful join clauses */
		if (!index->outer_relids)
			continue;
		/* identify set of relevant outer relids for this index */
		index_outer_relids = set_intersecti(index->outer_relids, outer_relids);
		if (!index_outer_relids)
			continue;
1478
		/*
1479
		 * Look to see if we already computed the result for this index.
1480
		 */
1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491
		foreach(jlist, index->inner_paths)
		{
			info = (InnerIndexscanInfo *) lfirst(jlist);
			if (sameseti(info->other_relids, index_outer_relids) &&
				info->isouterjoin == isouterjoin)
			{
				path = info->best_innerpath;
				freeList(index_outer_relids); /* not needed anymore */
				break;
			}
		}
Bruce Momjian's avatar
Bruce Momjian committed
1492

1493
		if (jlist == NIL)		/* failed to find a match? */
1494
		{
1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511
			List	   *clausegroup;

			/* find useful clauses for this index and outerjoin set */
			clausegroup = group_clauses_by_indexkey_for_join(rel,
															 index,
															 index_outer_relids,
															 isouterjoin);
			if (clausegroup)
			{
				/* remove duplicate and redundant clauses */
				clausegroup = remove_redundant_join_clauses(root,
															clausegroup,
															jointype);
				/* make the path */
				path = make_innerjoin_index_path(root, rel, index,
												 clausegroup);
			}
1512

1513 1514 1515 1516 1517 1518
			/* Cache the result --- whether positive or negative */
			info = makeNode(InnerIndexscanInfo);
			info->other_relids = index_outer_relids;
			info->isouterjoin = isouterjoin;
			info->best_innerpath = path;
			index->inner_paths = lcons(info, index->inner_paths);
1519 1520
		}

1521 1522 1523 1524 1525
		if (path != NULL &&
			(cheapest == NULL ||
			 compare_path_costs(path, cheapest, TOTAL_COST) < 0))
			cheapest = path;
	}
1526

1527 1528 1529 1530 1531 1532
	/* Cache the result --- whether positive or negative */
	info = makeNode(InnerIndexscanInfo);
	info->other_relids = outer_relids;
	info->isouterjoin = isouterjoin;
	info->best_innerpath = cheapest;
	rel->index_inner_paths = lcons(info, rel->index_inner_paths);
1533

1534 1535
	MemoryContextSwitchTo(oldcontext);

1536 1537
	return cheapest;
}
1538

1539 1540 1541
/****************************************************************************
 *				----  PATH CREATION UTILITIES  ----
 ****************************************************************************/
1542

1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557
/*
 * make_innerjoin_index_path
 *	  Create an index path node for a path to be used as an inner
 *	  relation in a nestloop join.
 *
 * 'rel' is the relation for which 'index' is defined
 * 'clausegroup' is a list of restrictinfo nodes that can use 'index'
 */
static Path *
make_innerjoin_index_path(Query *root,
						  RelOptInfo *rel, IndexOptInfo *index,
						  List *clausegroup)
{
	IndexPath  *pathnode = makeNode(IndexPath);
	List	   *indexquals;
1558

1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610
	/* XXX this code ought to be merged with create_index_path? */

	pathnode->path.pathtype = T_IndexScan;
	pathnode->path.parent = rel;

	/*
	 * There's no point in marking the path with any pathkeys, since
	 * it will only ever be used as the inner path of a nestloop, and
	 * so its ordering does not matter.
	 */
	pathnode->path.pathkeys = NIL;

	/* Extract bare indexqual clauses from restrictinfos */
	indexquals = get_actual_clauses(clausegroup);

	/* expand special operators to indexquals the executor can handle */
	indexquals = expand_indexqual_conditions(indexquals);

	/*
	 * Note that we are making a pathnode for a single-scan indexscan;
	 * therefore, both indexinfo and indexqual should be single-element lists.
	 */
	pathnode->indexinfo = makeList1(index);
	pathnode->indexqual = makeList1(indexquals);

	/* We don't actually care what order the index scans in ... */
	pathnode->indexscandir = NoMovementScanDirection;

	/*
	 * We must compute the estimated number of output rows for the
	 * indexscan.  This is less than rel->rows because of the
	 * additional selectivity of the join clauses.	Since clausegroup
	 * may contain both restriction and join clauses, we have to do a
	 * set union to get the full set of clauses that must be
	 * considered to compute the correct selectivity.  (We can't just
	 * nconc the two lists; then we might have some restriction
	 * clauses appearing twice, which'd mislead
	 * restrictlist_selectivity into double-counting their
	 * selectivity.)
	 */
	pathnode->rows = rel->tuples *
		restrictlist_selectivity(root,
								 set_union(rel->baserestrictinfo,
										   clausegroup),
								 lfirsti(rel->relids));
	/* Like costsize.c, force estimate to be at least one row */
	if (pathnode->rows < 1.0)
		pathnode->rows = 1.0;

	cost_index(&pathnode->path, root, rel, index, indexquals, true);

	return (Path *) pathnode;
1611 1612
}

1613 1614 1615 1616 1617 1618 1619 1620
/****************************************************************************
 *				----  ROUTINES TO CHECK OPERANDS  ----
 ****************************************************************************/

/*
 * match_index_to_operand()
 *	  Generalized test for a match between an index's key
 *	  and the operand on one side of a restriction or join clause.
1621
 *	  Now check for functional indices as well.
1622 1623 1624
 */
static bool
match_index_to_operand(int indexkey,
1625
					   Var *operand,
1626
					   RelOptInfo *rel,
1627
					   IndexOptInfo *index)
1628
{
1629
	/*
1630
	 * Ignore any RelabelType node above the indexkey.	This is needed to
1631 1632 1633 1634 1635 1636 1637
	 * be able to apply indexscanning in binary-compatible-operator cases.
	 * Note: we can assume there is at most one RelabelType node;
	 * eval_const_expressions() will have simplified if more than one.
	 */
	if (operand && IsA(operand, RelabelType))
		operand = (Var *) ((RelabelType *) operand)->arg;

1638 1639 1640
	if (index->indproc == InvalidOid)
	{
		/*
1641
		 * Simple index.
1642
		 */
1643
		if (operand && IsA(operand, Var) &&
1644 1645 1646 1647 1648
			lfirsti(rel->relids) == operand->varno &&
			indexkey == operand->varattno)
			return true;
		else
			return false;
1649 1650 1651
	}

	/*
1652
	 * Functional index.
1653
	 */
1654
	return function_index_operand((Expr *) operand, rel, index);
1655 1656
}

1657
static bool
1658
function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index)
1659
{
1660
	int			relvarno = lfirsti(rel->relids);
1661
	FuncExpr   *function;
1662 1663 1664 1665
	List	   *funcargs;
	int		   *indexKeys = index->indexkeys;
	List	   *arg;
	int			i;
1666

1667 1668 1669
	/*
	 * sanity check, make sure we know what we're dealing with here.
	 */
1670 1671
	if (funcOpnd == NULL || !IsA(funcOpnd, FuncExpr) ||
		indexKeys == NULL)
1672
		return false;
1673

1674 1675
	function = (FuncExpr *) funcOpnd;
	funcargs = function->args;
1676 1677 1678 1679

	if (function->funcid != index->indproc)
		return false;

1680
	/*----------
1681
	 * Check that the arguments correspond to the same arguments used to
1682 1683 1684 1685 1686 1687
	 * create the functional index.  To do this we must check that
	 *	1. they refer to the right relation.
	 *	2. the args have the right attr. numbers in the right order.
	 * We must ignore RelabelType nodes above the argument Vars in order
	 * to recognize binary-compatible-function cases correctly.
	 *----------
1688 1689 1690 1691
	 */
	i = 0;
	foreach(arg, funcargs)
	{
1692
		Var		   *var = (Var *) lfirst(arg);
1693

1694 1695 1696
		if (var && IsA(var, RelabelType))
			var = (Var *) ((RelabelType *) var)->arg;
		if (var == NULL || !IsA(var, Var))
1697
			return false;
1698
		if (indexKeys[i] == 0)
1699
			return false;
1700
		if (var->varno != relvarno || var->varattno != indexKeys[i])
1701
			return false;
1702 1703 1704 1705

		i++;
	}

1706 1707 1708
	if (indexKeys[i] != 0)
		return false;			/* not enough arguments */

1709
	return true;
1710
}
1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721

/****************************************************************************
 *			----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
 ****************************************************************************/

/*----------
 * These routines handle special optimization of operators that can be
 * used with index scans even though they are not known to the executor's
 * indexscan machinery.  The key idea is that these operators allow us
 * to derive approximate indexscan qual clauses, such that any tuples
 * that pass the operator clause itself must also satisfy the simpler
1722
 * indexscan condition(s).	Then we can use the indexscan machinery
1723 1724
 * to avoid scanning as much of the table as we'd otherwise have to,
 * while applying the original operator as a qpqual condition to ensure
1725
 * we deliver only the tuples we want.	(In essence, we're using a regular
1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757
 * index as if it were a lossy index.)
 *
 * An example of what we're doing is
 *			textfield LIKE 'abc%'
 * from which we can generate the indexscanable conditions
 *			textfield >= 'abc' AND textfield < 'abd'
 * which allow efficient scanning of an index on textfield.
 * (In reality, character set and collation issues make the transformation
 * from LIKE to indexscan limits rather harder than one might think ...
 * but that's the basic idea.)
 *
 * Two routines are provided here, match_special_index_operator() and
 * expand_indexqual_conditions().  match_special_index_operator() is
 * just an auxiliary function for match_clause_to_indexkey(); after
 * the latter fails to recognize a restriction opclause's operator
 * as a member of an index's opclass, it asks match_special_index_operator()
 * whether the clause should be considered an indexqual anyway.
 * expand_indexqual_conditions() converts a list of "raw" indexqual
 * conditions (with implicit AND semantics across list elements) into
 * a list that the executor can actually handle.  For operators that
 * are members of the index's opclass this transformation is a no-op,
 * but operators recognized by match_special_index_operator() must be
 * converted into one or more "regular" indexqual conditions.
 *----------
 */

/*
 * match_special_index_operator
 *	  Recognize restriction clauses that can be used to generate
 *	  additional indexscanable qualifications.
 *
 * The given clause is already known to be a binary opclause having
1758
 * the form (indexkey OP pseudoconst) or (pseudoconst OP indexkey),
1759 1760 1761 1762
 * but the OP proved not to be one of the index's opclass operators.
 * Return 'true' if we can do something with it anyway.
 */
static bool
1763
match_special_index_operator(Expr *clause, Oid opclass,
1764
							 bool indexkey_on_left)
1765 1766 1767 1768 1769
{
	bool		isIndexable = false;
	Var		   *leftop,
			   *rightop;
	Oid			expr_op;
1770 1771 1772
	Const	   *patt = NULL;
	Const	   *prefix = NULL;
	Const	   *rest = NULL;
1773

1774 1775 1776 1777
	/*
	 * Currently, all known special operators require the indexkey on the
	 * left, but this test could be pushed into the switch statement if
	 * some are added that do not...
1778
	 */
1779
	if (!indexkey_on_left)
1780 1781 1782 1783 1784
		return false;

	/* we know these will succeed */
	leftop = get_leftop(clause);
	rightop = get_rightop(clause);
1785
	expr_op = ((OpExpr *) clause)->opno;
1786 1787

	/* again, required for all current special ops: */
1788
	if (!IsA(rightop, Const) ||
1789 1790
		((Const *) rightop)->constisnull)
		return false;
1791
	patt = (Const *) rightop;
1792 1793 1794 1795 1796 1797 1798

	switch (expr_op)
	{
		case OID_TEXT_LIKE_OP:
		case OID_BPCHAR_LIKE_OP:
		case OID_VARCHAR_LIKE_OP:
		case OID_NAME_LIKE_OP:
1799
			/* the right-hand const is type text for all of these */
1800 1801
			if (locale_is_like_safe())
				isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
1802
								  &prefix, &rest) != Pattern_Prefix_None;
1803 1804 1805 1806
			break;

		case OID_BYTEA_LIKE_OP:
			isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like,
Bruce Momjian's avatar
Bruce Momjian committed
1807
								  &prefix, &rest) != Pattern_Prefix_None;
1808 1809
			break;

1810 1811 1812 1813
		case OID_TEXT_ICLIKE_OP:
		case OID_BPCHAR_ICLIKE_OP:
		case OID_VARCHAR_ICLIKE_OP:
		case OID_NAME_ICLIKE_OP:
1814
			/* the right-hand const is type text for all of these */
1815 1816
			if (locale_is_like_safe())
				isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
1817
								  &prefix, &rest) != Pattern_Prefix_None;
1818 1819
			break;

1820 1821 1822 1823
		case OID_TEXT_REGEXEQ_OP:
		case OID_BPCHAR_REGEXEQ_OP:
		case OID_VARCHAR_REGEXEQ_OP:
		case OID_NAME_REGEXEQ_OP:
1824
			/* the right-hand const is type text for all of these */
1825 1826
			if (locale_is_like_safe())
				isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex,
1827
								  &prefix, &rest) != Pattern_Prefix_None;
1828 1829 1830 1831 1832 1833
			break;

		case OID_TEXT_ICREGEXEQ_OP:
		case OID_BPCHAR_ICREGEXEQ_OP:
		case OID_VARCHAR_ICREGEXEQ_OP:
		case OID_NAME_ICREGEXEQ_OP:
1834
			/* the right-hand const is type text for all of these */
1835 1836
			if (locale_is_like_safe())
				isIndexable = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
1837
								  &prefix, &rest) != Pattern_Prefix_None;
1838
			break;
1839 1840 1841 1842 1843 1844 1845

		case OID_INET_SUB_OP:
		case OID_INET_SUBEQ_OP:
		case OID_CIDR_SUB_OP:
		case OID_CIDR_SUBEQ_OP:
			isIndexable = true;
			break;
1846 1847
	}

1848 1849 1850 1851 1852 1853
	if (prefix)
	{
		pfree(DatumGetPointer(prefix->constvalue));
		pfree(prefix);
	}

1854
	/* done if the expression doesn't look indexable */
1855
	if (!isIndexable)
1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866
		return false;

	/*
	 * Must also check that index's opclass supports the operators we will
	 * want to apply.  (A hash index, for example, will not support ">=".)
	 * We cheat a little by not checking for availability of "=" ... any
	 * index type should support "=", methinks.
	 */
	switch (expr_op)
	{
		case OID_TEXT_LIKE_OP:
1867
		case OID_TEXT_ICLIKE_OP:
1868 1869
		case OID_TEXT_REGEXEQ_OP:
		case OID_TEXT_ICREGEXEQ_OP:
1870 1871
			if (!op_in_opclass(find_operator(">=", TEXTOID), opclass) ||
				!op_in_opclass(find_operator("<", TEXTOID), opclass))
1872 1873 1874
				isIndexable = false;
			break;

1875 1876 1877 1878 1879 1880
		case OID_BYTEA_LIKE_OP:
			if (!op_in_opclass(find_operator(">=", BYTEAOID), opclass) ||
				!op_in_opclass(find_operator("<", BYTEAOID), opclass))
				isIndexable = false;
			break;

1881
		case OID_BPCHAR_LIKE_OP:
1882
		case OID_BPCHAR_ICLIKE_OP:
1883 1884
		case OID_BPCHAR_REGEXEQ_OP:
		case OID_BPCHAR_ICREGEXEQ_OP:
1885 1886
			if (!op_in_opclass(find_operator(">=", BPCHAROID), opclass) ||
				!op_in_opclass(find_operator("<", BPCHAROID), opclass))
1887 1888 1889 1890
				isIndexable = false;
			break;

		case OID_VARCHAR_LIKE_OP:
1891
		case OID_VARCHAR_ICLIKE_OP:
1892 1893
		case OID_VARCHAR_REGEXEQ_OP:
		case OID_VARCHAR_ICREGEXEQ_OP:
1894 1895
			if (!op_in_opclass(find_operator(">=", VARCHAROID), opclass) ||
				!op_in_opclass(find_operator("<", VARCHAROID), opclass))
1896 1897 1898 1899
				isIndexable = false;
			break;

		case OID_NAME_LIKE_OP:
1900
		case OID_NAME_ICLIKE_OP:
1901 1902
		case OID_NAME_REGEXEQ_OP:
		case OID_NAME_ICREGEXEQ_OP:
1903 1904
			if (!op_in_opclass(find_operator(">=", NAMEOID), opclass) ||
				!op_in_opclass(find_operator("<", NAMEOID), opclass))
1905 1906
				isIndexable = false;
			break;
1907 1908 1909 1910

		case OID_INET_SUB_OP:
		case OID_INET_SUBEQ_OP:
			/* for SUB we actually need ">" not ">=", but this should do */
1911 1912
			if (!op_in_opclass(find_operator(">=", INETOID), opclass) ||
				!op_in_opclass(find_operator("<=", INETOID), opclass))
1913 1914 1915 1916 1917 1918
				isIndexable = false;
			break;

		case OID_CIDR_SUB_OP:
		case OID_CIDR_SUBEQ_OP:
			/* for SUB we actually need ">" not ">=", but this should do */
1919 1920
			if (!op_in_opclass(find_operator(">=", CIDROID), opclass) ||
				!op_in_opclass(find_operator("<=", CIDROID), opclass))
1921 1922
				isIndexable = false;
			break;
1923 1924
	}

1925 1926 1927 1928 1929 1930 1931
	return isIndexable;
}

/*
 * expand_indexqual_conditions
 *	  Given a list of (implicitly ANDed) indexqual clauses,
 *	  expand any "special" index operators into clauses that the indexscan
1932
 *	  machinery will know what to do with.	Clauses that were not
1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944
 *	  recognized by match_special_index_operator() must be passed through
 *	  unchanged.
 */
List *
expand_indexqual_conditions(List *indexquals)
{
	List	   *resultquals = NIL;
	List	   *q;

	foreach(q, indexquals)
	{
		Expr	   *clause = (Expr *) lfirst(q);
1945

1946 1947 1948
		/* we know these will succeed */
		Var		   *leftop = get_leftop(clause);
		Var		   *rightop = get_rightop(clause);
1949
		Oid			expr_op = ((OpExpr *) clause)->opno;
1950 1951 1952
		Const	   *patt = (Const *) rightop;
		Const	   *prefix = NULL;
		Const	   *rest = NULL;
1953
		Pattern_Prefix_Status pstatus;
1954 1955 1956

		switch (expr_op)
		{
1957 1958 1959 1960 1961 1962
				/*
				 * LIKE and regex operators are not members of any index
				 * opclass, so if we find one in an indexqual list we can
				 * assume that it was accepted by
				 * match_special_index_operator().
				 */
1963 1964 1965 1966
			case OID_TEXT_LIKE_OP:
			case OID_BPCHAR_LIKE_OP:
			case OID_VARCHAR_LIKE_OP:
			case OID_NAME_LIKE_OP:
1967
			case OID_BYTEA_LIKE_OP:
1968 1969
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
											   &prefix, &rest);
1970 1971 1972 1973 1974
				resultquals = nconc(resultquals,
									prefix_quals(leftop, expr_op,
												 prefix, pstatus));
				break;

1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986
			case OID_TEXT_ICLIKE_OP:
			case OID_BPCHAR_ICLIKE_OP:
			case OID_VARCHAR_ICLIKE_OP:
			case OID_NAME_ICLIKE_OP:
				/* the right-hand const is type text for all of these */
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
											   &prefix, &rest);
				resultquals = nconc(resultquals,
									prefix_quals(leftop, expr_op,
												 prefix, pstatus));
				break;

1987 1988 1989 1990 1991
			case OID_TEXT_REGEXEQ_OP:
			case OID_BPCHAR_REGEXEQ_OP:
			case OID_VARCHAR_REGEXEQ_OP:
			case OID_NAME_REGEXEQ_OP:
				/* the right-hand const is type text for all of these */
1992 1993
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
											   &prefix, &rest);
1994 1995 1996 1997 1998 1999 2000 2001 2002 2003
				resultquals = nconc(resultquals,
									prefix_quals(leftop, expr_op,
												 prefix, pstatus));
				break;

			case OID_TEXT_ICREGEXEQ_OP:
			case OID_BPCHAR_ICREGEXEQ_OP:
			case OID_VARCHAR_ICREGEXEQ_OP:
			case OID_NAME_ICREGEXEQ_OP:
				/* the right-hand const is type text for all of these */
2004 2005
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
											   &prefix, &rest);
2006 2007 2008 2009 2010
				resultquals = nconc(resultquals,
									prefix_quals(leftop, expr_op,
												 prefix, pstatus));
				break;

2011 2012 2013 2014 2015 2016
			case OID_INET_SUB_OP:
			case OID_INET_SUBEQ_OP:
			case OID_CIDR_SUB_OP:
			case OID_CIDR_SUBEQ_OP:
				resultquals = nconc(resultquals,
									network_prefix_quals(leftop, expr_op,
Bruce Momjian's avatar
Bruce Momjian committed
2017
													  patt->constvalue));
2018 2019
				break;

2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036
			default:
				resultquals = lappend(resultquals, clause);
				break;
		}
	}

	return resultquals;
}

/*
 * Given a fixed prefix that all the "leftop" values must have,
 * generate suitable indexqual condition(s).  expr_op is the original
 * LIKE or regex operator; we use it to deduce the appropriate comparison
 * operators.
 */
static List *
prefix_quals(Var *leftop, Oid expr_op,
2037
			 Const *prefix_const, Pattern_Prefix_Status pstatus)
2038 2039 2040
{
	List	   *result;
	Oid			datatype;
2041
	Oid			oproid;
2042
	char	   *prefix;
2043 2044
	Const	   *con;
	Expr	   *expr;
2045
	Const	   *greaterstr = NULL;
2046

2047
	Assert(pstatus != Pattern_Prefix_None);
2048 2049 2050 2051

	switch (expr_op)
	{
		case OID_TEXT_LIKE_OP:
2052
		case OID_TEXT_ICLIKE_OP:
2053 2054 2055 2056 2057
		case OID_TEXT_REGEXEQ_OP:
		case OID_TEXT_ICREGEXEQ_OP:
			datatype = TEXTOID;
			break;

2058 2059 2060 2061
		case OID_BYTEA_LIKE_OP:
			datatype = BYTEAOID;
			break;

2062
		case OID_BPCHAR_LIKE_OP:
2063
		case OID_BPCHAR_ICLIKE_OP:
2064 2065 2066 2067 2068 2069
		case OID_BPCHAR_REGEXEQ_OP:
		case OID_BPCHAR_ICREGEXEQ_OP:
			datatype = BPCHAROID;
			break;

		case OID_VARCHAR_LIKE_OP:
2070
		case OID_VARCHAR_ICLIKE_OP:
2071 2072 2073 2074 2075 2076
		case OID_VARCHAR_REGEXEQ_OP:
		case OID_VARCHAR_ICREGEXEQ_OP:
			datatype = VARCHAROID;
			break;

		case OID_NAME_LIKE_OP:
2077
		case OID_NAME_ICLIKE_OP:
2078 2079 2080 2081 2082 2083 2084 2085 2086 2087
		case OID_NAME_REGEXEQ_OP:
		case OID_NAME_ICREGEXEQ_OP:
			datatype = NAMEOID;
			break;

		default:
			elog(ERROR, "prefix_quals: unexpected operator %u", expr_op);
			return NIL;
	}

2088 2089 2090 2091 2092
	if (prefix_const->consttype != BYTEAOID)
		prefix = DatumGetCString(DirectFunctionCall1(textout, prefix_const->constvalue));
	else
		prefix = DatumGetCString(DirectFunctionCall1(byteaout, prefix_const->constvalue));

2093 2094 2095
	/*
	 * If we found an exact-match pattern, generate an "=" indexqual.
	 */
2096
	if (pstatus == Pattern_Prefix_Exact)
2097
	{
2098 2099
		oproid = find_operator("=", datatype);
		if (oproid == InvalidOid)
2100
			elog(ERROR, "prefix_quals: no = operator for type %u", datatype);
2101
		con = string_to_const(prefix, datatype);
2102 2103
		expr = make_opclause(oproid, BOOLOID, false,
							 (Expr *) leftop, (Expr *) con);
2104
		result = makeList1(expr);
2105 2106 2107 2108 2109 2110 2111 2112
		return result;
	}

	/*
	 * Otherwise, we have a nonempty required prefix of the values.
	 *
	 * We can always say "x >= prefix".
	 */
2113 2114
	oproid = find_operator(">=", datatype);
	if (oproid == InvalidOid)
2115
		elog(ERROR, "prefix_quals: no >= operator for type %u", datatype);
2116
	con = string_to_const(prefix, datatype);
2117 2118
	expr = make_opclause(oproid, BOOLOID, false,
						 (Expr *) leftop, (Expr *) con);
2119
	result = makeList1(expr);
2120

2121 2122 2123 2124
	/*-------
	 * If we can create a string larger than the prefix, we can say
	 * "x < greaterstr".
	 *-------
2125
	 */
2126
	greaterstr = make_greater_string(con);
2127 2128 2129 2130 2131
	if (greaterstr)
	{
		oproid = find_operator("<", datatype);
		if (oproid == InvalidOid)
			elog(ERROR, "prefix_quals: no < operator for type %u", datatype);
2132 2133
		expr = make_opclause(oproid, BOOLOID, false,
							 (Expr *) leftop, (Expr *) greaterstr);
2134 2135
		result = lappend(result, expr);
	}
2136

2137 2138 2139
	return result;
}

2140 2141 2142
/*
 * Given a leftop and a rightop, and a inet-class sup/sub operator,
 * generate suitable indexqual condition(s).  expr_op is the original
2143
 * operator.
2144 2145 2146 2147
 */
static List *
network_prefix_quals(Var *leftop, Oid expr_op, Datum rightop)
{
2148 2149 2150 2151 2152 2153
	bool		is_eq;
	char	   *opr1name;
	Datum		opr1right;
	Datum		opr2right;
	Oid			opr1oid;
	Oid			opr2oid;
2154 2155 2156 2157 2158 2159 2160
	List	   *result;
	Oid			datatype;
	Expr	   *expr;

	switch (expr_op)
	{
		case OID_INET_SUB_OP:
2161 2162
			datatype = INETOID;
			is_eq = false;
2163 2164
			break;
		case OID_INET_SUBEQ_OP:
2165 2166
			datatype = INETOID;
			is_eq = true;
2167 2168
			break;
		case OID_CIDR_SUB_OP:
2169 2170
			datatype = CIDROID;
			is_eq = false;
2171 2172
			break;
		case OID_CIDR_SUBEQ_OP:
2173 2174
			datatype = CIDROID;
			is_eq = true;
2175 2176 2177 2178 2179
			break;
		default:
			elog(ERROR, "network_prefix_quals: unexpected operator %u",
				 expr_op);
			return NIL;
2180
	}
2181 2182

	/*
2183 2184
	 * create clause "key >= network_scan_first( rightop )", or ">" if the
	 * operator disallows equality.
2185 2186 2187 2188 2189 2190 2191 2192
	 */

	opr1name = is_eq ? ">=" : ">";
	opr1oid = find_operator(opr1name, datatype);
	if (opr1oid == InvalidOid)
		elog(ERROR, "network_prefix_quals: no %s operator for type %u",
			 opr1name, datatype);

2193
	opr1right = network_scan_first(rightop);
2194

2195 2196 2197 2198
	expr = make_opclause(opr1oid, BOOLOID, false,
						 (Expr *) leftop,
						 (Expr *) makeConst(datatype, -1, opr1right,
											false, false));
2199 2200 2201 2202 2203 2204 2205 2206 2207
	result = makeList1(expr);

	/* create clause "key <= network_scan_last( rightop )" */

	opr2oid = find_operator("<=", datatype);
	if (opr2oid == InvalidOid)
		elog(ERROR, "network_prefix_quals: no <= operator for type %u",
			 datatype);

2208
	opr2right = network_scan_last(rightop);
2209

2210 2211 2212 2213
	expr = make_opclause(opr2oid, BOOLOID, false,
						 (Expr *) leftop,
						 (Expr *) makeConst(datatype, -1, opr2right,
											false, false));
2214 2215 2216 2217 2218
	result = lappend(result, expr);

	return result;
}

2219 2220 2221 2222
/*
 * Handy subroutines for match_special_index_operator() and friends.
 */

2223
/* See if there is a binary op of the given name for the given datatype */
2224
/* NB: we assume that only built-in system operators are searched for */
2225
static Oid
2226
find_operator(const char *opname, Oid datatype)
2227
{
2228
	return GetSysCacheOid(OPERNAMENSP,
2229 2230 2231
						  PointerGetDatum(opname),
						  ObjectIdGetDatum(datatype),
						  ObjectIdGetDatum(datatype),
2232
						  ObjectIdGetDatum(PG_CATALOG_NAMESPACE));
2233
}
2234 2235 2236 2237 2238 2239 2240

/*
 * Generate a Datum of the appropriate type from a C string.
 * Note that all of the supported types are pass-by-ref, so the
 * returned value should be pfree'd if no longer needed.
 */
static Datum
2241
string_to_datum(const char *str, Oid datatype)
2242
{
2243 2244 2245
	/*
	 * We cheat a little by assuming that textin() will do for bpchar and
	 * varchar constants too...
2246 2247
	 */
	if (datatype == NAMEOID)
2248
		return DirectFunctionCall1(namein, CStringGetDatum(str));
2249 2250
	else if (datatype == BYTEAOID)
		return DirectFunctionCall1(byteain, CStringGetDatum(str));
2251
	else
2252
		return DirectFunctionCall1(textin, CStringGetDatum(str));
2253 2254 2255 2256 2257 2258
}

/*
 * Generate a Const node of the appropriate type from a C string.
 */
static Const *
2259
string_to_const(const char *str, Oid datatype)
2260 2261 2262 2263
{
	Datum		conval = string_to_datum(str, datatype);

	return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2264
					 conval, false, false);
2265
}