Erronous sort used in query plan

I am putting together searches on the catalog info and came up with a
select that was rather slow and I noticed that in the explain analyze
there is a sort step on one of the left joins which I don't think
belongs there.

I found the small error in my query (using tl.oid instead of tr.oid and
tres.oid) that caused the query to slow down and generate the sort in
the plan but am not sure that the given condition should even generate a
sort step and if it does then I believe it should be a (more?) stable
decision.

Removing one of the left join's that is in error (tr or tres) changes
the column that is sorted, neither of which is related to the join/s
that appear to generate the step.

With tl, tr and tres in place the sort is performed on pjoin.oid.

Removing or correcting either tr or tres the sort is changed to perform
on olsort.oid.

Removing or correcting both tr and tres removes the sort from the plan.

Also - removing all the pg_operator joins the sort is still there (on
pjoin.oid) but if I remove one of the erroneous joins as well the sort
goes. (correcting one of the joins leaves the sort there but removing it
removes the sort)

Using postgres 8.2.0 on Mac OSX 10.4.8


The full query is -

explain analyze
SELECT
o.oid as "OID"
, n.nspname as "Schema"
, o.oprname as "Name"
, r.rolname as "Owner"
, CASE WHEN o.oprkind='b' THEN 'infix(left and right)'
WHEN o.oprkind='l' THEN 'prefix (left)'
WHEN o.oprkind='r' THEN 'postfix (right)'
END as "Kind"
, CASE WHEN o.oprcanhash='t' THEN 'Yes'
WHEN o.oprcanhash='f' THEN 'No' END as "Supports Hash Joins"
, tl.typname as "Left Operand"
, tr.typname as "Right Operand"
, tres.typname as "Result Type"
, ocom.oprname as "Commutator Operator"
, onegate.oprname as "Negator Operator"
, olsort.oprname as "Left Sort Operator"
, orsort.oprname as "Right Sort Operator"
, oltcm.oprname as "Less Than Operator"
, ogtcm.oprname as "Greater Than Operator"
, pcode.proname as "Operator Function"
, prest.proname as "Restriction Selectivity Function"
, pjoin.proname as "Join Selectivity Function"


FROM pg_catalog.pg_operator o
left join pg_catalog.pg_namespace n ON n.oid = o.oprnamespace
left join pg_catalog.pg_roles r on r.oid=o.oprowner
left join pg_catalog.pg_type tl on tl.oid=o.oprleft
left join pg_catalog.pg_type tr on tl.oid=o.oprright
left join pg_catalog.pg_type tres on tl.oid=o.oprresult
left join pg_catalog.pg_operator ocom on ocom.oid=o.oprcom
left join pg_catalog.pg_operator onegate on onegate.oid=o.oprnegate
left join pg_catalog.pg_operator oneg on oneg.oid=o.oprnegate
left join pg_catalog.pg_operator olsort on olsort.oid=o.oprlsortop
left join pg_catalog.pg_operator orsort on orsort.oid=o.oprrsortop
left join pg_catalog.pg_operator oltcm on oltcm.oid=o.oprltcmpop
left join pg_catalog.pg_operator ogtcm on ogtcm.oid=o.oprgtcmpop
left join pg_catalog.pg_proc pcode on pcode.oid=o.oprcode
left join pg_catalog.pg_proc prest on prest.oid=o.oprrest
left join pg_catalog.pg_proc pjoin on pjoin.oid=o.oprjoin

WHERE n.nspname like 'public'



I have attached a copy of the query and plan.
--

Shane Ambler
pgSQL@007Marketing.com

Get Sheeky @ http://Sheeky.Biz
explain analyze
SELECT
o.oid as "OID"
, n.nspname as "Schema"
, o.oprname as "Name"
, r.rolname as "Owner"
, CASE WHEN o.oprkind='b' THEN 'infix(left and right)'
WHEN o.oprkind='l' THEN 'prefix (left)'
WHEN o.oprkind='r' THEN 'postfix (right)'
END as "Kind"
, CASE WHEN o.oprcanhash='t' THEN 'Yes' WHEN o.oprcanhash='f' THEN 'No' END as "Supports Hash Joins"
, tl.typname as "Left Operand"
, tr.typname as "Right Operand"
, tres.typname as "Result Type"
, ocom.oprname as "Commutator Operator"
, onegate.oprname as "Negator Operator"
, olsort.oprname as "Left Sort Operator"
, orsort.oprname as "Right Sort Operator"
, oltcm.oprname as "Less Than Operator"
, ogtcm.oprname as "Greater Than Operator"
, pcode.proname as "Operator Function"
, prest.proname as "Restriction Selectivity Function"
, pjoin.proname as "Join Selectivity Function"


