Performance cost of a sort-merge join

Hi, I have the given tables and query, but I'm confused why the cost
of the query is so high. I've left it running over night. By
comparison, a "select * from metarelcloud_transactionlog order by
transactionid" takes on the order of seconds/minutes (at least in
MySQL). As far as I can tell, the complex query below basically just
consists of two sorts (three if PG doesn't in fact reuse the leaf
sorts). Why the enormous estimated page IO count (cost) on the second
sort? There are roughly 30 tuples per transactionid, so the join
shouldn't produce a vastly exploded dataset. Thanks in advance.

tpcc=# \d metarelcloud_graph
Table "public.metarelcloud_graph"
Column | Type | Modifiers
----------+-----------------------+-----------
tableid1 | character varying(20) | not null
tupleid1 | integer | not null
tableid2 | character varying(20) | not null
tupleid2 | integer | not null
node1 | integer | not null
node2 | integer | not null
weight | integer | not null
Indexes:
"metarelcloud_graph_pkey" PRIMARY KEY, btree (tableid1, tupleid1,
tableid2, tupleid2)

tpcc=# \d metarelcloud_transactionlog
Table
"public.metarelcloud_transactionlog"
Column | Type |
Modifiers
---------------------+-----------------------+--------------------------------------------------------------------------
id | integer | not null default
nextval('metarelcloud_transactionlog_id_seq'::regclass)
transactionid | integer | not null
queryid | smallint | not null
tableid | character varying(30) | not null
tupleid | integer | not null
querytype | character varying | not null
graphpartition | smallint |
replicatedpartition | smallint |
justifiedpartition | smallint |
hashpartition | smallint |
nodeid | integer |
manualpartition | smallint |
Indexes:
"metarelcloud_transactionlog_pkey" PRIMARY KEY, btree (id)
Check constraints:
"metarelcloud_transactionlog_graphpartition_check" CHECK
(graphpartition >= 0)
"metarelcloud_transactionlog_hashpartition_check" CHECK (hashpartition >= 0)
"metarelcloud_transactionlog_justifiedpartition_check" CHECK
(justifiedpartition >= 0)
"metarelcloud_transactionlog_manualpartition_check" CHECK
(manualpartition >= 0)
"metarelcloud_transactionlog_querytype_check" CHECK
(querytype::text = ANY (ARRAY['select'::character varying,
'insert'::character varying, 'delete'::character varying,
'update'::character varying]::text[]))
"metarelcloud_transactionlog_replicatedpartition_check" CHECK
(replicatedpartition >= 0)

tpcc=# analyze metarelcloud_transactionlog;
ANALYZE

tpcc=# explain insert into metarelcloud_graph (node1, node2, tableid1,
tupleid1, tableid2, tupleid2, weight)
select 0, 0, a.tableid, a.tupleid, b.tableid, b.tupleid, count(*)
from metarelcloud_transactionlog a, metarelcloud_transactionlog b
where a.transactionid = b.transactionid
and (a.tableid, a.tupleid) < (b.tableid, b.tupleid)
group by a.tableid, a.tupleid, b.tableid, b.tupleid;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Subquery Scan "*SELECT*" (cost=968062444010.30..1088362355018.20
rows=2673331355731 width=180)
-> GroupAggregate (cost=968062444010.30..1041579056292.91
rows=2673331355731 width=26)
-> Sort (cost=968062444010.30..974745772399.63
rows=2673331355731 width=26)
Sort Key: a.tableid, a.tupleid, b.tableid, b.tupleid
-> Merge Join (cost=16817274.69..160416950669.79
rows=2673331355731 width=26)
Merge Cond: (a.transactionid = b.transactionid)
Join Filter: (ROW((a.tableid)::text, a.tupleid) <
ROW((b.tableid)::text, b.tupleid))
-> Sort (cost=8408637.34..8534662.95
rows=50410244 width=17)
Sort Key: a.transactionid
-> Seq Scan on metarelcloud_transactionlog
a (cost=0.00..925543.44 rows=50410244 width=17)
-> Materialize (cost=8408637.34..9038765.39
rows=50410244 width=17)
-> Sort (cost=8408637.34..8534662.95
rows=50410244 width=17)
Sort Key: b.transactionid
-> Seq Scan on
metarelcloud_transactionlog b (cost=0.00..925543.44 rows=50410244
width=17)
(14 rows)

--
Yang Zhang
http://www.mit.edu/~y_z/