pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
problem with OR'ed AND queriess
7+ messages / 4 participants
[nested] [flat]

* problem with OR'ed AND queriess
@ 1999-12-21 21:05 Michael McCarthy <michael@tcsi.com>
  1999-12-21 22:53 ` Re: [SQL] problem with OR'ed AND queriess David C Hartwig Jr <daybee@bellatlantic.net>
  1999-12-22 00:02 ` Re: [SQL] problem with OR'ed AND queriess Tom Lane <tgl@sss.pgh.pa.us>
  1999-12-22 03:51 ` Re: [SQL] problem with OR'ed AND queriess Bruce Momjian <pgman@candle.pha.pa.us>
  0 siblings, 3 replies; 7+ messages in thread

From: Michael McCarthy @ 1999-12-21 21:05 UTC (permalink / raw)
  To: pgsql-sql

Using PQexec from libpq in postgresql 6.5.3, I submit a query of the
following form, which has 13 OR'ed AND expressions:

    DECLARE my_cursor CURSOR FOR SELECT col1 FROM testCNF where
    ( ( col1=0  and col2=1  ) OR ( col1=1  and col2=2  ) OR
      ( col1=2  and col2=3  ) OR ( col1=3  and col2=4  ) OR
      ( col1=4  and col2=5  ) OR ( col1=5  and col2=6  ) OR
      ( col1=6  and col2=7  ) OR ( col1=7  and col2=8  ) OR
      ( col1=8  and col2=9  ) OR ( col1=9  and col2=10 ) OR
      ( col1=10 and col2=11 ) OR ( col1=11 and col2=12 ) OR
      ( col1=12 and col2=13 ) )

After 265 seconds, my test client gets back a NULL response from PQexec.
During the 265 seconds, the backend server machine (Sparc Ultra 2) slows
to a crawl. In the postmaster log, I see the following:

    FATAL 1:  Memory exhausted in AllocSetAlloc()

A similar query with 12 OR'ed AND expresions is successful, but only after
123 seconds. Queries with fewer OR'ed AND expresions get faster; 6 OR'ed
ANDS takes around one second. With other query types, I encounter no such
limitation; AND'ed ORs, all ANDs and all ORs can be as large a query as
the internal buffer can support (around 16k), with no problem.

I have traced the backend server in a debugger; a stack trace is attached
below. What I see in examining the code is a recursive normalization of
the query; postgres is running out of memory trying to convert the OR'ed
ANDs query to conjunctive normal form (CNF).

So, some questions for all you postgres gurus:

1. Has anyone else encountered this problem?

2. Has anyone patched the query optimizer to get around this problem, and
   if so, where can I find the patch?

3. If I am truly the first to encounter this (which I doubt), how would I
   go about altering the query optimizer to not fail on this valid query? 

Thanks,

//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
Michael McCarthy                             TCSI Corporation
michael@tcsi.com                             1080 Marina Village Parkway
(510) 749-8739                               Alameda, CA 94501

(/opt/packages/SUNWspro/bin/dbx) where       
  [1] AllocSetReset(0x56d488, 0x40aaf0, 0x1, 0x9c, 0x0, 0x0), at 0x285f80
  [2] EndPortalAllocMode(0x502a70, 0x6fd0495c, 0x0, 0x0, 0x0, 0x0), at 0x28a398
  [3] PortalResetHeapMemory(0x502a40, 0x0, 0x0, 0x0, 0x0, 0x0), at 0x289fcc
  [4] AtAbort_Memory(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xb68bc
  [5] AbortTransaction(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xb6d8c
  [6] AbortOutOfAnyTransaction(0x0, 0x6feaa484, 0x4d88c8, 0x5015a7, 0x6fea2ca4, 0x0), at 0xb740c
  [7] remove_all_temp_relations(0x0, 0x0, 0x0, 0x0, 0x6fea2ca4, 0x0), at 0x27c5dc
  [8] shmem_exit(0x0, 0x409c98, 0x0, 0x0, 0x0, 0x0), at 0x1df424
  [9] proc_exit(0x0, 0x6feaa484, 0x2e, 0x7efefeff, 0x6fea2ca4, 0x27d294), at 0x1df214
  [10] elog(0x1, 0x411a00, 0x0, 0x0, 0x0, 0x0), at 0x27d58c
  [11] AllocSetAlloc(0x56d488, 0xc, 0x0, 0x0, 0x0, 0x0), at 0x2866cc
  [12] PortalHeapMemoryAlloc(0x502a70, 0xc, 0x0, 0x0, 0x0, 0x0), at 0x287f34
  [13] MemoryContextAlloc(0x502a70, 0xc, 0x0, 0x0, 0x0, 0x0), at 0x286fdc
  [14] newNode(0xc, 0x1f5, 0x0, 0x0, 0x0, 0x0), at 0x168928
  [15] lcons(0x1f66e5c8, 0x0, 0x0, 0x0, 0x0, 0x0), at 0x168b6c
  [16] copyObject(0x1f662a90, 0x66, 0x0, 0x0, 0x0, 0x0), at 0x16ecf4
  [17] _copyExpr(0x1f662998, 0x1f5, 0x0, 0x0, 0x0, 0x0), at 0x16b3e8
  [18] copyObject(0x1f662998, 0x0, 0x0, 0x0, 0x0, 0x0), at 0x16e7c4
  [19] copyObject(0x1f662980, 0x66, 0x0, 0x0, 0x0, 0x0), at 0x16ecdc
  [20] _copyExpr(0x1f661e50, 0x14, 0x0, 0x0, 0x0, 0x0), at 0x16b3e8
  [21] copyObject(0x1f661e50, 0x14, 0x0, 0x0, 0x0, 0x0), at 0x16e7c4
  [22] copyObject(0x1f6634b8, 0x66, 0x0, 0x0, 0x0, 0x0), at 0x16ec94
  [23] _copyExpr(0x1f661e28, 0x1f5, 0x0, 0x0, 0x0, 0x0), at 0x16b3e8
  [24] copyObject(0x1f661e28, 0x0, 0x0, 0x0, 0x0, 0x0), at 0x16e7c4
  [25] copyObject(0x1f661e10, 0x66, 0x0, 0x0, 0x0, 0x0), at 0x16ecdc
  [26] _copyExpr(0x1f660740, 0x14, 0x0, 0x0, 0x0, 0x0), at 0x16b3e8
  [27] copyObject(0x1f660740, 0x14, 0x0, 0x0, 0x0, 0x0), at 0x16e7c4
  [28] copyObject(0x1f6634e8, 0x66, 0x0, 0x0, 0x0, 0x0), at 0x16ec94
  [29] _copyExpr(0x1f660718, 0x1f5, 0x0, 0x0, 0x0, 0x0), at 0x16b3e8
  [30] copyObject(0x1f660718, 0x0, 0x0, 0x0, 0x0, 0x0), at 0x16e7c4
  [31] copyObject(0x1f660700, 0x66, 0x0, 0x0, 0x0, 0x0), at 0x16ecdc
  [32] _copyExpr(0x1f65d8f0, 0xc, 0x0, 0x0, 0x0, 0x0), at 0x16b3e8
  [33] copyObject(0x1f65d8f0, 0xc, 0x0, 0x0, 0x0, 0x0), at 0x16e7c4
  [34] copyObject(0x1f663518, 0xc, 0x0, 0x0, 0x0, 0x0), at 0x16ec94
  [35] pull_ors(0x1f669210, 0x1f5, 0x0, 0x0, 0x0, 0x0), at 0x19d584
  [36] pull_ors(0x1f669228, 0x1f669210, 0x0, 0x0, 0x0, 0x0), at 0x19d5f8
  [37] distribute_args(0x69ace48, 0x1f663530, 0x0, 0x0, 0x0, 0x0), at 0x19dd64
  [38] or_normalize(0x1f6691f8, 0x1f65d870, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [39] distribute_args(0x69ace48, 0x1f651e90, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [40] or_normalize(0x1f65d858, 0x1f6464d0, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [41] distribute_args(0x69ace48, 0x1f62f0f0, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [42] or_normalize(0x1f6464b8, 0x1f617d30, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [43] distribute_args(0x69ace48, 0x1f49fb58, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [44] or_normalize(0x1f4ce320, 0x1f471398, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [45] distribute_args(0x69ace48, 0x1f123fd8, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [46] or_normalize(0x1f180fa0, 0x1f0c7018, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [47] distribute_args(0x69ace48, 0x1e972820, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [48] or_normalize(0x1ea2c7e8, 0x1e8b8860, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [49] distribute_args(0x69ace48, 0x1e744880, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [50] or_normalize(0x1e8b8848, 0x1e5d08c0, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [51] distribute_args(0x69ace48, 0x1c2ae828, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [52] or_normalize(0x1c596810, 0x1bfc6868, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [53] distribute_args(0x69ace48, 0xf7d2280, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [54] or_normalize(0x1bfc6850, 0x1bfc6808, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [55] distribute_args(0x1333e468, 0x69ace00, 0x0, 0x0, 0x0, 0x0), at 0x19dd74
  [56] or_normalize(0x1333e490, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc34
  [57] or_normalize(0xbc660a0, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [58] or_normalize(0x8ae9e58, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [59] or_normalize(0x76afca8, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [60] or_normalize(0x6e9ab00, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [61] or_normalize(0x6b77150, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [62] or_normalize(0x6a4a3d0, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [63] or_normalize(0x69df050, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [64] or_normalize(0x69bb5d0, 0x6982cd0, 0x0, 0x0, 0x0, 0x0), at 0x19dc64
  [65] or_normalize(0x69b0ad0, 0x6982cd0, 0x69ada90, 0xefffa9e4, 0x3, 0x0), at 0x19dc64
  [66] or_normalize(0x69adf90, 0x6982cd0, 0x0, 0xefff660b, 0x5734c8, 0x0), at 0x19dc64
  [67] or_normalize(0x6982bb0, 0x69adae8, 0x0, 0x5a5ea8, 0x0, 0x0), at 0x19dc64
  [68] normalize(0x6982a80, 0x0, 0x0, 0x0, 0x0, 0x5a5850), at 0x19cbdc
  [69] cnfify(0x5a5f78, 0x1, 0x1, 0x0, 0x0, 0x5a5965), at 0x19c368
  [70] query_planner(0x5a5a18, 0x1, 0x627458, 0x5a5f78, 0x54a55a, 0xf), at 0x194dfc
  [71] union_planner(0x5a5a18, 0x0, 0xefff6098, 0xefff66d0, 0x70b, 0x70a), at 0x1958e0
  [72] planner(0x5a5a18, 0x627410, 0x0, 0x5015ac, 0x51, 0xefffa9db), at 0x195380
  [73] pg_parse_and_plan(0xefffaad3, 0x0, 0x0, 0xefffa9e4, 0x3, 0x0), at 0x1fc368
  [74] pg_exec_query_dest(0xefffaad3, 0x3, 0x0, 0x5015ac, 0x6fea2ca4, 0x0), at 0x1fc628
  [75] pg_exec_query(0xefffaad3, 0x40bdf8, 0x20202900, 0x7efefeff, 0x81010100, 0xff00), at 0x1fc568
  [76] PostgresMain(0x4, 0xeffff0a4, 0x5, 0xeffff824, 0x0, 0xefffeba0), at 0x1febf8
=>[77] DoBackend(port = 0x4f5800), line 1628 in "postmaster.c"
  [78] BackendStartup(port = 0x4f5800), line 1373 in "postmaster.c"
  [79] ServerLoop(), line 823 in "postmaster.c"
  [80] PostmasterMain(argc = 5, argv = 0xeffff824), line 616 in "postmaster.c"
  [81] main(argc = 5, argv = 0xeffff824), line 93 in "main.c"




^ permalink  raw  reply  [nested|flat] 7+ messages in thread

* Re: [SQL] problem with OR'ed AND queriess
  1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
@ 1999-12-21 22:53 ` David C Hartwig Jr <daybee@bellatlantic.net>
  1999-12-21 23:33   ` Re: [SQL] problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
  2 siblings, 1 reply; 7+ messages in thread

From: David C Hartwig Jr @ 1999-12-21 22:53 UTC (permalink / raw)
  To: Michael McCarthy <michael@tcsi.com>; +Cc: pgsql-sql

Michael McCarthy wrote:

> Using PQexec from libpq in postgresql 6.5.3, I submit a query of the
> following form, which has 13 OR'ed AND expressions:
>
>     DECLARE my_cursor CURSOR FOR SELECT col1 FROM testCNF where
>     ( ( col1=0  and col2=1  ) OR ( col1=1  and col2=2  ) OR
>       ( col1=2  and col2=3  ) OR ( col1=3  and col2=4  ) OR
>       ( col1=4  and col2=5  ) OR ( col1=5  and col2=6  ) OR
>       ( col1=6  and col2=7  ) OR ( col1=7  and col2=8  ) OR
>       ( col1=8  and col2=9  ) OR ( col1=9  and col2=10 ) OR
>       ( col1=10 and col2=11 ) OR ( col1=11 and col2=12 ) OR
>       ( col1=12 and col2=13 ) )
>
> After 265 seconds, my test client gets back a NULL response from PQexec.
> During the 265 seconds, the backend server machine (Sparc Ultra 2) slows
> to a crawl. In the postmaster log, I see the following:
>
>     FATAL 1:  Memory exhausted in AllocSetAlloc()
>
> A similar query with 12 OR'ed AND expresions is successful, but only after
> 123 seconds. Queries with fewer OR'ed AND expresions get faster; 6 OR'ed
> ANDS takes around one second. With other query types, I encounter no such
> limitation; AND'ed ORs, all ANDs and all ORs can be as large a query as
> the internal buffer can support (around 16k), with no problem.
>
> I have traced the backend server in a debugger; a stack trace is attached
> below. What I see in examining the code is a recursive normalization of
> the query; postgres is running out of memory trying to convert the OR'ed
> ANDs query to conjunctive normal form (CNF).
>
> So, some questions for all you postgres gurus:
>
> 1. Has anyone else encountered this problem?

Yes, its on the todo list.   I do not know if it is being actively persued.

>
>
> 2. Has anyone patched the query optimizer to get around this problem, and
>    if so, where can I find the patch?
>

There is a work around feature that works for queries that gererate a parse tree similar to yours.
ODBC tools generate these kinds of queries all the time.    Keyset queries.   To acivate the
feature:    SET ksqo TO 'on';    It rewrites the parse tree into a series of UNIONs.   Not optimal but
it works for rectangular where clauses.   (n ANDs) x  (m ORs)

--   Here is an example using a 3 part key
     select ... from foo where
         (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 1
         (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 2
                 ...
         (v1 = "?" AND v2 = "?" AND v3 ="?") OR        --  line 9
         (v1 = "?" AND v2 = "?" AND v3 ="?");              --  line 10
     --  The question marks are replaced with the constant key values


>
> 3. If I am truly the first to encounter this (which I doubt), how would I
>    go about altering the query optimizer to not fail on this valid query?
>
> Thanks,




^ permalink  raw  reply  [nested|flat] 7+ messages in thread

* Re: [SQL] problem with OR'ed AND queriess
  1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
  1999-12-21 22:53 ` Re: [SQL] problem with OR'ed AND queriess David C Hartwig Jr <daybee@bellatlantic.net>