FROM pg_catalog.pg_operator o
left join pg_catalog.pg_namespace n ON n.oid = o.oprnamespace
left join pg_catalog.pg_roles r on r.oid=o.oprowner
left join pg_catalog.pg_type tl on tl.oid=o.oprleft
left join pg_catalog.pg_type tr on tl.oid=o.oprright
left join pg_catalog.pg_type tres on tl.oid=o.oprresult
left join pg_catalog.pg_operator ocom on ocom.oid=o.oprcom
left join pg_catalog.pg_operator onegate on onegate.oid=o.oprnegate
left join pg_catalog.pg_operator oneg on oneg.oid=o.oprnegate
left join pg_catalog.pg_operator olsort on olsort.oid=o.oprlsortop
left join pg_catalog.pg_operator orsort on orsort.oid=o.oprrsortop
left join pg_catalog.pg_operator oltcm on oltcm.oid=o.oprltcmpop
left join pg_catalog.pg_operator ogtcm on ogtcm.oid=o.oprgtcmpop
left join pg_catalog.pg_proc pcode on pcode.oid=o.oprcode
left join pg_catalog.pg_proc prest on prest.oid=o.oprrest
left join pg_catalog.pg_proc pjoin on pjoin.oid=o.oprjoin


WHERE n.nspname like 'public'


ORDER BY lower(n.nspname), lower(o.oprname)



                                                                                                                  QUERY
PLAN                                                                                                                  

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=2707.30..2707.66 rows=143 width=966) (actual time=22085.090..23284.736 rows=314064 loops=1)
   Sort Key: lower((n.nspname)::text), lower((o.oprname)::text)
   ->  Hash Left Join  (cost=2652.63..2702.18 rows=143 width=966) (actual time=3668.065..9163.877 rows=314064 loops=1)
         Hash Cond: ((o.oprcode)::oid = pcode.oid)
         ->  Hash Left Join  (cost=2567.13..2600.79 rows=143 width=906) (actual time=3661.366..7305.265 rows=314064
loops=1)
               Hash Cond: ((o.oprrest)::oid = prest.oid)
               ->  Hash Left Join  (cost=2481.63..2504.16 rows=143 width=846) (actual time=3654.311..6704.433
rows=314064loops=1) 
                     Hash Cond: (o.oprlsortop = olsort.oid)
                     ->  Hash Left Join  (cost=2453.91..2474.29 rows=143 width=786) (actual time=3651.827..6250.536
rows=314064loops=1) 
                           Hash Cond: (o.oprrsortop = orsort.oid)
                           ->  Hash Left Join  (cost=2426.18..2444.42 rows=143 width=726) (actual
time=3649.287..5795.792rows=314064 loops=1) 
                                 Hash Cond: (o.oprltcmpop = oltcm.oid)
                                 ->  Hash Left Join  (cost=2398.46..2414.55 rows=143 width=666) (actual
time=3646.749..5331.642rows=314064 loops=1) 
                                       Hash Cond: (o.oprgtcmpop = ogtcm.oid)
                                       ->  Merge Left Join  (cost=2370.73..2384.68 rows=143 width=606) (actual
time=3643.994..4867.855rows=314064 loops=1) 
                                             Merge Cond: ("outer"."?column19?" = pjoin.oid)
                                             ->  Sort  (cost=2158.92..2159.27 rows=143 width=546) (actual
time=3634.598..3800.837rows=314064 loops=1) 
                                                   Sort Key: (o.oprjoin)::oid
                                                   ->  Hash Left Join  (cost=49.70..2153.80 rows=143 width=546) (actual
time=5.883..2061.807rows=314064 loops=1) 
                                                         Hash Cond: (o.oprnegate = oneg.oid)
                                                         ->  Hash Left Join  (cost=21.98..2123.93 rows=143 width=550)
(actualtime=4.022..1348.066 rows=314064 loops=1) 
                                                               Hash Cond: (o.oprowner = r.oid)
                                                               ->  Nested Loop Left Join  (cost=20.89..2120.69 rows=143
width=490)(actual time=3.878..709.734 rows=314064 loops=1) 
                                                                     Join Filter: (tl.oid = o.oprright)
                                                                     ->  Nested Loop Left Join  (cost=10.44..1103.17
rows=143width=434) (actual time=3.843..73.766 rows=1128 loops=1) 
                                                                           Join Filter: (tl.oid = o.oprresult)
                                                                           ->  Nested Loop Left Join  (cost=0.00..85.65
rows=143width=374) (actual time=2.654..13.504 rows=192 loops=1) 
                                                                                 ->  Nested Loop Left Join
(cost=0.00..75.35rows=143 width=310) (actual time=2.637..10.730 rows=192 loops=1) 
                                                                                       ->  Nested Loop Left Join
(cost=0.00..56.37rows=143 width=250) (actual time=2.625..8.149 rows=192 loops=1) 
                                                                                             ->  Nested Loop
(cost=0.00..37.38rows=143 width=186) (actual time=2.588..4.261 rows=192 loops=1) 
                                                                                                   Join Filter: (n.oid
=o.oprnamespace) 
                                                                                                   ->  Seq Scan on
