Comparing two slices within one table efficiently

From: Ken Simpson <ksimpson(at)mailchannels(dot)com>
To: pgsql-sql(at)postgresql(dot)org
Subject: Comparing two slices within one table efficiently
Date: 2007-08-13 17:58:16
Message-ID: 1694202581-1187027999-cardhu_decombobulator_blackberry.rim.net-401169594-@bxe119.bisx.prod.on.blackberry
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-sql

I have a table with the following simplified form:

create table t (
run_id integer,
domain_id integer,
mta_id integer,
attribute1 integer,
attribute2 integer,
unique(run_id, domain_id, mta_id)
);

The table has about 1 million rows with run_id=1, another 1 million rows with run_id=2, and so on.

I need to efficiently query the differences between "runs" - i.e. For each (domain_id, mta_id) tuple in run 1, is there a coresponding tuple in run 2 where either attribute1 or attribute2 have changed?

The only way I have been able to think of doing this so far is an o(n^2) search, which even with indexes takes a long time. e.g.

select * from t t1 where exists (select 1 from t t2 where t2.mta_id=t1.mta_id and t2.domain_id=t1.domain_id and (t2.attribute1 != t1.attribute1 or t2.attribute2 != t1.attribute2)

This query takes millenia...

Any help would be greatly appreciated. I hope I am naively missing some obvious alternative strategy, since this sort of operation must be common in databases.

Thanks,
Ken

--
Ken Simpson, CEO
MailChannels Corporation
Reliable Email Delivery (tm)
http://www.mailchannels.com

Responses

Browse pgsql-sql by date

  From Date Subject
Next Message chester c young 2007-08-13 18:45:41 Re: Comparing two slices within one table efficiently
Previous Message Tom Lane 2007-08-13 13:37:20 Re: [NOVICE] Install two different versions of postgres which should run in parallel