Horton

Thread

  1. UNION ALL has higher cost than inheritance

    Itagaki Takahiro <itagaki.takahiro@gmail.com> — 2010-10-21T05:02:39Z

    I found an explicit UNION ALL has higher cost than an automatic expansion
by inheritance (49 vs. 83 in the example below). Where does the difference
come from?  Since they have almost same plan trees, should it be the same cost?

=# CREATE TABLE parent (i integer);
=# CREATE TABLE child () INHERITS (parent);
=# INSERT INTO child SELECT generate_series(1, 1000);
=# CREATE INDEX ON child (i);
=# ANALYZE;

=# EXPLAIN SELECT * FROM parent;
                                 QUERY PLAN
----------------------------------------------------------------------------
 Result  (cost=0.00..49.00 rows=3400 width=4)
   ->  Append  (cost=0.00..49.00 rows=3400 width=4)
         ->  Seq Scan on parent  (cost=0.00..34.00 rows=2400 width=4)
         ->  Seq Scan on child parent  (cost=0.00..15.00 rows=1000 width=4)
(4 rows)

=# EXPLAIN SELECT * FROM ONLY parent UNION ALL SELECT * FROM child;
                           QUERY PLAN
----------------------------------------------------------------
 Append  (cost=0.00..83.00 rows=3400 width=4)
   ->  Seq Scan on parent  (cost=0.00..34.00 rows=2400 width=4)
   ->  Seq Scan on child  (cost=0.00..15.00 rows=1000 width=4)
(3 rows)

-- 
Itagaki Takahiro

  2. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-10-21T05:18:05Z

    Itagaki Takahiro <itagaki.takahiro@gmail.com> writes:
> I found an explicit UNION ALL has higher cost than an automatic expansion
> by inheritance (49 vs. 83 in the example below). Where does the difference
> come from?

The plan for UNION initially involves a couple of SubqueryScan nodes,
which impose an extra cost of cpu_tuple_cost per tuple.  Those later
get optimized away, but we don't try to readjust the cost estimates
for that.

			regards, tom lane

  3. Re: UNION ALL has higher cost than inheritance

    Itagaki Takahiro <itagaki.takahiro@gmail.com> — 2010-10-21T06:16:15Z

    On Thu, Oct 21, 2010 at 2:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> The plan for UNION initially involves a couple of SubqueryScan nodes,
> which impose an extra cost of cpu_tuple_cost per tuple.  Those later
> get optimized away, but we don't try to readjust the cost estimates
> for that.

Thanks. It also explains my another question why Merge Append cannot
be used for UNION ALL plans. Inheritance is better than UNION ALL
in much more cases thanks to Merge Append.

=# EXPLAIN SELECT * FROM parent ORDER BY i LIMIT 10;
                                              QUERY PLAN
------------------------------------------------------------------------------------------------------
 Limit  (cost=1.02..1.58 rows=10 width=4)
   ->  Result  (cost=1.02..56.79 rows=1001 width=4)
         ->  Merge Append  (cost=1.02..56.79 rows=1001 width=4)
               Sort Key: public.parent.i
               ->  Sort  (cost=1.01..1.01 rows=1 width=4)
                     Sort Key: public.parent.i
                     ->  Seq Scan on parent  (cost=0.00..1.00 rows=1 width=4)
               ->  Index Scan using child_i_idx on child parent
(cost=0.00..43.25 rows=1000 width=4)
(8 rows)

=# EXPLAIN (SELECT * FROM ONLY parent ORDER BY i) UNION ALL (SELECT *
FROM child ORDER BY i) ORDER BY i LIMIT 10;
                                          QUERY PLAN
-----------------------------------------------------------------------------------------------
 Limit  (cost=75.91..75.93 rows=10 width=4)
   ->  Sort  (cost=75.91..78.41 rows=1001 width=4)
         Sort Key: parent.i
         ->  Append  (cost=1.01..54.28 rows=1001 width=4)
               ->  Sort  (cost=1.01..1.01 rows=1 width=4)
                     Sort Key: parent.i
                     ->  Seq Scan on parent  (cost=0.00..1.00 rows=1 width=4)
               ->  Index Scan using child_i_idx on child
(cost=0.00..43.25 rows=1000 width=4)
(8 rows)

