indxpath.c 90.4 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * indxpath.c
4 5
 *	  Routines to determine which indexes are usable for scanning a
 *	  given relation, and create Paths accordingly.
6
 *
Bruce Momjian's avatar
Bruce Momjian committed
7
 * Portions Copyright (c) 1996-2009, 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
 *	  $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.238 2009/03/11 03:32:22 tgl Exp $
13 14 15 16
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"
Bruce Momjian's avatar
Bruce Momjian committed
17

18 19
#include <math.h>

20
#include "access/skey.h"
21
#include "catalog/pg_am.h"
22
#include "catalog/pg_operator.h"
23
#include "catalog/pg_opfamily.h"
24
#include "catalog/pg_type.h"
25 26 27
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
Bruce Momjian's avatar
Bruce Momjian committed
28
#include "optimizer/pathnode.h"
Bruce Momjian's avatar
Bruce Momjian committed
29
#include "optimizer/paths.h"
30
#include "optimizer/predtest.h"
Bruce Momjian's avatar
Bruce Momjian committed
31
#include "optimizer/restrictinfo.h"
32
#include "optimizer/var.h"
33
#include "utils/builtins.h"
Bruce Momjian's avatar
Bruce Momjian committed
34
#include "utils/lsyscache.h"
Tom Lane's avatar
Tom Lane committed
35
#include "utils/pg_locale.h"
36
#include "utils/selfuncs.h"
37

38

39 40 41
/*
 * DoneMatchingIndexKeys() - MACRO
 */
Bruce Momjian's avatar
Bruce Momjian committed
42
#define DoneMatchingIndexKeys(families) (families[0] == InvalidOid)
43

44 45
#define IsBooleanOpfamily(opfamily) \
	((opfamily) == BOOL_BTREE_FAM_OID || (opfamily) == BOOL_HASH_FAM_OID)
46

47

48 49 50 51 52 53 54 55
/* Whether we are looking for plain indexscan, bitmap scan, or either */
typedef enum
{
	ST_INDEXSCAN,				/* must support amgettuple */
	ST_BITMAPSCAN,				/* must support amgetbitmap */
	ST_ANYSCAN					/* either is okay */
} ScanTypeControl;

56 57 58 59 60 61 62
/* Per-path data used within choose_bitmap_and() */
typedef struct
{
	Path	   *path;			/* IndexPath, BitmapAndPath, or BitmapOrPath */
	List	   *quals;			/* the WHERE clauses it uses */
	List	   *preds;			/* predicates of its partial index(es) */
	Bitmapset  *clauseids;		/* quals+preds represented as a bitmapset */
63
} PathClauseUsage;
64 65


66
static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
67
					List *clauses, List *outer_clauses,
68
					bool istoplevel, RelOptInfo *outer_rel,
69
					SaOpControl saop_control, ScanTypeControl scantype);
70 71
static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
				List *clauses, List *outer_clauses,
72
				bool istoplevel, RelOptInfo *outer_rel);
73
static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
Bruce Momjian's avatar
Bruce Momjian committed
74
				  List *paths, RelOptInfo *outer_rel);
75 76 77
static int	path_usage_comparator(const void *a, const void *b);
static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
					 Path *ipath, RelOptInfo *outer_rel);
78
static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
Bruce Momjian's avatar
Bruce Momjian committed
79
					List *paths, RelOptInfo *outer_rel);
80
static PathClauseUsage *classify_index_clause_usage(Path *path,
Bruce Momjian's avatar
Bruce Momjian committed
81
							List **clauselist);
82
static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
83
static int	find_list_position(Node *node, List **nodelist);
84
static bool match_clause_to_indexcol(IndexOptInfo *index,
85
						 int indexcol, Oid opfamily,
86
						 RestrictInfo *rinfo,
87 88
						 Relids outer_relids,
						 SaOpControl saop_control);
89
static bool is_indexable_operator(Oid expr_op, Oid opfamily,
Bruce Momjian's avatar
Bruce Momjian committed
90
					  bool indexkey_on_left);
91 92
static bool match_rowcompare_to_indexcol(IndexOptInfo *index,
							 int indexcol,
93
							 Oid opfamily,
94 95
							 RowCompareExpr *clause,
							 Relids outer_relids);
96
static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
97
static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
98
				  Relids outer_relids);
99
static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
100
					  Relids outer_relids, bool isouterjoin);
101
static bool match_boolean_index_clause(Node *clause, int indexcol,
102
						   IndexOptInfo *index);
103
static bool match_special_index_operator(Expr *clause, Oid opfamily,
104
							 bool indexkey_on_left);
105
static Expr *expand_boolean_index_clause(Node *clause, int indexcol,
106
							IndexOptInfo *index);
107
static List *expand_indexqual_opclause(RestrictInfo *rinfo, Oid opfamily);
108 109 110
static RestrictInfo *expand_indexqual_rowcompare(RestrictInfo *rinfo,
							IndexOptInfo *index,
							int indexcol);
111
static List *prefix_quals(Node *leftop, Oid opfamily,
112
			 Const *prefix, Pattern_Prefix_Status pstatus);
113
static List *network_prefix_quals(Node *leftop, Oid expr_op, Oid opfamily,
Bruce Momjian's avatar
Bruce Momjian committed
114
					 Datum rightop);
115 116
static Datum string_to_datum(const char *str, Oid datatype);
static Const *string_to_const(const char *str, Oid datatype);
117 118


119 120 121
/*
 * create_index_paths()
 *	  Generate all interesting index paths for the given relation.
122
 *	  Candidate paths are added to the rel's pathlist (using add_path).
123
 *
124
 * To be considered for an index scan, an index must match one or more
125
 * restriction clauses or join clauses from the query's qual condition,
126 127
 * or match the query's ORDER BY condition, or have a predicate that
 * matches the query's qual condition.
128
 *
129 130 131 132 133 134 135 136 137
 * 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.
 *
138 139 140 141
 * 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
Bruce Momjian's avatar
Bruce Momjian committed
142
 * clauses that could be used with each index.	The actually best innerjoin
143 144 145
 * 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.
146
 *
147
 * 'rel' is the relation for which we want to generate index paths
148
 *
149
 * Note: check_partial_indexes() must have been run previously for this rel.
150
 */
151
void
152
create_index_paths(PlannerInfo *root, RelOptInfo *rel)
153
{
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
	List	   *indexpaths;
	List	   *bitindexpaths;
	ListCell   *l;

	/* Skip the whole mess if no indexes */
	if (rel->indexlist == NIL)
	{
		rel->index_outer_relids = NULL;
		return;
	}

	/*
	 * Examine join clauses to see which ones are potentially usable with
	 * indexes of this rel, and generate the set of all other relids that
	 * participate in such join clauses.  We'll use this set later to
	 * recognize outer rels that are equivalent for joining purposes.
	 */
171
	rel->index_outer_relids = indexable_outerrelids(root, rel);
172 173 174 175 176 177 178

	/*
	 * Find all the index paths that are directly usable for this relation
	 * (ie, are valid without considering OR or JOIN clauses).
	 */
	indexpaths = find_usable_indexes(root, rel,
									 rel->baserestrictinfo, NIL,
179
									 true, NULL, SAOP_FORBID, ST_ANYSCAN);
180 181

	/*
182 183 184 185 186 187 188
	 * Submit all the ones that can form plain IndexScan plans to add_path.
	 * (A plain IndexPath always represents a plain IndexScan plan; however
	 * some of the indexes might support only bitmap scans, and those we
	 * mustn't submit to add_path here.)  Also, pick out the ones that might
	 * be useful as bitmap scans.  For that, we must discard indexes that
	 * don't support bitmap scans, and we also are only interested in paths
	 * that have some selectivity; we should discard anything that was
189 190 191 192 193 194 195
	 * generated solely for ordering purposes.
	 */
	bitindexpaths = NIL;
	foreach(l, indexpaths)
	{
		IndexPath  *ipath = (IndexPath *) lfirst(l);

196 197
		if (ipath->indexinfo->amhasgettuple)
			add_path(rel, (Path *) ipath);
198

199 200
		if (ipath->indexinfo->amhasgetbitmap &&
			ipath->indexselectivity < 1.0 &&
201 202 203 204 205 206 207 208 209 210
			!ScanDirectionIsBackward(ipath->indexscandir))
			bitindexpaths = lappend(bitindexpaths, ipath);
	}

	/*
	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
	 * restriction list.  Add these to bitindexpaths.
	 */
	indexpaths = generate_bitmap_or_paths(root, rel,
										  rel->baserestrictinfo, NIL,
211
										  NULL);
212 213
	bitindexpaths = list_concat(bitindexpaths, indexpaths);

214 215 216 217 218 219
	/*
	 * Likewise, generate paths using ScalarArrayOpExpr clauses; these can't
	 * be simple indexscans but they can be used in bitmap scans.
	 */
	indexpaths = find_saop_paths(root, rel,
								 rel->baserestrictinfo, NIL,
220
								 true, NULL);
221 222
	bitindexpaths = list_concat(bitindexpaths, indexpaths);

223
	/*
224 225
	 * If we found anything usable, generate a BitmapHeapPath for the most
	 * promising combination of bitmap index paths.
226 227 228 229 230 231
	 */
	if (bitindexpaths != NIL)
	{
		Path	   *bitmapqual;
		BitmapHeapPath *bpath;

232 233
		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL);
		bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL);
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
		add_path(rel, (Path *) bpath);
	}
}


/*----------
 * find_usable_indexes
 *	  Given a list of restriction clauses, find all the potentially usable
 *	  indexes for the given relation, and return a list of IndexPaths.
 *
 * The caller actually supplies two lists of restriction clauses: some
 * "current" ones and some "outer" ones.  Both lists can be used freely
 * to match keys of the index, but an index must use at least one of the
 * "current" clauses to be considered usable.  The motivation for this is
 * examples like
 *		WHERE (x = 42) AND (... OR (y = 52 AND z = 77) OR ....)
 * While we are considering the y/z subclause of the OR, we can use "x = 42"
 * as one of the available index conditions; but we shouldn't match the
 * subclause to any index on x alone, because such a Path would already have
 * been generated at the upper level.  So we could use an index on x,y,z
 * or an index on x,y for the OR subclause, but not an index on just x.
255 256
 * When dealing with a partial index, a match of the index predicate to
 * one of the "current" clauses also makes the index usable.
257 258 259 260 261 262 263 264 265 266
 *
 * If istoplevel is true (indicating we are considering the top level of a
 * rel's restriction clauses), we will include indexes in the result that
 * have an interesting sort order, even if they have no matching restriction
 * clauses.
 *
 * 'rel' is the relation for which we want to generate index paths
 * 'clauses' is the current list of clauses (RestrictInfo nodes)
 * 'outer_clauses' is the list of additional upper-level clauses
 * 'istoplevel' is true if clauses are the rel's top-level restriction list
267
 *		(outer_clauses must be NIL when this is true)
268 269
 * 'outer_rel' is the outer side of the join if forming an inner indexscan
 *		(so some of the given clauses are join clauses); NULL if not
270
 * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
271
 * 'scantype' indicates whether we need plain or bitmap scan support
272 273 274 275 276
 *
 * Note: check_partial_indexes() must have been run previously.
 *----------
 */
static List *
277
find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
278
					List *clauses, List *outer_clauses,
279
					bool istoplevel, RelOptInfo *outer_rel,
280
					SaOpControl saop_control, ScanTypeControl scantype)
