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

Commit8a6ac83

Browse files
committed
Fix some planner performance problems with large WHERE clauses, by
introducing new 'FastList' list-construction subroutines to use inhot spots. This avoids the O(N^2) behavior of repeated lappend'sby keeping a tail pointer, while not changing behavior by reversinglist order as the lcons() method would do.
1 parent0f3c68a commit8a6ac83

File tree

8 files changed

+364
-192
lines changed

8 files changed

+364
-192
lines changed

‎src/backend/executor/execQual.c

Lines changed: 19 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/executor/execQual.c,v 1.129 2003/05/02 20:54:33 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/execQual.c,v 1.130 2003/05/28 22:32:49 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -2320,9 +2320,10 @@ ExecInitExpr(Expr *node, PlanState *parent)
23202320
{
23212321
CaseExpr*caseexpr= (CaseExpr*)node;
23222322
CaseExprState*cstate=makeNode(CaseExprState);
2323-
List*outlist=NIL;
2323+
FastListoutlist;
23242324
List*inlist;
23252325

2326+
FastListInit(&outlist);
23262327
foreach(inlist,caseexpr->args)
23272328
{
23282329
CaseWhen*when= (CaseWhen*)lfirst(inlist);
@@ -2332,9 +2333,9 @@ ExecInitExpr(Expr *node, PlanState *parent)
23322333
wstate->xprstate.expr= (Expr*)when;
23332334
wstate->expr=ExecInitExpr(when->expr,parent);
23342335
wstate->result=ExecInitExpr(when->result,parent);
2335-
outlist=lappend(outlist,wstate);
2336+
FastAppend(&outlist,wstate);
23362337
}
2337-
cstate->args=outlist;
2338+
cstate->args=FastListValue(&outlist);
23382339
/* caseexpr->arg should be null by now */
23392340
Assert(caseexpr->arg==NULL);
23402341
cstate->defresult=ExecInitExpr(caseexpr->defresult,parent);
@@ -2345,18 +2346,19 @@ ExecInitExpr(Expr *node, PlanState *parent)
23452346
{
23462347
ArrayExpr*arrayexpr= (ArrayExpr*)node;
23472348
ArrayExprState*astate=makeNode(ArrayExprState);
2348-
List*outlist=NIL;
2349+
FastListoutlist;
23492350
List*inlist;
23502351

2352+
FastListInit(&outlist);
23512353
foreach(inlist,arrayexpr->elements)
23522354
{
23532355
Expr*e= (Expr*)lfirst(inlist);
23542356
ExprState*estate;
23552357

23562358
estate=ExecInitExpr(e,parent);
2357-
outlist=lappend(outlist,estate);
2359+
FastAppend(&outlist,estate);
23582360
}
2359-
astate->elements=outlist;
2361+
astate->elements=FastListValue(&outlist);
23602362
/* do one-time catalog lookup for type info */
23612363
get_typlenbyvalalign(arrayexpr->element_typeid,
23622364
&astate->elemlength,
@@ -2369,18 +2371,19 @@ ExecInitExpr(Expr *node, PlanState *parent)
23692371
{
23702372
CoalesceExpr*coalesceexpr= (CoalesceExpr*)node;
23712373
CoalesceExprState*cstate=makeNode(CoalesceExprState);
2372-
List*outlist=NIL;
2374+
FastListoutlist;
23732375
List*inlist;
23742376

2377+
FastListInit(&outlist);
23752378
foreach(inlist,coalesceexpr->args)
23762379
{
23772380
Expr*e= (Expr*)lfirst(inlist);
23782381
ExprState*estate;
23792382

23802383
estate=ExecInitExpr(e,parent);
2381-
outlist=lappend(outlist,estate);
2384+
FastAppend(&outlist,estate);
23822385
}
2383-
cstate->args=outlist;
2386+
cstate->args=FastListValue(&outlist);
23842387
state= (ExprState*)cstate;
23852388
}
23862389
break;
@@ -2434,17 +2437,18 @@ ExecInitExpr(Expr *node, PlanState *parent)
24342437
break;
24352438
caseT_List:
24362439
{
2437-
List*outlist=NIL;
2440+
FastListoutlist;
24382441
List*inlist;
24392442

2443+
FastListInit(&outlist);
24402444
foreach(inlist, (List*)node)
24412445
{
2442-
outlist=lappend(outlist,
2443-
ExecInitExpr((Expr*)lfirst(inlist),
2444-
parent));
2446+
FastAppend(&outlist,
2447+
ExecInitExpr((Expr*)lfirst(inlist),
2448+
parent));
24452449
}
24462450
/* Don't fall through to the "common" code below */
2447-
return (ExprState*)outlist;
2451+
return (ExprState*)FastListValue(&outlist);
24482452
}
24492453
default:
24502454
elog(ERROR,"ExecInitExpr: unknown expression type %d",

‎src/backend/nodes/list.c

Lines changed: 117 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.48 2003/02/09 06:56:27 tgl Exp $
12+
* $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.49 2003/05/28 22:32:49 tgl Exp $
1313
*
1414
* NOTES
1515
* XXX a few of the following functions are duplicated to handle
@@ -141,9 +141,9 @@ lconso(Oid datum, List *list)
141141
* MORE EXPENSIVE THAN lcons
142142
*/
143143
List*
144-
lappend(List*list,void*obj)
144+
lappend(List*list,void*datum)
145145
{
146-
returnnconc(list,makeList1(obj));
146+
returnnconc(list,makeList1(datum));
147147
}
148148

149149
/*
@@ -195,6 +195,120 @@ nconc(List *l1, List *l2)
195195
returnl1;/* list1 is now list1+list2 */
196196
}
197197

198+
/*
199+
* FastAppend - append to a FastList.
200+
*
201+
* For long lists this is significantly faster than repeated lappend's,
202+
* since we avoid having to chase down the list again each time.
203+
*/
204+
void
205+
FastAppend(FastList*fl,void*datum)
206+
{
207+
List*cell=makeList1(datum);
208+
209+
if (fl->tail)
210+
{
211+
lnext(fl->tail)=cell;
212+
fl->tail=cell;
213+
}
214+
else
215+
{
216+
/* First cell of list */
217+
Assert(fl->head==NIL);
218+
fl->head=fl->tail=cell;
219+
}
220+
}
221+
222+
/*
223+
* FastAppendi - same for integers
224+
*/
225+
void
226+
FastAppendi(FastList*fl,intdatum)
227+
{
228+
List*cell=makeListi1(datum);
229+
230+
if (fl->tail)
231+
{
232+
lnext(fl->tail)=cell;
233+
fl->tail=cell;
234+
}
235+
else
236+
{
237+
/* First cell of list */
238+
Assert(fl->head==NIL);
239+
fl->head=fl->tail=cell;
240+
}
241+
}
242+
243+
/*
244+
* FastAppendo - same for Oids
245+
*/
246+
void
247+
FastAppendo(FastList*fl,Oiddatum)
248+
{
249+
List*cell=makeListo1(datum);
250+
251+
if (fl->tail)
252+
{
253+
lnext(fl->tail)=cell;
254+
fl->tail=cell;
255+
}
256+
else
257+
{
258+
/* First cell of list */
259+
Assert(fl->head==NIL);
260+
fl->head=fl->tail=cell;
261+
}
262+
}
263+
264+
/*
265+
* FastConc - nconc() for FastList building
266+
*
267+
* Note that the cells of the second argument are absorbed into the FastList.
268+
*/
269+
void
270+
FastConc(FastList*fl,List*cells)
271+
{
272+
if (cells==NIL)
273+
return;/* nothing to do */
274+
if (fl->tail)
275+
{
276+
lnext(fl->tail)=cells;
277+
}
278+
else
279+
{
280+
/* First cell of list */
281+
Assert(fl->head==NIL);
282+
fl->head=cells;
283+
}
284+
while (lnext(cells)!=NIL)
285+
cells=lnext(cells);
286+
fl->tail=cells;
287+
}
288+
289+
/*
290+
* FastConcFast - nconc() for FastList building
291+
*
292+
* Note that the cells of the second argument are absorbed into the first.
293+
*/
294+
void
295+
FastConcFast(FastList*fl,FastList*fl2)
296+
{
297+
if (fl2->head==NIL)
298+
return;/* nothing to do */
299+
if (fl->tail)
300+
{
301+
lnext(fl->tail)=fl2->head;
302+
}
303+
else
304+
{
305+
/* First cell of list */
306+
Assert(fl->head==NIL);
307+
fl->head=fl2->head;
308+
}
309+
fl->tail=fl2->tail;
310+
}
311+
198312
/*
199313
*nth
200314
*

0 commit comments

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