Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitf5e8366

Browse files
committed
Modify planner's implied-equality-deduction code so that when a set
of known-equal expressions includes any constant expressions (includingParams from outer queries), we actively suppress any 'var = var'clauses that are or could be deduced from the set, generating only thededucible 'var = const' clauses instead. The idea here is to push downthe restrictions implied by the equality set to base relations wheneverpossible. Once we have applied the 'var = const' clauses, the 'var = var'clauses are redundant, and should be suppressed both to save work atexecution and to avoid double-counting restrictivity.
1 parentef74225 commitf5e8366

File tree

12 files changed

+395
-168
lines changed

12 files changed

+395
-168
lines changed

‎src/backend/nodes/list.c

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.44 2003/01/20 18:54:47 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.45 2003/01/24 03:58:34 tgl Exp $
1212
*
1313
* NOTES
1414
* XXX a few of the following functions are duplicated to handle
@@ -357,6 +357,7 @@ set_union(List *l1, List *l2)
357357
returnretval;
358358
}
359359

360+
/* set_union for integer lists */
360361
List*
361362
set_unioni(List*l1,List*l2)
362363
{
@@ -371,6 +372,21 @@ set_unioni(List *l1, List *l2)
371372
returnretval;
372373
}
373374

375+
/* set_union when pointer-equality comparison is sufficient */
376+
List*
377+
set_ptrUnion(List*l1,List*l2)
378+
{
379+
List*retval=listCopy(l1);
380+
List*i;
381+
382+
foreach(i,l2)
383+
{
384+
if (!ptrMember(lfirst(i),retval))
385+
retval=lappend(retval,lfirst(i));
386+
}
387+
returnretval;
388+
}
389+
374390
/*
375391
* Generate the intersection of two lists,
376392
* ie, all members of both l1 and l2.

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

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.132 2003/01/20 18:54:49 tgl Exp $
12+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.133 2003/01/24 03:58:34 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -1596,12 +1596,14 @@ make_innerjoin_index_path(Query *root,
15961596
* nconc the two lists; then we might have some restriction
15971597
* clauses appearing twice, which'd mislead
15981598
* restrictlist_selectivity into double-counting their
1599-
* selectivity.)
1599+
* selectivity. However, since RestrictInfo nodes aren't copied when
1600+
* linking them into different lists, it should be sufficient to use
1601+
* pointer comparison to remove duplicates.)
16001602
*/
16011603
pathnode->rows=rel->tuples*
16021604
restrictlist_selectivity(root,
1603-
set_union(rel->baserestrictinfo,
1604-
clausegroup),
1605+
set_ptrUnion(rel->baserestrictinfo,
1606+
clausegroup),
16051607
lfirsti(rel->relids));
16061608
/* Like costsize.c, force estimate to be at least one row */
16071609
if (pathnode->rows<1.0)

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

