diff options
| author | Tom Lane <tgl@sss.pgh.pa.us> | 2003-08-22 20:34:33 +0000 |
|---|---|---|
| committer | Tom Lane <tgl@sss.pgh.pa.us> | 2003-08-22 20:34:33 +0000 |
| commit | 29a43f398afdbc8372452010b330f242d9ff298d (patch) | |
| tree | 7d5da462ef9de68e362ec5e8936dc25c576f2c32 /src | |
| parent | 92ee2528d8bf46739a460e3395057416c53e10d1 (diff) | |
| download | postgresql-29a43f398afdbc8372452010b330f242d9ff298d.tar.gz postgresql-29a43f398afdbc8372452010b330f242d9ff298d.zip | |
Tweak grammar to use FastAppend rather than lappend when constructing
expr_lists. This appears to be the only remaining O(N^2) bottleneck
in processing many-way 'x IN (a,b,c,...)' conditions.
Diffstat (limited to 'src')
| -rw-r--r-- | src/backend/parser/gram.y | 17 | ||||
| -rw-r--r-- | src/include/nodes/pg_list.h | 8 |
2 files changed, 21 insertions, 4 deletions
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y index ef6f8a80c5c..5bdbe012a95 100644 --- a/src/backend/parser/gram.y +++ b/src/backend/parser/gram.y @@ -11,7 +11,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/parser/gram.y,v 2.429 2003/08/17 19:58:05 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/parser/gram.y,v 2.430 2003/08/22 20:34:33 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -108,6 +108,7 @@ static void doNegateFloat(Value *v); DropBehavior dbehavior; OnCommitAction oncommit; List *list; + FastList fastlist; Node *node; Value *value; ColumnRef *columnref; @@ -6719,8 +6720,18 @@ opt_indirection: { $$ = NIL; } ; -expr_list: a_expr { $$ = makeList1($1); } - | expr_list ',' a_expr { $$ = lappend($1, $3); } +expr_list: a_expr + { + FastList *dst = (FastList *) &$$; + makeFastList1(dst, $1); + } + | expr_list ',' a_expr + { + FastList *dst = (FastList *) &$$; + FastList *src = (FastList *) &$1; + *dst = *src; + FastAppend(dst, $3); + } ; extract_list: diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h index 4d9ce8304b1..8ab22560ce6 100644 --- a/src/include/nodes/pg_list.h +++ b/src/include/nodes/pg_list.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: pg_list.h,v 1.40 2003/08/08 21:42:48 momjian Exp $ + * $Id: pg_list.h,v 1.41 2003/08/22 20:34:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -132,6 +132,9 @@ typedef struct List * FastList is an optimization for building large lists. The conventional * way to build a list is repeated lappend() operations, but that is O(N^2) * in the number of list items, which gets tedious for large lists. + * + * Note: there are some hacks in gram.y that rely on the head pointer (the + * value-as-list) being the first field. */ typedef struct FastList { @@ -144,6 +147,9 @@ typedef struct FastList ( (fl)->head = (l), (fl)->tail = llastnode((fl)->head) ) #define FastListValue(fl) ( (fl)->head ) +#define makeFastList1(fl, x1) \ + ( (fl)->head = (fl)->tail = makeList1(x1) ) + /* * function prototypes in nodes/list.c |