Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 3e4b346

Browse filesBrowse files
tglsfdctglsfdc
committed
Improve planner's ability to recognize cases where an IN's RHS is unique.
If the right-hand side of a semijoin is unique, then we can treat it like a normal join (or another way to say that is: we don't need to explicitly unique-ify the data before doing it as a normal join). We were recognizing such cases when the RHS was a sub-query with appropriate DISTINCT or GROUP BY decoration, but there's another way: if the RHS is a plain relation with unique indexes, we can check if any of the indexes prove the output is unique. Most of the infrastructure for that was there already in the join removal code, though I had to rearrange it a bit. Per reflection about a recent example in pgsql-performance.
1 parent 360429e commit 3e4b346
Copy full SHA for 3e4b346

File tree

Expand file treeCollapse file tree

4 files changed

+134
-49
lines changed
Filter options
Expand file treeCollapse file tree

4 files changed

+134
-49
lines changed

‎src/backend/optimizer/path/indxpath.c

Copy file name to clipboardExpand all lines: src/backend/optimizer/path/indxpath.c
+102-12Lines changed: 102 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -2253,21 +2253,74 @@ find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
22532253
* a set of equality conditions, because the conditions constrain all
22542254
* columns of some unique index.
22552255
*
2256-
* The conditions are provided as a list of RestrictInfo nodes, where the
2257-
* caller has already determined that each condition is a mergejoinable
2258-
* equality with an expression in this relation on one side, and an
2259-
* expression not involving this relation on the other. The transient
2260-
* outer_is_left flag is used to identify which side we should look at:
2261-
* left side if outer_is_left is false, right side if it is true.
2256+
* The conditions can be represented in either or both of two ways:
2257+
* 1. A list of RestrictInfo nodes, where the caller has already determined
2258+
* that each condition is a mergejoinable equality with an expression in
2259+
* this relation on one side, and an expression not involving this relation
2260+
* on the other. The transient outer_is_left flag is used to identify which
2261+
* side we should look at: left side if outer_is_left is false, right side
2262+
* if it is true.
2263+
* 2. A list of expressions in this relation, and a corresponding list of
2264+
* equality operators. The caller must have already checked that the operators
2265+
* represent equality. (Note: the operators could be cross-type; the
2266+
* expressions should correspond to their RHS inputs.)
2267+
*
2268+
* The caller need only supply equality conditions arising from joins;
2269+
* this routine automatically adds in any usable baserestrictinfo clauses.
2270+
* (Note that the passed-in restrictlist will be destructively modified!)
22622271
*/
22632272
bool
22642273
relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
2265-
List *restrictlist)
2274+
List *restrictlist,
2275+
List *exprlist, List *oprlist)
22662276
{
22672277
ListCell *ic;
22682278

2279+
Assert(list_length(exprlist) == list_length(oprlist));
2280+
2281+
/* Short-circuit if no indexes... */
2282+
if (rel->indexlist == NIL)
2283+
return false;
2284+
2285+
/*
2286+
* Examine the rel's restriction clauses for usable var = const clauses
2287+
* that we can add to the restrictlist.
2288+
*/
2289+
foreach(ic, rel->baserestrictinfo)
2290+
{
2291+
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(ic);
2292+
2293+
/*
2294+
* Note: can_join won't be set for a restriction clause, but
2295+
* mergeopfamilies will be if it has a mergejoinable operator and
2296+
* doesn't contain volatile functions.
2297+
*/
2298+
if (restrictinfo->mergeopfamilies == NIL)
2299+
continue; /* not mergejoinable */
2300+
2301+
/*
2302+
* The clause certainly doesn't refer to anything but the given rel.
2303+
* If either side is pseudoconstant then we can use it.
2304+
*/
2305+
if (bms_is_empty(restrictinfo->left_relids))
2306+
{
2307+
/* righthand side is inner */
2308+
restrictinfo->outer_is_left = true;
2309+
}
2310+
else if (bms_is_empty(restrictinfo->right_relids))
2311+
{
2312+
/* lefthand side is inner */
2313+
restrictinfo->outer_is_left = false;
2314+
}
2315+
else
2316+
continue;
2317+
2318+
/* OK, add to list */
2319+
restrictlist = lappend(restrictlist, restrictinfo);
2320+
}
2321+
22692322
/* Short-circuit the easy case */
2270-
if (restrictlist == NIL)
2323+
if (restrictlist == NIL && exprlist == NIL)
22712324
return false;
22722325

22732326
/* Examine each index of the relation ... */
@@ -2285,12 +2338,14 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
22852338
continue;
22862339

22872340
/*
2288-
* Try to find each index column in the list of conditions. This is
2289-
* O(n^2) or worse, but we expect all the lists to be short.
2341+
* Try to find each index column in the lists of conditions. This is
2342+
* O(N^2) or worse, but we expect all the lists to be short.
22902343
*/
22912344
for (c = 0; c < ind->ncolumns; c++)
22922345
{
2346+
bool matched = false;
22932347
ListCell *lc;
2348+
ListCell *lc2;
22942349

22952350
foreach(lc, restrictlist)
22962351
{
@@ -2319,10 +2374,45 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
23192374
rexpr = get_leftop(rinfo->clause);
23202375

23212376
if (match_index_to_operand(rexpr, c, ind))
2322-
break; /* found a match; column is unique */
2377+
{
2378+
matched = true; /* column is unique */
2379+
break;
2380+
}
2381+
}
2382+
2383+
if (matched)
2384+
continue;
2385+
2386+
forboth(lc, exprlist, lc2, oprlist)
2387+
{
2388+
Node *expr = (Node *) lfirst(lc);
2389+
Oid opr = lfirst_oid(lc2);
2390+
2391+
/* See if the expression matches the index key */
2392+
if (!match_index_to_operand(expr, c, ind))
2393+
continue;
2394+
2395+
/*
2396+
* The equality operator must be a member of the index
2397+
* opfamily, else it is not asserting the right kind of
2398+
* equality behavior for this index. We assume the caller
2399+
* determined it is an equality operator, so we don't need to
2400+
* check any more tightly than this.
2401+
*/
2402+
if (!op_in_opfamily(opr, ind->opfamily[c]))
2403+
continue;
2404+
2405+
/*
2406+
* XXX at some point we may need to check collations here too.
2407+
* For the moment we assume all collations reduce to the same
2408+
* notion of equality.
2409+
*/
2410+
2411+
matched = true; /* column is unique */
2412+
break;
23232413
}
23242414

2325-
if (lc == NULL)
2415+
if (!matched)
23262416
break; /* no match; this index doesn't help us */
23272417
}
23282418

‎src/backend/optimizer/plan/analyzejoins.c

Copy file name to clipboardExpand all lines: src/backend/optimizer/plan/analyzejoins.c
+5-34Lines changed: 5 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -264,42 +264,13 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
264264
clause_list = lappend(clause_list, restrictinfo);
265265
}
266266

