Thread
-
union vs. sort
Karel Zak <zakkr@zf.jcu.cz> — 2004-04-06T12:04:35Z
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/ -
Re: union vs. sort
Tom Lane <tgl@sss.pgh.pa.us> — 2004-04-06T14:33:25Z
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
-
Re: union vs. sort
Karel Zak <zakkr@zf.jcu.cz> — 2004-04-07T07:33:17Z
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/ -
Re: union vs. sort
Tom Lane <tgl@sss.pgh.pa.us> — 2004-04-07T18:20:55Z
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 -
Re: union vs. sort
Karel Zak <zakkr@zf.jcu.cz> — 2004-04-08T07:00:46Z
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/