Trying to eliminate union and sort

Hi All,

(basic info)
PostgreSQL 9.2.4
64 bit Linux host
4GB shared_buffers with 14GB system memory, dedicated database VM
10MB work_mem

I have a query that takes over 6 minutes to complete, and it's due
mainly to the two sorting operations being done on this query. The data
it is returning itself is quite large, and with the two sorting
operations it does (one because of the union, one because of the order
by), it ends up using about *2.1GB* of temporary file space (and there
is no way I can increase work_mem to hold this).

--[Query]----------------------------
SELECT
t.id,
t.mycolumn1,
(SELECT table3.otherid FROM table3 WHERE table3.id = t.typeid),
(SELECT table3.otherid FROM table3 WHERE table3.id = t2.third_id),
t.mycolumn2 AS mycolumn2

FROM table1 t

LEFT OUTER JOIN table2 t2 ON t2.real_id = t.id

WHERE t.external_id IN ('6544', '2234', '2', '4536')

UNION

SELECT
t.id,
t.mycolumn1,
(SELECT table3.otherid FROM table3 WHERE table3.id = t.typeid),
(SELECT table3.otherid FROM table3 WHERE table3.id = t2.third_id),
t.mycolumn2 AS mycolumn2

FROM table1 t

LEFT OUTER JOIN table2 t2 ON t2.real_id = t.backup_id

WHERE t.external_id IN ('6544', '2234', '2', '4536')

ORDER BY t.mycolumn2, t.id;

--[Explain Analyze (sorry for the anonymizing)]----------------------------
Sort (cost=133824460.450..133843965.150 rows=7801882 width=56) (actual
time=849405.656..894724.453 rows=9955729 loops=1)
Sort Key: romeo.three, romeo.quebec_seven
*Sort Method: external merge Disk: 942856kB*
-> Unique (cost=132585723.530..132702751.760 rows=7801882 width=56)
(actual time=535267.196..668982.694 rows=9955729 loops=1)
-> Sort (cost=132585723.530..132605228.240 rows=7801882
width=56) (actual time=535267.194..649304.631 rows=10792011 loops=1)
Sort Key: romeo.quebec_seven, romeo.golf, ((delta_four
3)), ((delta_four 4)), romeo.three
*Sort Method: external merge Disk: 1008216kB*
-> Append (cost=0.000..131464014.850 rows=7801882
width=56) (actual time=0.798..291477.595 rows=10792011 loops=1)
-> Merge Left Join (cost=0.000..46340412.140
rows=2748445 width=56) (actual time=0.797..70748.213 rows=3690431 loops=1)
Merge Cond: (romeo.quebec_seven =
alpha_bravo.six_kilo)
-> Index Scan using juliet on zulu romeo
(cost=0.000..163561.710 rows=2748445 width=52) (actual
time=0.019..11056.883 rows=3653472 loops=1)
Filter: (delta_uniform = ANY
('two'::integer[]))
-> Index Only Scan using sierra on
quebec_juliet alpha_bravo (cost=0.000..86001.860 rows=2191314 width=8)
(actual time=0.047..3996.543 rows=2191314 loops=1)
Heap Fetches: 2191314
SubPlan
-> Index Scan using oscar on six_delta
(cost=0.000..8.380 rows=1 width=23) (actual time=0.009..0.009 rows=1
loops=3690431)
Index Cond: (quebec_seven = romeo.lima)
SubPlan
-> Index Scan using oscar on six_delta
(cost=0.000..8.380 rows=1 width=23) (actual time=0.001..0.001 rows=0
loops=3690431)
Index Cond: (quebec_seven =
alpha_bravo.delta_november)
-> Merge Right Join (cost=0.000..85045583.890
rows=5053437 width=56) (actual time=0.843..213450.477 rows=7101580 loops=1)
Merge Cond: (alpha_bravo.six_kilo =
romeo.india)
-> Index Only Scan using sierra on
quebec_juliet alpha_bravo (cost=0.000..86001.860 rows=2191314 width=8)
(actual time=0.666..6165.870 rows=2191314 loops=1)
Heap Fetches: 2191314
-> Materialize (cost=0.000..193106.580
rows=2748445 width=56) (actual time=0.134..25852.353 rows=7101580 loops=1)
-> Index Scan using alpha_seven on
zulu romeo (cost=0.000..186235.470 rows=2748445 width=56) (actual
time=0.108..18439.857 rows=3653472 loops=1)
Filter: (delta_uniform = ANY
('two'::integer[]))
SubPlan
-> Index Scan using oscar on six_delta
(cost=0.000..8.380 rows=1 width=23) (actual time=0.009..0.010 rows=1
loops=7101580)
Index Cond: (quebec_seven = romeo.lima)
SubPlan
-> Index Scan using oscar on six_delta
(cost=0.000..8.380 rows=1 width=23) (actual time=0.007..0.008 rows=1
loops=7101580)
Index Cond: (quebec_seven =
alpha_bravo.delta_november)
--[end]----------------------------

*My attempts:*
1. I tried to get an index set up on table1 that orders t.mycolumn2 and
t.id so that the sorting operation might be skipped, however when table1
is accessed it is using an index that's on t.id due to the left join to
table2, then filters out the "WHERE t.external_id IN ('6544', '2234',
'2', '4536')", so at this point the data I've accessed came from
something other than my 'order by' and must be reordered at the end.

NOTE: The where clause (WHERE t.external_id IN ('6544', '2234', '2',
'4536')) alone doesn't use an index at all, but results in a sequential
scan (result set is about 60% of the total rows I believe).

I've been unable to get the query planner to pick an index on
(t.mycolumn2, t.id).

2. I reworked the entire query to eliminate the subqueries living all in
joins. Overall the query LOOKS more efficient, but takes about the same
amount of time as the main one because most of the execution time is
done in the two sorting operations.

3. I'm trying to eliminate the union, however I have two problems.
A) I can't figure out how to have an 'or' clause in a single join that
would fetch all the correct rows. If I just do:
LEFT OUTER JOIN table2 t2 ON (t2.real_id = t.id OR t2.real_id =
t.backup_id), I end up with many less rows than the original query. B.

I believe the issue with this is a row could have one of three
possibilities:
* part of the first query but not the second -> results in 1 row after
the union
* part of the second query but not the first -> results in 1 row after
the union
* part of the first query and the second -> results in 2 rows after the
union (see 'B)' for why)

B) the third and fourth column in the SELECT will need to be different
depending on what column the row is joined on in the LEFT OUTER JOIN to
table2, so I may need some expensive case when logic to filter what is
put there based on whether that row came from the first join clause, or
the second.

Any thoughts or things I'm looking over? Any help would be greatly
appreciated. My first goal is to get rid of the sort by the UNION, if
possible. The second would be to eliminate the last sort by the ORDER
BY, but I'm not sure if it will be easily doable.

Thanks,
- Brian F