267-
/* Now examine the rel's restriction clauses for var = const clauses */
268-
foreach(l, innerrel->baserestrictinfo)
269-
{
270-
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
271-
272-
/*
273-
* Note: can_join won't be set for a restriction clause, but
274-
* mergeopfamilies will be if it has a mergejoinable operator and
275-
* doesn't contain volatile functions.
276-
*/
277-
if (restrictinfo->mergeopfamilies == NIL)
278-
continue; /* not mergejoinable */
279-
280-
/*
281-
* The clause certainly doesn't refer to anything but the given rel.
282-
* If either side is pseudoconstant then we can use it.
283-
*/
284-
if (bms_is_empty(restrictinfo->left_relids))
285-
{
286-
/* righthand side is inner */
287-
restrictinfo->outer_is_left = true;
288-
}
289-
else if (bms_is_empty(restrictinfo->right_relids))
290-
{
291-
/* lefthand side is inner */
292-
restrictinfo->outer_is_left = false;
293-
}
294-
else
295-
continue;
296-
297-
/* OK, add to list */
298-
clause_list = lappend(clause_list, restrictinfo);
299-
}
267+
/*
268+
* relation_has_unique_index_for automatically adds any usable restriction
269+
* clauses for the innerrel, so we needn't do that here.
270+
*/
300271

301272
/* Now examine the indexes to see if we have a matching unique index */
302-
if (relation_has_unique_index_for(root, innerrel, clause_list))
273+
if (relation_has_unique_index_for(root, innerrel, clause_list, NIL, NIL))
303274
return true;
304275

305276
/*

‎src/backend/optimizer/util/pathnode.c

Copy file name to clipboardExpand all lines: src/backend/optimizer/util/pathnode.c
+25-2Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1021,15 +1021,38 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
10211021
pathnode->path.parent = rel;
10221022

10231023
/*
1024-
* Treat the output as always unsorted, since we don't necessarily have
1025-
* pathkeys to represent it.
1024+
* Assume the output is unsorted, since we don't necessarily have pathkeys
1025+
* to represent it. (This might get overridden below.)
10261026
*/
10271027
pathnode->path.pathkeys = NIL;
10281028

10291029
pathnode->subpath = subpath;
10301030
pathnode->in_operators = in_operators;
10311031
pathnode->uniq_exprs = uniq_exprs;
10321032

1033+
/*
1034+
* If the input is a relation and it has a unique index that proves the
1035+
* uniq_exprs are unique, then we don't need to do anything. Note that
1036+
* relation_has_unique_index_for automatically considers restriction
1037+
* clauses for the rel, as well.
1038+
*/
1039+
if (rel->rtekind == RTE_RELATION && all_btree &&
1040+
relation_has_unique_index_for(root, rel, NIL,
1041+
uniq_exprs, in_operators))
1042+
{
1043+
pathnode->umethod = UNIQUE_PATH_NOOP;
1044+
pathnode->rows = rel->rows;
1045+
pathnode->path.startup_cost = subpath->startup_cost;
1046+
pathnode->path.total_cost = subpath->total_cost;
1047+
pathnode->path.pathkeys = subpath->pathkeys;
1048+
1049+
rel->cheapest_unique_path = (Path *) pathnode;
1050+
1051+
MemoryContextSwitchTo(oldcontext);
1052+
1053+
return pathnode;
1054+
}
1055+
10331056
/*
10341057
* If the input is a subquery whose output must be unique already, then we
10351058
* don't need to do anything. The test for uniqueness has to consider

‎src/include/optimizer/paths.h

Copy file name to clipboardExpand all lines: src/include/optimizer/paths.h
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,8 @@ extern void best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
5050
RelOptInfo *outer_rel, JoinType jointype,
5151
Path **cheapest_startup, Path **cheapest_total);
5252
extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
53-
List *restrictlist);
53+
List *restrictlist,
54+
List *exprlist, List *oprlist);
5455
extern bool eclass_matches_any_index(EquivalenceClass *ec,
5556
EquivalenceMember *em,
5657
RelOptInfo *rel);

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.