281
{
282
	Relids		outer_relids = outer_rel ? outer_rel->relids : NULL;
283
	bool		possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
284 285
	List	   *result = NIL;
	List	   *all_clauses = NIL;		/* not computed till needed */
286
	ListCell   *ilist;
287

288
	foreach(ilist, rel->indexlist)
289
	{
290
		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
291
		IndexPath  *ipath;
292
		List	   *restrictclauses;
293 294
		List	   *index_pathkeys;
		List	   *useful_pathkeys;
295 296
		bool		useful_predicate;
		bool		found_clause;
297
		bool		index_is_ordered;
298

299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
		/*
		 * Check that index supports the desired scan type(s)
		 */
		switch (scantype)
		{
			case ST_INDEXSCAN:
				if (!index->amhasgettuple)
					continue;
				break;
			case ST_BITMAPSCAN:
				if (!index->amhasgetbitmap)
					continue;
				break;
			case ST_ANYSCAN:
				/* either or both are OK */
				break;
		}

317
		/*
318 319 320 321 322 323 324
		 * Ignore partial indexes that do not match the query.	If a partial
		 * index is marked predOK then we know it's OK; otherwise, if we are
		 * at top level we know it's not OK (since predOK is exactly whether
		 * its predicate could be proven from the toplevel clauses).
		 * Otherwise, we have to test whether the added clauses are sufficient
		 * to imply the predicate.	If so, we could use the index in the
		 * current context.
325
		 *
326 327
		 * We set useful_predicate to true iff the predicate was proven using
		 * the current set of clauses.	This is needed to prevent matching a
328 329 330
		 * predOK index to an arm of an OR, which would be a legal but
		 * pointlessly inefficient plan.  (A better plan will be generated by
		 * just scanning the predOK index alone, no OR.)
331
		 */
332 333
		useful_predicate = false;
		if (index->indpred != NIL)
334
		{
335 336 337 338 339 340 341 342 343 344 345
			if (index->predOK)
			{
				if (istoplevel)
				{
					/* we know predicate was proven from these clauses */
					useful_predicate = true;
				}
			}
			else
			{
				if (istoplevel)
346
					continue;	/* no point in trying to prove it */
347 348 349 350 351

				/* Form all_clauses if not done already */
				if (all_clauses == NIL)
					all_clauses = list_concat(list_copy(clauses),
											  outer_clauses);
352

353
				if (!predicate_implied_by(index->indpred, all_clauses))
354
					continue;	/* can't use it at all */
355

356
				if (!predicate_implied_by(index->indpred, outer_clauses))
357 358
					useful_predicate = true;
			}
359
		}
360

361
		/*
362
		 * 1. Match the index against the available restriction clauses.
363
		 * found_clause is set true only if at least one of the current
Bruce Momjian's avatar
Bruce Momjian committed
364 365
		 * clauses was used (and, if saop_control is SAOP_REQUIRE, it has to
		 * have been a ScalarArrayOpExpr clause).
366
		 */
367 368 369
		restrictclauses = group_clauses_by_indexkey(index,
													clauses,
													outer_clauses,
370
													outer_relids,
371
													saop_control,
372 373 374
													&found_clause);

		/*
375 376
		 * Not all index AMs support scans with no restriction clauses. We
		 * can't generate a scan over an index with amoptionalkey = false
377 378 379 380
		 * unless there's at least one restriction clause.
		 */
		if (restrictclauses == NIL && !index->amoptionalkey)
			continue;
381

382
		/*
383 384 385
		 * 2. Compute pathkeys describing index's ordering, if any, then see
		 * how many of them are actually useful for this query.  This is not
		 * relevant unless we are at top level.
386
		 */
387
		index_is_ordered = OidIsValid(index->fwdsortop[0]);
388 389
		if (index_is_ordered && possibly_useful_pathkeys &&
			istoplevel && outer_rel == NULL)
390 391
		{
			index_pathkeys = build_index_pathkeys(root, index,
392
												  ForwardScanDirection);
393 394 395 396 397
			useful_pathkeys = truncate_useless_pathkeys(root, rel,
														index_pathkeys);
		}
		else
			useful_pathkeys = NIL;
398

399
		/*
400
		 * 3. Generate an indexscan path if there are relevant restriction
401
		 * clauses in the current clauses, OR the index ordering is
402 403
		 * potentially useful for later merging or final output ordering, OR
		 * the index has a predicate that was proven by the current clauses.
404
		 */
405
		if (found_clause || useful_pathkeys != NIL || useful_predicate)
406 407 408 409 410 411 412
		{
			ipath = create_index_path(root, index,
									  restrictclauses,
									  useful_pathkeys,
									  index_is_ordered ?
									  ForwardScanDirection :
									  NoMovementScanDirection,
413
									  outer_rel);
414 415
			result = lappend(result, ipath);
		}
416 417

		/*
Bruce Momjian's avatar
Bruce Momjian committed
418 419
		 * 4. If the index is ordered, a backwards scan might be interesting.
		 * Again, this is only interesting at top level.
420
		 */
421 422
		if (index_is_ordered && possibly_useful_pathkeys &&
			istoplevel && outer_rel == NULL)
423
		{
424 425 426 427 428
			index_pathkeys = build_index_pathkeys(root, index,
												  BackwardScanDirection);
			useful_pathkeys = truncate_useless_pathkeys(root, rel,
														index_pathkeys);
			if (useful_pathkeys != NIL)
429 430 431
			{
				ipath = create_index_path(root, index,
										  restrictclauses,
432 433
										  useful_pathkeys,
										  BackwardScanDirection,
434
										  outer_rel);
435 436
				result = lappend(result, ipath);
			}
437
		}
438 439 440 441 442
	}

	return result;
}

443

444 445 446 447 448 449 450 451 452 453 454
/*
 * find_saop_paths
 *		Find all the potential indexpaths that make use of ScalarArrayOpExpr
 *		clauses.  The executor only supports these in bitmap scans, not
 *		plain indexscans, so we need to segregate them from the normal case.
 *		Otherwise, same API as find_usable_indexes().
 *		Returns a list of IndexPaths.
 */
static List *
find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
				List *clauses, List *outer_clauses,
455
				bool istoplevel, RelOptInfo *outer_rel)
456 457 458 459 460
{
	bool		have_saop = false;
	ListCell   *l;

	/*
Bruce Momjian's avatar
Bruce Momjian committed
461 462
	 * Since find_usable_indexes is relatively expensive, don't bother to run
	 * it unless there are some top-level ScalarArrayOpExpr clauses.
463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479
	 */
	foreach(l, clauses)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

		Assert(IsA(rinfo, RestrictInfo));
		if (IsA(rinfo->clause, ScalarArrayOpExpr))
		{
			have_saop = true;
			break;
		}
	}
	if (!have_saop)
		return NIL;

	return find_usable_indexes(root, rel,
							   clauses, outer_clauses,
480
							   istoplevel, outer_rel,
481
							   SAOP_REQUIRE, ST_BITMAPSCAN);
482 483 484
}


485 486
/*
 * generate_bitmap_or_paths
487 488 489
 *		Look through the list of clauses to find OR clauses, and generate
 *		a BitmapOrPath for each one we can handle that way.  Return a list
 *		of the generated BitmapOrPaths.
490 491 492
 *
 * outer_clauses is a list of additional clauses that can be assumed true
 * for the purpose of generating indexquals, but are not to be searched for
493 494
 * ORs.  (See find_usable_indexes() for motivation.)  outer_rel is the outer
 * side when we are considering a nestloop inner indexpath.
495
 */
496
List *
497
generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
498
						 List *clauses, List *outer_clauses,
499
						 RelOptInfo *outer_rel)
500 501 502 503 504 505 506 507 508 509 510 511 512 513
{
	List	   *result = NIL;
	List	   *all_clauses;
	ListCell   *l;

	/*
	 * We can use both the current and outer clauses as context for
	 * find_usable_indexes
	 */
	all_clauses = list_concat(list_copy(clauses), outer_clauses);

	foreach(l, clauses)
	{
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
514 515 516
		List	   *pathlist;
		Path	   *bitmapqual;
		ListCell   *j;
517 518

		Assert(IsA(rinfo, RestrictInfo));
519
		/* Ignore RestrictInfos that aren't ORs */
520 521 522 523
		if (!restriction_is_or_clause(rinfo))
			continue;

		/*
524 525
		 * We must be able to match at least one index to each of the arms of
		 * the OR, else we can't use it.
526 527 528 529
		 */
		pathlist = NIL;
		foreach(j, ((BoolExpr *) rinfo->orclause)->args)
		{
530 531
			Node	   *orarg = (Node *) lfirst(j);
			List	   *indlist;
532 533 534 535

			/* OR arguments should be ANDs or sub-RestrictInfos */
			if (and_clause(orarg))
			{
536
				List	   *andargs = ((BoolExpr *) orarg)->args;
537 538 539 540 541

				indlist = find_usable_indexes(root, rel,
											  andargs,
											  all_clauses,
											  false,
542
											  outer_rel,
543 544
											  SAOP_ALLOW,
											  ST_BITMAPSCAN);
545 546 547 548 549
				/* Recurse in case there are sub-ORs */
				indlist = list_concat(indlist,
									  generate_bitmap_or_paths(root, rel,
															   andargs,
															   all_clauses,
550
															   outer_rel));
551 552 553 554 555 556 557 558 559
			}
			else
			{
				Assert(IsA(orarg, RestrictInfo));
				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
				indlist = find_usable_indexes(root, rel,
											  list_make1(orarg),
											  all_clauses,
											  false,
560
											  outer_rel,
561 562
											  SAOP_ALLOW,
											  ST_BITMAPSCAN);
563
			}
564

565
			/*
566 567
			 * If nothing matched this arm, we can't do anything with this OR
			 * clause.
568 569 570 571 572 573
			 */
			if (indlist == NIL)
			{
				pathlist = NIL;
				break;
			}
574

575
			/*
576 577
			 * OK, pick the most promising AND combination, and add it to
			 * pathlist.
578
			 */
579
			bitmapqual = choose_bitmap_and(root, rel, indlist, outer_rel);
580 581
			pathlist = lappend(pathlist, bitmapqual);
		}
582

583
		/*
584 585
		 * If we have a match for every arm, then turn them into a
		 * BitmapOrPath, and add to result list.
586
		 */
587 588 589 590 591
		if (pathlist != NIL)
		{
			bitmapqual = (Path *) create_bitmap_or_path(root, rel, pathlist);
			result = lappend(result, bitmapqual);
		}
592
	}
593

594 595 596 597 598 599 600 601 602
	return result;
}


/*
 * choose_bitmap_and
 *		Given a nonempty list of bitmap paths, AND them into one path.
 *
 * This is a nontrivial decision since we can legally use any subset of the
603
 * given path set.	We want to choose a good tradeoff between selectivity
604 605 606 607 608 609
 * and cost of computing the bitmap.
 *
 * The result is either a single one of the inputs, or a BitmapAndPath
 * combining multiple inputs.
 */
static Path *
610 611
choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
				  List *paths, RelOptInfo *outer_rel)
612
{
613
	int			npaths = list_length(paths);
614 615 616 617 618
	PathClauseUsage **pathinfoarray;
	PathClauseUsage *pathinfo;
	List	   *clauselist;
	List	   *bestpaths = NIL;
	Cost		bestcost = 0;
Bruce Momjian's avatar
Bruce Momjian committed
619 620
	int			i,
				j;
621 622
	ListCell   *l;

623
	Assert(npaths > 0);			/* else caller error */
624 625 626
	if (npaths == 1)
		return (Path *) linitial(paths);		/* easy case */

627
	/*
628 629 630
	 * In theory we should consider every nonempty subset of the given paths.
	 * In practice that seems like overkill, given the crude nature of the
	 * estimates, not to mention the possible effects of higher-level AND and
Bruce Momjian's avatar
Bruce Momjian committed
631
	 * OR clauses.	Moreover, it's completely impractical if there are a large
632
	 * number of paths, since the work would grow as O(2^N).
633
	 *
Bruce Momjian's avatar
Bruce Momjian committed
634 635 636 637 638 639 640
	 * As a heuristic, we first check for paths using exactly the same sets of
	 * WHERE clauses + index predicate conditions, and reject all but the
	 * cheapest-to-scan in any such group.	This primarily gets rid of indexes
	 * that include the interesting columns but also irrelevant columns.  (In
	 * situations where the DBA has gone overboard on creating variant
	 * indexes, this can make for a very large reduction in the number of
	 * paths considered further.)
641
	 *
Bruce Momjian's avatar
Bruce Momjian committed
642 643 644 645 646 647 648 649
	 * We then sort the surviving paths with the cheapest-to-scan first, and
	 * for each path, consider using that path alone as the basis for a bitmap
	 * scan.  Then we consider bitmap AND scans formed from that path plus
	 * each subsequent (higher-cost) path, adding on a subsequent path if it
	 * results in a reduction in the estimated total scan cost. This means we
	 * consider about O(N^2) rather than O(2^N) path combinations, which is
	 * quite tolerable, especially given than N is usually reasonably small
	 * because of the prefiltering step.  The cheapest of these is returned.
650
	 *
Bruce Momjian's avatar
Bruce Momjian committed
651 652
	 * We will only consider AND combinations in which no two indexes use the
	 * same WHERE clause.  This is a bit of a kluge: it's needed because
653 654 655
	 * costsize.c and clausesel.c aren't very smart about redundant clauses.
	 * They will usually double-count the redundant clauses, producing a
	 * too-small selectivity that makes a redundant AND step look like it
Bruce Momjian's avatar
Bruce Momjian committed
656
	 * reduces the total cost.	Perhaps someday that code will be smarter and
657 658 659 660
	 * we can remove this limitation.  (But note that this also defends
	 * against flat-out duplicate input paths, which can happen because
	 * best_inner_indexscan will find the same OR join clauses that
	 * create_or_index_quals has pulled OR restriction clauses out of.)
661
	 *
662
	 * For the same reason, we reject AND combinations in which an index
Bruce Momjian's avatar
Bruce Momjian committed
663
	 * predicate clause duplicates another clause.	Here we find it necessary
664 665 666 667 668 669 670 671 672 673
	 * to be even stricter: we'll reject a partial index if any of its
	 * predicate clauses are implied by the set of WHERE clauses and predicate
	 * clauses used so far.  This covers cases such as a condition "x = 42"
	 * used with a plain index, followed by a clauseless scan of a partial
	 * index "WHERE x >= 40 AND x < 50".  The partial index has been accepted
	 * only because "x = 42" was present, and so allowing it would partially
	 * double-count selectivity.  (We could use predicate_implied_by on
	 * regular qual clauses too, to have a more intelligent, but much more
	 * expensive, check for redundancy --- but in most cases simple equality
	 * seems to suffice.)
674
	 */
675

676
	/*
Bruce Momjian's avatar
Bruce Momjian committed
677 678 679
	 * Extract clause usage info and detect any paths that use exactly the
	 * same set of clauses; keep only the cheapest-to-scan of any such groups.
	 * The surviving paths are put into an array for qsort'ing.
680 681 682 683 684
	 */
	pathinfoarray = (PathClauseUsage **)
		palloc(npaths * sizeof(PathClauseUsage *));
	clauselist = NIL;
	npaths = 0;
685 686
	foreach(l, paths)
	{
Bruce Momjian's avatar
Bruce Momjian committed
687
		Path	   *ipath = (Path *) lfirst(l);
688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712

		pathinfo = classify_index_clause_usage(ipath, &clauselist);
		for (i = 0; i < npaths; i++)
		{
			if (bms_equal(pathinfo->clauseids, pathinfoarray[i]->clauseids))
				break;
		}
		if (i < npaths)
		{
			/* duplicate clauseids, keep the cheaper one */
			Cost		ncost;
			Cost		ocost;
			Selectivity nselec;
			Selectivity oselec;

			cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec);
			cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec);
			if (ncost < ocost)
				pathinfoarray[i] = pathinfo;
		}
		else
		{
			/* not duplicate clauseids, add to array */
			pathinfoarray[npaths++] = pathinfo;
		}
713 714
	}

715 716 717 718 719 720 721
	/* If only one surviving path, we're done */
	if (npaths == 1)
		return pathinfoarray[0]->path;

	/* Sort the surviving paths by index access cost */
	qsort(pathinfoarray, npaths, sizeof(PathClauseUsage *),
		  path_usage_comparator);
722

723
	/*
Bruce Momjian's avatar
Bruce Momjian committed
724 725 726
	 * For each surviving index, consider it as an "AND group leader", and see
	 * whether adding on any of the later indexes results in an AND path with
	 * cheaper total cost than before.	Then take the cheapest AND group.
727 728
	 */
	for (i = 0; i < npaths; i++)
