From 8a6ac83dab3b3a5701a0508daa1d9356e2d59cdb Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 28 May 2003 22:32:50 +0000
Subject: 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.

---
 src/include/nodes/pg_list.h | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

(limited to 'src/include')

diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index b48fc02e855..bc42917a355 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pg_list.h,v 1.35 2003/02/09 06:56:28 tgl Exp $
+ * $Id: pg_list.h,v 1.36 2003/05/28 22:32:50 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -128,6 +128,21 @@ typedef struct List
 #define makeListo1(x1)				lconso(x1, NIL)
 #define makeListo2(x1,x2)			lconso(x1, makeListo1(x2))
 
+/*
+ * 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.
+ */
+typedef struct FastList
+{
+	List	   *head;
+	List	   *tail;
+} FastList;
+
+#define FastListInit(fl)	( (fl)->head = (fl)->tail = NIL )
+#define FastListValue(fl)	( (fl)->head )
+
+
 /*
  * function prototypes in nodes/list.c
  */
@@ -143,6 +158,11 @@ extern List *lappend(List *list, void *datum);
 extern List *lappendi(List *list, int datum);
 extern List *lappendo(List *list, Oid datum);
 extern List *nconc(List *list1, List *list2);
+extern void FastAppend(FastList *fl, void *datum);
+extern void FastAppendi(FastList *fl, int datum);
+extern void FastAppendo(FastList *fl, Oid datum);
+extern void FastConc(FastList *fl, List *cells);
+extern void FastConcFast(FastList *fl, FastList *fl2);
 extern void *nth(int n, List *l);
 extern int	length(List *list);
 extern void *llast(List *list);
-- 
cgit v1.2.3