-- 
Itagaki Takahiro

  4. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-10-21T13:57:42Z

    Itagaki Takahiro <itagaki.takahiro@gmail.com> writes:
> On Thu, Oct 21, 2010 at 2:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The plan for UNION initially involves a couple of SubqueryScan nodes,
>> which impose an extra cost of cpu_tuple_cost per tuple. Those later
>> get optimized away, but we don't try to readjust the cost estimates
>> for that.

> Thanks. It also explains my another question why Merge Append cannot
> be used for UNION ALL plans.

Hmm, seems like the example you show ought to work.  I wonder if there
was an oversight in that patch...

			regards, tom lane

  5. Re: UNION ALL has higher cost than inheritance

    Greg Stark <gsstark@mit.edu> — 2010-10-21T18:10:35Z

    On Thu, Oct 21, 2010 at 6:57 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Thanks. It also explains my another question why Merge Append cannot
>> be used for UNION ALL plans.
>
> Hmm, seems like the example you show ought to work.  I wonder if there
> was an oversight in that patch...
>

Huh, that definitely worked in the earlier versions of the patch (as
much as it "worked" at all)

-- 
greg

  6. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-10-21T21:17:10Z

    Greg Stark <gsstark@mit.edu> writes:
> On Thu, Oct 21, 2010 at 6:57 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> Thanks. It also explains my another question why Merge Append cannot
>>> be used for UNION ALL plans.

>> Hmm, seems like the example you show ought to work. I wonder if there
>> was an oversight in that patch...

> Huh, that definitely worked in the earlier versions of the patch (as
> much as it "worked" at all)

Actually, it works as long as the UNION is in a subquery:

regression=# EXPLAIN select * from (
(SELECT * FROM ONLY parent ORDER BY i) UNION ALL
(SELECT * FROM child ORDER BY i)) ss ORDER BY i LIMIT 10;
                                          QUERY PLAN                            
-----------------------------------------------------------------------------------------------
 Limit  (cost=168.76..169.13 rows=10 width=4)
   ->  Result  (cost=168.76..294.51 rows=3400 width=4)
         ->  Merge Append  (cost=168.76..294.51 rows=3400 width=4)
               Sort Key: parent.i
               ->  Sort  (cost=168.75..174.75 rows=2400 width=4)
                     Sort Key: parent.i
                     ->  Seq Scan on parent  (cost=0.00..34.00 rows=2400 width=4)
               ->  Index Scan using child_i_idx on child  (cost=0.00..43.25 rows=1000 width=4)
(8 rows)

The oversight here is that we don't use appendrel planning for
a top-level UNION ALL construct.  That didn't use to matter,
because you always got the same stupid Append plan either way.
Now it seems like we ought to have some more intelligence for the
top-level SetOp case.  I smell some code refactoring coming up.

			regards, tom lane

  7. Re: UNION ALL has higher cost than inheritance

    David Wheeler <david@kineticode.com> — 2010-10-21T21:47:25Z

    On Oct 21, 2010, at 2:17 PM, Tom Lane wrote:

> The oversight here is that we don't use appendrel planning for
> a top-level UNION ALL construct.  That didn't use to matter,
> because you always got the same stupid Append plan either way.
> Now it seems like we ought to have some more intelligence for the
> top-level SetOp case.  I smell some code refactoring coming up.

Does it smell like chicken?

Best,

David

  8. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-11-08T04:00:08Z

    I wrote:
> The oversight here is that we don't use appendrel planning for
> a top-level UNION ALL construct.  That didn't use to matter,
> because you always got the same stupid Append plan either way.
> Now it seems like we ought to have some more intelligence for the
> top-level SetOp case.  I smell some code refactoring coming up.

I did some hacking on this and came up with the attached patch, which
could use a bit more work on the comments but passes regression tests.
However, this just solves the issue of being smart about top-level
UNION ALL cases.  It might be worth looking into using MergeAppend
for the sorting required for other types of set operations.  That would
involve quite a different patch, and I'm not sure if it'd remove the
need for this one or not.

			regards, tom lane

  9. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-11-08T18:19:54Z

    I wrote:
> I did some hacking on this and came up with the attached patch, which
> could use a bit more work on the comments but passes regression tests.
> However, this just solves the issue of being smart about top-level
> UNION ALL cases.  It might be worth looking into using MergeAppend
> for the sorting required for other types of set operations.  That would
> involve quite a different patch, and I'm not sure if it'd remove the
> need for this one or not.