729
	{
730 731 732 733 734 735 736 737 738 739 740 741 742
		Cost		costsofar;
		List	   *qualsofar;
		Bitmapset  *clauseidsofar;
		ListCell   *lastcell;

		pathinfo = pathinfoarray[i];
		paths = list_make1(pathinfo->path);
		costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path, outer_rel);
		qualsofar = list_concat(list_copy(pathinfo->quals),
								list_copy(pathinfo->preds));
		clauseidsofar = bms_copy(pathinfo->clauseids);
		lastcell = list_head(paths);	/* for quick deletions */

Bruce Momjian's avatar
Bruce Momjian committed
743
		for (j = i + 1; j < npaths; j++)
744
		{
745
			Cost		newcost;
746

747 748 749
			pathinfo = pathinfoarray[j];
			/* Check for redundancy */
			if (bms_overlap(pathinfo->clauseids, clauseidsofar))
Bruce Momjian's avatar
Bruce Momjian committed
750
				continue;		/* consider it redundant */
751
			if (pathinfo->preds)
752
			{
Bruce Momjian's avatar
Bruce Momjian committed
753
				bool		redundant = false;
754

755 756
				/* we check each predicate clause separately */
				foreach(l, pathinfo->preds)
757
				{
758 759 760 761 762
					Node	   *np = (Node *) lfirst(l);

					if (predicate_implied_by(list_make1(np), qualsofar))
					{
						redundant = true;
Bruce Momjian's avatar
Bruce Momjian committed
763
						break;	/* out of inner foreach loop */
764
					}
765
				}
766 767
				if (redundant)
					continue;
768
			}
769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789
			/* tentatively add new path to paths, so we can estimate cost */
			paths = lappend(paths, pathinfo->path);
			newcost = bitmap_and_cost_est(root, rel, paths, outer_rel);
			if (newcost < costsofar)
			{
				/* keep new path in paths, update subsidiary variables */
				costsofar = newcost;
				qualsofar = list_concat(qualsofar,
										list_copy(pathinfo->quals));
				qualsofar = list_concat(qualsofar,
										list_copy(pathinfo->preds));
				clauseidsofar = bms_add_members(clauseidsofar,
												pathinfo->clauseids);
				lastcell = lnext(lastcell);
			}
			else
			{
				/* reject new path, remove it from paths list */
				paths = list_delete_cell(paths, lnext(lastcell), lastcell);
			}
			Assert(lnext(lastcell) == NULL);
790
		}
791 792 793

		/* Keep the cheapest AND-group (or singleton) */
		if (i == 0 || costsofar < bestcost)
794
		{
795 796
			bestpaths = paths;
			bestcost = costsofar;
797
		}
798 799 800

		/* some easy cleanup (we don't try real hard though) */
		list_free(qualsofar);
801 802
	}

803
	if (list_length(bestpaths) == 1)
Bruce Momjian's avatar
Bruce Momjian committed
804
		return (Path *) linitial(bestpaths);	/* no need for AND */
805
	return (Path *) create_bitmap_and_path(root, rel, bestpaths);
806 807
}

808
/* qsort comparator to sort in increasing index access cost order */
809
static int
810
path_usage_comparator(const void *a, const void *b)
811
{
812 813
	PathClauseUsage *pa = *(PathClauseUsage *const *) a;
	PathClauseUsage *pb = *(PathClauseUsage *const *) b;
814 815
	Cost		acost;
	Cost		bcost;
816 817
	Selectivity aselec;
	Selectivity bselec;
818

819 820
	cost_bitmap_tree_node(pa->path, &acost, &aselec);
	cost_bitmap_tree_node(pb->path, &bcost, &bselec);
821

822
	/*
823
	 * If costs are the same, sort by selectivity.
824
	 */
825
	if (acost < bcost)
826
		return -1;
827
	if (acost > bcost)
828
		return 1;
829

830
	if (aselec < bselec)
831
		return -1;
832
	if (aselec > bselec)
833
		return 1;
834

835 836 837 838
	return 0;
}

/*
839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854
 * Estimate the cost of actually executing a bitmap scan with a single
 * index path (no BitmapAnd, at least not at this level).
 */
static Cost
bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
					 Path *ipath, RelOptInfo *outer_rel)
{
	Path		bpath;

	cost_bitmap_heap_scan(&bpath, root, rel, ipath, outer_rel);

	return bpath.total_cost;
}

/*
 * Estimate the cost of actually executing a BitmapAnd scan with the given
855 856 857
 * inputs.
 */
static Cost
858 859
bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
					List *paths, RelOptInfo *outer_rel)
860 861 862 863 864 865 866 867 868 869 870
{
	BitmapAndPath apath;
	Path		bpath;

	/* Set up a dummy BitmapAndPath */
	apath.path.type = T_BitmapAndPath;
	apath.path.parent = rel;
	apath.bitmapquals = paths;
	cost_bitmap_and_node(&apath, root);

	/* Now we can do cost_bitmap_heap_scan */
871
	cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, outer_rel);
872 873 874 875

	return bpath.total_cost;
}

876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909

/*
 * classify_index_clause_usage
 *		Construct a PathClauseUsage struct describing the WHERE clauses and
 *		index predicate clauses used by the given indexscan path.
 *		We consider two clauses the same if they are equal().
 *
 * At some point we might want to migrate this info into the Path data
 * structure proper, but for the moment it's only needed within
 * choose_bitmap_and().
 *
 * *clauselist is used and expanded as needed to identify all the distinct
 * clauses seen across successive calls.  Caller must initialize it to NIL
 * before first call of a set.
 */
static PathClauseUsage *
classify_index_clause_usage(Path *path, List **clauselist)
{
	PathClauseUsage *result;
	Bitmapset  *clauseids;
	ListCell   *lc;

	result = (PathClauseUsage *) palloc(sizeof(PathClauseUsage));
	result->path = path;

	/* Recursively find the quals and preds used by the path */
	result->quals = NIL;
	result->preds = NIL;
	find_indexpath_quals(path, &result->quals, &result->preds);

	/* Build up a bitmapset representing the quals and preds */
	clauseids = NULL;
	foreach(lc, result->quals)
	{
Bruce Momjian's avatar
Bruce Momjian committed
910
		Node	   *node = (Node *) lfirst(lc);
911 912 913 914 915 916

		clauseids = bms_add_member(clauseids,
								   find_list_position(node, clauselist));
	}
	foreach(lc, result->preds)
	{
Bruce Momjian's avatar
Bruce Momjian committed
917
		Node	   *node = (Node *) lfirst(lc);
918 919 920 921 922 923 924 925 926 927

		clauseids = bms_add_member(clauseids,
								   find_list_position(node, clauselist));
	}
	result->clauseids = clauseids;

	return result;
}


928
/*
929
 * find_indexpath_quals
930
 *
931
 * Given the Path structure for a plain or bitmap indexscan, extract lists
932
 * of all the indexquals and index predicate conditions used in the Path.
933 934
 * These are appended to the initial contents of *quals and *preds (hence
 * caller should initialize those to NIL).
935 936 937 938 939
 *
 * This is sort of a simplified version of make_restrictinfo_from_bitmapqual;
 * here, we are not trying to produce an accurate representation of the AND/OR
 * semantics of the Path, but just find out all the base conditions used.
 *
940
 * The result lists contain pointers to the expressions used in the Path,
941
 * but all the list cells are freshly built, so it's safe to destructively
942
 * modify the lists (eg, by concat'ing with other lists).
943
 */
944 945
static void
find_indexpath_quals(Path *bitmapqual, List **quals, List **preds)
946 947 948 949
{
	if (IsA(bitmapqual, BitmapAndPath))
	{
		BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
950
		ListCell   *l;
951 952 953

		foreach(l, apath->bitmapquals)
		{
954
			find_indexpath_quals((Path *) lfirst(l), quals, preds);
955 956 957 958 959
		}
	}
	else if (IsA(bitmapqual, BitmapOrPath))
	{
		BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
960
		ListCell   *l;
961 962 963

		foreach(l, opath->bitmapquals)
		{
964
			find_indexpath_quals((Path *) lfirst(l), quals, preds);
965 966 967 968 969 970
		}
	}
	else if (IsA(bitmapqual, IndexPath))
	{
		IndexPath  *ipath = (IndexPath *) bitmapqual;

971 972
		*quals = list_concat(*quals, get_actual_clauses(ipath->indexclauses));
		*preds = list_concat(*preds, list_copy(ipath->indexinfo->indpred));
973 974 975 976 977
	}
	else
		elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
}

978

979
/*
980 981
 * find_list_position
 *		Return the given node's position (counting from 0) in the given
Bruce Momjian's avatar
Bruce Momjian committed
982
 *		list of nodes.	If it's not equal() to any existing list member,
983
 *		add it at the end, and return that position.
984
 */
985 986
static int
find_list_position(Node *node, List **nodelist)
987
{
988 989
	int			i;
	ListCell   *lc;
990

991 992
	i = 0;
	foreach(lc, *nodelist)
993
	{
Bruce Momjian's avatar
Bruce Momjian committed
994
		Node	   *oldnode = (Node *) lfirst(lc);
995

996 997 998
		if (equal(node, oldnode))
			return i;
		i++;
999 1000
	}

1001 1002 1003
	*nodelist = lappend(*nodelist, node);

	return i;
1004 1005 1006
}


1007
/****************************************************************************
1008
 *				----  ROUTINES TO CHECK RESTRICTIONS  ----
1009 1010 1011
 ****************************************************************************/


1012
/*
1013
 * group_clauses_by_indexkey
1014
 *	  Find restriction clauses that can be used with an index.
1015
 *
1016 1017 1018 1019 1020
 * Returns a list of sublists of RestrictInfo nodes for clauses that can be
 * used with this index.  Each sublist contains clauses that can be used
 * with one index key (in no particular order); the top list is ordered by
 * index key.  (This is depended on by expand_indexqual_conditions().)
 *
1021 1022
 * We can use clauses from either the current clauses or outer_clauses lists,
 * but *found_clause is set TRUE only if we used at least one clause from
1023
 * the "current clauses" list.	See find_usable_indexes() for motivation.
1024 1025 1026 1027
 *
 * outer_relids determines what Vars will be allowed on the other side
 * of a possible index qual; see match_clause_to_indexcol().
 *
1028 1029 1030 1031
 * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used.
 * When it's SAOP_REQUIRE, *found_clause is set TRUE only if we used at least
 * one ScalarArrayOpExpr from the current clauses list.
 *
1032 1033 1034 1035
 * If the index has amoptionalkey = false, we give up and return NIL when
 * there are no restriction clauses matching the first index key.  Otherwise,
 * we return NIL if there are no restriction clauses matching any index key.
 * A non-NIL result will have one (possibly empty) sublist for each index key.
1036
 *
1037 1038 1039
 * Example: given an index on (A,B,C), we would return ((C1 C2) () (C3 C4))
 * if we find that clauses C1 and C2 use column A, clauses C3 and C4 use
 * column C, and no clauses use column B.
1040 1041 1042 1043
 *
 * Note: in some circumstances we may find the same RestrictInfos coming
 * from multiple places.  Defend against redundant outputs by using
 * list_append_unique_ptr (pointer equality should be good enough).
1044
 */
1045
List *
1046 1047
group_clauses_by_indexkey(IndexOptInfo *index,
						  List *clauses, List *outer_clauses,
1048
						  Relids outer_relids,
1049
						  SaOpControl saop_control,
1050
						  bool *found_clause)
1051
{
1052
	List	   *clausegroup_list = NIL;
1053
	bool		found_outer_clause = false;
1054
	int			indexcol = 0;
1055
	Oid		   *families = index->opfamily;
1056

1057 1058 1059
	*found_clause = false;		/* default result */

	if (clauses == NIL && outer_clauses == NIL)
1060
		return NIL;				/* cannot succeed */
1061

1062
	do
1063
	{
1064
		Oid			curFamily = families[0];
1065
		List	   *clausegroup = NIL;
1066
		ListCell   *l;
1067

1068 1069
		/* check the current clauses */
		foreach(l, clauses)
1070
		{
1071
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1072

1073
			Assert(IsA(rinfo, RestrictInfo));
1074
			if (match_clause_to_indexcol(index,
1075
										 indexcol,
1076
										 curFamily,
1077
										 rinfo,
1078 1079
										 outer_relids,
										 saop_control))
1080
			{
1081
				clausegroup = list_append_unique_ptr(clausegroup, rinfo);
1082 1083 1084
				if (saop_control != SAOP_REQUIRE ||
					IsA(rinfo->clause, ScalarArrayOpExpr))
					*found_clause = true;
1085
			}
1086
		}
1087

1088 1089
		/* check the outer clauses */
		foreach(l, outer_clauses)
1090
		{
1091
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1092

1093
			Assert(IsA(rinfo, RestrictInfo));
1094
			if (match_clause_to_indexcol(index,
1095
										 indexcol,
1096
										 curFamily,
1097
										 rinfo,
1098 1099
										 outer_relids,
										 saop_control))
1100 1101 1102 1103
			{
				clausegroup = list_append_unique_ptr(clausegroup, rinfo);
				found_outer_clause = true;
			}
1104 1105
		}

1106
		/*
1107
		 * If no clauses match this key, check for amoptionalkey restriction.
1108
		 */
1109 1110
		if (clausegroup == NIL && !index->amoptionalkey && indexcol == 0)
			return NIL;
1111

1112
		clausegroup_list = lappend(clausegroup_list, clausegroup);
1113

1114
		indexcol++;
1115
		families++;
1116

1117
	} while (!DoneMatchingIndexKeys(families));
1118

1119 1120
	if (!*found_clause && !found_outer_clause)
		return NIL;				/* no indexable clauses anywhere */
1121

1122
	return clausegroup_list;
1123 1124
}

1125