pg_namespacen  (cost=0.00..1.07 rows=1 width=68) (actual time=0.052..0.054 rows=1 loops=1) 
                                                                                                         Filter:
(nspname~~ 'public'::text) 
                                                                                                   ->  Seq Scan on
pg_operatoro  (cost=0.00..25.58 rows=858 width=126) (actual time=0.022..3.408 rows=858 loops=1) 
                                                                                             ->  Index Scan using
pg_operator_oid_indexon pg_operator onegate  (cost=0.00..0.12 rows=1 width=68) (actual time=0.014..0.016 rows=1
loops=192)
                                                                                                   Index Cond:
(onegate.oid= o.oprnegate) 
                                                                                       ->  Index Scan using
pg_operator_oid_indexon pg_operator ocom  (cost=0.00..0.12 rows=1 width=68) (actual time=0.008..0.010 rows=1 loops=192) 
                                                                                             Index Cond: (ocom.oid =
o.oprcom)
                                                                                 ->  Index Scan using pg_type_oid_index
onpg_type tl  (cost=0.00..0.06 rows=1 width=68) (actual time=0.007..0.011 rows=1 loops=192) 
                                                                                       Index Cond: (tl.oid = o.oprleft)
                                                                           ->  Materialize  (cost=10.44..13.57 rows=313
width=64)(actual time=0.001..0.125 rows=313 loops=192) 
                                                                                 ->  Seq Scan on pg_type tr2
(cost=0.00..10.13rows=313 width=64) (actual time=0.013..0.328 rows=313 loops=1) 
                                                                     ->  Materialize  (cost=10.44..13.57 rows=313
width=64)(actual time=0.000..0.133 rows=313 loops=1128) 
                                                                           ->  Seq Scan on pg_type tr
(cost=0.00..10.13rows=313 width=64) (actual time=0.007..0.320 rows=313 loops=1) 
                                                               ->  Hash  (cost=1.08..1.08 rows=4 width=68) (actual
time=0.065..0.065rows=5 loops=1) 
                                                                     ->  Subquery Scan r  (cost=0.00..1.08 rows=4
width=68)(actual time=0.021..0.037 rows=5 loops=1) 
                                                                           ->  Seq Scan on pg_authid  (cost=0.00..1.04
rows=4width=118) (actual time=0.018..0.027 rows=5 loops=1) 
                                                         ->  Hash  (cost=25.58..25.58 rows=858 width=4) (actual
time=1.797..1.797rows=858 loops=1) 
                                                               ->  Seq Scan on pg_operator oneg  (cost=0.00..25.58
rows=858width=4) (actual time=0.012..0.781 rows=858 loops=1) 
                                             ->  Sort  (cost=211.81..217.71 rows=2360 width=68) (actual
time=9.366..104.265rows=216851 loops=1) 
                                                   Sort Key: pjoin.oid
                                                   ->  Seq Scan on pg_proc pjoin  (cost=0.00..79.60 rows=2360 width=68)
(actualtime=0.039..2.700 rows=2360 loops=1) 
                                       ->  Hash  (cost=25.58..25.58 rows=858 width=68) (actual time=2.589..2.589
rows=858loops=1) 
                                             ->  Seq Scan on pg_operator ogtcm  (cost=0.00..25.58 rows=858 width=68)
(actualtime=0.040..1.024 rows=858 loops=1) 
                                 ->  Hash  (cost=25.58..25.58 rows=858 width=68) (actual time=2.448..2.448 rows=858
loops=1)
                                       ->  Seq Scan on pg_operator oltcm  (cost=0.00..25.58 rows=858 width=68) (actual
time=0.016..0.909rows=858 loops=1) 
                           ->  Hash  (cost=25.58..25.58 rows=858 width=68) (actual time=2.471..2.471 rows=858 loops=1)
                                 ->  Seq Scan on pg_operator orsort  (cost=0.00..25.58 rows=858 width=68) (actual
time=0.015..0.923rows=858 loops=1) 
                     ->  Hash  (cost=25.58..25.58 rows=858 width=68) (actual time=2.409..2.409 rows=858 loops=1)
                           ->  Seq Scan on pg_operator olsort  (cost=0.00..25.58 rows=858 width=68) (actual
time=0.022..0.928rows=858 loops=1) 
               ->  Hash  (cost=79.60..79.60 rows=2360 width=68) (actual time=6.983..6.983 rows=2360 loops=1)
                     ->  Seq Scan on pg_proc prest  (cost=0.00..79.60 rows=2360 width=68) (actual time=0.020..2.793
rows=2360loops=1) 
         ->  Hash  (cost=79.60..79.60 rows=2360 width=68) (actual time=6.571..6.571 rows=2360 loops=1)
               ->  Seq Scan on pg_proc pcode  (cost=0.00..79.60 rows=2360 width=68) (actual time=0.017..2.593 rows=2360
loops=1)
 Total runtime: 24195.085 ms
(65 rows)