Skip to content

Commit 8a6ac83

Browse files
tglsfdctglsfdc
committed
Fix some planner performance problems with large WHERE clauses, by
introducing new 'FastList' list-construction subroutines to use in hot spots. This avoids the O(N^2) behavior of repeated lappend's by keeping a tail pointer, while not changing behavior by reversing list order as the lcons() method would do.
1 parent 0f3c68a commit 8a6ac83

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+
FastList outlist;
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+
FastList outlist;
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+
FastList outlist;
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
case T_List:
24362439
{
2437-
List *outlist = NIL;
2440+
FastList outlist;
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-
return nconc(list, makeList1(obj));
146+
return nconc(list, makeList1(datum));
147147
}
148148

149149
/*
@@ -195,6 +195,120 @@ nconc(List *l1, List *l2)
195195
return l1; /* 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, int datum)
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, Oid datum)
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)