archiveopteryx=# EXPLAIN ANALYZE WITH RECURSIVE t (mailbox, uid, date, subject, sender, has_attachments, parent_uid, idx, depth) AS (
  SELECT mailbox, uid, date, subject, sender, has_attachments, parent_uid, uid::text, 1
  FROM arc_messages
  WHERE parent_uid IS NULL AND mailbox = 17 AND date >= '2007-11-01' AND date < '2007-12-01'
  UNION ALL
  SELECT a.mailbox, a.uid, a.date, a.subject, a.sender, a.has_attachments, a.parent_uid, t.idx || '.' || a.uid::text, t.depth + 1
  FROM t JOIN arc_messages a USING (mailbox)
  WHERE t.uid = a.parent_uid
) SELECT * FROM t ORDER BY idx ;
                                                                                               QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=92761.67..92769.91 rows=1647 width=121) (actual time=4183.736..4185.762 rows=1428 loops=1)
   Sort Key: t.idx
   Sort Method:  quicksort  Memory: 366kB
   CTE t
     ->  Recursive Union  (cost=0.00..92579.09 rows=1647 width=130) (actual time=0.030..4173.724 rows=1428 loops=1)
           ->  Index Scan using arc_messages_mailbox_parent_id_date_key on arc_messages  (cost=0.00..486.42 rows=567 width=94) (actual time=0.025..1.432 rows=482 loops=1)
                 Index Cond: ((mailbox = 17) AND (parent_uid IS NULL) AND (date >= '2007-11-01 00:00:00+01'::timestamp with time zone) AND (date < '2007-12-01 00:00:00+01'::timestamp with time zone))
           ->  Merge Join  (cost=729.68..9208.61 rows=108 width=130) (actual time=262.120..277.819 rows=63 loops=15)
                 Merge Cond: ((a.mailbox = t.mailbox) AND (a.parent_uid = t.uid))
                 ->  Index Scan using arc_messages_mailbox_parent_id_key on arc_messages a  (cost=0.00..6452.25 rows=193871 width=94) (actual time=0.018..147.782 rows=85101 loops=15)
                 ->  Sort  (cost=729.68..758.03 rows=5670 width=44) (actual time=0.403..0.559 rows=109 loops=15)
                       Sort Key: t.mailbox, t.uid
                       Sort Method:  quicksort  Memory: 25kB
                       ->  WorkTable Scan on t  (cost=0.00..22.68 rows=5670 width=44) (actual time=0.003..0.145 rows=95 loops=15)
   ->  CTE Scan on t  (cost=0.00..6.59 rows=1647 width=121) (actual time=0.035..4179.686 rows=1428 loops=1)
 Total runtime: 4188.187 ms
(16 rows)