Lines changed: 111 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
* Portions Copyright (c) 1994, Regents of the University of California
1212
*
1313
* IDENTIFICATION
14-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.44 2003/01/15 19:35:40 tgl Exp $
14+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.45 2003/01/24 03:58:35 tgl Exp $
1515
*
1616
*-------------------------------------------------------------------------
1717
*/
@@ -23,6 +23,7 @@
2323
#include"optimizer/paths.h"
2424
#include"optimizer/planmain.h"
2525
#include"optimizer/tlist.h"
26+
#include"optimizer/var.h"
2627
#include"parser/parsetree.h"
2728
#include"parser/parse_func.h"
2829
#include"utils/lsyscache.h"
@@ -147,14 +148,30 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
147148
* generate_implied_equalities
148149
* Scan the completed equi_key_list for the query, and generate explicit
149150
* qualifications (WHERE clauses) for all the pairwise equalities not
150-
* already mentioned in the quals. This is useful because the additional
151-
* clauses help the selectivity-estimation code, and in fact it's
152-
* *necessary* to ensure that sort keys we think are equivalent really
153-
* are (see src/backend/optimizer/README for more info).
151+
* already mentioned in the quals; or remove qualifications found to be
152+
* redundant.
153+
*
154+
* Adding deduced equalities is useful because the additional clauses help
155+
* the selectivity-estimation code and may allow better joins to be chosen;
156+
* and in fact it's *necessary* to ensure that sort keys we think are
157+
* equivalent really are (see src/backend/optimizer/README for more info).
158+
*
159+
* If an equi_key_list set includes any constants then we adopt a different
160+
* strategy: we record all the "var = const" deductions we can make, and
161+
* actively remove all the "var = var" clauses that are implied by the set
162+
* (including the clauses that originally gave rise to the set!). The reason
163+
* is that given input like "a = b AND b = 42", once we have deduced "a = 42"
164+
* there is no longer any need to apply the clause "a = b"; not only is
165+
* it a waste of time to check it, but we will misestimate selectivity if the
166+
* clause is left in. So we must remove it. For this purpose, any pathkey
167+
* item that mentions no Vars of the current level can be taken as a constant.
168+
* (The only case where this would be risky is if the item contains volatile
169+
* functions; but we will never consider such an expression to be a pathkey
170+
* at all, because check_mergejoinable() will reject it.)
154171
*
155172
* This routine just walks the equi_key_list to find all pairwise equalities.
156-
* We call process_implied_equality (in plan/initsplan.c) todetermine whether
157-
*each is already known and add it to the properrestrictinfolist if not.
173+
* We call process_implied_equality (in plan/initsplan.c) toadjust the
174+
* restrictinfodatastructures for each pair.
158175
*/
159176
void
160177
generate_implied_equalities(Query*root)
@@ -164,35 +181,119 @@ generate_implied_equalities(Query *root)
164181
foreach(cursetlink,root->equi_key_list)
165182
{
166183
List*curset=lfirst(cursetlink);
184+
intnitems=length(curset);
185+
Relids*relids;
186+
boolhave_consts;
167187
List*ptr1;
188+
inti1;
168189

169190
/*
170191
* A set containing only two items cannot imply any equalities
171192
* beyond the one that created the set, so we can skip it.
172193
*/
173-
if (length(curset)<3)
194+
if (nitems<3)
174195
continue;
175196

197+
/*
198+
* Collect info about relids mentioned in each item. For this
199+
* routine we only really care whether there are any at all in
200+
* each item, but process_implied_equality() needs the exact
201+
* lists, so we may as well pull them here.
202+
*/
203+
relids= (Relids*)palloc(nitems*sizeof(Relids));
204+
have_consts= false;
205+
i1=0;
206+
foreach(ptr1,curset)
207+
{
208+
PathKeyItem*item1= (PathKeyItem*)lfirst(ptr1);
209+
210+
relids[i1]=pull_varnos(item1->key);
211+
if (relids[i1]==NIL)
212+
have_consts= true;
213+
i1++;
214+
}
215+
176216
/*
177217
* Match each item in the set with all that appear after it (it's
178218
* sufficient to generate A=B, need not process B=A too).
179219
*/
220+
i1=0;
180221
foreach(ptr1,curset)
181222
{
182223
PathKeyItem*item1= (PathKeyItem*)lfirst(ptr1);
183224
List*ptr2;
225+
inti2=i1+1;
184226

185227
foreach(ptr2,lnext(ptr1))
186228
{
187229
PathKeyItem*item2= (PathKeyItem*)lfirst(ptr2);
188230

189-
process_implied_equality(root,item1->key,item2->key,
190-
item1->sortop,item2->sortop);
231+
/*
232+
* If it's "const = const" then just ignore it altogether.
233+
* There is no place in the restrictinfo structure to store
234+
* it. (If the two consts are in fact unequal, then
235+
* propagating the comparison to Vars will cause us to
236+
* produce zero rows out, as expected.)
237+
*/
238+
if (relids[i1]!=NIL||relids[i2]!=NIL)
239+
{
240+
/*
241+
* Tell process_implied_equality to delete the clause,
242+
* not add it, if it's "var = var" and we have constants
243+
* present in the list.
244+
*/
245+
booldelete_it= (have_consts&&
246+
relids[i1]!=NIL&&
247+
relids[i2]!=NIL);
248+
process_implied_equality(root,
249+
item1->key,item2->key,
250+
item1->sortop,item2->sortop,
251+
relids[i1],relids[i2],
252+
delete_it);
253+
}
254+
i2++;
191255
}
256+
i1++;
257+
}
258+
}
259+
}
260+
261+
/*
262+
* exprs_known_equal
263+
* Detect whether two expressions are known equal due to equijoin clauses.
264+
*
265+
* Note: does not bother to check for "equal(item1, item2)"; caller must
266+
* check that case if it's possible to pass identical items.
267+
*/
268+
bool
269+
exprs_known_equal(Query*root,Node*item1,Node*item2)
270+
{
271+
List*cursetlink;
272+
273+
foreach(cursetlink,root->equi_key_list)
274+
{
275+
List*curset=lfirst(cursetlink);
276+
boolitem1member= false;
277+
boolitem2member= false;
278+
List*ptr;
279+
280+
foreach(ptr,curset)
281+
{
282+
PathKeyItem*pitem= (PathKeyItem*)lfirst(ptr);
283+
284+
if (equal(item1,pitem->key))
285+
item1member= true;
286+
elseif (equal(item2,pitem->key))
287+
item2member= true;
288+
/* Exit as soon as equality is proven */
289+
if (item1member&&item2member)
290+
return true;
192291
}
193292
}
293+
return false;
194294
}
195295

296+
196297
/*
197298
* make_canonical_pathkey
198299
* Given a PathKeyItem, find the equi_key_list subset it is a member of,

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp