From: Sean Davis <sdavis2@mail.nih.gov>
To: PostgreSQL SQL <pgsql-sql@postgresql.org>
Subject: Self-referencing table question
Date: Tue, 22 Mar 2005 14:33:12 -0500
Message-ID: <0af8c6d3baaf3d4a6d918df294019507@mail.nih.gov> (raw)
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,27
,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,27
,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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: sdavis2@mail.nih.gov
Subject: Re: Self-referencing table question
In-Reply-To: <0af8c6d3baaf3d4a6d918df294019507@mail.nih.gov>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox