let's assume we have a simple table:
Table "public.test" Column | Type | Modifiers --------+---------+----------- a | integer | not null b | integer | not null Indexes: "test_pkey" PRIMARY KEY, btree (a, b) "q" UNIQUE, btree (b, a)
now, let's insert some rows to it:
# INSERT INTO test SELECT * FROM generate_series(1,100) AS a, generate_series(1,100) AS b^J; INSERT 0 10000
remove rows with a = b:
# DELETE FROM test WHERE a = b; DELETE 100
and prepare test-case by randomly removing some rows:
# DELETE FROM test WHERE random() < 0.002; DELETE 17
the question is – find all pairs of (a,b) where there is no row (a',b') where (a'=b and b'=a).
in other words – every row (a,b) should be paired. rows with a = 2 and b = 3, is paired by row with a = 3 and b = 2.
how to find incomplete pairs?
the basic approach would be to do something like:
SELECT * FROM test t WHERE NOT EXISTS (SELECT * FROM test t2 WHERE (t2.a, t2.b) = (t.b, t.a))
no. unfortunately no.
execution plan for this query consisted of 1 seq scan of test table, and nested index scan for every row of it.
does it look bad? with 10k rows, it is not really bad – after all, 1 seq scan over 10k rows, plus 10k index scans – it's doable.
but what if you have 70 million rows in the table?
in this situation it goes simply to 70 million index scans. quick test showed that (out of 10 tries) i got:
- minimal time: 0.047ms
- maximal time: 215ms
- average time: around 0.9-1ms.
full seq scan of the table took about 40 seconds. assuming best situation (0.047ms per index scan), it adds up to nearly 1 hour. with average time of 1ms, total time escalates to … 49 days!
oops. now, i don't have that much time for the task 🙂
perhaps left outer join approach?
SELECT t1.* FROM test t1 LEFT OUTER JOIN test t2 ON (t1.a, t1.b) = (t2.b, t2.a) WHERE t2.a IS NULL
this becomes 2 sequential scans joined with hash join (with small 10k rows table it becomes merge join of 2 index (but full table) scans.
better, but can it be done faster?
SELECT least(a,b), greatest(a,b), COUNT(*) FROM test GROUP BY least(a,b), greatest(a,b) HAVING COUNT(*) = 1;
this query does only 1 table scan, with hash aggregate. time is unbeatable 🙂
how does it work?
basically i thought about finding a way to tell postgresql that pair (12,50) and (50,12) are “the same", so i could use grouping.
there is a simple way to do it – using least() and greatest() functions. least() always returns smaller, and greatest() bigger number.
so, for both (12,50) and (50,12), output of (least(), greatest) is (12,50)!
now, that i have a way to “group it", i can use standard “having" trick to filter only the groups that contain only 1 row.
effect – total time of execution – 5minutes 🙂 for 70 million rows.
and how to add missing pairs?
first, let's copy the group info to temp table:
CREATE temp TABLE depesz_temp AS SELECT least(a,b) AS x, greatest(a,b) AS y, COUNT(*) FROM test GROUP BY least(a,b), greatest(a,b) HAVING COUNT(*) = 1
now – we need to find what row exactly is there, and insert it's pair.
to make the story short – full insert looks like this:
INSERT INTO test (a,b) SELECT (CASE WHEN t.a = q.x THEN q.y ELSE q.x END), (CASE WHEN t.b = q.x THEN q.y ELSE q.x END) FROM test t, depesz_temp q WHERE (t.a, t.b) = (q.x, q.y) OR (t.b, t.a) = (q.x, q.y)
you might be tempted to reuse least/greatest trick in the where condition in above insert/select, but if you'd do – indexes on (a,b) and (b,a) wouldn't be used, so it would become really slow 🙂