Re: union vs. sort

On Tue, Apr 06, 2004 at 10:33:25AM -0400, Tom Lane wrote:
> Karel Zak <zakkr(at)zf(dot)jcu(dot)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(at)zf(dot)jcu(dot)cz>
http://home.zf.jcu.cz/~zakkr/