1126
/*
1127 1128
 * match_clause_to_indexcol()
 *	  Determines whether a restriction clause matches a column of an index.
1129
 *
1130
 *	  To match a normal index, the clause:
1131
 *
1132 1133
 *	  (1)  must be in the form (indexkey op const) or (const op indexkey);
 *		   and
1134
 *	  (2)  must contain an operator which is in the same family as the index
1135
 *		   operator for this column, or is a "special" operator as recognized
1136
 *		   by match_special_index_operator().
1137
 *
1138 1139 1140 1141
 *	  Our definition of "const" is pretty liberal: we allow Vars belonging
 *	  to the caller-specified outer_relids relations (which had better not
 *	  include the relation whose index is being tested).  outer_relids should
 *	  be NULL when checking simple restriction clauses, and the outer side
1142
 *	  of the join when building a join inner scan.	Other than that, the
1143 1144 1145 1146 1147 1148 1149 1150
 *	  only thing we don't like is volatile functions.
 *
 *	  Note: in most cases we already know that the clause as a whole uses
 *	  vars from the interesting set of relations.  The reason for the
 *	  outer_relids test is to reject clauses like (a.f1 OP (b.f2 OP a.f3));
 *	  that's not processable by an indexscan nestloop join on A, whereas
 *	  (a.f1 OP (b.f2 OP c.f3)) is.
 *
1151 1152 1153 1154 1155
 *	  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.
1156
 *
1157 1158 1159
 *	  It is also possible to match RowCompareExpr clauses to indexes (but
 *	  currently, only btree indexes handle this).  In this routine we will
 *	  report a match if the first column of the row comparison matches the
Bruce Momjian's avatar
Bruce Momjian committed
1160
 *	  target index column.	This is sufficient to guarantee that some index
1161 1162 1163 1164
 *	  condition can be constructed from the RowCompareExpr --- whether the
 *	  remaining columns match the index too is considered in
 *	  expand_indexqual_rowcompare().
 *
1165 1166 1167 1168 1169
 *	  It is also possible to match ScalarArrayOpExpr clauses to indexes, when
 *	  the clause is of the form "indexkey op ANY (arrayconst)".  Since the
 *	  executor can only handle these in the context of bitmap index scans,
 *	  our caller specifies whether to allow these or not.
 *
1170 1171 1172
 *	  For boolean indexes, it is also possible to match the clause directly
 *	  to the indexkey; or perhaps the clause is (NOT indexkey).
 *
1173
 * 'index' is the index of interest.
1174
 * 'indexcol' is a column number of 'index' (counting from 0).
1175
 * 'opfamily' is the corresponding operator family.
1176
 * 'rinfo' is the clause to be tested (as a RestrictInfo node).
1177
 * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used.
1178
 *
1179 1180
 * Returns true if the clause can be used with this index key.
 *
1181 1182
 * NOTE:  returns false if clause is an OR or AND clause; it is the
 * responsibility of higher-level routines to cope with those.
1183
 */
1184
static bool
1185
match_clause_to_indexcol(IndexOptInfo *index,
1186
						 int indexcol,
1187
						 Oid opfamily,
1188
						 RestrictInfo *rinfo,
1189 1190
						 Relids outer_relids,
						 SaOpControl saop_control)
1191
{
1192
	Expr	   *clause = rinfo->clause;
1193
	Node	   *leftop,
1194
			   *rightop;
1195 1196 1197 1198
	Relids		left_relids;
	Relids		right_relids;
	Oid			expr_op;
	bool		plain_op;
1199

1200
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1201 1202 1203 1204
	 * Never match pseudoconstants to indexes.	(Normally this could not
	 * happen anyway, since a pseudoconstant clause couldn't contain a Var,
	 * but what if someone builds an expression index on a constant? It's not
	 * totally unreasonable to do so with a partial index, either.)
1205 1206 1207 1208
	 */
	if (rinfo->pseudoconstant)
		return false;

1209
	/* First check for boolean-index cases. */
1210
	if (IsBooleanOpfamily(opfamily))
1211
	{
1212
		if (match_boolean_index_clause((Node *) clause, indexcol, index))
1213 1214 1215
			return true;
	}

1216 1217
	/*
	 * Clause must be a binary opclause, or possibly a ScalarArrayOpExpr
1218 1219
	 * (which is always binary, by definition).  Or it could be a
	 * RowCompareExpr, which we pass off to match_rowcompare_to_indexcol().
1220
	 * Or, if the index supports it, we can handle IS NULL clauses.
1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247
	 */
	if (is_opclause(clause))
	{
		leftop = get_leftop(clause);
		rightop = get_rightop(clause);
		if (!leftop || !rightop)
			return false;
		left_relids = rinfo->left_relids;
		right_relids = rinfo->right_relids;
		expr_op = ((OpExpr *) clause)->opno;
		plain_op = true;
	}
	else if (saop_control != SAOP_FORBID &&
			 clause && IsA(clause, ScalarArrayOpExpr))
	{
		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;

		/* We only accept ANY clauses, not ALL */
		if (!saop->useOr)
			return false;
		leftop = (Node *) linitial(saop->args);
		rightop = (Node *) lsecond(saop->args);
		left_relids = NULL;		/* not actually needed */
		right_relids = pull_varnos(rightop);
		expr_op = saop->opno;
		plain_op = false;
	}
1248 1249
	else if (clause && IsA(clause, RowCompareExpr))
	{
1250
		return match_rowcompare_to_indexcol(index, indexcol, opfamily,
1251 1252 1253
											(RowCompareExpr *) clause,
											outer_relids);
	}
1254 1255
	else if (index->amsearchnulls && IsA(clause, NullTest))
	{
Bruce Momjian's avatar
Bruce Momjian committed
1256
		NullTest   *nt = (NullTest *) clause;
1257 1258 1259 1260 1261 1262

		if (nt->nulltesttype == IS_NULL &&
			match_index_to_operand((Node *) nt->arg, indexcol, index))
			return true;
		return false;
	}
1263
	else
1264
		return false;
1265

1266
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1267
	 * Check for clauses of the form: (indexkey operator constant) or
1268
	 * (constant operator indexkey).  See above notes about const-ness.
1269
	 */
1270
	if (match_index_to_operand(leftop, indexcol, index) &&
1271
		bms_is_subset(right_relids, outer_relids) &&
1272
		!contain_volatile_functions(rightop))
1273
	{
1274
		if (is_indexable_operator(expr_op, opfamily, true))
1275 1276
			return true;

1277
		/*
1278
		 * If we didn't find a member of the index's opfamily, see whether it
1279
		 * is a "special" indexable operator.
1280
		 */
1281
		if (plain_op &&
1282
			match_special_index_operator(clause, opfamily, true))
1283 1284 1285
			return true;
		return false;
	}
Bruce Momjian's avatar
Bruce Momjian committed
1286

1287 1288 1289
	if (plain_op &&
		match_index_to_operand(rightop, indexcol, index) &&
		bms_is_subset(left_relids, outer_relids) &&
1290
		!contain_volatile_functions(leftop))
1291
	{
1292
		if (is_indexable_operator(expr_op, opfamily, false))
1293
			return true;
1294

1295
		/*
1296
		 * If we didn't find a member of the index's opfamily, see whether it
1297
		 * is a "special" indexable operator.
1298
		 */
1299
		if (match_special_index_operator(clause, opfamily, false))
1300 1301 1302
			return true;
		return false;
	}
1303

1304 1305 1306
	return false;
}

1307
/*
1308
 * is_indexable_operator
1309
 *	  Does the operator match the specified index opfamily?
1310
 *
1311 1312
 * If the indexkey is on the right, what we actually want to know
 * is whether the operator has a commutator operator that matches
1313
 * the opfamily.
1314
 */
1315
static bool
1316
is_indexable_operator(Oid expr_op, Oid opfamily, bool indexkey_on_left)
1317 1318
{
	/* Get the commuted operator if necessary */
1319 1320 1321 1322 1323 1324
	if (!indexkey_on_left)
	{
		expr_op = get_commutator(expr_op);
		if (expr_op == InvalidOid)
			return false;
	}
1325

1326 1327
	/* OK if the (commuted) operator is a member of the index's opfamily */
	return op_in_opfamily(expr_op, opfamily);
1328 1329
}

1330 1331 1332 1333 1334 1335 1336 1337
/*
 * match_rowcompare_to_indexcol()
 *	  Handles the RowCompareExpr case for match_clause_to_indexcol(),
 *	  which see for comments.
 */
static bool
match_rowcompare_to_indexcol(IndexOptInfo *index,
							 int indexcol,
1338
							 Oid opfamily,
1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350
							 RowCompareExpr *clause,
							 Relids outer_relids)
{
	Node	   *leftop,
			   *rightop;
	Oid			expr_op;

	/* Forget it if we're not dealing with a btree index */
	if (index->relam != BTREE_AM_OID)
		return false;

	/*
1351 1352
	 * We could do the matching on the basis of insisting that the opfamily
	 * shown in the RowCompareExpr be the same as the index column's opfamily,
Bruce Momjian's avatar
Bruce Momjian committed
1353 1354 1355 1356 1357 1358
	 * but that could fail in the presence of reverse-sort opfamilies: it'd be
	 * a matter of chance whether RowCompareExpr had picked the forward or
	 * reverse-sort family.  So look only at the operator, and match if it is
	 * a member of the index's opfamily (after commutation, if the indexkey is
	 * on the right).  We'll worry later about whether any additional
	 * operators are matchable to the index.
1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384
	 */
	leftop = (Node *) linitial(clause->largs);
	rightop = (Node *) linitial(clause->rargs);
	expr_op = linitial_oid(clause->opnos);

	/*
	 * These syntactic tests are the same as in match_clause_to_indexcol()
	 */
	if (match_index_to_operand(leftop, indexcol, index) &&
		bms_is_subset(pull_varnos(rightop), outer_relids) &&
		!contain_volatile_functions(rightop))
	{
		/* OK, indexkey is on left */
	}
	else if (match_index_to_operand(rightop, indexcol, index) &&
			 bms_is_subset(pull_varnos(leftop), outer_relids) &&
			 !contain_volatile_functions(leftop))
	{
		/* indexkey is on right, so commute the operator */
		expr_op = get_commutator(expr_op);
		if (expr_op == InvalidOid)
			return false;
	}
	else
		return false;

1385 1386
	/* We're good if the operator is the right type of opfamily member */
	switch (get_op_opfamily_strategy(expr_op, opfamily))
1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398
	{
		case BTLessStrategyNumber:
		case BTLessEqualStrategyNumber:
		case BTGreaterEqualStrategyNumber:
		case BTGreaterStrategyNumber:
			return true;
	}

	return false;
}


1399
/****************************************************************************
1400
 *				----  ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS	----
1401 1402
 ****************************************************************************/

1403 1404
/*
 * check_partial_indexes
1405 1406 1407 1408 1409 1410
 *		Check each partial index of the relation, and mark it predOK if
 *		the index's predicate is satisfied for this query.
 *
 * Note: it is possible for this to get re-run after adding more restrictions
 * to the rel; so we might be able to prove more indexes OK.  We assume that
 * adding more restrictions can't make an index not OK.
1411 1412
 */
void
1413
check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
1414 1415
{
	List	   *restrictinfo_list = rel->baserestrictinfo;
1416
	ListCell   *ilist;
1417

1418
	foreach(ilist, rel->indexlist)
1419
	{
1420
		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
1421

1422 1423
		if (index->indpred == NIL)
			continue;			/* ignore non-partial indexes */
1424

1425 1426 1427
		if (index->predOK)
			continue;			/* don't repeat work if already proven OK */

1428 1429
		index->predOK = predicate_implied_by(index->indpred,
											 restrictinfo_list);
1430
	}
1431 1432 1433
}

/****************************************************************************
1434
 *				----  ROUTINES TO CHECK JOIN CLAUSES  ----
1435 1436
 ****************************************************************************/

1437
/*
1438 1439
 * indexable_outerrelids
 *	  Finds all other relids that participate in any indexable join clause
1440
 *	  for the specified table.	Returns a set of relids.
1441
 */
1442
static Relids
1443
indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel)
1444
{
1445
	Relids		outer_relids = NULL;
1446 1447
	bool		is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
	ListCell   *lc1;
1448

1449 1450 1451 1452
	/*
	 * Examine each joinclause in the joininfo list to see if it matches any
	 * key of any index.  If so, add the clause's other rels to the result.
	 */
1453
	foreach(lc1, rel->joininfo)
1454
	{
1455
		RestrictInfo *joininfo = (RestrictInfo *) lfirst(lc1);
1456
		Relids		other_rels;
1457

1458
		other_rels = bms_difference(joininfo->required_relids, rel->relids);
1459 1460 1461 1462
		if (matches_any_index(joininfo, rel, other_rels))
			outer_relids = bms_join(outer_relids, other_rels);
		else
			bms_free(other_rels);
1463
	}
1464

1465
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1466 1467
	 * We also have to look through the query's EquivalenceClasses to see if
	 * any of them could generate indexable join conditions for this rel.
1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478
	 */
	if (rel->has_eclass_joins)
	{
		foreach(lc1, root->eq_classes)
		{
			EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
			Relids		other_rels = NULL;
			bool		found_index = false;
			ListCell   *lc2;

			/*
Bruce Momjian's avatar
Bruce Momjian committed
1479 1480
			 * Won't generate joinclauses if const or single-member (the
			 * latter test covers the volatile case too)
1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529
			 */
			if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
				continue;

			/*
			 * Note we don't test ec_broken; if we did, we'd need a separate
			 * code path to look through ec_sources.  Checking the members
			 * anyway is OK as a possibly-overoptimistic heuristic.
			 */

			/*
			 * No point in searching if rel not mentioned in eclass (but we
			 * can't tell that for a child rel).
			 */
			if (!is_child_rel &&
				!bms_is_subset(rel->relids, cur_ec->ec_relids))
				continue;

			/*
			 * Scan members, looking for both an index match and join
			 * candidates
			 */
			foreach(lc2, cur_ec->ec_members)
			{
				EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);

				/* Join candidate? */
				if (!cur_em->em_is_child &&
					!bms_overlap(cur_em->em_relids, rel->relids))
				{
					other_rels = bms_add_members(other_rels,
												 cur_em->em_relids);
					continue;
				}

				/* Check for index match (only need one) */
				if (!found_index &&
					bms_equal(cur_em->em_relids, rel->relids) &&
					eclass_matches_any_index(cur_ec, cur_em, rel))
					found_index = true;
			}

			if (found_index)
				outer_relids = bms_join(outer_relids, other_rels);
			else
				bms_free(other_rels);
		}
	}

