Commit29a43f3

committed

Tweak grammar to use FastAppend rather than lappend when constructing

expr_lists. This appears to be the only remaining O(N^2) bottleneckin processing many-way 'x IN (a,b,c,...)' conditions.

1 parent92ee252 commit29a43f3Copy full SHA for 29a43f3

File tree

+21

-4

lines changed

+21

-4

lines changed

Lines changed: 14 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -11,7 +11,7 @@`
`11`	`11`	`*`
`12`	`12`	`*`
`13`	`13`	`* IDENTIFICATION`
`14`		`- * $Header: /cvsroot/pgsql/src/backend/parser/gram.y,v 2.429 2003/08/17 19:58:05 tgl Exp $`
	`14`	`+ * $Header: /cvsroot/pgsql/src/backend/parser/gram.y,v 2.430 2003/08/22 20:34:33 tgl Exp $`
`15`	`15`	`*`
`16`	`16`	`* HISTORY`
`17`	`17`	`* AUTHORDATEMAJOR EVENT`
`@@ -108,6 +108,7 @@ static void doNegateFloat(Value *v);`
`108`	`108`	`DropBehaviordbehavior;`
`109`	`109`	`OnCommitActiononcommit;`
`110`	`110`	`List*list;`
	`111`	`+FastListfastlist;`
`111`	`112`	`Node*node;`
`112`	`113`	`Value*value;`
`113`	`114`	`ColumnRef*columnref;`
`@@ -6719,8 +6720,18 @@ opt_indirection:`
`6719`	`6720`	`{ $$ = NIL; }`
`6720`	`6721`	`;`
`6721`	`6722`
`6722`		`-expr_list:a_expr{ $$ =makeList1($1); }`
`6723`		`-\| expr_list',' a_expr{ $$ =lappend($1, $3); }`
	`6723`	`+expr_list:a_expr`
	`6724`	`+{`
	`6725`	`+FastList dst = (FastList ) &$$;`
	`6726`	`+makeFastList1(dst, $1);`
	`6727`	`+}`
	`6728`	`+\| expr_list',' a_expr`
	`6729`	`+{`
	`6730`	`+FastList dst = (FastList ) &$$;`
	`6731`	`+FastList src = (FastList ) &$1;`
	`6732`	`+dst = src;`
	`6733`	`+FastAppend(dst, $3);`
	`6734`	`+}`
`6724`	`6735`	`;`
`6725`	`6736`
`6726`	`6737`	`extract_list:`

Lines changed: 7 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -7,7 +7,7 @@`
`7`	`7`	`* Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group`
`8`	`8`	`* Portions Copyright (c) 1994, Regents of the University of California`
`9`	`9`	`*`
`10`		`- * $Id: pg_list.h,v 1.40 2003/08/08 21:42:48 momjian Exp $`
	`10`	`+ * $Id: pg_list.h,v 1.41 2003/08/22 20:34:33 tgl Exp $`
`11`	`11`	`*`
`12`	`12`	`*-------------------------------------------------------------------------`
`13`	`13`	`*/`
`@@ -132,6 +132,9 @@ typedef struct List`
`132`	`132`	`* FastList is an optimization for building large lists. The conventional`
`133`	`133`	`* way to build a list is repeated lappend() operations, but that is O(N^2)`
`134`	`134`	`* in the number of list items, which gets tedious for large lists.`
	`135`	`+ *`
	`136`	`+ * Note: there are some hacks in gram.y that rely on the head pointer (the`
	`137`	`+ * value-as-list) being the first field.`
`135`	`138`	`*/`
`136`	`139`	`typedefstructFastList`
`137`	`140`	`{`
`@@ -144,6 +147,9 @@ typedef struct FastList`
`144`	`147`	`( (fl)->head = (l), (fl)->tail = llastnode((fl)->head) )`
`145`	`148`	`#defineFastListValue(fl)( (fl)->head )`
`146`	`149`
	`150`	`+#definemakeFastList1(fl,x1) \`
	`151`	`+( (fl)->head = (fl)->tail = makeList1(x1) )`
	`152`	`+`
`147`	`153`
`148`	`154`	`/*`
`149`	`155`	`* function prototypes in nodes/list.c`

Comments

(0)