I spent some more time thinking about this.  It seems difficult to make
any real further progress without essentially throwing out the current
approach to planning set-operation trees and starting over.  What we'd
want is to generate Paths representing the different ways a set-op could
be implemented and then pick the best one.  I can see the general shape
of how to do that: a set-op should be thought of as generating a
constrained join relation in a fashion similar to an OUTER JOIN
construct, and then the different Paths are possible implementations for
the join rel.  We'd need new Path types for hashed or sorted UNION,
INTERSECT, EXCEPT, as well as some analog of the SpecialJoinInfo
struct (or extend that struct to cover these cases).

It strikes me that maybe top-level DISTINCT could be married into this
too, since it's basically the same as a one-input UNION operator.  But
not sure what to do with DISTINCT ON.

Another thought here is that the current definition of the SetOp
execution node type could be improved.  Instead of taking a single
pre-merged input tuple stream, it'd be better if it had two inputs
like a JOIN node.  Then we could eliminate the "flag" column, which
would simplify matters for planning and reduce the amount of data
that has to be passed through sorting.  SetOp itself would need to
borrow some of the capability of MergeAppend so that it could read
two sorted streams in parallel and keep them in sync.

But this all looks like a pretty substantial amount of work, and
given the low level of user demand for improving the performance of
set operations, it seems to belong fairly far down the to-do list.
So I'm not going to tackle it now.  Barring objection, I'll clean up
yesterday's patch a bit more and commit it.

			regards, tom lane

  10. Re: UNION ALL has higher cost than inheritance

    Robert Haas <robertmhaas@gmail.com> — 2010-11-08T19:56:31Z

    On Mon, Nov 8, 2010 at 1:19 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
>> I did some hacking on this and came up with the attached patch, which
>> could use a bit more work on the comments but passes regression tests.
>> However, this just solves the issue of being smart about top-level
>> UNION ALL cases.  It might be worth looking into using MergeAppend
>> for the sorting required for other types of set operations.  That would
>> involve quite a different patch, and I'm not sure if it'd remove the
>> need for this one or not.
>
> I spent some more time thinking about this.  It seems difficult to make
> any real further progress without essentially throwing out the current
> approach to planning set-operation trees and starting over.  What we'd
> want is to generate Paths representing the different ways a set-op could
> be implemented and then pick the best one.  I can see the general shape
> of how to do that: a set-op should be thought of as generating a
> constrained join relation in a fashion similar to an OUTER JOIN
> construct, and then the different Paths are possible implementations for
> the join rel.  We'd need new Path types for hashed or sorted UNION,
> INTERSECT, EXCEPT, as well as some analog of the SpecialJoinInfo
> struct (or extend that struct to cover these cases).

It strikes me that INTERSECT ALL and EXCEPT ALL are pretty much JUST a
semi- or anti-join (on the entire set of output columns).   But
without ALL it's completely different.

> It strikes me that maybe top-level DISTINCT could be married into this
> too, since it's basically the same as a one-input UNION operator.  But
> not sure what to do with DISTINCT ON.
>
> Another thought here is that the current definition of the SetOp
> execution node type could be improved.  Instead of taking a single
> pre-merged input tuple stream, it'd be better if it had two inputs
> like a JOIN node.  Then we could eliminate the "flag" column, which
> would simplify matters for planning and reduce the amount of data
> that has to be passed through sorting.  SetOp itself would need to
> borrow some of the capability of MergeAppend so that it could read
> two sorted streams in parallel and keep them in sync.
>
> But this all looks like a pretty substantial amount of work, and
> given the low level of user demand for improving the performance of
> set operations, it seems to belong fairly far down the to-do list.
> So I'm not going to tackle it now.  Barring objection, I'll clean up
> yesterday's patch a bit more and commit it.

I agree.  If we had infinite resources it would be nice to tackle
this, but I think we have bigger fish to fry.  In particular, I wonder
if you've thought any more about the generalized inner-indexscan
machinery, or taken a look at any of the issues around KNNGIST.  I'd
like to see our limited supply of planner-fu invested in those areas,
or perhaps in making inner join removal work.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  11. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-11-08T20:05:16Z

    Robert Haas <robertmhaas@gmail.com> writes:
