Message-ID: <4787A1FB.2050808@ikv.de>
Date: Fri, 11 Jan 2008 18:06:03 +0100
From: =?ISO-8859-1?Q?J=F6rg_Kiegeland?= <kiegeland@ikv.de>
User-Agent: Thunderbird 1.5.0.10 (Windows/20070221)
MIME-Version: 1.0
To: pgsql-performance@postgresql.org
Subject: Evaluating boolean formula: slow performance 
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

I have the following problem:

In my table T, there are a fixed number of boolean columns, C1, .., Cn.

Now, a common query is to search in this table for tuples fullfilling an 
arbitrary boolean condition (however only using AND and OR),  e.g.

SELECT * FROM T WHERE (C1 OR C2) AND (C3 OR C4 AND C5) OR C6

For every boolean column, I created an index, e.g.

CREATE INDEX columnIndexForC2 ON DIM (C2);

Now I did performance tests and got response times for such a query 
which are worser than linear response time..

However I also realized that with boolean queries which use only OR or 
use only AND, the response time is very fast, i.e. it seems to be 
constant, regardless of how many tuples I add to the table.

So my question is: How can I get an acceptable response time for 
arbitrary boolean terms?

Thanks