
 I'm  surprise  with query  plan  that  PostgreSQL planner  prepare  for
 selects with ORDER  BY if all data are from  sub-select that is already
 sorted.
 
        # explain select data from 
                         (select distinct data from addr) 
                  as x order by x.data;
        -------------------------------------------------
         Subquery Scan x
           ->  Unique
                 ->  Sort
                       Sort Key: data
                       ->  Seq Scan on addr


 This is  right -- the  main of query doesn't  use "Sort" for  ORDER BY,
 because subselect is sorted by "Unique".


 And almost same query, but in the subselect is union:
 
        # explain select data from 
                         (select data from addr 
                             union 
                          select data from addr2) 
                  as x order by x.data;
        -----------------------------------------
         Sort
           Sort Key: data
           ->  Subquery Scan x
                 ->  Unique
                       ->  Sort
                             Sort Key: data
                             ->  Append
                                   ->  Subquery Scan "*SELECT* 1" 
                                         ->  Seq Scan on addr
                                   ->  Subquery Scan "*SELECT* 2"
                                         ->  Seq Scan on addr2


   
 I think  it's bad, because  there is used extra  sort for ORDER  BY for
 already by "Unique" sorted data.

 If I add ORDER BY to subselect:

        # explain select data from 
                     (select data from addr 
                         union 
                      select data from addr2 order by data) 
                  as x order by x.data;
        ---------------------------------------------------
         Sort
           Sort Key: data
           ->  Subquery Scan x
                 ->  Sort
                       Sort Key: data
                       ->  Unique 
                             ->  Sort
                                   Sort Key: data
                                   ->  Append 
                                         ->  Subquery Scan "*SELECT* 1"
                                               ->  Seq Scan on addr 
                                         ->  Subquery Scan "*SELECT* 2"
                                               ->  Seq Scan on addr2 


 I see two unnecessary sorts for unique and already sorted data.

 The core of problem is probbaly UNION, because if I use simple query without 
 subselect it still sort already sorderd data:

        # explain select data from addr 
                      union 
                  select data from addr2 
                  order by data;
        -----------------------------------
         Sort
           Sort Key: data
           ->  Unique
                 ->  Sort
                       Sort Key: data
                       ->  Append
                             ->  Subquery Scan "*SELECT* 1"
                                   ->  Seq Scan on addr
                             ->  Subquery Scan "*SELECT* 2"
                                   ->  Seq Scan on addr2


 Or order of data which returns "unique" is for UNION diffrent that data
 from DISTINCT? (see first example).

    Karel

-- 
 Karel Zak  <zakkr@zf.jcu.cz>
 http://home.zf.jcu.cz/~zakkr/

Tue, 6 Apr 2004 14:04:35 +0200
Karel Zak <zakkr@zf.jcu.cz>
union vs. sort
Karel Zak <zakkr@zf.jcu.cz> writes:
>  I'm  surprise  with query  plan  that  PostgreSQL planner  prepare  for
>  selects with ORDER  BY if all data are from  sub-select that is already
>  sorted.

This isn't simply a matter of "omitting the sort".  Even if the inputs
are sorted, their concatenation (Append result) isn't sorted: "1 2 3 4"
and "1 3 7 9" are sorted, but "1 2 3 4 1 3 7 9" isn't.

To do what you're thinking about, we'd have to build a variant
implementation of Unique that merges two presorted inputs --- and it
wouldn't work for more than two inputs (at least not without a lot of
pain ... Append is a messy special case in many ways, and we'd have to
duplicate most of that cruft to make an N-input version of Unique).
This is possible, without doubt, but I'm not excited about expending
that much time on it.  You haven't shown any evidence that this would be
an important optimization in practice.

			regards, tom lane

Tue, 06 Apr 2004 10:33:25 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: union vs. sort 
On Tue, Apr 06, 2004 at 10:33:25AM -0400, Tom Lane wrote:
> Karel Zak <zakkr@zf.jcu.cz> writes:
> >  I'm  surprise  with query  plan  that  PostgreSQL planner  prepare  for
> >  selects with ORDER  BY if all data are from  sub-select that is already
> >  sorted.
> 
> This isn't simply a matter of "omitting the sort".  Even if the inputs
> are sorted, their concatenation (Append result) isn't sorted: "1 2 3 4"
> and "1 3 7 9" are sorted, but "1 2 3 4 1 3 7 9" isn't.

 I didn't  talk about  "Append" result,  but about  "Unique" result. The
 ORDER BY  in UNION  query works  with final  concanated data  -- that's
 right. My question is why a result from this ORDER BY is again sorted:

        # explain select data from 
                     (select data from addr 
                          union 
                      select data from addr2 order by data) 
                  as x order by x.data;
        -----------------------------------------------
(1)      Sort
           Sort Key: data
           ->  Subquery Scan x
(2)              ->  Sort
                       Sort Key: data
                       ->  Unique 
(3)                         ->  Sort
                                   Sort Key: data
                                   ->  Append 
                                         ->  Subquery Scan "*SELECT* 1"
                                               ->  Seq Scan on addr 
                                         ->  Subquery Scan "*SELECT* 2"
                                               ->  Seq Scan on addr2 

  I see three sorts with same data.

> To do what you're thinking about, we'd have to build a variant
> implementation of Unique that merges two presorted inputs --- and it
> wouldn't work for more than two inputs (at least not without a lot of
> pain ... Append is a messy special case in many ways, and we'd have to
> duplicate most of that cruft to make an N-input version of Unique).

  I think it is not needful touch Append, but it should detect
  redundant sorts. Why 
  
 "select data from (select data from addr order by data) as x order by x.data"

  use only one sort?

> This is possible, without doubt, but I'm not excited about expending
> that much time on it.  You haven't shown any evidence that this would be
> an important optimization in practice.

 It's nothing important  for me. It's from Czech  databases mailing list
 where some PostgreSQL users was  surprised with EXPLAIN result of UNION
 and speed of these queries.

    Karel

-- 
 Karel Zak  <zakkr@zf.jcu.cz>
 http://home.zf.jcu.cz/~zakkr/

Wed, 7 Apr 2004 09:33:17 +0200
Karel Zak <zakkr@zf.jcu.cz>
Re: union vs. sort
Karel Zak <zakkr@zf.jcu.cz> writes:
> On Tue, Apr 06, 2004 at 10:33:25AM -0400, Tom Lane wrote:
>> This isn't simply a matter of "omitting the sort".

>  I didn't  talk about  "Append" result,  but about  "Unique" result. The
>  ORDER BY  in UNION  query works  with final  concanated data  -- that's
>  right. My question is why a result from this ORDER BY is again sorted:

Oh, okay, that's just something that never got done, per this old
comment:

        /*
         * We set current_pathkeys NIL indicating we do not know sort
         * order.  This is correct when the top set operation is UNION
         * ALL, since the appended-together results are unsorted even if
         * the subplans were sorted.  For other set operations we could be
         * smarter --- room for future improvement!
         */

I've committed changes to do the right thing in CVS tip.

			regards, tom lane

Wed, 07 Apr 2004 14:20:55 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: union vs. sort 
On Wed, Apr 07, 2004 at 02:20:55PM -0400, Tom Lane wrote:
> 
> I've committed changes to do the right thing in CVS tip.

 Thanks man!

    Karel

-- 
 Karel Zak  <zakkr@zf.jcu.cz>
 http://home.zf.jcu.cz/~zakkr/

Thu, 8 Apr 2004 09:00:46 +0200
Karel Zak <zakkr@zf.jcu.cz>
Re: union vs. sort