Skip to content

Commit 82b4dd3

Browse files
tglsfdctglsfdc
committed
Merge restrictlist_selectivity into clauselist_selectivity by
teaching the latter to accept either RestrictInfo nodes or bare clause expressions; and cache the selectivity result in the RestrictInfo node when possible. This extends the caching behavior of approx_selectivity to many more contexts, and should reduce duplicate selectivity calculations.
1 parent 21a1202 commit 82b4dd3

File tree

12 files changed

+196
-200
lines changed

12 files changed

+196
-200
lines changed

‎src/backend/nodes/copyfuncs.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
* Portions Copyright (c) 1994, Regents of the University of California
1616
*
1717
* IDENTIFICATION
18-
* $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.271 2004/01/04 00:07:32 tgl Exp $
18+
* $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.272 2004/01/04 03:51:52 tgl Exp $
1919
*
2020
*-------------------------------------------------------------------------
2121
*/
@@ -1170,6 +1170,7 @@ _copyRestrictInfo(RestrictInfo *from)
11701170
COPY_NODE_FIELD(clause);
11711171
COPY_SCALAR_FIELD(ispusheddown);
11721172
COPY_SCALAR_FIELD(canjoin);
1173+
COPY_BITMAPSET_FIELD(clause_relids);
11731174
COPY_BITMAPSET_FIELD(left_relids);
11741175
COPY_BITMAPSET_FIELD(right_relids);
11751176
COPY_NODE_FIELD(orclause);

‎src/backend/nodes/outfuncs.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.224 2004/01/04 00:07:32 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.225 2004/01/04 03:51:52 tgl Exp $
1212
*
1313
* NOTES
1414
* Every node type that can appear in stored rules' parsetrees *must*
@@ -1075,6 +1075,7 @@ _outRestrictInfo(StringInfo str, RestrictInfo *node)
10751075
WRITE_NODE_FIELD(clause);
10761076
WRITE_BOOL_FIELD(ispusheddown);
10771077
WRITE_BOOL_FIELD(canjoin);
1078+
WRITE_BITMAPSET_FIELD(clause_relids);
10781079
WRITE_BITMAPSET_FIELD(left_relids);
10791080
WRITE_BITMAPSET_FIELD(right_relids);
10801081
WRITE_NODE_FIELD(orclause);

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

Lines changed: 133 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/clausesel.c,v 1.62 2003/12/29 21:44:49 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/clausesel.c,v 1.63 2004/01/04 03:51:52 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -54,33 +54,13 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause,
5454
* ROUTINES TO COMPUTE SELECTIVITIES
5555
****************************************************************************/
5656

57-
/*
58-
* restrictlist_selectivity -
59-
* Compute the selectivity of an implicitly-ANDed list of RestrictInfo
60-
* clauses.
61-
*
62-
* This is the same as clauselist_selectivity except for the representation
63-
* of the clause list.
64-
*/
65-
Selectivity
66-
restrictlist_selectivity(Query *root,
67-
List *restrictinfo_list,
68-
int varRelid,
69-
JoinType jointype)
70-
{
71-
List *clauselist = get_actual_clauses(restrictinfo_list);
72-
Selectivity result;
73-
74-
result = clauselist_selectivity(root, clauselist, varRelid, jointype);
75-
freeList(clauselist);
76-
return result;
77-
}
78-
7957
/*
8058
* clauselist_selectivity -
8159
* Compute the selectivity of an implicitly-ANDed list of boolean
8260
* expression clauses. The list can be empty, in which case 1.0
83-
* must be returned.
61+
* must be returned. List elements may be either RestrictInfos
62+
* or bare expression clauses --- the former is preferred since
63+
* it allows caching of results.
8464
*
8565
* See clause_selectivity() for the meaning of the additional parameters.
8666
*
@@ -133,64 +113,80 @@ clauselist_selectivity(Query *root,
133113
foreach(clist, clauses)
134114
{
135115
Node *clause = (Node *) lfirst(clist);
116+
RestrictInfo *rinfo;
136117
Selectivity s2;
137118

119+
/* Always compute the selectivity using clause_selectivity */
120+
s2 = clause_selectivity(root, clause, varRelid, jointype);
121+
122+
/*
123+
* Check for being passed a RestrictInfo.
124+
*/
125+
if (IsA(clause, RestrictInfo))
126+
{
127+
rinfo = (RestrictInfo *) clause;
128+
clause = (Node *) rinfo->clause;
129+
}
130+
else
131+
rinfo = NULL;
132+
138133
/*
139134
* See if it looks like a restriction clause with a pseudoconstant
140135
* on one side. (Anything more complicated than that might not
141-
* behave in the simple way we are expecting.)
142-
*
143-
* NB: for consistency of results, this fragment of code had better
144-
* match what clause_selectivity() would do in the cases it
145-
* handles.
136+
* behave in the simple way we are expecting.) Most of the tests
137+
* here can be done more efficiently with rinfo than without.
146138
*/
147-
if (is_opclause(clause) &&
148-
(varRelid != 0 || NumRelids(clause) == 1))
139+
if (is_opclause(clause) && length(((OpExpr *) clause)->args) == 2)
149140
{
150141
OpExpr *expr = (OpExpr *) clause;
142+
bool varonleft = true;
143+
bool ok;
151144

152-
if (length(expr->args) == 2)
145+
if (rinfo)
153146
{
154-
bool varonleft = true;
147+
ok = (bms_membership(rinfo->clause_relids) == BMS_SINGLETON) &&
148+
(is_pseudo_constant_clause_relids(lsecond(expr->args),
149+
rinfo->right_relids) ||
150+
(varonleft = false,
151+
is_pseudo_constant_clause_relids(lfirst(expr->args),
152+
rinfo->left_relids)));
153+
}
154+
else
155+
{
156+
ok = (NumRelids(clause) == 1) &&
157+
(is_pseudo_constant_clause(lsecond(expr->args)) ||
158+
(varonleft = false,
159+
is_pseudo_constant_clause(lfirst(expr->args))));
160+
}
155161

156-
if (is_pseudo_constant_clause(lsecond(expr->args)) ||
157-
(varonleft = false,
158-
is_pseudo_constant_clause(lfirst(expr->args))))
162+
if (ok)
163+
{
164+
/*
165+
* If it's not a "<" or ">" operator, just merge the
166+
* selectivity in generically. But if it's the
167+
* right oprrest, add the clause to rqlist for later
168+
* processing.
169+
*/
170+
switch (get_oprrest(expr->opno))
159171
{
160-
Oid opno = expr->opno;
161-
RegProcedure oprrest = get_oprrest(opno);
162-
163-
s2 = restriction_selectivity(root, opno,
164-
expr->args, varRelid);
165-
166-
/*
167-
* If we reach here, we have computed the same result
168-
* that clause_selectivity would, so we can just use
169-
* s2 if it's the wrong oprrest. But if it's the
170-
* right oprrest, add the clause to rqlist for later
171-
* processing.
172-
*/
173-
switch (oprrest)
174-
{
175-
case F_SCALARLTSEL:
176-
addRangeClause(&rqlist, clause,
177-
varonleft, true, s2);
178-
break;
179-
case F_SCALARGTSEL:
180-
addRangeClause(&rqlist, clause,
181-
varonleft, false, s2);
182-
break;
183-
default:
184-
/* Just merge the selectivity in generically */
185-
s1 = s1 * s2;
186-
break;
187-
}
188-
continue; /* drop to loop bottom */
172+
case F_SCALARLTSEL:
173+
addRangeClause(&rqlist, clause,
174+
varonleft, true, s2);
175+
break;
176+
case F_SCALARGTSEL:
177+
addRangeClause(&rqlist, clause,
178+
varonleft, false, s2);
179+
break;
180+
default:
181+
/* Just merge the selectivity in generically */
182+
s1 = s1 * s2;
183+
break;
189184
}
185+
continue; /* drop to loop bottom */
190186
}
191187
}
188+
192189
/* Not the right form, so treat it generically. */
193-
s2 = clause_selectivity(root, clause, varRelid, jointype);
194190
s1 = s1 * s2;
195191
}
196192

@@ -352,11 +348,39 @@ addRangeClause(RangeQueryClause **rqlist, Node *clause,
352348
*rqlist = rqelem;
353349
}
354350