1530 1531
	return outer_relids;
}
1532

1533
/*
1534 1535 1536
 * matches_any_index
 *	  Workhorse for indexable_outerrelids: see if a joinclause can be
 *	  matched to any index of the given rel.
1537 1538
 */
static bool
1539
matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
1540 1541
{
	ListCell   *l;
1542

1543
	Assert(IsA(rinfo, RestrictInfo));
1544

1545 1546 1547
	if (restriction_is_or_clause(rinfo))
	{
		foreach(l, ((BoolExpr *) rinfo->orclause)->args)
1548
		{
1549
			Node	   *orarg = (Node *) lfirst(l);
1550 1551 1552 1553

			/* OR arguments should be ANDs or sub-RestrictInfos */
			if (and_clause(orarg))
			{
1554
				ListCell   *j;
1555 1556

				/* Recurse to examine AND items and sub-ORs */
1557 1558 1559 1560 1561 1562 1563
				foreach(j, ((BoolExpr *) orarg)->args)
				{
					RestrictInfo *arinfo = (RestrictInfo *) lfirst(j);

					if (matches_any_index(arinfo, rel, outer_relids))
						return true;
				}
1564 1565 1566
			}
			else
			{
1567
				/* Recurse to examine simple clause */
1568 1569 1570
				Assert(IsA(orarg, RestrictInfo));
				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
				if (matches_any_index((RestrictInfo *) orarg, rel,
1571
									  outer_relids))
1572 1573
					return true;
			}
1574
		}
1575

1576 1577
		return false;
	}
1578 1579 1580 1581 1582 1583

	/* Normal case for a simple restriction clause */
	foreach(l, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
		int			indexcol = 0;
1584
		Oid		   *families = index->opfamily;
1585 1586 1587

		do
		{
1588
			Oid			curFamily = families[0];
1589 1590 1591

			if (match_clause_to_indexcol(index,
										 indexcol,
1592
										 curFamily,
1593
										 rinfo,
1594 1595
										 outer_relids,
										 SAOP_ALLOW))
1596 1597 1598
				return true;

			indexcol++;
1599 1600
			families++;
		} while (!DoneMatchingIndexKeys(families));
1601 1602 1603
	}

	return false;
1604 1605
}

1606 1607 1608 1609 1610 1611 1612 1613
/*
 * eclass_matches_any_index
 *	  Workhorse for indexable_outerrelids: see if an EquivalenceClass member
 *	  can be matched to any index column of the given rel.
 *
 * This is also exported for use by find_eclass_clauses_for_index_join.
 */
bool
1614
eclass_matches_any_index(EquivalenceClass *ec, EquivalenceMember *em,
1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628
						 RelOptInfo *rel)
{
	ListCell   *l;

	foreach(l, rel->indexlist)
	{
		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
		int			indexcol = 0;
		Oid		   *families = index->opfamily;

		do
		{
			Oid			curFamily = families[0];

1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640
			/*
			 * If it's a btree index, we can reject it if its opfamily isn't
			 * compatible with the EC, since no clause generated from the
			 * EC could be used with the index.  For non-btree indexes,
			 * we can't easily tell whether clauses generated from the EC
			 * could be used with the index, so only check for expression
			 * match.  This might mean we return "true" for a useless index,
			 * but that will just cause some wasted planner cycles; it's
			 * better than ignoring useful indexes.
			 */
			if ((index->relam != BTREE_AM_OID ||
				 list_member_oid(ec->ec_opfamilies, curFamily)) &&
1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652
				match_index_to_operand((Node *) em->em_expr, indexcol, index))
				return true;

			indexcol++;
			families++;
		} while (!DoneMatchingIndexKeys(families));
	}

	return false;
}


1653
/*
1654
 * best_inner_indexscan
1655
 *	  Finds the best available inner indexscans for a nestloop join
1656
 *	  with the given rel on the inside and the given outer_rel outside.
1657
 *
1658 1659 1660 1661 1662 1663 1664
 * *cheapest_startup gets the path with least startup cost
 * *cheapest_total gets the path with least total cost (often the same path)
 * Both are set to NULL if there are no possible inner indexscans.
 *
 * We ignore ordering considerations, since a nestloop's inner scan's order
 * is uninteresting.  Hence startup cost and total cost are the only figures
 * of merit to consider.
1665 1666
 *
 * Note: create_index_paths() must have been run previously for this rel,
1667
 * else the results will always be NULL.
1668
 */
1669
void
1670
best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
1671 1672
					 RelOptInfo *outer_rel, JoinType jointype,
					 Path **cheapest_startup, Path **cheapest_total)
1673
{
1674
	Relids		outer_relids;
1675
	bool		isouterjoin;
1676 1677 1678
	List	   *clause_list;
	List	   *indexpaths;
	List	   *bitindexpaths;
1679
	List	   *allindexpaths;
1680
	ListCell   *l;
1681
	InnerIndexscanInfo *info;
1682
	MemoryContext oldcontext;
1683

1684 1685 1686
	/* Initialize results for failure returns */
	*cheapest_startup = *cheapest_total = NULL;

1687
	/*
1688
	 * Nestloop only supports inner, left, semi, and anti joins.
1689 1690
	 */
	switch (jointype)
1691
	{
1692
		case JOIN_INNER:
1693
		case JOIN_SEMI:
1694 1695 1696
			isouterjoin = false;
			break;
		case JOIN_LEFT:
1697
		case JOIN_ANTI:
1698 1699 1700
			isouterjoin = true;
			break;
		default:
1701
			return;
1702
	}
Bruce Momjian's avatar
Bruce Momjian committed
1703

1704 1705 1706
	/*
	 * If there are no indexable joinclauses for this rel, exit quickly.
	 */
1707
	if (bms_is_empty(rel->index_outer_relids))
1708
		return;
Bruce Momjian's avatar
Bruce Momjian committed
1709

1710
	/*
1711 1712 1713 1714
	 * Otherwise, we have to do path selection in the main planning context,
	 * 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.)
1715
	 */
1716
	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
Bruce Momjian's avatar
Bruce Momjian committed
1717

1718
	/*
1719
	 * Intersect the given outer relids with index_outer_relids to find the
1720 1721
	 * set of outer relids actually relevant for this rel. If there are none,
	 * again we can fail immediately.
1722
	 */
1723
	outer_relids = bms_intersect(rel->index_outer_relids, outer_rel->relids);
1724
	if (bms_is_empty(outer_relids))
1725
	{
1726
		bms_free(outer_relids);
1727
		MemoryContextSwitchTo(oldcontext);
1728
		return;
1729
	}
Bruce Momjian's avatar
Bruce Momjian committed
1730

1731
	/*
1732 1733 1734
	 * 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
1735
	 * should always be the same for a given combination of rels.)
1736 1737
	 *
	 * NOTE: because we cache on outer_relids rather than outer_rel->relids,
1738
	 * we will report the same paths and hence path cost for joins with
1739
	 * different sets of irrelevant rels on the outside.  Now that cost_index
Bruce Momjian's avatar
Bruce Momjian committed
1740 1741 1742
	 * is sensitive to outer_rel->rows, this is not really right.  However the
	 * error is probably not large.  Is it worth establishing a separate cache
	 * entry for each distinct outer_rel->relids set to get this right?
1743
	 */
1744
	foreach(l, rel->index_inner_paths)
1745
	{
1746
		info = (InnerIndexscanInfo *) lfirst(l);
1747
		if (bms_equal(info->other_relids, outer_relids) &&
1748 1749
			info->isouterjoin == isouterjoin)
		{
1750
			bms_free(outer_relids);
1751
			MemoryContextSwitchTo(oldcontext);
1752 1753 1754
			*cheapest_startup = info->cheapest_startup_innerpath;
			*cheapest_total = info->cheapest_total_innerpath;
			return;
1755 1756
		}
	}
1757

1758
	/*
1759 1760 1761 1762
	 * Find all the relevant restriction and join clauses.
	 *
	 * Note: because we include restriction clauses, we will find indexscans
	 * that could be plain indexscans, ie, they don't require the join context
Bruce Momjian's avatar
Bruce Momjian committed
1763
	 * at all.	This may seem redundant, but we need to include those scans in
1764
	 * the input given to choose_bitmap_and() to be sure we find optimal AND
Bruce Momjian's avatar
Bruce Momjian committed
1765 1766 1767
	 * combinations of join and non-join scans.  Also, even if the "best inner
	 * indexscan" is just a plain indexscan, it will have a different cost
	 * estimate because of cache effects.
1768
	 */
1769
	clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);
1770

1771 1772
	/*
	 * Find all the index paths that are usable for this join, except for
1773
	 * stuff involving OR and ScalarArrayOpExpr clauses.
1774
	 */
1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795
	allindexpaths = find_usable_indexes(root, rel,
										clause_list, NIL,
										false, outer_rel,
										SAOP_FORBID,
										ST_ANYSCAN);

	/*
	 * Include the ones that are usable as plain indexscans in indexpaths, and
	 * include the ones that are usable as bitmap scans in bitindexpaths.
	 */
	indexpaths = bitindexpaths = NIL;
	foreach(l, allindexpaths)
	{
		IndexPath  *ipath = (IndexPath *) lfirst(l);

		if (ipath->indexinfo->amhasgettuple)
			indexpaths = lappend(indexpaths, ipath);

		if (ipath->indexinfo->amhasgetbitmap)
			bitindexpaths = lappend(bitindexpaths, ipath);
	}
Bruce Momjian's avatar
Bruce Momjian committed
1796

1797
	/*
1798 1799
	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
	 * clause list.
1800
	 */
1801 1802 1803 1804
	bitindexpaths = list_concat(bitindexpaths,
								generate_bitmap_or_paths(root, rel,
														 clause_list, NIL,
														 outer_rel));
Bruce Momjian's avatar
Bruce Momjian committed
1805

1806 1807 1808 1809 1810 1811 1812
	/*
	 * Likewise, generate paths using ScalarArrayOpExpr clauses; these can't
	 * be simple indexscans but they can be used in bitmap scans.
	 */
	bitindexpaths = list_concat(bitindexpaths,
								find_saop_paths(root, rel,
												clause_list, NIL,
1813
												false, outer_rel));
1814

1815
	/*
1816 1817
	 * If we found anything usable, generate a BitmapHeapPath for the most
	 * promising combination of bitmap index paths.
1818 1819 1820 1821 1822 1823
	 */
	if (bitindexpaths != NIL)
	{
		Path	   *bitmapqual;
		BitmapHeapPath *bpath;

1824 1825
		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, outer_rel);
		bpath = create_bitmap_heap_path(root, rel, bitmapqual, outer_rel);
1826 1827 1828 1829
		indexpaths = lappend(indexpaths, bpath);
	}

	/*
1830
	 * Now choose the cheapest members of indexpaths.
1831
	 */
1832
	if (indexpaths != NIL)
1833
	{
1834 1835 1836 1837 1838
		*cheapest_startup = *cheapest_total = (Path *) linitial(indexpaths);

		for_each_cell(l, lnext(list_head(indexpaths)))
		{
			Path	   *path = (Path *) lfirst(l);
1839

1840 1841 1842 1843 1844
			if (compare_path_costs(path, *cheapest_startup, STARTUP_COST) < 0)
				*cheapest_startup = path;
			if (compare_path_costs(path, *cheapest_total, TOTAL_COST) < 0)
				*cheapest_total = path;
		}
1845
	}
1846

1847
	/* Cache the results --- whether positive or negative */
1848 1849 1850
	info = makeNode(InnerIndexscanInfo);
	info->other_relids = outer_relids;
	info->isouterjoin = isouterjoin;
1851 1852
	info->cheapest_startup_innerpath = *cheapest_startup;
	info->cheapest_total_innerpath = *cheapest_total;
1853
	rel->index_inner_paths = lcons(info, rel->index_inner_paths);
1854

1855
	MemoryContextSwitchTo(oldcontext);
1856
}
1857

1858
/*
1859
 * find_clauses_for_join
1860
 *	  Generate a list of clauses that are potentially useful for
1861
 *	  scanning rel as the inner side of a nestloop join.
1862
 *
1863 1864 1865 1866
 * We consider both 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 there isn't any potential win here.
1867
 */
1868
static List *
1869
find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
1870
					  Relids outer_relids, bool isouterjoin)
1871
{
1872
	List	   *clause_list = NIL;
1873
	Relids		join_relids;
1874
	ListCell   *l;
1875

1876 1877 1878 1879 1880 1881
	/*
	 * Look for joinclauses that are usable with given outer_relids.  Note
	 * we'll take anything that's applicable to the join whether it has
	 * anything to do with an index or not; since we're only building a list,
	 * it's not worth filtering more finely here.
	 */
1882 1883
	join_relids = bms_union(rel->relids, outer_relids);

1884 1885
	foreach(l, rel->joininfo)
	{
1886
		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1887

1888
		/* Can't use pushed-down join clauses in outer join */
1889 1890 1891
		if (isouterjoin && rinfo->is_pushed_down)
			continue;
		if (!bms_is_subset(rinfo->required_relids, join_relids))
1892
			continue;
1893

1894
		clause_list = lappend(clause_list, rinfo);
1895 1896
	}

1897 1898
	bms_free(join_relids);

1899 1900
	/*
	 * Also check to see if any EquivalenceClasses can produce a relevant
Bruce Momjian's avatar
Bruce Momjian committed
1901 1902
	 * joinclause.	Since all such clauses are effectively pushed-down, this
	 * doesn't apply to outer joins.
1903 1904 1905 1906 1907
	 */
	if (!isouterjoin && rel->has_eclass_joins)
		clause_list = list_concat(clause_list,
								  find_eclass_clauses_for_index_join(root,
																	 rel,
Bruce Momjian's avatar
Bruce Momjian committed
1908
															  outer_relids));
1909 1910

	/* If no join clause was matched then forget it, per comments above */
1911
	if (clause_list == NIL)
1912
		return NIL;
1913

1914
	/* We can also use any plain restriction clauses for the rel */
1915 1916
	clause_list = list_concat(list_copy(rel->baserestrictinfo), clause_list);

1917
	return clause_list;
1918 1919
}