> On Mon, Nov 8, 2010 at 1:19 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> But this all looks like a pretty substantial amount of work, and
>> given the low level of user demand for improving the performance of
>> set operations, it seems to belong fairly far down the to-do list.
>> So I'm not going to tackle it now. Barring objection, I'll clean up
>> yesterday's patch a bit more and commit it.

> I agree.  If we had infinite resources it would be nice to tackle
> this, but I think we have bigger fish to fry.  In particular, I wonder
> if you've thought any more about the generalized inner-indexscan
> machinery, or taken a look at any of the issues around KNNGIST.  I'd
> like to see our limited supply of planner-fu invested in those areas,
> or perhaps in making inner join removal work.

The two top things on my to-do list for 9.1 are the generalized
inner-indexscan stuff and automatic replans for parameterized queries.
I had been hoping to finish one or the other before the next commitfest,
though time is draining away rapidly.

I'll try to look at KNNGIST during the fest.

			regards, tom lane

  12. Re: UNION ALL has higher cost than inheritance

    Robert Haas <robertmhaas@gmail.com> — 2010-11-08T20:07:43Z

    On Mon, Nov 8, 2010 at 3:05 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Mon, Nov 8, 2010 at 1:19 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> But this all looks like a pretty substantial amount of work, and
>>> given the low level of user demand for improving the performance of
>>> set operations, it seems to belong fairly far down the to-do list.
>>> So I'm not going to tackle it now.  Barring objection, I'll clean up
>>> yesterday's patch a bit more and commit it.
>
>> I agree.  If we had infinite resources it would be nice to tackle
>> this, but I think we have bigger fish to fry.  In particular, I wonder
>> if you've thought any more about the generalized inner-indexscan
>> machinery, or taken a look at any of the issues around KNNGIST.  I'd
>> like to see our limited supply of planner-fu invested in those areas,
>> or perhaps in making inner join removal work.
>
> The two top things on my to-do list for 9.1 are the generalized
> inner-indexscan stuff and automatic replans for parameterized queries.
> I had been hoping to finish one or the other before the next commitfest,
> though time is draining away rapidly.

Cool beans.

> I'll try to look at KNNGIST during the fest.

Thanks.  I have posted on it a few times; you may or may not find it
helpful to review those before diving in yourself...

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  13. Re: UNION ALL has higher cost than inheritance

    Dimitri Fontaine <dimitri@2ndquadrant.fr> — 2010-11-08T20:14:20Z

    Tom Lane <tgl@sss.pgh.pa.us> writes:
> But this all looks like a pretty substantial amount of work, and
> given the low level of user demand for improving the performance of
> set operations, it seems to belong fairly far down the to-do list.

Whatever you say, that's your own todo list after all. I just wanted to
chime in and say that it could well be a chicken-and-eggs problem.

Other than that, the only general way I know of to optimise a WHERE
clause containing OR branches is producing the UNION ALL equivalent.
Now maybe I'm all wet, but your explaining sounded like a very nice
first step towards such an automatic optimisation.

Regards,
-- 
Dimitri Fontaine
http://2ndQuadrant.fr     PostgreSQL : Expertise, Formation et Support

  14. Re: UNION ALL has higher cost than inheritance

    Tom Lane <tgl@sss.pgh.pa.us> — 2010-11-08T20:27:14Z

    BTW, one other point for the archives, before I forget it: it'd probably
also be wise to change the parser's output representation of set
operations.  I think it should create a separate RTE entry corresponding
to each SetOperation node, similar to what we do for explicit JOIN
nodes.  Then there is a clean representation for Vars referencing the
setop outputs: they can use the RT index of the SetOp RTE entry.
The current implementation is that all Vars in the upper query use the
RTI of the leftmost leaf query of the setop structure, which is really
bogus.  First, that query doesn't necessarily output the same datatypes
as the upper setops do, so the datatypes shown by the Vars don't always
match the RTE they claim to refer to.  (This is one reason why all of
the setop optimizations we do have tend to punt as soon as any datatype
changes occur.)  Second, this design provides no good way to refer to
outputs of intermediate setops.  I think we will *have* to fix that if
we want to make the planner's handling of these cases much smarter than
it is now.

			regards, tom lane