@ 1999-12-21 23:33   ` Michael McCarthy <michael@tcsi.com>
  1999-12-22 02:47     ` Re: [SQL] problem with OR'ed AND queriess David C Hartwig Jr <daybee@bellatlantic.net>
  1999-12-22 04:13     ` Re: [SQL] problem with OR'ed AND queriess Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 2 replies; 7+ messages in thread

From: Michael McCarthy @ 1999-12-21 23:33 UTC (permalink / raw)
  To: David C Hartwig Jr <daybee@bellatlantic.net>; +Cc: pgsql-sql@postgresql.org, Hemant Yevale <hemant@tcsi.com>; Savyasachi Jog <jog@tcsi.com>

Hello David:

Thanks for the quick reply; it means a lot to me.

I tried "SET ksqo TO 'on'", and it works fine for my problem query; it
allowed 570 key sets to be resolved in 2 seconds, which is a big step
forward.

I am writing a layer which makes postgres one RDBMS (of several) which can
support a generic object persistence framework. The use of "SET ksqo TO
'on'" is a postgres implementation detail which applications using the
framework will not be aware of. I am faced with the problem of whether or
not to use "SET ksqo TO 'on'" for all queries, or find some criteria for
turning it on and off.

A quick examination of backend/optimizer/prep/prepkeyset.c shows me that
there is some qualification of a query for keyset optimization; is there
any reason why I should not always set ksqo on?

Thanks for your help!

//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
Michael McCarthy                             TCSI Corporation
michael@tcsi.com                             1080 Marina Village Parkway
(510) 749-8739                               Alameda, CA 94501

On Tue, 21 Dec 1999, David C Hartwig Jr wrote:

> There is a work around feature that works for queries that gererate a parse tree similar to yours.
> ODBC tools generate these kinds of queries all the time.    Keyset queries.   To acivate the
> feature:    SET ksqo TO 'on';    It rewrites the parse tree into a series of UNIONs.   Not optimal but
> it works for rectangular where clauses.   (n ANDs) x  (m ORs)
> 
> --   Here is an example using a 3 part key
>      select ... from foo where
>          (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 1
>          (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 2
>                  ...
>          (v1 = "?" AND v2 = "?" AND v3 ="?") OR        --  line 9
>          (v1 = "?" AND v2 = "?" AND v3 ="?");              --  line 10
>      --  The question marks are replaced with the constant key values




^ permalink  raw  reply  [nested|flat] 7+ messages in thread

* Re: [SQL] problem with OR'ed AND queriess
  1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
  1999-12-21 22:53 ` Re: [SQL] problem with OR'ed AND queriess David C Hartwig Jr <daybee@bellatlantic.net>
  1999-12-21 23:33   ` Re: [SQL] problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
@ 1999-12-22 02:47     ` David C Hartwig Jr <daybee@bellatlantic.net>
  1 sibling, 0 replies; 7+ messages in thread

