X-Original-To: pgsql-sql-postgresql.org@postgresql.org Received: from localhost (mx1.hub.org [200.46.208.251]) by postgresql.org (Postfix) with ESMTP id DC65B9FA491 for ; Tue, 15 Aug 2006 18:59:35 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.208.251]) (amavisd-new, port 10024) with ESMTP id 88775-10 for ; Tue, 15 Aug 2006 18:59:21 -0300 (ADT) X-Greylist: delayed 20:52:28.06574 by SQLgrey- Received: from pow.actarg.com (host25.actarg.com [209.180.91.25]) by postgresql.org (Postfix) with ESMTP id 1A7609FA38B for ; Tue, 15 Aug 2006 18:59:21 -0300 (ADT) Received: from [192.168.2.40] (pal.actarg.com [192.168.2.40]) (authenticated bits=0) by pow.actarg.com (8.13.1/8.13.1) with ESMTP id k7FLwrm8031829 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Tue, 15 Aug 2006 15:59:15 -0600 Message-ID: <44E2438F.8000105@actarg.com> Date: Tue, 15 Aug 2006 15:58:39 -0600 From: Kyle Bateman User-Agent: Mozilla Thunderbird 1.0.8-1.1.fc4 (X11/20060501) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tom Lane CC: pgsql-sql@postgresql.org, Florian Weimer Subject: Re: Using bitmap index scans-more efficient References: <44DF6582.4000806@actarg.com> <82mza77rch.fsf@mid.bfk.de> <44E11E1A.8020507@actarg.com> <27367.1155606817@sss.pgh.pa.us> In-Reply-To: <27367.1155606817@sss.pgh.pa.us> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: ClamAV 0.88/1656/Sun Aug 13 21:24:35 2006 on pow.actarg.com X-Virus-Status: Clean X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests= X-Spam-Level: X-Archive-Number: 200608/116 X-Sequence-Number: 26074 Tom Lane wrote: >Kyle Bateman writes: > > >>But I'm assuming that using an interval-encoded project tree, I would >>have to do something like the following to get a progency group: >> >> > > > >>select * from ledger l, proj p where p.proj_id = l.proj and p.left > >>1234 and p.right < 2345; >> >> > >btree has no idea about the constraint (that I imagine exists) that left ><= right. If you're just doing a simple index on (left, right) then the >above query requires scanning all index entries with left > 1234. It >would probably help to say > >select * from ledger l, proj p where p.proj_id = l.proj and > p.left > 1234 and p.left < 2345 and p.right < 2345; > >so that you can constrain the range of "left" values scanned. > > Thanks for the replies, Tom and Florian. My problem is not that it is difficult (or costly) to determine the progeny of a given project. I can determine this in about 90 msec regardless of whether I use an adjacency model, interval-encoding, or materialized path (current implementation). The problem is, when I try to extract the ledger entries belonging to that progeny from a set of a million records, it seems to need to process all million records rather than being able to index right into the ones I want. I'm not very good at reading explain output, but I tried to set up the query Tom suggests by creating an interval-encoded project table (proj_int) and then joining it to my ledger like so: select l.* from ledger l, proj_int i where l.proj = i.proj_id and i.lft >= 5283 and i.lft < 5300 and i.rgt <= 5300; On my mini-test-ledger of 100,000 entries, this takes the longest time (5 seconds) with the following explain output: Hash Join (cost=19018.46..23411.52 rows=14 width=85) Hash Cond: ("outer".proj = "inner".proj_id) -> Nested Loop Left Join (cost=18994.38..23378.41 rows=1700 width=85) -> Hash Join (cost=18990.84..23340.87 rows=1700 width=81) Hash Cond: ("outer".vendid = "inner".org_id) -> Merge Join (cost=18935.35..23255.64 rows=1700 width=63) Merge Cond: (("outer".vendid = "inner".vendid) AND (("outer".invnum)::text = "inner"."?column10?")) -> Index Scan using apinv_hdr_pkey on apinv_hdr h (cost=0.00..3148.16 rows=51016 width=21) -> Sort (cost=18935.35..19235.45 rows=120041 width=55) Sort Key: i.vendid, (i.invnum)::text -> Seq Scan on apinv_items i (cost=0.00..4152.99 rows=120041 width=55) Filter: ((status = 'en'::bpchar) OR (status = 'cl'::bpchar) OR (status = 'pd'::bpchar)) -> Hash (cost=50.99..50.99 rows=1799 width=26) -> Seq Scan on vend_org v (cost=0.00..50.99 rows=1799 width=26) -> Materialize (cost=3.54..3.55 rows=1 width=4) -> Seq Scan on acct a (cost=0.00..3.54 rows=1 width=4) Filter: ((code)::text = 'ap'::text) -> Hash (cost=24.06..24.06 rows=10 width=4) -> Bitmap Heap Scan on proj_int i (cost=2.26..24.06 rows=10 width=4) Recheck Cond: ((lft >= 5283) AND (lft < 5300) AND (rgt <= 5300)) -> Bitmap Index Scan on i_proj_int_lft_rgt (cost=0.00..2.26 rows=10 width=0) Index Cond: ((lft >= 5283) AND (lft < 5300) AND (rgt <= 5300)) That is roughly equivalent to my materialized path method: select l.* from ledger l where l.proj in (select proj_id from proj_v where 4737 = any(ppath)); And is quite slow compared to 150 msec when enumerating the progeny projects like so: select l.* from ledger l where l.proj in (4737,4789,4892,4893,4894,4895,4933,4934,4935); Nested Loop Left Join (cost=19.73..4164.10 rows=7 width=85) -> Nested Loop (cost=19.73..4139.08 rows=7 width=81) -> Nested Loop (cost=19.73..4100.07 rows=7 width=63) -> Bitmap Heap Scan on apinv_items i (cost=19.73..1185.71 rows=487 width=55) Recheck Cond: ((proj = 4737) OR (proj = 4789) OR (proj = 4892) OR (proj = 4893) OR (proj = 4894) OR (proj = 4895) OR (proj = 4933) OR (proj = 4934) OR (proj = 4935)) Filter: ((status = 'en'::bpchar) OR (status = 'cl'::bpchar) OR (status = 'pd'::bpchar)) -> BitmapOr (cost=19.73..19.73 rows=495 width=0) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4737) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4789) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4892) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4893) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4894) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4895) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4933) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4934) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4935) -> Index Scan using apinv_hdr_pkey on apinv_hdr h (cost=0.00..5.97 rows=1 width=21) Index Cond: (("outer".vendid = h.vendid) AND (("outer".invnum)::text = (h.invnum)::text)) -> Index Scan using vend_org_pkey on vend_org v (cost=0.00..5.56 rows=1 width=26) Index Cond: (v.org_id = "outer".vendid) Nested Loop Left Join (cost=19.73..4164.10 rows=7 width=85) -> Nested Loop (cost=19.73..4139.08 rows=7 width=81) -> Nested Loop (cost=19.73..4100.07 rows=7 width=63) -> Bitmap Heap Scan on apinv_items i (cost=19.73..1185.71 rows=487 width=55) Recheck Cond: ((proj = 4737) OR (proj = 4789) OR (proj = 4892) OR (proj = 4893) OR (proj = 4894) OR (proj = 4895) OR (proj = 4933) OR (proj = 4934) OR (proj = 4935)) Filter: ((status = 'en'::bpchar) OR (status = 'cl'::bpchar) OR (status = 'pd'::bpchar)) -> BitmapOr (cost=19.73..19.73 rows=495 width=0) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4737) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4789) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4892) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4893) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4894) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4895) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4933) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4934) -> Bitmap Index Scan on i_apinv_items_proj (cost=0.00..2.19 rows=55 width=0) Index Cond: (proj = 4935) -> Index Scan using apinv_hdr_pkey on apinv_hdr h (cost=0.00..5.97 rows=1 width=21) Index Cond: (("outer".vendid = h.vendid) AND (("outer".invnum)::text = (h.invnum)::text)) -> Index Scan using vend_org_pkey on vend_org v (cost=0.00..5.56 rows=1 width=26) Index Cond: (v.org_id = "outer".vendid) -> Seq Scan on acct a (cost=0.00..3.54 rows=1 width=4) Filter: ((code)::text = 'ap'::text) -> Seq Scan on acct a (cost=0.00..3.54 rows=1 width=4) Filter: ((code)::text = 'ap'::text) I'm still stumped...