351+
/*
352+
* bms_is_subset_singleton
353+
*
354+
* Same result as bms_is_subset(s, bms_make_singleton(x)),
355+
* but a little faster and doesn't leak memory.
356+
*
357+
* Is this of use anywhere else? If so move to bitmapset.c ...
358+
*/
359+
static bool
360+
bms_is_subset_singleton(const Bitmapset *s, int x)
361+
{
362+
switch (bms_membership(s))
363+
{
364+
case BMS_EMPTY_SET:
365+
return true;
366+
case BMS_SINGLETON:
367+
return bms_is_member(x, s);
368+
case BMS_MULTIPLE:
369+
return false;
370+
}
371+
/* can't get here... */
372+
return false;
373+
}
374+
355375

356376
/*
357377
* clause_selectivity -
358378
* Compute the selectivity of a general boolean expression clause.
359379
*
380+
* The clause can be either a RestrictInfo or a plain expression. If it's
381+
* a RestrictInfo, we try to cache the selectivity for possible re-use,
382+
* so passing RestrictInfos is preferred.
383+
*
360384
* varRelid is either 0 or a rangetable index.
361385
*
362386
* When varRelid is not 0, only variables belonging to that relation are
@@ -379,9 +403,37 @@ clause_selectivity(Query *root,
379403
JoinType jointype)
380404
{
381405
Selectivity s1 = 1.0; /* default for any unhandled clause type */
406+
RestrictInfo *rinfo = NULL;
407+
bool cacheable = false;
382408

383-
if (clause == NULL)
409+
if (clause == NULL) /* can this still happen? */
384410
return s1;
411+
412+
if (IsA(clause, RestrictInfo))
413+
{
414+
rinfo = (RestrictInfo *) clause;
415+
416+
/*
417+
* If possible, cache the result of the selectivity calculation for
418+
* the clause. We can cache if varRelid is zero or the clause
419+
* contains only vars of that relid --- otherwise varRelid will affect
420+
* the result, so mustn't cache. We ignore the possibility that
421+
* jointype will affect the result, which should be okay because outer
422+
* join clauses will always be examined with the same jointype value.
423+
*/
424+
if (varRelid == 0 ||
425+
bms_is_subset_singleton(rinfo->clause_relids, varRelid))
426+
{
427+
/* Cacheable --- do we already have the result? */
428+
if (rinfo->this_selec >= 0)
429+
return rinfo->this_selec;
430+
cacheable = true;
431+
}
432+
433+
/* Proceed with examination of contained clause */
434+
clause = (Node *) rinfo->clause;
435+
}
436+
385437
if (IsA(clause, Var))
386438
{
387439
Var *var = (Var *) clause;
@@ -448,9 +500,10 @@ clause_selectivity(Query *root,
448500
else if (or_clause(clause))
449501
{
450502
/*
451-
* Selectivities for an 'or' clause are computed as s1+s2 - s1*s2
452-
* to account for the probable overlap of selected tuple sets. XXX
453-
* is this too conservative?
503+
* Selectivities for an OR clause are computed as s1+s2 - s1*s2
504+
* to account for the probable overlap of selected tuple sets.
505+
*
506+
* XXX is this too conservative?
454507
*/
455508
List *arg;
456509

@@ -483,9 +536,13 @@ clause_selectivity(Query *root,
483536
{
484537
/*
485538
* Otherwise, it's a join if there's more than one relation
486-
* used.
539+
* used. We can optimize this calculation if an rinfo was passed.
487540
*/
488-
is_join_clause = (NumRelids(clause) > 1);
541+
if (rinfo)
542+
is_join_clause = (bms_membership(rinfo->clause_relids) ==
543+
BMS_MULTIPLE);
544+
else
545+
is_join_clause = (NumRelids(clause) > 1);
489546
}
490547

491548
if (is_join_clause)
@@ -559,6 +616,10 @@ clause_selectivity(Query *root,
559616
jointype);
560617
}
561618

619+
/* Cache the result if possible */
620+
if (cacheable)
621+
rinfo->this_selec = s1;
622+
562623
#ifdef SELECTIVITY_DEBUG
563624
elog(DEBUG4, "clause_selectivity: s1 %f", s1);
564625
#endif /* SELECTIVITY_DEBUG */

0 commit comments

Comments
 (0)