X-Original-To: pgsql-sql-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 8952456892 for ; Tue, 22 Mar 2005 20:41:08 +0000 (GMT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 69008-10 for ; Tue, 22 Mar 2005 20:40:57 +0000 (GMT) Received: from mx5.net.nih.gov (mx5.net.nih.gov [165.112.130.36]) by svr1.postgresql.org (Postfix) with ESMTP id 24F72568D1 for ; Tue, 22 Mar 2005 20:40:56 +0000 (GMT) Received: from mx5.net.nih.gov (localhost [127.0.0.1]) by mx5.net.nih.gov (8.12.10/8.11.6) with ESMTP id j2MKevas026505 for ; Tue, 22 Mar 2005 15:40:57 -0500 Received: from [128.231.145.14] (holmes.nhgri.nih.gov [128.231.145.14]) by mx5.net.nih.gov (8.12.10/8.11.6) with ESMTP id j2MKevKd026502; Tue, 22 Mar 2005 15:40:57 -0500 In-Reply-To: <0af8c6d3baaf3d4a6d918df294019507@mail.nih.gov> References: <0af8c6d3baaf3d4a6d918df294019507@mail.nih.gov> Mime-Version: 1.0 (Apple Message framework v619.2) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <7e154914b76fb1a7c55912b621400860@mail.nih.gov> Content-Transfer-Encoding: 7bit Cc: PostgreSQL SQL From: Sean Davis Subject: Re: Self-referencing table question Date: Tue, 22 Mar 2005 15:40:57 -0500 To: Sean Davis X-Mailer: Apple Mail (2.619.2) X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.006 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200503/303 X-Sequence-Number: 20782 I answer my own question, if only for my own records. The following query is about 5-6 times faster than the original. Of course, if anyone else has other ideas, I'd be happy to hear them. Sean explain analyze select from_id,to_id,val from exprsdb.correlation where from_id in (select to_id from exprsdb.correlation where from_id=2424 order by val desc limit 100) and to_id in (select to_id from exprsdb.correlation where from_id=2424 order by val desc limit 100) and val>0.6 and to_id Nested Loop (cost=2354.97..72181.72 rows=43154 width=17) (actual time=54.036..1612.746 rows=1482 loops=1) -> HashAggregate (cost=2354.97..2354.97 rows=100 width=4) (actual time=53.656..54.062 rows=100 loops=1) -> Subquery Scan "IN_subquery" (cost=2353.47..2354.72 rows=100 width=4) (actual time=53.473..53.595 rows=100 loops=1) -> Limit (cost=2353.47..2353.72 rows=100 width=13) (actual time=53.469..53.507 rows=100 loops=1) -> Sort (cost=2353.47..2415.03 rows=24624 width=13) (actual time=53.467..53.481 rows=100 loops=1) Sort Key: val -> Index Scan using correlation_from_id_idx on correlation (cost=0.00..557.42 rows=24624 width=13) (actual time=0.199..17.717 rows=7788 loops=1) Index Cond: (from_id = 2424) -> Index Scan using correlation_from_id_idx on correlation (cost=0.00..692.87 rows=432 width=17) (actual time=2.765..15.560 rows=15 loops=100) Index Cond: (correlation.from_id = "outer".to_id) Filter: ((val > 0.6) AND (to_id < from_id)) -> Hash (cost=2354.72..2354.72 rows=100 width=4) (actual time=56.239..56.239 rows=0 loops=1) -> Subquery Scan "IN_subquery" (cost=2353.47..2354.72 rows=100 width=4) (actual time=56.004..56.121 rows=100 loops=1) -> Limit (cost=2353.47..2353.72 rows=100 width=13) (actual time=56.001..56.038 rows=100 loops=1) -> Sort (cost=2353.47..2415.03 rows=24624 width=13) (actual time=55.999..56.012 rows=100 loops=1) Sort Key: val -> Index Scan using correlation_from_id_idx on correlation (cost=0.00..557.42 rows=24624 width=13) (actual time=0.517..20.307 rows=7788 loops=1) Index Cond: (from_id = 2424) Total runtime: 1676.966 ms On Mar 22, 2005, at 2:33 PM, Sean Davis wrote: > I have a table that looks like: > > Column | Type | Modifiers | Description > ---------+--------------+-----------+------------- > from_id | integer | not null | > to_id | integer | not null | > val | numeric(4,3) | | > Indexes: > "correlation_pkey" PRIMARY KEY, btree (from_id, to_id) > "correlation_from_id_idx" btree (from_id) > "correlation_to_id_idx" btree (to_id) > "correlation_val_idx" btree (val) > Has OIDs: yes > > The table describes a pairwise correlation matrix between about 7700 > vectors (so the table has n^2= 60652944 rows, to be exact). I am > trying to choose the top 100 correlated vectors with a seed vector; > this is easily: > > select to_id from correlation where from_id=623 order by val desc > limit 100; > > Then, I want to take those 100 values and find all from_id,to_id > tuples where val>0.5 (to construct a graph where all "ids" are nodes > and are connected to each other when their correlation is >0.5). I > can do this like: > > explain analyze select > from_id,to_id,val > from exprsdb.correlation > where from_id in > (1,2,3,4,5,6,7,8,10,9,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,2 > 7,28,29,30) > and to_id in > (1,2,3,4,5,6,7,8,10,9,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,2 > 7,28,29,30) > and from_id>to_id > and val>0.5; > > However, this does not scale well AT ALL. The actual (very messy) > explain analyze output is below. The thing I notice is that the index > on to_id is not used. Also, the primary key index on (from_id, to_id > is not used, it seems. Finally, with only 30 values, this already > takes 2.6 seconds and I am proposing to do this on 100-200 values. > Any hints on how better to accomplish this set of tasks? > > Index Scan using correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx, > correlation_from_id_idx, correlation_from_id_idx on correlation > (cost=0.00..129377.49 rows=62 width=17) (actual time=340.563..2603.967 > rows=19 loops=1) > Index Cond: ((from_id = 1) OR (from_id = 2) OR (from_id = 3) OR > (from_id = 4) OR (from_id = 5) OR (from_id = 6) OR (from_id = 7) OR > (from_id = 8) OR (from_id = 10) OR (from_id = 9) OR (from_id = 11) OR > (from_id = 12) OR (from_id = 13) OR (from_id = 14) OR (from_id = 15) > OR (from_id = 16) OR (from_id = 17) OR (from_id = 18) OR (from_id = > 19) OR (from_id = 20) OR (from_id = 21) OR (from_id = 22) OR (from_id > = 23) OR (from_id = 24) OR (from_id = 25) OR (from_id = 26) OR > (from_id = 27) OR (from_id = 28) OR (from_id = 29) OR (from_id = 30)) > Filter: (((to_id = 1) OR (to_id = 2) OR (to_id = 3) OR (to_id = 4) > OR (to_id = 5) OR (to_id = 6) OR (to_id = 7) OR (to_id = 8) OR (to_id > = 10) OR (to_id = 9) OR (to_id = 11) OR (to_id = 12) OR (to_id = 13) > OR (to_id = 14) OR (to_id = 15) OR (to_id = 16) OR (to_id = 17) OR > (to_id = 18) OR (to_id = 19) OR (to_id = 20) OR (to_id = 21) OR (to_id > = 22) OR (to_id = 23) OR (to_id = 24) OR (to_id = 25) OR (to_id = 26) > OR (to_id = 27) OR (to_id = 28) OR (to_id = 29) OR (to_id = 30)) AND > (from_id > to_id) AND (val > 0.5)) > Total runtime: 2604.383 ms > > Thanks, > Sean > > > ---------------------------(end of > broadcast)--------------------------- > TIP 1: subscribe and unsubscribe commands go to > majordomo@postgresql.org