From: David C Hartwig Jr @ 1999-12-22 02:47 UTC (permalink / raw)
  To: Michael McCarthy <michael@tcsi.com>; +Cc: pgsql-sql@postgreSQL.org, Hemant Yevale <hemant@tcsi.com>; Savyasachi Jog <jog@tcsi.com>

Michael McCarthy wrote:

> Hello David:
>
> Thanks for the quick reply; it means a lot to me.
>
> I tried "SET ksqo TO 'on'", and it works fine for my problem query; it
> allowed 570 key sets to be resolved in 2 seconds, which is a big step
> forward.
>
> I am writing a layer which makes postgres one RDBMS (of several) which can
> support a generic object persistence framework. The use of "SET ksqo TO
> 'on'" is a postgres implementation detail which applications using the
> framework will not be aware of. I am faced with the problem of whether or
> not to use "SET ksqo TO 'on'" for all queries, or find some criteria for
> turning it on and off.
>
> A quick examination of backend/optimizer/prep/prepkeyset.c shows me that
> there is some qualification of a query for keyset optimization; is there
> any reason why I should not always set ksqo on?

The qualification is strict so that it can be left on without breaking other queries.   Most MS ODBC users
use it all the time; I have yet to hear of it causing any problems.

>
>
>
> > There is a work around feature that works for queries that gererate a parse tree similar to yours.
> > ODBC tools generate these kinds of queries all the time.    Keyset queries.   To acivate the
> > feature:    SET ksqo TO 'on';    It rewrites the parse tree into a series of UNIONs.   Not optimal but
> > it works for rectangular where clauses.   (n ANDs) x  (m ORs)
> >
> > --   Here is an example using a 3 part key
> >      select ... from foo where
> >          (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 1
> >          (v1 = "?" AND v2 = "?" AND v3 ="?") OR        -- line 2
> >                  ...
> >          (v1 = "?" AND v2 = "?" AND v3 ="?") OR        --  line 9
> >          (v1 = "?" AND v2 = "?" AND v3 ="?");              --  line 10
> >      --  The question marks are replaced with the constant key values
>
> ************




^ permalink  raw  reply  [nested|flat] 7+ messages in thread

* Re: [SQL] problem with OR'ed AND queriess
  1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
  1999-12-21 22:53 ` Re: [SQL] problem with OR'ed AND queriess David C Hartwig Jr <daybee@bellatlantic.net>
  1999-12-21 23:33   ` Re: [SQL] problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
@ 1999-12-22 04:13     ` Tom Lane <tgl@sss.pgh.pa.us>
  1 sibling, 0 replies; 7+ messages in thread

From: Tom Lane @ 1999-12-22 04:13 UTC (permalink / raw)
  To: Michael McCarthy <michael@tcsi.com>; +Cc: David C Hartwig Jr <daybee@bellatlantic.net>; pgsql-sql@postgreSQL.org, Hemant Yevale <hemant@tcsi.com>; Savyasachi Jog <jog@tcsi.com>

Michael McCarthy <michael@tcsi.com> writes:
> A quick examination of backend/optimizer/prep/prepkeyset.c shows me that
> there is some qualification of a query for keyset optimization; is there
> any reason why I should not always set ksqo on?

If it seems to win more often than not for your query mix, go for it.

ksqo is a hack that I'm hoping to eliminate in the next release or
three.  But right now, it's a mighty useful hack if you do a lot of
OR-of-AND queries...

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 7+ messages in thread

* Re: [SQL] problem with OR'ed AND queriess
  1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
@ 1999-12-22 00:02 ` Tom Lane <tgl@sss.pgh.pa.us>
  2 siblings, 0 replies; 7+ messages in thread

From: Tom Lane @ 1999-12-22 00:02 UTC (permalink / raw)
  To: Michael McCarthy <michael@tcsi.com>; +Cc: pgsql-sql

Michael McCarthy <michael@tcsi.com> writes:
> I have traced the backend server in a debugger; a stack trace is attached
> below. What I see in examining the code is a recursive normalization of
> the query; postgres is running out of memory trying to convert the OR'ed
> ANDs query to conjunctive normal form (CNF).

Yes, the CNF-conversion code is pretty awful.  I have reduced its
badness somewhat in current sources, but really we need to rethink the
whole problem --- for queries that are naturally expressed as
OR-of-ANDs, forcing the condition into AND-of-ORs is a loser.

You could try folding prepqual.c from current sources (get the nightly
snapshot or use CVS) into 6.5.  I'm not sure it would merge cleanly,
but it'd beat reinventing the fixes I made.

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 7+ messages in thread

* Re: [SQL] problem with OR'ed AND queriess
  1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
@ 1999-12-22 03:51 ` Bruce Momjian <pgman@candle.pha.pa.us>
  2 siblings, 0 replies; 7+ messages in thread

From: Bruce Momjian @ 1999-12-22 03:51 UTC (permalink / raw)
  To: Michael McCarthy <michael@tcsi.com>; +Cc: pgsql-sql

> Using PQexec from libpq in postgresql 6.5.3, I submit a query of the
> following form, which has 13 OR'ed AND expressions:
> 
>     DECLARE my_cursor CURSOR FOR SELECT col1 FROM testCNF where
>     ( ( col1=0  and col2=1  ) OR ( col1=1  and col2=2  ) OR
>       ( col1=2  and col2=3  ) OR ( col1=3  and col2=4  ) OR
>       ( col1=4  and col2=5  ) OR ( col1=5  and col2=6  ) OR
>       ( col1=6  and col2=7  ) OR ( col1=7  and col2=8  ) OR
>       ( col1=8  and col2=9  ) OR ( col1=9  and col2=10 ) OR
>       ( col1=10 and col2=11 ) OR ( col1=11 and col2=12 ) OR
>       ( col1=12 and col2=13 ) )

I have this in the cvs log file, and it will appear in 7.0.  You can
check the current cvs snapshot to see how much better it is:

---------------------------------------------------------------------------

revision 1.18
date: 1999/09/07 03:47:06;  author: tgl;  state: Exp;  lines: +236 -249
Performance improvements in cnfify(): get rid of exponential
space consumption in pull_args, and avoid doing the full CNF transform on
operands of operator clauses, where it's really not particularly helpful.
This answers the TODO item about large numbers of OR clauses, at least
partially.  I was able to do a ten-thousand-OR-clause query with about
20Mb memory consumption ... it took an obscenely long time, but it worked...


-- 
  Bruce Momjian                        |  http://www.op.net/~candle
  maillist@candle.pha.pa.us            |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026



^ permalink  raw  reply  [nested|flat] 7+ messages in thread


end of thread, other threads:[~1999-12-22 04:13 UTC | newest]

Thread overview: 7+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
1999-12-21 21:05 problem with OR'ed AND queriess Michael McCarthy <michael@tcsi.com>
1999-12-21 22:53 ` David C Hartwig Jr <daybee@bellatlantic.net>
1999-12-21 23:33   ` Michael McCarthy <michael@tcsi.com>
1999-12-22 02:47     ` David C Hartwig Jr <daybee@bellatlantic.net>
1999-12-22 04:13     ` Tom Lane <tgl@sss.pgh.pa.us>
1999-12-22 00:02 ` Tom Lane <tgl@sss.pgh.pa.us>
1999-12-22 03:51 ` Bruce Momjian <pgman@candle.pha.pa.us>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox