Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id D79D69FB425 for ; Sat, 14 Apr 2007 14:20:08 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 20424-05 for ; Sat, 14 Apr 2007 14:20:04 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by postgresql.org (Postfix) with ESMTP id D9F939FB38A for ; Sat, 14 Apr 2007 14:19:35 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.6/8.13.6) with ESMTP id l3EHJXH6005224; Sat, 14 Apr 2007 13:19:33 -0400 (EDT) To: Alvaro Herrera cc: pgsql-hackers@postgresql.org, PostgreSQL Performance , Steve Subject: Re: [HACKERS] choose_bitmap_and again (was Re: Strangely Variable Query Performance) In-reply-to: <20070413232409.GI27255@alvh.no-ip.org> References: <10117.1176420763@sss.pgh.pa.us> <10355.1176422445@sss.pgh.pa.us> <10503.1176423606@sss.pgh.pa.us> <12360.1176436194@sss.pgh.pa.us> <26399.1176504501@sss.pgh.pa.us> <20070413232409.GI27255@alvh.no-ip.org> Comments: In-reply-to Alvaro Herrera message dated "Fri, 13 Apr 2007 19:24:09 -0400" Date: Sat, 14 Apr 2007 13:19:33 -0400 Message-ID: <5223.1176571173@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200704/308 X-Sequence-Number: 24185 Alvaro Herrera writes: > I think the concern about condition redundancy should be attacked > separately. How about just comparing whether they have common prefixes > of conditions? I admit I don't understand what would happen with > indexes defined like (lower(A), B, C) versus (A, B) for example. I understand that issue a bit better than I did when I wrote the comment (so I suppose I better rewrite it). The $64 reason for rejecting AND-combinations of indexes that are using some of the same WHERE-conditions is that if we don't, we effectively double-count the selectivity of those conditions, causing us to prefer useless AND-combinations. An example is "WHERE A > 42 AND B < 100" where we have an index on A and one on (A,B). The selectivity calculation will blindly assume that the selectivities of the two indexes are independent and thus prefer to BitmapAnd them, when obviously there is no point in using both. Ideally we should improve the selectivity calculation to not get fooled like this, but that seems hard and probably slow. So for the moment we have the heuristic that no WHERE-clause should be used twice in any AND-combination. Given that we are using that heuristic, it becomes important that we visit the indexes in the "right order" --- as the code stands, in the (A) vs (A,B) case it will consider only the first index it arrives at in the selectivity sort order, because the second will be rejected on the basis of re-use of the WHERE A > 42 condition. Sorting by selectivity tends to ensure that we pick the index that can make use of as many WHERE-clauses as possible. The idea of considering each index alone fixes the order dependency for cases where a single index is the best answer, but it doesn't help much for cases where you really do want a BitmapAnd, only not one using the index with the individually best selectivity. We really need a heuristic here --- exhaustive search will be impractical in cases where there are many indexes, because you'd be looking at 2^N combinations. (In Steve's example there are actually 38 relevant indexes, which is bad database design if you ask me, but in any case we cannot afford to search through 2^38 possibilities.) But the one we're using now is too fragile. Maybe we should use a cutoff similar to the GEQO one: do exhaustive search if there are less than N relevant indexes, for some N. But that's not going to help Steve; we still need a smarter heuristic for what to look for above the cutoff. regards, tom lane