1920

1921 1922 1923 1924
/****************************************************************************
 *				----  PATH CREATION UTILITIES  ----
 ****************************************************************************/

1925 1926 1927 1928 1929 1930
/*
 * flatten_clausegroups_list
 *	  Given a list of lists of RestrictInfos, flatten it to a list
 *	  of RestrictInfos.
 *
 * This is used to flatten out the result of group_clauses_by_indexkey()
1931 1932
 * to produce an indexclauses list.  The original list structure mustn't
 * be altered, but it's OK to share copies of the underlying RestrictInfos.
1933 1934 1935 1936 1937
 */
List *
flatten_clausegroups_list(List *clausegroups)
{
	List	   *allclauses = NIL;
1938
	ListCell   *l;
1939 1940

	foreach(l, clausegroups)
1941
		allclauses = list_concat(allclauses, list_copy((List *) lfirst(l)));
1942 1943 1944 1945
	return allclauses;
}


1946 1947 1948 1949 1950 1951 1952 1953
/****************************************************************************
 *				----  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.
1954 1955 1956 1957
 *
 * operand: the nodetree to be compared to the index
 * indexcol: the column number of the index (counting from 0)
 * index: the index of interest
1958
 */
1959
bool
1960 1961
match_index_to_operand(Node *operand,
					   int indexcol,
1962
					   IndexOptInfo *index)
1963
{
1964 1965
	int			indkey;

1966
	/*
1967 1968 1969
	 * Ignore any RelabelType node above the operand.	This is needed to be
	 * able to apply indexscanning in binary-compatible-operator cases. Note:
	 * we can assume there is at most one RelabelType node;
1970 1971 1972
	 * eval_const_expressions() will have simplified if more than one.
	 */
	if (operand && IsA(operand, RelabelType))
1973
		operand = (Node *) ((RelabelType *) operand)->arg;
1974

1975 1976
	indkey = index->indexkeys[indexcol];
	if (indkey != 0)
1977 1978
	{
		/*
1979
		 * Simple index column; operand must be a matching Var.
1980
		 */
1981
		if (operand && IsA(operand, Var) &&
1982
			index->rel->relid == ((Var *) operand)->varno &&
1983
			indkey == ((Var *) operand)->varattno)
1984
			return true;
1985
	}
1986
	else
1987
	{
1988
		/*
1989 1990 1991
		 * Index expression; find the correct expression.  (This search could
		 * be avoided, at the cost of complicating all the callers of this
		 * routine; doesn't seem worth it.)
1992
		 */
1993
		ListCell   *indexpr_item;
1994 1995
		int			i;
		Node	   *indexkey;
1996

1997
		indexpr_item = list_head(index->indexprs);
1998 1999 2000 2001
		for (i = 0; i < indexcol; i++)
		{
			if (index->indexkeys[i] == 0)
			{
2002
				if (indexpr_item == NULL)
2003
					elog(ERROR, "wrong number of index expressions");
2004
				indexpr_item = lnext(indexpr_item);
2005 2006
			}
		}
2007
		if (indexpr_item == NULL)
2008
			elog(ERROR, "wrong number of index expressions");
2009
		indexkey = (Node *) lfirst(indexpr_item);
Bruce Momjian's avatar
Bruce Momjian committed
2010

2011 2012 2013 2014 2015
		/*
		 * Does it match the operand?  Again, strip any relabeling.
		 */
		if (indexkey && IsA(indexkey, RelabelType))
			indexkey = (Node *) ((RelabelType *) indexkey)->arg;
2016

2017 2018
		if (equal(indexkey, operand))
			return true;
2019 2020
	}

2021
	return false;
2022
}
2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033

/****************************************************************************
 *			----  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
2034
 * indexscan condition(s).	Then we can use the indexscan machinery
2035 2036
 * 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
2037
 * we deliver only the tuples we want.	(In essence, we're using a regular
2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048
 * 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.)
 *
2049 2050
 * Another thing that we do with this machinery is to provide special
 * smarts for "boolean" indexes (that is, indexes on boolean columns
2051
 * that support boolean equality).	We can transform a plain reference
2052 2053 2054 2055 2056 2057 2058 2059 2060 2061
 * to the indexkey into "indexkey = true", or "NOT indexkey" into
 * "indexkey = false", so as to make the expression indexable using the
 * regular index operators.  (As of Postgres 8.1, we must do this here
 * because constant simplification does the reverse transformation;
 * without this code there'd be no way to use such an index at all.)
 *
 * Three routines are provided here:
 *
 * match_special_index_operator() is just an auxiliary function for
 * match_clause_to_indexcol(); after the latter fails to recognize a
2062
 * restriction opclause's operator as a member of an index's opfamily,
2063 2064 2065 2066 2067 2068
 * it asks match_special_index_operator() whether the clause should be
 * considered an indexqual anyway.
 *
 * match_boolean_index_clause() similarly detects clauses that can be
 * converted into boolean equality operators.
 *
2069 2070 2071
 * expand_indexqual_conditions() converts a list of lists of RestrictInfo
 * nodes (with implicit AND semantics across list elements) into
 * a list of clauses that the executor can actually handle.  For operators
2072
 * that are members of the index's opfamily this transformation is a no-op,
2073 2074 2075
 * but clauses recognized by match_special_index_operator() or
 * match_boolean_index_clause() must be converted into one or more "regular"
 * indexqual conditions.
2076 2077 2078
 *----------
 */

2079 2080 2081 2082
/*
 * match_boolean_index_clause
 *	  Recognize restriction clauses that can be matched to a boolean index.
 *
2083 2084
 * This should be called only when IsBooleanOpfamily() recognizes the
 * index's operator family.  We check to see if the clause matches the
2085 2086 2087 2088 2089 2090 2091 2092
 * index's key.
 */
static bool
match_boolean_index_clause(Node *clause,
						   int indexcol,
						   IndexOptInfo *index)
{
	/* Direct match? */
2093
	if (match_index_to_operand(clause, indexcol, index))
2094 2095 2096 2097 2098
		return true;
	/* NOT clause? */
	if (not_clause(clause))
	{
		if (match_index_to_operand((Node *) get_notclausearg((Expr *) clause),
2099
								   indexcol, index))
2100 2101
			return true;
	}
2102

2103 2104
	/*
	 * Since we only consider clauses at top level of WHERE, we can convert
2105 2106
	 * indexkey IS TRUE and indexkey IS FALSE to index searches as well. The
	 * different meaning for NULL isn't important.
2107 2108 2109
	 */
	else if (clause && IsA(clause, BooleanTest))
	{
2110
		BooleanTest *btest = (BooleanTest *) clause;
2111 2112 2113 2114

		if (btest->booltesttype == IS_TRUE ||
			btest->booltesttype == IS_FALSE)
			if (match_index_to_operand((Node *) btest->arg,
2115
									   indexcol, index))
2116 2117 2118 2119 2120
				return true;
	}
	return false;
}

2121 2122 2123 2124 2125 2126
/*
 * 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
2127
 * the form (indexkey OP pseudoconst) or (pseudoconst OP indexkey),
2128
 * but the OP proved not to be one of the index's opfamily operators.
2129 2130 2131
 * Return 'true' if we can do something with it anyway.
 */
static bool
2132
match_special_index_operator(Expr *clause, Oid opfamily,
2133
							 bool indexkey_on_left)
2134 2135
{
	bool		isIndexable = false;
2136
	Node	   *rightop;
2137
	Oid			expr_op;
2138
	Const	   *patt;
2139 2140
	Const	   *prefix = NULL;
	Const	   *rest = NULL;
2141
	Pattern_Prefix_Status pstatus = Pattern_Prefix_None;
2142

2143 2144
	/*
	 * Currently, all known special operators require the indexkey on the
2145 2146
	 * left, but this test could be pushed into the switch statement if some
	 * are added that do not...
2147
	 */
2148
	if (!indexkey_on_left)
2149 2150 2151 2152
		return false;

	/* we know these will succeed */
	rightop = get_rightop(clause);
2153
	expr_op = ((OpExpr *) clause)->opno;
2154 2155

	/* again, required for all current special ops: */
2156
	if (!IsA(rightop, Const) ||
2157 2158
		((Const *) rightop)->constisnull)
		return false;
2159
	patt = (Const *) rightop;
2160 2161 2162 2163 2164 2165

	switch (expr_op)
	{
		case OID_TEXT_LIKE_OP:
		case OID_BPCHAR_LIKE_OP:
		case OID_NAME_LIKE_OP:
2166
			/* the right-hand const is type text for all of these */
2167 2168 2169
			pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
										   &prefix, &rest);
			isIndexable = (pstatus != Pattern_Prefix_None);
2170 2171 2172
			break;

		case OID_BYTEA_LIKE_OP:
2173 2174 2175
			pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
										   &prefix, &rest);
			isIndexable = (pstatus != Pattern_Prefix_None);
2176 2177
			break;

2178 2179 2180
		case OID_TEXT_ICLIKE_OP:
		case OID_BPCHAR_ICLIKE_OP:
		case OID_NAME_ICLIKE_OP:
2181
			/* the right-hand const is type text for all of these */
2182 2183 2184
			pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
										   &prefix, &rest);
			isIndexable = (pstatus != Pattern_Prefix_None);
2185 2186
			break;

2187 2188 2189
		case OID_TEXT_REGEXEQ_OP:
		case OID_BPCHAR_REGEXEQ_OP:
		case OID_NAME_REGEXEQ_OP:
2190
			/* the right-hand const is type text for all of these */
2191 2192 2193
			pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
										   &prefix, &rest);
			isIndexable = (pstatus != Pattern_Prefix_None);
2194 2195 2196 2197 2198
			break;

		case OID_TEXT_ICREGEXEQ_OP:
		case OID_BPCHAR_ICREGEXEQ_OP:
		case OID_NAME_ICREGEXEQ_OP:
2199
			/* the right-hand const is type text for all of these */
2200 2201 2202
			pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
										   &prefix, &rest);
			isIndexable = (pstatus != Pattern_Prefix_None);
2203
			break;
2204 2205 2206 2207 2208

		case OID_INET_SUB_OP:
		case OID_INET_SUBEQ_OP:
			isIndexable = true;
			break;
2209 2210
	}

2211 2212 2213 2214 2215 2216
	if (prefix)
	{
		pfree(DatumGetPointer(prefix->constvalue));
		pfree(prefix);
	}

2217
	/* done if the expression doesn't look indexable */
2218
	if (!isIndexable)
2219 2220 2221
		return false;

	/*
2222
	 * Must also check that index's opfamily supports the operators we will
2223
	 * want to apply.  (A hash index, for example, will not support ">=".)
2224 2225
	 * Currently, only btree supports the operators we need.
	 *
2226 2227 2228 2229
	 * Note: actually, in the Pattern_Prefix_Exact case, we only need "="
	 * so a hash index would work.  Currently it doesn't seem worth checking
	 * for that, however.
	 *
Bruce Momjian's avatar
Bruce Momjian committed
2230 2231 2232
	 * We insist on the opfamily being the specific one we expect, else we'd
	 * do the wrong thing if someone were to make a reverse-sort opfamily with
	 * the same operators.
2233 2234 2235 2236
	 *
	 * The non-pattern opclasses will not sort the way we need in most non-C
	 * locales.  We can use such an index anyway for an exact match (simple
	 * equality), but not for prefix-match cases.
2237 2238 2239 2240
	 */
	switch (expr_op)
	{
		case OID_TEXT_LIKE_OP:
2241
		case OID_TEXT_ICLIKE_OP:
2242 2243
		case OID_TEXT_REGEXEQ_OP:
		case OID_TEXT_ICREGEXEQ_OP:
2244
			isIndexable =
2245
				(opfamily == TEXT_PATTERN_BTREE_FAM_OID) ||
2246 2247
				(opfamily == TEXT_BTREE_FAM_OID &&
				 (pstatus == Pattern_Prefix_Exact || lc_collate_is_c()));
2248 2249
			break;

2250
		case OID_BPCHAR_LIKE_OP:
2251
		case OID_BPCHAR_ICLIKE_OP:
2252 2253
		case OID_BPCHAR_REGEXEQ_OP:
		case OID_BPCHAR_ICREGEXEQ_OP:
2254
			isIndexable =
2255
				(opfamily == BPCHAR_PATTERN_BTREE_FAM_OID) ||
2256 2257
				(opfamily == BPCHAR_BTREE_FAM_OID &&
				 (pstatus == Pattern_Prefix_Exact || lc_collate_is_c()));
2258 2259 2260
			break;

		case OID_NAME_LIKE_OP:
2261
		case OID_NAME_ICLIKE_OP:
2262 2263
		case OID_NAME_REGEXEQ_OP:
		case OID_NAME_ICREGEXEQ_OP:
2264 2265
			/* name uses locale-insensitive sorting */
			isIndexable = (opfamily == NAME_BTREE_FAM_OID);
2266 2267 2268
			break;

		case OID_BYTEA_LIKE_OP:
2269
			isIndexable = (opfamily == BYTEA_BTREE_FAM_OID);
2270
			break;
2271 2272 2273

		case OID_INET_SUB_OP:
		case OID_INET_SUBEQ_OP:
2274
			isIndexable = (opfamily == NETWORK_BTREE_FAM_OID);
2275
			break;
2276 2277
	}

2278 2279 2280 2281 2282
	return isIndexable;
}

/*
 * expand_indexqual_conditions
2283 2284
 *	  Given a list of sublists of RestrictInfo nodes, produce a flat list
 *	  of index qual clauses.  Standard qual clauses (those in the index's
2285
 *	  opfamily) are passed through unchanged.  Boolean clauses and "special"
2286
 *	  index operators are expanded into clauses that the indexscan machinery
2287 2288
 *	  will know what to do with.  RowCompare clauses are simplified if
 *	  necessary to create a clause that is fully checkable by the index.
2289 2290
 *
 * The input list is ordered by index key, and so the output list is too.
2291 2292 2293
 * (The latter is not depended on by any part of the core planner, I believe,
 * but parts of the executor require it, and so do the amcostestimate
 * functions.)
2294 2295
 */
List *
2296
expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups)
2297
{
2298
	List	   *resultquals = NIL;
2299
	ListCell   *clausegroup_item;
2300
	int			indexcol = 0;
2301
	Oid		   *families = index->opfamily;
2302 2303 2304

	if (clausegroups == NIL)
		return NIL;
2305

2306
	clausegroup_item = list_head(clausegroups);
2307
	do
2308
	{
2309
		Oid			curFamily = families[0];
2310
		ListCell   *l;
2311

2312
		foreach(l, (List *) lfirst(clausegroup_item))
2313
		{
2314
			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
Bruce Momjian's avatar
Bruce Momjian committed
2315
			Expr	   *clause = rinfo->clause;
2316

2317
			/* First check for boolean cases */
2318
			if (IsBooleanOpfamily(curFamily))
2319
			{
2320
				Expr	   *boolqual;
2321

2322
				boolqual = expand_boolean_index_clause((Node *) clause,
2323 2324 2325 2326 2327 2328
													   indexcol,
													   index);
				if (boolqual)
				{
					resultquals = lappend(resultquals,
										  make_restrictinfo(boolqual,
2329
															true,
2330
															false,
2331
															false,
2332
															NULL));
2333 2334 2335 2336
					continue;
				}
			}

2337
			/*
2338 2339
			 * Else it must be an opclause (usual case), ScalarArrayOp,
			 * RowCompare, or NullTest
2340 2341
			 */
			if (is_opclause(clause))
2342
			{
2343 2344
				resultquals = list_concat(resultquals,
										  expand_indexqual_opclause(rinfo,
Bruce Momjian's avatar
Bruce Momjian committed
2345
																 curFamily));
2346 2347 2348 2349
			}
			else if (IsA(clause, ScalarArrayOpExpr))
			{
				/* no extra work at this time */
2350 2351
				resultquals = lappend(resultquals, rinfo);
			}
2352 2353 2354 2355 2356 2357 2358
			else if (IsA(clause, RowCompareExpr))
			{
				resultquals = lappend(resultquals,
									  expand_indexqual_rowcompare(rinfo,
																  index,
																  indexcol));
			}
2359 2360 2361 2362 2363 2364 2365 2366 2367 2368
			else if (IsA(clause, NullTest))
			{
				Assert(index->amsearchnulls);
				resultquals = lappend(resultquals,
									  make_restrictinfo(clause,
														true,
														false,
														false,
														NULL));
			}
2369 2370 2371
			else
				elog(ERROR, "unsupported indexqual type: %d",
					 (int) nodeTag(clause));
2372
		}
2373

2374
		clausegroup_item = lnext(clausegroup_item);
2375 2376

		indexcol++;
2377 2378
		families++;
	} while (clausegroup_item != NULL && !DoneMatchingIndexKeys(families));
2379

2380
	Assert(clausegroup_item == NULL);	/* else more groups than indexkeys */
2381

2382
	return resultquals;
2383 2384
}

2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397
/*
 * expand_boolean_index_clause
 *	  Convert a clause recognized by match_boolean_index_clause into
 *	  a boolean equality operator clause.
 *
 * Returns NULL if the clause isn't a boolean index qual.
 */
static Expr *
expand_boolean_index_clause(Node *clause,
							int indexcol,
							IndexOptInfo *index)
{
	/* Direct match? */
2398
	if (match_index_to_operand(clause, indexcol, index))
2399 2400 2401 2402 2403 2404 2405 2406 2407
	{
		/* convert to indexkey = TRUE */
		return make_opclause(BooleanEqualOperator, BOOLOID, false,
							 (Expr *) clause,
							 (Expr *) makeBoolConst(true, false));
	}
	/* NOT clause? */
	if (not_clause(clause))
	{
2408
		Node	   *arg = (Node *) get_notclausearg((Expr *) clause);
2409 2410

		/* It must have matched the indexkey */
2411
		Assert(match_index_to_operand(arg, indexcol, index));
2412 2413 2414 2415 2416 2417 2418
		/* convert to indexkey = FALSE */
		return make_opclause(BooleanEqualOperator, BOOLOID, false,
							 (Expr *) arg,
							 (Expr *) makeBoolConst(false, false));
	}
	if (clause && IsA(clause, BooleanTest))
	{
2419 2420
		BooleanTest *btest = (BooleanTest *) clause;
		Node	   *arg = (Node *) btest->arg;
2421 2422

		/* It must have matched the indexkey */
2423
		Assert(match_index_to_operand(arg, indexcol, index));
2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444
		if (btest->booltesttype == IS_TRUE)
		{
			/* convert to indexkey = TRUE */
			return make_opclause(BooleanEqualOperator, BOOLOID, false,
								 (Expr *) arg,
								 (Expr *) makeBoolConst(true, false));
		}
		if (btest->booltesttype == IS_FALSE)
		{
			/* convert to indexkey = FALSE */
			return make_opclause(BooleanEqualOperator, BOOLOID, false,
								 (Expr *) arg,
								 (Expr *) makeBoolConst(false, false));
		}
		/* Oops */
		Assert(false);
	}

	return NULL;
}

2445
/*
2446 2447
 * expand_indexqual_opclause --- expand a single indexqual condition
 *		that is an operator clause
2448
 *
2449 2450 2451 2452
 * The input is a single RestrictInfo, the output a list of RestrictInfos.
 *
 * In the base case this is just list_make1(), but we have to be prepared to
 * expand special cases that were accepted by match_special_index_operator().
2453 2454
 */
static List *
2455
expand_indexqual_opclause(RestrictInfo *rinfo, Oid opfamily)
2456
{
2457
	Expr	   *clause = rinfo->clause;
Bruce Momjian's avatar
Bruce Momjian committed
2458

2459 2460 2461 2462 2463 2464 2465 2466 2467
	/* we know these will succeed */
	Node	   *leftop = get_leftop(clause);
	Node	   *rightop = get_rightop(clause);
	Oid			expr_op = ((OpExpr *) clause)->opno;
	Const	   *patt = (Const *) rightop;
	Const	   *prefix = NULL;
	Const	   *rest = NULL;
	Pattern_Prefix_Status pstatus;

2468 2469 2470 2471 2472 2473 2474 2475
	/*
	 * LIKE and regex operators are not members of any btree index opfamily,
	 * but they can be members of opfamilies for more exotic index types such
	 * as GIN.  Therefore, we should only do expansion if the operator is
	 * actually not in the opfamily.  But checking that requires a syscache
	 * lookup, so it's best to first see if the operator is one we are
	 * interested in.
	 */
2476 2477 2478 2479 2480 2481
	switch (expr_op)
	{
		case OID_TEXT_LIKE_OP:
		case OID_BPCHAR_LIKE_OP:
		case OID_NAME_LIKE_OP:
		case OID_BYTEA_LIKE_OP:
2482 2483 2484 2485 2486 2487
			if (!op_in_opfamily(expr_op, opfamily))
			{
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like,
											   &prefix, &rest);
				return prefix_quals(leftop, opfamily, prefix, pstatus);
			}
2488 2489 2490 2491 2492
			break;

		case OID_TEXT_ICLIKE_OP:
		case OID_BPCHAR_ICLIKE_OP:
		case OID_NAME_ICLIKE_OP:
2493 2494 2495 2496 2497 2498 2499
			if (!op_in_opfamily(expr_op, opfamily))
			{
				/* the right-hand const is type text for all of these */
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Like_IC,
											   &prefix, &rest);
				return prefix_quals(leftop, opfamily, prefix, pstatus);
			}
2500 2501 2502 2503 2504
			break;

		case OID_TEXT_REGEXEQ_OP:
		case OID_BPCHAR_REGEXEQ_OP:
		case OID_NAME_REGEXEQ_OP:
2505 2506 2507 2508 2509 2510 2511
			if (!op_in_opfamily(expr_op, opfamily))
			{
				/* the right-hand const is type text for all of these */
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex,
											   &prefix, &rest);
				return prefix_quals(leftop, opfamily, prefix, pstatus);
			}
2512 2513 2514 2515 2516
			break;

		case OID_TEXT_ICREGEXEQ_OP:
		case OID_BPCHAR_ICREGEXEQ_OP:
		case OID_NAME_ICREGEXEQ_OP:
2517 2518 2519 2520 2521 2522 2523
			if (!op_in_opfamily(expr_op, opfamily))
			{
				/* the right-hand const is type text for all of these */
				pstatus = pattern_fixed_prefix(patt, Pattern_Type_Regex_IC,
											   &prefix, &rest);
				return prefix_quals(leftop, opfamily, prefix, pstatus);
			}
2524 2525 2526 2527
			break;

		case OID_INET_SUB_OP:
		case OID_INET_SUBEQ_OP:
2528 2529 2530 2531 2532
			if (!op_in_opfamily(expr_op, opfamily))
			{
				return network_prefix_quals(leftop, expr_op, opfamily,
											patt->constvalue);
			}
2533 2534 2535
			break;
	}

2536 2537
	/* Default case: just make a list of the unmodified indexqual */
	return list_make1(rinfo);
2538 2539
}

2540 2541 2542 2543 2544 2545 2546 2547
/*
 * expand_indexqual_rowcompare --- expand a single indexqual condition
 *		that is a RowCompareExpr
 *
 * It's already known that the first column of the row comparison matches
 * the specified column of the index.  We can use additional columns of the
 * row comparison as index qualifications, so long as they match the index
 * in the "same direction", ie, the indexkeys are all on the same side of the
2548
 * clause and the operators are all the same-type members of the opfamilies.
2549 2550 2551 2552 2553
 * If all the columns of the RowCompareExpr match in this way, we just use it
 * as-is.  Otherwise, we build a shortened RowCompareExpr (if more than one
 * column matches) or a simple OpExpr (if the first-column match is all
 * there is).  In these cases the modified clause is always "<=" or ">="
 * even when the original was "<" or ">" --- this is necessary to match all
Bruce Momjian's avatar
Bruce Momjian committed
2554
 * the rows that could match the original.	(We are essentially building a
2555 2556 2557 2558 2559 2560 2561 2562
 * lossy version of the row comparison when we do this.)
 */
