Re: Self-referencing table question

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<from_id;

QUERY PLAN
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------
Hash IN Join (cost=4709.94..74758.01 rows=555 width=17) (actual
time=110.291..1671.767 rows=973 loops=1)
Hash Cond: ("outer".to_id = "inner".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(at)postgresql(dot)org