static RestrictInfo *
expand_indexqual_rowcompare(RestrictInfo *rinfo,
							IndexOptInfo *index,
							int indexcol)
{
	RowCompareExpr *clause = (RowCompareExpr *) rinfo->clause;
Bruce Momjian's avatar
Bruce Momjian committed
2563 2564
	bool		var_on_left;
	int			op_strategy;
2565 2566
	Oid			op_lefttype;
	Oid			op_righttype;
Bruce Momjian's avatar
Bruce Momjian committed
2567 2568
	int			matching_cols;
	Oid			expr_op;
2569 2570 2571
	List	   *opfamilies;
	List	   *lefttypes;
	List	   *righttypes;
Bruce Momjian's avatar
Bruce Momjian committed
2572 2573 2574 2575
	List	   *new_ops;
	ListCell   *largs_cell;
	ListCell   *rargs_cell;
	ListCell   *opnos_cell;
2576 2577 2578 2579 2580 2581 2582 2583 2584 2585

	/* We have to figure out (again) how the first col matches */
	var_on_left = match_index_to_operand((Node *) linitial(clause->largs),
										 indexcol, index);
	Assert(var_on_left ||
		   match_index_to_operand((Node *) linitial(clause->rargs),
								  indexcol, index));
	expr_op = linitial_oid(clause->opnos);
	if (!var_on_left)
		expr_op = get_commutator(expr_op);
2586 2587 2588
	get_op_opfamily_properties(expr_op, index->opfamily[indexcol],
							   &op_strategy,
							   &op_lefttype,
2589
							   &op_righttype);
2590 2591 2592 2593
	/* Build lists of the opfamilies and operator datatypes in case needed */
	opfamilies = list_make1_oid(index->opfamily[indexcol]);
	lefttypes = list_make1_oid(op_lefttype);
	righttypes = list_make1_oid(op_righttype);
2594 2595

	/*
Bruce Momjian's avatar
Bruce Momjian committed
2596 2597 2598 2599 2600 2601
	 * See how many of the remaining columns match some index column in the
	 * same way.  A note about rel membership tests: we assume that the clause
	 * as a whole is already known to use only Vars from the indexed relation
	 * and possibly some acceptable outer relations. So the "other" side of
	 * any potential index condition is OK as long as it doesn't use Vars from
	 * the indexed relation.
2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634
	 */
	matching_cols = 1;
	largs_cell = lnext(list_head(clause->largs));
	rargs_cell = lnext(list_head(clause->rargs));
	opnos_cell = lnext(list_head(clause->opnos));

	while (largs_cell != NULL)
	{
		Node	   *varop;
		Node	   *constop;
		int			i;

		expr_op = lfirst_oid(opnos_cell);
		if (var_on_left)
		{
			varop = (Node *) lfirst(largs_cell);
			constop = (Node *) lfirst(rargs_cell);
		}
		else
		{
			varop = (Node *) lfirst(rargs_cell);
			constop = (Node *) lfirst(largs_cell);
			/* indexkey is on right, so commute the operator */
			expr_op = get_commutator(expr_op);
			if (expr_op == InvalidOid)
				break;			/* operator is not usable */
		}
		if (bms_is_member(index->rel->relid, pull_varnos(constop)))
			break;				/* no good, Var on wrong side */
		if (contain_volatile_functions(constop))
			break;				/* no good, volatile comparison value */

		/*
Bruce Momjian's avatar
Bruce Momjian committed
2635 2636 2637 2638
		 * The Var side can match any column of the index.	If the user does
		 * something weird like having multiple identical index columns, we
		 * insist the match be on the first such column, to avoid confusing
		 * the executor.
2639 2640 2641 2642 2643 2644 2645 2646 2647 2648
		 */
		for (i = 0; i < index->ncolumns; i++)
		{
			if (match_index_to_operand(varop, i, index))
				break;
		}
		if (i >= index->ncolumns)
			break;				/* no match found */

		/* Now, do we have the right operator for this column? */
2649
		if (get_op_opfamily_strategy(expr_op, index->opfamily[i])
2650 2651 2652
			!= op_strategy)
			break;

2653 2654 2655 2656
		/* Add opfamily and datatypes to lists */
		get_op_opfamily_properties(expr_op, index->opfamily[i],
								   &op_strategy,
								   &op_lefttype,
2657
								   &op_righttype);
2658 2659 2660
		opfamilies = lappend_oid(opfamilies, index->opfamily[i]);
		lefttypes = lappend_oid(lefttypes, op_lefttype);
		righttypes = lappend_oid(righttypes, op_righttype);
2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673

		/* This column matches, keep scanning */
		matching_cols++;
		largs_cell = lnext(largs_cell);
		rargs_cell = lnext(rargs_cell);
		opnos_cell = lnext(opnos_cell);
	}

	/* Return clause as-is if it's all usable as index quals */
	if (matching_cols == list_length(clause->opnos))
		return rinfo;

	/*
Bruce Momjian's avatar
Bruce Momjian committed
2674 2675 2676
	 * We have to generate a subset rowcompare (possibly just one OpExpr). The
	 * painful part of this is changing < to <= or > to >=, so deal with that
	 * first.
2677 2678 2679 2680 2681 2682 2683 2684 2685
	 */
	if (op_strategy == BTLessEqualStrategyNumber ||
		op_strategy == BTGreaterEqualStrategyNumber)
	{
		/* easy, just use the same operators */
		new_ops = list_truncate(list_copy(clause->opnos), matching_cols);
	}
	else
	{
2686 2687 2688
		ListCell   *opfamilies_cell;
		ListCell   *lefttypes_cell;
		ListCell   *righttypes_cell;
2689 2690 2691 2692 2693 2694 2695 2696

		if (op_strategy == BTLessStrategyNumber)
			op_strategy = BTLessEqualStrategyNumber;
		else if (op_strategy == BTGreaterStrategyNumber)
			op_strategy = BTGreaterEqualStrategyNumber;
		else
			elog(ERROR, "unexpected strategy number %d", op_strategy);
		new_ops = NIL;
2697 2698 2699
		lefttypes_cell = list_head(lefttypes);
		righttypes_cell = list_head(righttypes);
		foreach(opfamilies_cell, opfamilies)
2700
		{
Bruce Momjian's avatar
Bruce Momjian committed
2701 2702 2703
			Oid			opfam = lfirst_oid(opfamilies_cell);
			Oid			lefttype = lfirst_oid(lefttypes_cell);
			Oid			righttype = lfirst_oid(righttypes_cell);
2704 2705 2706

			expr_op = get_opfamily_member(opfam, lefttype, righttype,
										  op_strategy);
Bruce Momjian's avatar
Bruce Momjian committed
2707
			if (!OidIsValid(expr_op))	/* should not happen */
2708 2709
				elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
					 op_strategy, lefttype, righttype, opfam);
2710 2711 2712
			if (!var_on_left)
			{
				expr_op = get_commutator(expr_op);
Bruce Momjian's avatar
Bruce Momjian committed
2713
				if (!OidIsValid(expr_op))		/* should not happen */
2714 2715
					elog(ERROR, "could not find commutator of member %d(%u,%u) of opfamily %u",
						 op_strategy, lefttype, righttype, opfam);
2716 2717
			}
			new_ops = lappend_oid(new_ops, expr_op);
2718 2719
			lefttypes_cell = lnext(lefttypes_cell);
			righttypes_cell = lnext(righttypes_cell);
2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733
		}
	}

	/* If we have more than one matching col, create a subset rowcompare */
	if (matching_cols > 1)
	{
		RowCompareExpr *rc = makeNode(RowCompareExpr);

		if (var_on_left)
			rc->rctype = (RowCompareType) op_strategy;
		else
			rc->rctype = (op_strategy == BTLessEqualStrategyNumber) ?
				ROWCOMPARE_GE : ROWCOMPARE_LE;
		rc->opnos = new_ops;
2734 2735
		rc->opfamilies = list_truncate(list_copy(clause->opfamilies),
									   matching_cols);
2736 2737 2738 2739
		rc->largs = list_truncate((List *) copyObject(clause->largs),
								  matching_cols);
		rc->rargs = list_truncate((List *) copyObject(clause->rargs),
								  matching_cols);
2740
		return make_restrictinfo((Expr *) rc, true, false, false, NULL);
2741 2742 2743
	}
	else
	{
Bruce Momjian's avatar
Bruce Momjian committed
2744
		Expr	   *opexpr;
2745 2746 2747 2748

		opexpr = make_opclause(linitial_oid(new_ops), BOOLOID, false,
							   copyObject(linitial(clause->largs)),
							   copyObject(linitial(clause->rargs)));
2749
		return make_restrictinfo(opexpr, true, false, false, NULL);
2750 2751 2752
	}
}

2753 2754
/*
 * Given a fixed prefix that all the "leftop" values must have,
2755 2756
 * generate suitable indexqual condition(s).  opfamily is the index
 * operator family; we use it to deduce the appropriate comparison
2757
 * operators and operand datatypes.
2758 2759
 */
static List *
2760
prefix_quals(Node *leftop, Oid opfamily,
2761
			 Const *prefix_const, Pattern_Prefix_Status pstatus)
2762 2763 2764
{
	List	   *result;
	Oid			datatype;
2765
	Oid			oproid;
2766
	Expr	   *expr;
2767
	FmgrInfo	ltproc;
2768
	Const	   *greaterstr;
2769

2770
	Assert(pstatus != Pattern_Prefix_None);
2771

2772
	switch (opfamily)
2773
	{
2774 2775
		case TEXT_BTREE_FAM_OID:
		case TEXT_PATTERN_BTREE_FAM_OID:
2776 2777 2778
			datatype = TEXTOID;
			break;

2779 2780
		case BPCHAR_BTREE_FAM_OID:
		case BPCHAR_PATTERN_BTREE_FAM_OID:
2781 2782 2783
			datatype = BPCHAROID;
			break;

2784
		case NAME_BTREE_FAM_OID:
2785
			datatype = NAMEOID;
2786 2787
			break;

2788
		case BYTEA_BTREE_FAM_OID:
2789
			datatype = BYTEAOID;
2790 2791 2792
			break;

		default:
2793
			/* shouldn't get here */
2794
			elog(ERROR, "unexpected opfamily: %u", opfamily);
2795 2796 2797
			return NIL;
	}

2798
	/*
2799 2800
	 * If necessary, coerce the prefix constant to the right type. The given
	 * prefix constant is either text or bytea type.
2801 2802 2803
	 */
	if (prefix_const->consttype != datatype)
	{
Bruce Momjian's avatar
Bruce Momjian committed
2804
		char	   *prefix;
2805 2806 2807 2808

		switch (prefix_const->consttype)
		{
			case TEXTOID:
2809
				prefix = TextDatumGetCString(prefix_const->constvalue);
2810 2811 2812
				break;
			case BYTEAOID:
				prefix = DatumGetCString(DirectFunctionCall1(byteaout,
2813
												  prefix_const->constvalue));
2814 2815
				break;
			default:
2816
				elog(ERROR, "unexpected const type: %u",
2817 2818 2819 2820 2821 2822
					 prefix_const->consttype);
				return NIL;
		}
		prefix_const = string_to_const(prefix, datatype);
		pfree(prefix);
	}
2823

2824 2825 2826
	/*
	 * If we found an exact-match pattern, generate an "=" indexqual.
	 */
2827
	if (pstatus == Pattern_Prefix_Exact)
2828
	{
2829 2830
		oproid = get_opfamily_member(opfamily, datatype, datatype,
									 BTEqualStrategyNumber);
2831
		if (oproid == InvalidOid)
2832
			elog(ERROR, "no = operator for opfamily %u", opfamily);
2833
		expr = make_opclause(oproid, BOOLOID, false,
2834
							 (Expr *) leftop, (Expr *) prefix_const);
2835
		result = list_make1(make_restrictinfo(expr, true, false, false, NULL));
2836 2837 2838 2839 2840 2841 2842 2843
		return result;
	}

	/*
	 * Otherwise, we have a nonempty required prefix of the values.
	 *
	 * We can always say "x >= prefix".
	 */
2844 2845
	oproid = get_opfamily_member(opfamily, datatype, datatype,
								 BTGreaterEqualStrategyNumber);
2846
	if (oproid == InvalidOid)
2847
		elog(ERROR, "no >= operator for opfamily %u", opfamily);
2848
	expr = make_opclause(oproid, BOOLOID, false,
2849
						 (Expr *) leftop, (Expr *) prefix_const);
2850
	result = list_make1(make_restrictinfo(expr, true, false, false, NULL));
2851

2852 2853 2854 2855
	/*-------
	 * If we can create a string larger than the prefix, we can say
	 * "x < greaterstr".
	 *-------
2856
	 */
2857 2858 2859 2860 2861 2862
	oproid = get_opfamily_member(opfamily, datatype, datatype,
								 BTLessStrategyNumber);
	if (oproid == InvalidOid)
		elog(ERROR, "no < operator for opfamily %u", opfamily);
	fmgr_info(get_opcode(oproid), &ltproc);
	greaterstr = make_greater_string(prefix_const, &ltproc);
2863 2864
	if (greaterstr)
	{
2865 2866
		expr = make_opclause(oproid, BOOLOID, false,
							 (Expr *) leftop, (Expr *) greaterstr);
2867 2868
		result = lappend(result,
						 make_restrictinfo(expr, true, false, false, NULL));
2869
	}
2870

2871 2872 2873
	return result;
}

2874
/*
2875
 * Given a leftop and a rightop, and a inet-family sup/sub operator,
2876
 * generate suitable indexqual condition(s).  expr_op is the original
2877
 * operator, and opfamily is the index opfamily.
2878 2879
 */
static List *
2880
network_prefix_quals(Node *leftop, Oid expr_op, Oid opfamily, Datum rightop)
2881
{
2882
	bool		is_eq;
2883
	Oid			datatype;
2884 2885
	Oid			opr1oid;
	Oid			opr2oid;
2886 2887
	Datum		opr1right;
	Datum		opr2right;
2888 2889 2890 2891 2892 2893
	List	   *result;
	Expr	   *expr;

	switch (expr_op)
	{
		case OID_INET_SUB_OP:
2894 2895
			datatype = INETOID;
			is_eq = false;
2896 2897
			break;
		case OID_INET_SUBEQ_OP:
2898 2899
			datatype = INETOID;
			is_eq = true;
2900 2901
			break;
		default:
2902
			elog(ERROR, "unexpected operator: %u", expr_op);
2903
			return NIL;
2904
	}
2905 2906

	/*
2907 2908
	 * create clause "key >= network_scan_first( rightop )", or ">" if the
	 * operator disallows equality.
2909
	 */
2910 2911
	if (is_eq)
	{
2912 2913
		opr1oid = get_opfamily_member(opfamily, datatype, datatype,
									  BTGreaterEqualStrategyNumber);
2914
		if (opr1oid == InvalidOid)
2915
			elog(ERROR, "no >= operator for opfamily %u", opfamily);
2916 2917 2918
	}
	else
	{
2919 2920
		opr1oid = get_opfamily_member(opfamily, datatype, datatype,
									  BTGreaterStrategyNumber);
2921
		if (opr1oid == InvalidOid)
2922
			elog(ERROR, "no > operator for opfamily %u", opfamily);
2923
	}
2924

2925
	opr1right = network_scan_first(rightop);
2926

2927 2928
	expr = make_opclause(opr1oid, BOOLOID, false,
						 (Expr *) leftop,
2929
						 (Expr *) makeConst(datatype, -1, -1, opr1right,
2930
											false, false));
2931
	result = list_make1(make_restrictinfo(expr, true, false, false, NULL));
2932 2933 2934

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

2935 2936
	opr2oid = get_opfamily_member(opfamily, datatype, datatype,
								  BTLessEqualStrategyNumber);
2937
	if (opr2oid == InvalidOid)
2938
		elog(ERROR, "no <= operator for opfamily %u", opfamily);
2939

2940
	opr2right = network_scan_last(rightop);
2941

2942 2943
	expr = make_opclause(opr2oid, BOOLOID, false,
						 (Expr *) leftop,
2944
						 (Expr *) makeConst(datatype, -1, -1, opr2right,
2945
											false, false));
2946 2947
	result = lappend(result,
					 make_restrictinfo(expr, true, false, false, NULL));
2948 2949 2950 2951

	return result;
}

2952 2953 2954 2955 2956 2957 2958 2959 2960 2961
/*
 * Handy subroutines for match_special_index_operator() and friends.
 */

/*
 * 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
2962
string_to_datum(const char *str, Oid datatype)
2963
{
2964
	/*
2965 2966
	 * We cheat a little by assuming that CStringGetTextDatum() will do for
	 * bpchar and varchar constants too...
2967 2968
	 */
	if (datatype == NAMEOID)
2969
		return DirectFunctionCall1(namein, CStringGetDatum(str));
2970 2971
	else if (datatype == BYTEAOID)
		return DirectFunctionCall1(byteain, CStringGetDatum(str));
2972
	else
2973
		return CStringGetTextDatum(str);
2974 2975 2976 2977 2978 2979
}

/*
 * Generate a Const node of the appropriate type from a C string.
 */
static Const *
2980
string_to_const(const char *str, Oid datatype)
2981 2982 2983
{
	Datum		conval = string_to_datum(str, datatype);

2984 2985
	return makeConst(datatype, -1,
					 ((datatype == NAMEOID) ? NAMEDATALEN : -1),
2986
					 conval, false, false);
2987
}