Thread

1. upper planner path-ification

   Robert Haas <robertmhaas@gmail.com> — 2015-05-14T01:39:03Z

   Hi,
   
   I've been pulling over Tom's occasional remarks about redoing
   grouping_planner - and maybe further layers of the planner - to work
   with Paths instead of Plans.  I've had difficulty locating all of the
   relevant threads.  Here's everything I've found so far, which I'm
   pretty sure is not everything:
   
   http://www.postgresql.org/message-id/17400.1311716272@sss.pgh.pa.us
   http://www.postgresql.org/message-id/2614.1375730493@sss.pgh.pa.us
   http://www.postgresql.org/message-id/22721.1385048662@sss.pgh.pa.us
   http://www.postgresql.org/message-id/BANLkTinDjjFHNOzESG2J2U4GOkqLu69Zqg@mail.gmail.com
   http://www.postgresql.org/message-id/8479.1418420018@sss.pgh.pa.us
   
   I think there are two separate problems here.  First, there's the
   problem that grouping_planner() is complicated.  It's doing cost
   comparisons, but all in ad-hoc fashion rather than using a consistent
   mechanic the way add_path() does.  Generally, we can plan an aggregate
   using either (1) a hashed aggregate, (2) a sorted aggregate, or (3)
   for min or max, an index scan that just grabs the highest or lowest
   value in lieu of a full table scan.  Instead of generating a plan for
   each of these possibilities, we'd like to generate paths for each one,
   and then pick one to turn into a plan.  AIUI, the hope is that this
   would simplify the cost calculations, and also make it easier to
   inject other paths, such as a path where an FDW performs the
   aggregation step on the remote server.
   
   Second, there's the problem that we might like to order aggregates
   with respect to joins.  If we have something like SELECT DISTINCT ON
   (foo.x) foo.x, foo.y, bar.y FROM foo, bar WHERE foo.x = bar.x, then
   (a) if foo.x has many duplicates, it will be better to DISTINCT-ify
   foo and then join to bar afterwards but (b) if foo.x = bar.x is highly
   selective, it will be better to join to bar first and then
   DISTINCT-ify the result.  Currently, aggregation is always last;
   that's not great.  Hitoshi Harada's proposed strategy of essentially
   figuring out where the aggregation steps can go and then re-planning
   for each one is also not great, because each join problem will be a
   subtree of the one we use for the aggregate-last strategy, and thus
   we're wasting effort by planning the same subtrees multiple times.
   Instead, we might imagine letting grouping planner fish out the best
   paths for the joinrels that represent possible aggregation points,
   generate aggregation paths for each of those, and then work out what
   additional rels need to be joined afterwards.  That sounds hard, but
   not as hard as doing something sensible with what we have today.
   
   I'm inclined to think that it would be useful to solve the first
   problem even if we didn't solve the second one right away (but that
   might be wrong).  As a preparatory step, I'm thinking it would be
   sensible to split grouping_planner() into an outer function that would
   handle the addition of Limit and LockRows nodes and maybe planning of
   set operations, and an inner function that would handle GROUP BY,
   DISTINCT, and possibly window function planning.
   
   Thoughts?
   
   -- 
   Robert Haas
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   

2. Re: upper planner path-ification

   Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-14T02:27:46Z

   Robert Haas <robertmhaas@gmail.com> writes:
   > I've been pulling over Tom's occasional remarks about redoing
   > grouping_planner - and maybe further layers of the planner - to work
   > with Paths instead of Plans. ...
   > I think there are two separate problems here.  First, there's the
   > problem that grouping_planner() is complicated.
   > Second, there's the problem that we might like to order aggregates
   > with respect to joins.
   
   Both of those are problems all right, but there is more context here.
   
   * As some of the messages you cited mention, we would like to have Path
   representations for things like aggregation, because that's the only
   way we'll get to a sane API that lets FDWs propose remote aggregation.
   
   * We have also had requests for the planner to be smarter about
   UNION/INTERSECT/EXCEPT queries.  Again, that requires cost comparisons,
   which would be better done if we had Path representations for the various
   ways we'd want to consider.  Also, a big part of the issue there is
   wanting to be able to consider sorted versus unsorted plans for the leaf
   queries of the set-op (IOW, optionally pushing the sort requirements of
   the set-op down into the leaves).  Right now, such comparisons are
   impossible because prepunion.c uses subquery_planner to handle the leaf
   queries, and what it gets back from that is one finished plan, not
   alternative Paths.
   
   * Likewise, subqueries-in-FROM are handled by recursing to
   subquery_planner, which gives us back just one frozen Plan for the
   subquery.  Among other things this seems to make it too expensive to
   consider generating parameterized paths for the subquery.  I'd like
   to keep subquery plans in Path form until much later as well.
   
   So these considerations motivate wishing that the result of
   subquery_planner could be a list of alternative Paths rather than a Plan,
   which means that every operation it knows how to tack onto the scan/join
   plan has to be representable by a Path of some sort.
   
   I don't know how granular that needs to be, though.  For instance, one
   could certainly imagine that it might be sufficient initially to have a
   single "WindowPath" that represents "do all the window functions", and
   then at create_plan time we'd generate multiple WindowAgg plan nodes in
   the same ad-hoc way as now.  Breaking that down in the Path representation
   would only become interesting if it would affect higher-level decisions,
   and I'm not immediately seeing how it might do that.
   
   > I'm inclined to think that it would be useful to solve the first
   > problem even if we didn't solve the second one right away (but that
   > might be wrong).  As a preparatory step, I'm thinking it would be
   > sensible to split grouping_planner() into an outer function that would
   > handle the addition of Limit and LockRows nodes and maybe planning of
   > set operations, and an inner function that would handle GROUP BY,
   > DISTINCT, and possibly window function planning.
   
   For the reasons I mentioned, I'd like to get to a point where
   subquery_planner's output is Paths not Plans as soon as possible.  But the
   idea of coarse representation of steps that we aren't trying to be smart
   about might be useful to save some labor in the short run.
   
   The zero-order version of that might be a single Path node type that
   represents "do whatever grouping_planner would do", which we'd start to
   break down into multiple node types once we had the other APIs fixed.
   
   			regards, tom lane
   
   
   

3. Re: upper planner path-ification

   Robert Haas <robertmhaas@gmail.com> — 2015-05-14T03:43:57Z

   On Wed, May 13, 2015 at 10:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   > Both of those are problems all right, but there is more context here.
   
   Thanks for providing the context.
   
   >> I'm inclined to think that it would be useful to solve the first
   >> problem even if we didn't solve the second one right away (but that
   >> might be wrong).  As a preparatory step, I'm thinking it would be
   >> sensible to split grouping_planner() into an outer function that would
   >> handle the addition of Limit and LockRows nodes and maybe planning of
   >> set operations, and an inner function that would handle GROUP BY,
   >> DISTINCT, and possibly window function planning.
   >
   > For the reasons I mentioned, I'd like to get to a point where
   > subquery_planner's output is Paths not Plans as soon as possible.  But the
   > idea of coarse representation of steps that we aren't trying to be smart
   > about might be useful to save some labor in the short run.
   >
   > The zero-order version of that might be a single Path node type that
   > represents "do whatever grouping_planner would do", which we'd start to
   > break down into multiple node types once we had the other APIs fixed.
   
   The problem I'm really interested in solving is gaining the ability to
   add additional aggregation strategies, such as letting an FDW do it
   remotely, or doing it in parallel.  It seems to me that your proposed
   zero-order version of that wouldn't really get us terribly far toward
   that goal - it would be more oriented towards solving the other
   problems you mention, specifically adding more intelligence to setops
   and allowing parameterization of subqueries.  Those things certainly
   have some value, but I think supporting alternate aggregation
   strategies is a lot more interesting.
   
   -- 
   Robert Haas
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   

4. Re: upper planner path-ification

   Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> — 2015-05-14T07:25:41Z

   Hello, this topic lured me on..
   
   At Wed, 13 May 2015 23:43:57 -0400, Robert Haas <robertmhaas@gmail.com> wrote in <CA+TgmoaQa6BcASGCL8tOXWmmOom-D7EbesAdZ4y58Cb+TJQ79g@mail.gmail.com>
   > On Wed, May 13, 2015 at 10:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   > > Both of those are problems all right, but there is more context here.
   > 
   > Thanks for providing the context.
   > 
   > >> I'm inclined to think that it would be useful to solve the first
   > >> problem even if we didn't solve the second one right away (but that
   > >> might be wrong).  As a preparatory step, I'm thinking it would be
   > >> sensible to split grouping_planner() into an outer function that would
   > >> handle the addition of Limit and LockRows nodes and maybe planning of
   > >> set operations, and an inner function that would handle GROUP BY,
   > >> DISTINCT, and possibly window function planning.
   > >
   > > For the reasons I mentioned, I'd like to get to a point where
   > > subquery_planner's output is Paths not Plans as soon as possible.  But the
   > > idea of coarse representation of steps that we aren't trying to be smart
   > > about might be useful to save some labor in the short run.
   > >
   > > The zero-order version of that might be a single Path node type that
   > > represents "do whatever grouping_planner would do", which we'd start to
   > > break down into multiple node types once we had the other APIs fixed.
   > 
   > The problem I'm really interested in solving is gaining the ability to
   > add additional aggregation strategies, such as letting an FDW do it
   > remotely, or doing it in parallel.  It seems to me that your proposed
   > zero-order version of that wouldn't really get us terribly far toward
   > that goal - it would be more oriented towards solving the other
   > problems you mention, specifically adding more intelligence to setops
   > and allowing parameterization of subqueries.  Those things certainly
   > have some value, but I think supporting alternate aggregation
   > strategies is a lot more interesting.
   
   I don't know which you are planning the interface between the
   split layers to be path or plan, I guess simply splitting
   grouping_planner results in the latter.  Although Tom's "path
   representation up to higher layer" does not seem to clash with,
   or have anything to do directly with your layer splitting,
   complicating the existing complication should make it more
   difficult to refactor the planner to have more intelligence.
   
   For example, Limit could be pushed down into bottom of a path
   tree ideally and would be also effective for remote node greately
   like remote aggregations would be. The zero-order version would
   eliminate subqery scan (or frozen plan) path or such nodes (if
   any) which obstruct possible global optimization. But simple
   splitting of the current grouping_planner looks make it more
   difficult. It is so frustrating not to be able to express my
   thought well but IMHO, shortly, I wish the planner not to grow to
   be in such form.
   
   Certainly it seems not so easy to get over the zero-order
   version, but..
   
   regards,
   
   -- 
   Kyotaro Horiguchi
   NTT Open Source Software Center
   
   
   
   

5. Re: upper planner path-ification

   Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-14T14:54:34Z

   Robert Haas <robertmhaas@gmail.com> writes:
   > On Wed, May 13, 2015 at 10:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   >> For the reasons I mentioned, I'd like to get to a point where
   >> subquery_planner's output is Paths not Plans as soon as possible.  But the
   >> idea of coarse representation of steps that we aren't trying to be smart
   >> about might be useful to save some labor in the short run.
   >> 
   >> The zero-order version of that might be a single Path node type that
   >> represents "do whatever grouping_planner would do", which we'd start to
   >> break down into multiple node types once we had the other APIs fixed.
   
   > The problem I'm really interested in solving is gaining the ability to
   > add additional aggregation strategies, such as letting an FDW do it
   > remotely, or doing it in parallel.  It seems to me that your proposed
   > zero-order version of that wouldn't really get us terribly far toward
   > that goal - it would be more oriented towards solving the other
   > problems you mention, specifically adding more intelligence to setops
   > and allowing parameterization of subqueries.  Those things certainly
   > have some value, but I think supporting alternate aggregation
   > strategies is a lot more interesting.
   
   Clearly we'd like to get to both goals.  I don't see the "zero order"
   design as something we'd ship or even have in the tree for more than
   a short time.  But it might still be a useful refactorization step.
   
   In any case, the key question if we're to have Paths representing
   higher-level computations is "what do we hang our lists of such Paths
   off of?".  If we have say both GROUP BY and LIMIT, it's important to
   distinguish Paths that purport to do only the grouping step from those
   that do both the grouping and the limit.  For the scan/join part of
   planning, we do this by attaching the Paths to RelOptInfos that denote
   various levels of joining ... but how does that translate to the higher
   level processing steps?  Perhaps we could make dummy RelOptInfos that
   correspond to having completed different steps of processing; but I've
   not got a clear idea about how many such RelOptInfos we'd need, and
   in particular not about whether we need to cater for completing those
   steps in different orders.
   
   			regards, tom lane
   
   
   

6. Re: upper planner path-ification

   Robert Haas <robertmhaas@gmail.com> — 2015-05-14T16:19:44Z

   On Thu, May 14, 2015 at 10:54 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   > In any case, the key question if we're to have Paths representing
   > higher-level computations is "what do we hang our lists of such Paths
   > off of?".
   
   Yeah, I was wondering about that, too.
   
   > If we have say both GROUP BY and LIMIT, it's important to
   > distinguish Paths that purport to do only the grouping step from those
   > that do both the grouping and the limit.  For the scan/join part of
   > planning, we do this by attaching the Paths to RelOptInfos that denote
   > various levels of joining ... but how does that translate to the higher
   > level processing steps?  Perhaps we could make dummy RelOptInfos that
   > correspond to having completed different steps of processing; but I've
   > not got a clear idea about how many such RelOptInfos we'd need, and
   > in particular not about whether we need to cater for completing those
   > steps in different orders.
   
   Well, I'm just shooting from the hip here, but it seems to me that the
   basic pipeline as it exists today is Join -> Aggregate -> SetOp ->
   Limit -> LockRows. I don't think Limit or LockRows can be moved any
   earlier.  SetOps have a lot in common with Aggregates, though, and
   might be able to commute.  For instance, if you had an EXCEPT that was
   going to knock out most of the rows and also a DISTINCT, you might
   want to postpone the DISTINCT until after you do the EXCEPT, or you
   might just want to do both at once:
   
   rhaas=# explain select distinct * from (values (1), (1), (2), (3)) x
   except select 3;
                                        QUERY PLAN
   -------------------------------------------------------------------------------------
    HashSetOp Except  (cost=0.06..0.17 rows=4 width=3)
      ->  Append  (cost=0.06..0.16 rows=5 width=3)
            ->  Subquery Scan on "*SELECT* 1"  (cost=0.06..0.14 rows=4 width=4)
                  ->  HashAggregate  (cost=0.06..0.10 rows=4 width=4)
                        Group Key: "*VALUES*".column1
                        ->  Values Scan on "*VALUES*"  (cost=0.00..0.05
   rows=4 width=4)
            ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..0.02 rows=1 width=0)
                  ->  Result  (cost=0.00..0.01 rows=1 width=0)
   (8 rows)
   
   In an ideal world, we'd only hash once.
   
   And both set operations and aggregates can sometimes commute with
   joins, which seems like the stickiest wicket, because there can't be
   more than a couple of levels of grouping or aggregation in the same
   subquery (GROUP BY, DISTINCT, UNION?) but there can be lots of joins,
   and if a particular aggregate can be implemented in lots of places,
   things start to get complicated.
   
   Like, if you've got a SELECT DISTINCT ON (a.x) ... FROM
   ...lots...-type query, I think you can pretty much slap the DISTINCT
   on there at any point in the join nest, probably ideally at the point
   where the number of rows is the lowest it's going to get, or maybe
   when the sortorder is convenient.  For a GROUP BY query with ungrouped
   dependent columns, you can do the aggregation before or after those
   joins, but you must do it after the joins that are needed to provide
   all the values needed for the aggregated columns.  If you model this
   with RelOptInfos, you're basically going to need a RelOptInfo to say
   "i include these relids and these aggregation or setop operations".
   So in the worst case each agg/setop doubles the number of RelOptInfos,
   although probably in reality it doesn't because you won't have
   infinite flexibility to reorder things.
   
   -- 
   Robert Haas
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   

7. Re: upper planner path-ification

   Martijn van Oosterhout <kleptog@svana.org> — 2015-05-14T21:34:43Z

   On Thu, May 14, 2015 at 12:19:44PM -0400, Robert Haas wrote:
   > Well, I'm just shooting from the hip here, but it seems to me that the
   > basic pipeline as it exists today is Join -> Aggregate -> SetOp ->
   > Limit -> LockRows. I don't think Limit or LockRows can be moved any
   > earlier.  SetOps have a lot in common with Aggregates, though, and
   > might be able to commute.  For instance, if you had an EXCEPT that was
   > going to knock out most of the rows and also a DISTINCT, you might
   > want to postpone the DISTINCT until after you do the EXCEPT, or you
   > might just want to do both at once:
   
   Also thinking a little from the side: an SQL query is a expression of
   some tree in relational algebra, and a Path is a representation of a
   way to acheive some sub-part of it.  The planner attempts to try find
   alternative ways of generating path by reordering joins but AIUI
   doesn't do much about aggregations.
   
   What is essentially being discussed here is also allowing commuting
   aggregations and joins.  DISTINCT and DISTINCT ON are just special
   kinds of aggregations so don't need to be considered especially.
   
   ISTM you should be able to for each aggregation note which joins it
   commutes with and which it doesn't, perhaps even with a simple bitmap. 
   The backbone of the plan is the order of the aggregations which
   generally won't commute at all, and the joins which can float around as
   long as the dependancies (stuff that won't commute) are satisfied.
   
   > And both set operations and aggregates can sometimes commute with
   > joins, which seems like the stickiest wicket, because there can't be
   > more than a couple of levels of grouping or aggregation in the same
   > subquery (GROUP BY, DISTINCT, UNION?) but there can be lots of joins,
   > and if a particular aggregate can be implemented in lots of places,
   > things start to get complicated.
   
   I think this is basically the same idea. I'm not sure aggregates and
   set operations can commute in general, unless you could somehow
   (conceptually) describe them as a join/antijoin.  UNION might be
   special here.
   
   > Like, if you've got a SELECT DISTINCT ON (a.x) ... FROM
   > ...lots...-type query, I think you can pretty much slap the DISTINCT
   > on there at any point in the join nest, probably ideally at the point
   > where the number of rows is the lowest it's going to get, or maybe
   > when the sortorder is convenient.  For a GROUP BY query with ungrouped
   > dependent columns, you can do the aggregation before or after those
   > joins, but you must do it after the joins that are needed to provide
   > all the values needed for the aggregated columns.  If you model this
   > with RelOptInfos, you're basically going to need a RelOptInfo to say
   > "i include these relids and these aggregation or setop operations".
   > So in the worst case each agg/setop doubles the number of RelOptInfos,
   > although probably in reality it doesn't because you won't have
   > infinite flexibility to reorder things.
   
   I think it's more like the number of possibilities doubles for each
   join that could commute with the aggregate.  But as you say the number
   of actual possibilities doesn't actually grow that fast.  I think it
   may be better to have each path track the relids and aggregates it
   covers, but then you need to have an efficient way to work out which
   rels/aggregates can be considered for each path.  Either sounds it
   sounds like quite a planner overhaul.
   
   Hope this helps,
   -- 
   Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
   > He who writes carelessly confesses thereby at the very outset that he does
   > not attach much importance to his own thoughts.
      -- Arthur Schopenhauer
   

8. Re: upper planner path-ification

   Ashutosh Bapat <ashutosh.bapat@enterprisedb.com> — 2015-05-15T04:41:38Z

   On Thu, May 14, 2015 at 7:09 AM, Robert Haas <robertmhaas@gmail.com> wrote:
   
   > Hi,
   >
   > I've been pulling over Tom's occasional remarks about redoing
   > grouping_planner - and maybe further layers of the planner - to work
   > with Paths instead of Plans.  I've had difficulty locating all of the
   > relevant threads.  Here's everything I've found so far, which I'm
   > pretty sure is not everything:
   >
   > http://www.postgresql.org/message-id/17400.1311716272@sss.pgh.pa.us
   > http://www.postgresql.org/message-id/2614.1375730493@sss.pgh.pa.us
   > http://www.postgresql.org/message-id/22721.1385048662@sss.pgh.pa.us
   >
   > http://www.postgresql.org/message-id/BANLkTinDjjFHNOzESG2J2U4GOkqLu69Zqg@mail.gmail.com
   > http://www.postgresql.org/message-id/8479.1418420018@sss.pgh.pa.us
   >
   > I think there are two separate problems here.  First, there's the
   > problem that grouping_planner() is complicated.  It's doing cost
   > comparisons, but all in ad-hoc fashion rather than using a consistent
   > mechanic the way add_path() does.  Generally, we can plan an aggregate
   > using either (1) a hashed aggregate, (2) a sorted aggregate, or (3)
   > for min or max, an index scan that just grabs the highest or lowest
   > value in lieu of a full table scan.  Instead of generating a plan for
   > each of these possibilities, we'd like to generate paths for each one,
   > and then pick one to turn into a plan.  AIUI, the hope is that this
   > would simplify the cost calculations, and also make it easier to
   > inject other paths, such as a path where an FDW performs the
   > aggregation step on the remote server.
   >
   > Second, there's the problem that we might like to order aggregates
   > with respect to joins.  If we have something like SELECT DISTINCT ON
   > (foo.x) foo.x, foo.y, bar.y FROM foo, bar WHERE foo.x = bar.x, then
   > (a) if foo.x has many duplicates, it will be better to DISTINCT-ify
   > foo and then join to bar afterwards but (b) if foo.x = bar.x is highly
   > selective, it will be better to join to bar first and then
   > DISTINCT-ify the result.  Currently, aggregation is always last;
   > that's not great.  Hitoshi Harada's proposed strategy of essentially
   > figuring out where the aggregation steps can go and then re-planning
   > for each one is also not great, because each join problem will be a
   > subtree of the one we use for the aggregate-last strategy, and thus
   > we're wasting effort by planning the same subtrees multiple times.
   > Instead, we might imagine letting grouping planner fish out the best
   > paths for the joinrels that represent possible aggregation points,
   > generate aggregation paths for each of those, and then work out what
   > additional rels need to be joined afterwards.  That sounds hard, but
   > not as hard as doing something sensible with what we have today.
   >
   >
   Another futuristic avenue for optimization would be commuting Append and
   Join when joining two similarly partitioned tables.
   
   
   > I'm inclined to think that it would be useful to solve the first
   > problem even if we didn't solve the second one right away (but that
   > might be wrong).  As a preparatory step, I'm thinking it would be
   > sensible to split grouping_planner() into an outer function that would
   > handle the addition of Limit and LockRows nodes and maybe planning of
   > set operations, and an inner function that would handle GROUP BY,
   > DISTINCT, and possibly window function planning.
   >
   > Thoughts?
   >
   > --
   > Robert Haas
   > EnterpriseDB: http://www.enterprisedb.com
   > The Enterprise PostgreSQL Company
   >
   >
   > --
   > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
   > To make changes to your subscription:
   > http://www.postgresql.org/mailpref/pgsql-hackers
   >
   
   
   
   -- 
   Best Wishes,
   Ashutosh Bapat
   EnterpriseDB Corporation
   The Postgres Database Company
   

9. Re: upper planner path-ification

   Ashutosh Bapat <ashutosh.bapat@enterprisedb.com> — 2015-05-15T05:32:19Z

   On Thu, May 14, 2015 at 8:24 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   
   > Robert Haas <robertmhaas@gmail.com> writes:
   > > On Wed, May 13, 2015 at 10:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   > >> For the reasons I mentioned, I'd like to get to a point where
   > >> subquery_planner's output is Paths not Plans as soon as possible.  But
   > the
   > >> idea of coarse representation of steps that we aren't trying to be smart
   > >> about might be useful to save some labor in the short run.
   > >>
   > >> The zero-order version of that might be a single Path node type that
   > >> represents "do whatever grouping_planner would do", which we'd start to
   > >> break down into multiple node types once we had the other APIs fixed.
   >
   > > The problem I'm really interested in solving is gaining the ability to
   > > add additional aggregation strategies, such as letting an FDW do it
   > > remotely, or doing it in parallel.  It seems to me that your proposed
   > > zero-order version of that wouldn't really get us terribly far toward
   > > that goal - it would be more oriented towards solving the other
   > > problems you mention, specifically adding more intelligence to setops
   > > and allowing parameterization of subqueries.  Those things certainly
   > > have some value, but I think supporting alternate aggregation
   > > strategies is a lot more interesting.
   >
   > Clearly we'd like to get to both goals.  I don't see the "zero order"
   > design as something we'd ship or even have in the tree for more than
   > a short time.  But it might still be a useful refactorization step.
   >
   > In any case, the key question if we're to have Paths representing
   > higher-level computations is "what do we hang our lists of such Paths
   > off of?".  If we have say both GROUP BY and LIMIT, it's important to
   > distinguish Paths that purport to do only the grouping step from those
   > that do both the grouping and the limit.  For the scan/join part of
   > planning, we do this by attaching the Paths to RelOptInfos that denote
   > various levels of joining ... but how does that translate to the higher
   > level processing steps?  Perhaps we could make dummy RelOptInfos that
   > correspond to having completed different steps of processing; but I've
   > not got a clear idea about how many such RelOptInfos we'd need, and
   > in particular not about whether we need to cater for completing those
   > steps in different orders.
   >
   >
   Given that the results of such computations are "relations", having a
   RelOptInfo for each operation looks natural. Although, Sort/Order, which
   doesn't alter the result-set but just re-orders it, may be an exception
   here. It can be modeled as a property of some RelOptInfo rather than
   modelling as a RelOptInfo by itself. Same might be the case of row locking
   operation.
   
   As Robert has mentioned earlier, reordering does open opportunities for
   optimizations and hence can not be ignored. If we are restructuring the
   planner, we should restructure to enable such reordering. One possible
   solution would be to imitate make_one_rel(). make_one_rel() creates
   possible relations (and paths for each of them) which represent joining
   order for a given joinlist. Similarly, given a list of operations requested
   by user, a function would generate relations (and paths for each of them)
   which represent possible orders of those operations (operations also
   include JOINs). But that might explode the number of relations (and hence
   paths) we examine during planning.
   
   
   >                         regards, tom lane
   >
   >
   > --
   > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
   > To make changes to your subscription:
   > http://www.postgresql.org/mailpref/pgsql-hackers
   >
   
   
   
   -- 
   Best Wishes,
   Ashutosh Bapat
   EnterpriseDB Corporation
   The Postgres Database Company
   

10. Re: upper planner path-ification

    Robert Haas <robertmhaas@gmail.com> — 2015-05-17T02:31:08Z

    On Wed, May 13, 2015 at 10:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    > For the reasons I mentioned, I'd like to get to a point where
    > subquery_planner's output is Paths not Plans as soon as possible.  But the
    > idea of coarse representation of steps that we aren't trying to be smart
    > about might be useful to save some labor in the short run.
    >
    > The zero-order version of that might be a single Path node type that
    > represents "do whatever grouping_planner would do", which we'd start to
    > break down into multiple node types once we had the other APIs fixed.
    
    So, getting back to this part, what's the value of returning a list of
    Paths rather than a list of Plans?  It seems that, in general terms,
    what we're trying to do is delay performing some of the work, so that
    we can generate several candidates relatively inexpensively and decide
    only later which one to turn into a Plan.  What's not entirely clear
    to me is which parts of the work we're trying to delay.  For example,
    target lists are normally computed when paths are converted to plans,
    but for the higher-level plan nodes adding by grouping_planner, the
    path list is typically just passed in.  So would the new path types be
    expected to carry target lists of their own, or would they need to
    figure out the target list on the fly at plan generation time?
    
    One thing that seems like it might complicate things here is that a
    lot of planner functions take PlannerInfo *root as an argument.  But
    if we generate only paths in grouping_planner() and path-ify them
    later, the subquery's root will not be available when we're trying to
    do the Path -> Plan transformation.  Presumably that means anything we
    need from the PlannerInfo has to be dug out and saved in the path.
    
    I think grouping_planner() is badly in need of some refactoring just
    to make it shorter.  It's over 1000 lines of code, which IMHO is a
    fairly ridiculous length for a single function.
    
    -- 
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
    
    
    

11. Re: upper planner path-ification

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2015-05-17T15:14:29Z

    >>>>> "Robert" == Robert Haas <robertmhaas@gmail.com> writes:
    
     Robert> I think grouping_planner() is badly in need of some refactoring
     Robert> just to make it shorter.  It's over 1000 lines of code, which
     Robert> IMHO is a fairly ridiculous length for a single function.
    
    If there's interest, we could do that specific task as part of adding
    hashagg support for grouping sets (which would otherwise make it even
    longer), or as preparatory work for that.
    
    -- 
    Andrew (irc:RhodiumToad)
    
    
    

12. Re: upper planner path-ification

    Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-17T15:34:26Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
    > "Robert" == Robert Haas <robertmhaas@gmail.com> writes:
    >  Robert> I think grouping_planner() is badly in need of some refactoring
    >  Robert> just to make it shorter.  It's over 1000 lines of code, which
    >  Robert> IMHO is a fairly ridiculous length for a single function.
    
    > If there's interest, we could do that specific task as part of adding
    > hashagg support for grouping sets (which would otherwise make it even
    > longer), or as preparatory work for that.
    
    I think that refactoring without changing anything about the way it works
    will be painful and probably ultimately a dead end.  As an example, the
    current_pathkeys local variable is state that's needed throughout that
    process, so you'd need some messy notation to pass it around (unless you
    stuck it into PlannerRoot, which would be ugly too).  But that would
    go away in a path-ified universe, because each Path would be marked as
    to its output sort order.  More, a lot of the code that you'd be
    relocating is code that we should be trying to get rid of altogether,
    not just relocate (to wit all the stuff that does cost-based comparisons
    of alternatives).
    
    So I'm all for refactoring, but I think it will happen as a natural
    byproduct of path-ification, and otherwise would be rather forced.
    
    			regards, tom lane
    
    
    

13. Re: upper planner path-ification

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2015-05-17T15:41:17Z

    >>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
    
     >> If there's interest, we could do that specific task as part of
     >> adding hashagg support for grouping sets (which would otherwise make
     >> it even longer), or as preparatory work for that.
    
     Tom> I think that refactoring without changing anything about the way
     Tom> it works will be painful and probably ultimately a dead end.  As
     Tom> an example, the current_pathkeys local variable is state that's
     Tom> needed throughout that process, so you'd need some messy notation
     Tom> to pass it around (unless you stuck it into PlannerRoot, which
     Tom> would be ugly too).  But that would go away in a path-ified
     Tom> universe, because each Path would be marked as to its output sort
     Tom> order.  More, a lot of the code that you'd be relocating is code
     Tom> that we should be trying to get rid of altogether, not just
     Tom> relocate (to wit all the stuff that does cost-based comparisons of
     Tom> alternatives).
    
     Tom> So I'm all for refactoring, but I think it will happen as a natural
     Tom> byproduct of path-ification, and otherwise would be rather forced.
    
    Hrm, ok. So for the near future, we should leave it more or less as-is?
    We don't have a timescale yet, but it's our intention to submit a
    hashagg support patch for grouping sets as soon as time permits.
    
    -- 
    Andrew (irc:RhodiumToad)
    
    
    

14. Re: upper planner path-ification

    Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-17T15:51:10Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
    > "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
    >  Tom> So I'm all for refactoring, but I think it will happen as a natural
    >  Tom> byproduct of path-ification, and otherwise would be rather forced.
    
    > Hrm, ok. So for the near future, we should leave it more or less as-is?
    > We don't have a timescale yet, but it's our intention to submit a
    > hashagg support patch for grouping sets as soon as time permits.
    
    Well, mumble.  I keep saying that I want to tackle path-ification in
    that area, and I keep not finding the time to actually do it.  So I'm
    hesitant to tell you that you should wait on it.  But certainly I think
    that it'll be a lot easier to get hashagg costing done in that framework
    than in what currently exists.
    
    			regards, tom lane
    
    
    

15. Re: upper planner path-ification

    Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-17T16:11:46Z

    Robert Haas <robertmhaas@gmail.com> writes:
    > So, getting back to this part, what's the value of returning a list of
    > Paths rather than a list of Plans?
    
    (1) less work, since we don't have to fill in details not needed for
        costing purposes;
    (2) paths carry info that the planner wants but the executor doesn't,
        notably sort-order annotations.
    
    > target lists are normally computed when paths are converted to plans,
    > but for the higher-level plan nodes adding by grouping_planner, the
    > path list is typically just passed in.  So would the new path types be
    > expected to carry target lists of their own, or would they need to
    > figure out the target list on the fly at plan generation time?
    
    Yeah, that is something I've been struggling with while thinking about
    this.  I don't really want to add tlists as such to Paths, but it's
    not very clear how else to annotate a Path as to what it computes,
    and that seems like an annotation we have to have in some form in order
    to convert these planning steps into a Path universe.
    
    There are other cases where it would be useful to have some notion of
    this kind.  An example is that right now, if you have an expression index
    on an expensive function and a query that wants the value of that function,
    the planner is able to extract the value from the index --- but there is
    nothing that gives any cost benefit to doing so, so it's just as likely
    to choose some other index and eat the cost of recalculating the function.
    It seems like the only way to fix that in a principled fashion is to have
    some concept that the index-scan Path can produce the function value,
    and then when we come to some appropriate costing step, penalize the other
    paths for having to compute the value that's available for free from this
    one.
    
    Rather than adding tlists per se to Paths, I've been vaguely toying with
    a notion of identifying all the "interesting" subexpressions in a query
    (expensive functions, aggregates, etc), giving them indexes 1..n, and then
    marking Paths with bitmapsets showing which interesting subexpressions
    they can produce values for.  This would make things like "does this Path
    compute all the needed aggregates" much cheaper to deal with than a raw
    tlist representation would do.  But maybe that's still not the best way.
    
    Another point is that a Path that computes aggregates is fundamentally
    different from a Path that doesn't, because it doesn't even produce the
    same number of rows.  So I'm not at all sure how to visualize the idea
    of a Path that computes only some aggregates, or whether it's even a
    sensible thing to worry about supporting.
    
    > One thing that seems like it might complicate things here is that a
    > lot of planner functions take PlannerInfo *root as an argument.  But
    > if we generate only paths in grouping_planner() and path-ify them
    > later, the subquery's root will not be available when we're trying to
    > do the Path -> Plan transformation.
    
    Ah, you're wrong there, because we hang onto the subquery's root already
    (I forget why exactly, but see PlannerGlobal.subroots for SubPlans, and
    RelOptInfo.subroot for subquery-in-FROM).  So it would not be a
    fundamental problem to postpone create_plan() for a subquery.
    
    > I think grouping_planner() is badly in need of some refactoring just
    > to make it shorter.  It's over 1000 lines of code, which IMHO is a
    > fairly ridiculous length for a single function.
    
    Amen to that.  But as I said to Andrew, I think this will be a side-effect
    of path-ification in this area, and is probably not something to set out
    to do first.
    
    			regards, tom lane
    
    
    

16. Re: upper planner path-ification

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2015-05-18T12:37:05Z

    >>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
    
     >> Hrm, ok. So for the near future, we should leave it more or less
     >> as-is?  We don't have a timescale yet, but it's our intention to
     >> submit a hashagg support patch for grouping sets as soon as time
     >> permits.
    
     Tom> Well, mumble.  I keep saying that I want to tackle path-ification
     Tom> in that area, and I keep not finding the time to actually do it.
     Tom> So I'm hesitant to tell you that you should wait on it.  But
     Tom> certainly I think that it'll be a lot easier to get hashagg
     Tom> costing done in that framework than in what currently exists.
    
    Incidentally, the most obvious obstacle to better planning of grouping
    sets in the sorted cases is not so much how to pick paths in
    grouping_planner itself, but rather the fact that query_planner wants to
    be given only one sort order. Is there any prospect for improvement
    there?
    
    -- 
    Andrew (irc:RhodiumToad)
    
    
    

17. Re: upper planner path-ification

    Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-18T14:12:04Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
    > Incidentally, the most obvious obstacle to better planning of grouping
    > sets in the sorted cases is not so much how to pick paths in
    > grouping_planner itself, but rather the fact that query_planner wants to
    > be given only one sort order. Is there any prospect for improvement
    > there?
    
    Hm.  That's a hangover from when query_planner also gave back a Plan
    (singular) rather than a set of Paths.  I don't see any fundamental reason
    why we couldn't generalize it to be a list of potentially useful output
    orderings rather than just one.  But I'm a bit concerned about the ensuing
    growth in planning time; is it really all that useful?
    
    			regards, tom lane
    
    
    

18. Re: upper planner path-ification

    Robert Haas <robertmhaas@gmail.com> — 2015-05-18T18:27:46Z

    On Sun, May 17, 2015 at 12:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    > Rather than adding tlists per se to Paths, I've been vaguely toying with
    > a notion of identifying all the "interesting" subexpressions in a query
    > (expensive functions, aggregates, etc), giving them indexes 1..n, and then
    > marking Paths with bitmapsets showing which interesting subexpressions
    > they can produce values for.  This would make things like "does this Path
    > compute all the needed aggregates" much cheaper to deal with than a raw
    > tlist representation would do.  But maybe that's still not the best way.
    
    I don't know, but it seems like this might be pulling in the opposite
    direction from your previously-stated desire to get subquery_planner
    to output Paths rather than Plans as soon as possible.  I'm inclined
    to think that we need to make a start on this in whatever way is
    simplest, and then refine it later.  Adding tlists to (some?) paths
    might not be the most beautiful way to get there, but there's a lot of
    important stuff piling up behind making some kind of a start on this
    refactoring, and we can't just keep postponing all of that stuff
    indefinitely.  Or if we do, the project as a whole will be worse off
    for it, I think.
    
    -- 
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
    
    
    

19. Re: upper planner path-ification

    Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-18T18:50:05Z

    Robert Haas <robertmhaas@gmail.com> writes:
    > On Sun, May 17, 2015 at 12:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    >> Rather than adding tlists per se to Paths, I've been vaguely toying with
    >> a notion of identifying all the "interesting" subexpressions in a query
    >> (expensive functions, aggregates, etc), giving them indexes 1..n, and then
    >> marking Paths with bitmapsets showing which interesting subexpressions
    >> they can produce values for.  This would make things like "does this Path
    >> compute all the needed aggregates" much cheaper to deal with than a raw
    >> tlist representation would do.  But maybe that's still not the best way.
    
    > I don't know, but it seems like this might be pulling in the opposite
    > direction from your previously-stated desire to get subquery_planner
    > to output Paths rather than Plans as soon as possible.
    
    Sorry, I didn't mean to suggest that that necessarily had to happen right
    away.
    
    What we do need right away, though, is *some* design for distinguishing
    Paths for the different possible upper-level steps.  I won't cry if we
    change it around later, but we have to have something to start with.
    
    So for the moment, let's assume that we still rigidly follow the sequence
    of upper-level steps currently embodied in grouping_planner.  (I'm not
    sure if it even makes sense to consider other orderings of those
    processing steps, but in any case we don't need to allow it on day zero.)
    Then, make a dummy RelOptInfo corresponding to the result of each step,
    and insert links to those in new fields in PlannerInfo.  (We create these
    *before* starting scan/join planning, so that FDWs, custom scans, etc, can
    inject paths into these RelOptInfos if they want, so as to represent cases
    like remote aggregation.)  Then just use add_path with the appropriate
    target RelOptInfo when producing different ways to do grouping etc.
    
    This is a bit ad-hoc but it would be a place to start.
    
    Comments?
    
    			regards, tom lane
    
    
    

20. Re: upper planner path-ification

    Simon Riggs <simon@2ndquadrant.com> — 2015-05-18T19:18:30Z

    On 18 May 2015 at 14:50, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    
    > Robert Haas <robertmhaas@gmail.com> writes:
    > > On Sun, May 17, 2015 at 12:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    > >> Rather than adding tlists per se to Paths, I've been vaguely toying with
    > >> a notion of identifying all the "interesting" subexpressions in a query
    > >> (expensive functions, aggregates, etc), giving them indexes 1..n, and
    > then
    > >> marking Paths with bitmapsets showing which interesting subexpressions
    > >> they can produce values for.  This would make things like "does this
    > Path
    > >> compute all the needed aggregates" much cheaper to deal with than a raw
    > >> tlist representation would do.  But maybe that's still not the best way.
    >
    > > I don't know, but it seems like this might be pulling in the opposite
    > > direction from your previously-stated desire to get subquery_planner
    > > to output Paths rather than Plans as soon as possible.
    >
    > Sorry, I didn't mean to suggest that that necessarily had to happen right
    > away.
    >
    > What we do need right away, though, is *some* design for distinguishing
    > Paths for the different possible upper-level steps.  I won't cry if we
    > change it around later, but we have to have something to start with.
    >
    > So for the moment, let's assume that we still rigidly follow the sequence
    > of upper-level steps currently embodied in grouping_planner.  (I'm not
    > sure if it even makes sense to consider other orderings of those
    > processing steps, but in any case we don't need to allow it on day zero.)
    > Then, make a dummy RelOptInfo corresponding to the result of each step,
    > and insert links to those in new fields in PlannerInfo.  (We create these
    > *before* starting scan/join planning, so that FDWs, custom scans, etc, can
    > inject paths into these RelOptInfos if they want, so as to represent cases
    > like remote aggregation.)  Then just use add_path with the appropriate
    > target RelOptInfo when producing different ways to do grouping etc.
    >
    > This is a bit ad-hoc but it would be a place to start.
    >
    > Comments?
    >
    
    My thinking was to push aggregation down to the lowest level possible in
    the plan, hopefully a single relation. That way we can generate paths for
    the current grouping_planner options as well as others, such as these
    
    * Push down aggregate prior to a join (which might then affect join
    planning)
    * Allow parallel queries to follow a
    scan-aggregate-collectfromslaves-aggregate strategy (hence need for double
    aggregation semantics)
    * Allow a lookaside to a Mat View rather than do a scan-aggregate (assume
    for now these are maintained correctly)
    * Allow a lookaside to an alternate datastore/mechanism via CustomScan
    (assume these are maintained correctly)
    
    all of which need to be costed against each other and the current
    strategies (aggregate last).
    
    The above proposal sounds like it will do that, but not completely sure.
    
    I'm assuming the O(N^2) Mat View planning problem can be solved in part by
    recognizing that many MVs are just single-table plus aggregates, and that
    we'd have a small enough number of MVs in play that search would not be a
    problem in practice.
    
    I'm also aware that LIMIT is still very badly optimized, so I'm hoping it
    helps there also.
    
    -- 
    Simon Riggs                http://www.2ndQuadrant.com/
    <http://www.2ndquadrant.com/>
    PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
    

21. Re: upper planner path-ification

    Tom Lane <tgl@sss.pgh.pa.us> — 2015-05-18T19:45:10Z

    Simon Riggs <simon@2ndQuadrant.com> writes:
    > On 18 May 2015 at 14:50, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    >> So for the moment, let's assume that we still rigidly follow the sequence
    >> of upper-level steps currently embodied in grouping_planner.  (I'm not
    >> sure if it even makes sense to consider other orderings of those
    >> processing steps, but in any case we don't need to allow it on day zero.)
    >> Then, make a dummy RelOptInfo corresponding to the result of each step,
    >> and insert links to those in new fields in PlannerInfo.  (We create these
    >> *before* starting scan/join planning, so that FDWs, custom scans, etc, can
    >> inject paths into these RelOptInfos if they want, so as to represent cases
    >> like remote aggregation.)  Then just use add_path with the appropriate
    >> target RelOptInfo when producing different ways to do grouping etc.
    >> 
    >> This is a bit ad-hoc but it would be a place to start.
    
    > My thinking was to push aggregation down to the lowest level possible in
    > the plan, hopefully a single relation.
    
    In this sketch, it's basically up to an FDW to recognize when remote
    aggregation is possible, and put a suitable ForeignScan path into the
    RelOptInfo that corresponds to "aggregate output".  It could do that for
    either a single foreign relation or a foreign join, if it had enough
    smarts.  This is more or less where we are today for foreign queries of
    all types: the responsibility is totally on the FDW to figure out whether
    it can optimize the query.  I have hopes that we can later provide some
    infrastructure that would assist FDWs in that, so they're not all
    reinventing the wheel.  But I don't yet have much idea what such
    infrastructure ought to look like, and it's probably hopeless to try to
    design it until things have stabilized more.
    
    Most of the other stuff you're talking about is entirely off the table
    until we think about ways that aggregation could be done below the top
    level, which this sketch isn't pretending to address.  I agree with
    Robert that that's probably best left till later.  There's a fair amount
    of work to do before we even have this much done.
    
    			regards, tom lane
    
    
    

22. Re: upper planner path-ification

    Robert Haas <robertmhaas@gmail.com> — 2015-05-18T19:49:17Z

    On Mon, May 18, 2015 at 2:50 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    >> I don't know, but it seems like this might be pulling in the opposite
    >> direction from your previously-stated desire to get subquery_planner
    >> to output Paths rather than Plans as soon as possible.
    >
    > Sorry, I didn't mean to suggest that that necessarily had to happen right
    > away.
    >
    > What we do need right away, though, is *some* design for distinguishing
    > Paths for the different possible upper-level steps.  I won't cry if we
    > change it around later, but we have to have something to start with.
    
    That sounds good to me.
    
    > So for the moment, let's assume that we still rigidly follow the sequence
    > of upper-level steps currently embodied in grouping_planner.  (I'm not
    > sure if it even makes sense to consider other orderings of those
    > processing steps, but in any case we don't need to allow it on day zero.)
    > Then, make a dummy RelOptInfo corresponding to the result of each step,
    > and insert links to those in new fields in PlannerInfo.  (We create these
    > *before* starting scan/join planning, so that FDWs, custom scans, etc, can
    > inject paths into these RelOptInfos if they want, so as to represent cases
    > like remote aggregation.)  Then just use add_path with the appropriate
    > target RelOptInfo when producing different ways to do grouping etc.
    >
    > This is a bit ad-hoc but it would be a place to start.
    >
    > Comments?
    
    That sounds reasonable, but I think the key thing is to nail down what
    the new Path types are going to look like.  If we know that, then
    rearranging grouping_planner becomes a matter of adjusting things
    piece by piece for the new data structures.  Or at least I think it
    does.
    
    I think it would also be an excellent idea to split each of those
    "upper level steps" embodied in grouping_planner into its own
    function.
    
    -- 
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
    
    
    

23. Re: upper planner path-ification

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2015-05-19T11:19:55Z

    >>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
    
     Tom> Hm.  That's a hangover from when query_planner also gave back a
     Tom> Plan (singular) rather than a set of Paths.  I don't see any
     Tom> fundamental reason why we couldn't generalize it to be a list of
     Tom> potentially useful output orderings rather than just one.  But I'm
     Tom> a bit concerned about the ensuing growth in planning time; is it
     Tom> really all that useful?
    
    The planning time growth is a possible concern, yes. The potential gain
    is eliminating one sort step, in the case when the input has a usable
    sorted path but grouping_planner happens not to ask for it (when there's
    more than just a single rollup, the code currently asks for one of the
    sort orders pretty much arbitrarily since it has no real way to know
    otherwise). Whether that would justify it... I don't know. Maybe that's
    one to save for later to see if there's any feedback from actual use.
    
    -- 
    Andrew (irc:RhodiumToad)
    
    
    

24. Re: upper planner path-ification

    Robert Haas <robertmhaas@gmail.com> — 2015-05-19T13:04:00Z

    On Tue, May 19, 2015 at 7:19 AM, Andrew Gierth
    <andrew@tao11.riddles.org.uk> wrote:
    >>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
    >  Tom> Hm.  That's a hangover from when query_planner also gave back a
    >  Tom> Plan (singular) rather than a set of Paths.  I don't see any
    >  Tom> fundamental reason why we couldn't generalize it to be a list of
    >  Tom> potentially useful output orderings rather than just one.  But I'm
    >  Tom> a bit concerned about the ensuing growth in planning time; is it
    >  Tom> really all that useful?
    >
    > The planning time growth is a possible concern, yes. The potential gain
    > is eliminating one sort step, in the case when the input has a usable
    > sorted path but grouping_planner happens not to ask for it (when there's
    > more than just a single rollup, the code currently asks for one of the
    > sort orders pretty much arbitrarily since it has no real way to know
    > otherwise). Whether that would justify it... I don't know. Maybe that's
    > one to save for later to see if there's any feedback from actual use.
    
    I kind of doubt that the growth in planning time would be anything too
    unreasonable.  We already consider multiple orderings for ordinary
    base relations, so it's not very obvious why consideration multiple
    orderings for subqueries would be any worse.  If we can arrange to
    throw away useless orderings early, as we do in other cases, then any
    extra paths we consider have a reasonable chance of being useful.
    
    -- 
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
    
    
    

25. Re: upper planner path-ification

    Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> — 2015-05-20T02:06:02Z

    At Tue, 19 May 2015 09:04:00 -0400, Robert Haas <robertmhaas@gmail.com> wrote in <CA+TgmobAV3_DS1sXA+PFWkjvX1K-VNiAnMMJrzPfD43g=-4OYA@mail.gmail.com>
    > On Tue, May 19, 2015 at 7:19 AM, Andrew Gierth
    > <andrew@tao11.riddles.org.uk> wrote:
    > >>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
    > >  Tom> Hm.  That's a hangover from when query_planner also gave back a
    > >  Tom> Plan (singular) rather than a set of Paths.  I don't see any
    > >  Tom> fundamental reason why we couldn't generalize it to be a list of
    > >  Tom> potentially useful output orderings rather than just one.  But I'm
    > >  Tom> a bit concerned about the ensuing growth in planning time; is it
    > >  Tom> really all that useful?
    > >
    > > The planning time growth is a possible concern, yes. The potential gain
    > > is eliminating one sort step, in the case when the input has a usable
    > > sorted path but grouping_planner happens not to ask for it (when there's
    > > more than just a single rollup, the code currently asks for one of the
    > > sort orders pretty much arbitrarily since it has no real way to know
    > > otherwise). Whether that would justify it... I don't know. Maybe that's
    > > one to save for later to see if there's any feedback from actual use.
    > 
    > I kind of doubt that the growth in planning time would be anything too
    > unreasonable.  We already consider multiple orderings for ordinary
    > base relations, so it's not very obvious why consideration multiple
    > orderings for subqueries would be any worse.  If we can arrange to
    > throw away useless orderings early, as we do in other cases, then any
    > extra paths we consider have a reasonable chance of being useful.
    
    Though I don't think that the simple path-ification of what is
    currently done make it grow in any degree, it could rapidly grow
    if we unconditionally construct extra upper-paths using the
    previously-abandoned extra paths or make them involved in join
    considerations. But the growth in planning time could be kept
    reasonable if we pay attention so that, as we have done so, the
    additional optimization schemes to have simple and precise
    bailing-out logic even if they require some complicated
    calculation or yields more extra paths.
    
    regards,
    
    -- 
    Kyotaro Horiguchi
    NTT Open Source Software Center
    
    
    
    

26. Re: upper planner path-ification

    Kouhei Kaigai <kaigai@ak.jp.nec.com> — 2015-06-23T01:55:20Z

    > -----Original Message-----
    > From: pgsql-hackers-owner@postgresql.org
    > [mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Robert Haas
    > Sent: Thursday, May 14, 2015 10:39 AM
    > To: pgsql-hackers@postgresql.org; Tom Lane
    > Subject: [HACKERS] upper planner path-ification
    > 
    > Hi,
    > 
    > I've been pulling over Tom's occasional remarks about redoing
    > grouping_planner - and maybe further layers of the planner - to work
    > with Paths instead of Plans.  I've had difficulty locating all of the
    > relevant threads.  Here's everything I've found so far, which I'm
    > pretty sure is not everything:
    > 
    > http://www.postgresql.org/message-id/17400.1311716272@sss.pgh.pa.us
    > http://www.postgresql.org/message-id/2614.1375730493@sss.pgh.pa.us
    > http://www.postgresql.org/message-id/22721.1385048662@sss.pgh.pa.us
    > http://www.postgresql.org/message-id/BANLkTinDjjFHNOzESG2J2U4GOkqLu69Zqg@mai
    > l.gmail.com
    > http://www.postgresql.org/message-id/8479.1418420018@sss.pgh.pa.us
    > 
    > I think there are two separate problems here.  First, there's the
    > problem that grouping_planner() is complicated.  It's doing cost
    > comparisons, but all in ad-hoc fashion rather than using a consistent
    > mechanic the way add_path() does.  Generally, we can plan an aggregate
    > using either (1) a hashed aggregate, (2) a sorted aggregate, or (3)
    > for min or max, an index scan that just grabs the highest or lowest
    > value in lieu of a full table scan.  Instead of generating a plan for
    > each of these possibilities, we'd like to generate paths for each one,
    > and then pick one to turn into a plan.  AIUI, the hope is that this
    > would simplify the cost calculations, and also make it easier to
    > inject other paths, such as a path where an FDW performs the
    > aggregation step on the remote server.
    > 
    > Second, there's the problem that we might like to order aggregates
    > with respect to joins.  If we have something like SELECT DISTINCT ON
    > (foo.x) foo.x, foo.y, bar.y FROM foo, bar WHERE foo.x = bar.x, then
    > (a) if foo.x has many duplicates, it will be better to DISTINCT-ify
    > foo and then join to bar afterwards but (b) if foo.x = bar.x is highly
    > selective, it will be better to join to bar first and then
    > DISTINCT-ify the result.  Currently, aggregation is always last;
    > that's not great.  Hitoshi Harada's proposed strategy of essentially
    > figuring out where the aggregation steps can go and then re-planning
    > for each one is also not great, because each join problem will be a
    > subtree of the one we use for the aggregate-last strategy, and thus
    > we're wasting effort by planning the same subtrees multiple times.
    > Instead, we might imagine letting grouping planner fish out the best
    > paths for the joinrels that represent possible aggregation points,
    > generate aggregation paths for each of those, and then work out what
    > additional rels need to be joined afterwards.  That sounds hard, but
    > not as hard as doing something sensible with what we have today.
    >
    Once we support to add aggregation path during path consideration,
    we need to pay attention morphing of the final target-list according
    to the intermediate path combination, tentatively chosen.
    For example, if partial-aggregation makes sense from cost perspective;
    like SUM(NRows) of partial COUNT(*) AS NRows instead of COUNT(*) on
    billion rows, planner also has to adjust the final target-list according
    to the interim paths. In this case, final output shall be SUM(), instead
    of COUNT().
    
    I think, this planner enhancement needs a mechanism to inform planner
    expected final output for each Path. It means, individual Path node
    can have a replacement rule: which target-entry should have what
    expression instead, once this path is applied.
    In above case, PartialAggPath will have an indication; SUM(nrows)
    shall be applied on the location where "COUNT(*)" is originally
    placed.
    
    In case of relations join that involves paths with this replacement
    rules, it may be a bit complicated if an expression takes argument
    come from both relations; like CORR(inner_rel.X, outer_rel.Y),
    I'm not sure whether we can have more broken-down partial aggregate.
    However, relations on either of inner/outer side are responsible to
    the columns in inner/outer side. Unless all the arguments in aggregate
    function come from same side, it should not block aggregate push-
    down as long as estimated cost makes sense.
    
    That is a probably makes a problem when we allow to add aggregate
    path as a part of partial plan tree.
    
    Thanks,
    
    
    > I'm inclined to think that it would be useful to solve the first
    > problem even if we didn't solve the second one right away (but that
    > might be wrong).  As a preparatory step, I'm thinking it would be
    > sensible to split grouping_planner() into an outer function that would
    > handle the addition of Limit and LockRows nodes and maybe planning of
    > set operations, and an inner function that would handle GROUP BY,
    > DISTINCT, and possibly window function planning.
    > 
    > Thoughts?
    >
    --
    NEC Business Creation Division / PG-Strom Project
    KaiGai Kohei <kaigai@ak.jp.nec.com>
    
    
    

27. Re: upper planner path-ification

    David Rowley <david.rowley@2ndquadrant.com> — 2015-06-23T05:05:32Z

    On 23 June 2015 at 13:55, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
    
    > Once we support to add aggregation path during path consideration,
    > we need to pay attention morphing of the final target-list according
    > to the intermediate path combination, tentatively chosen.
    > For example, if partial-aggregation makes sense from cost perspective;
    > like SUM(NRows) of partial COUNT(*) AS NRows instead of COUNT(*) on
    > billion rows, planner also has to adjust the final target-list according
    > to the interim paths. In this case, final output shall be SUM(), instead
    > of COUNT().
    >
    >
    This sounds very much like what's been discussed here:
    
    http://www.postgresql.org/message-id/CA+U5nMJ92azm0Yt8TT=hNxFP=VjFhDqFpaWfmj+66-4zvCGv3w@mail.gmail.com
    
    
    The basic concept is that we add another function set to aggregates that
    allow the combination of 2 states. For the case of MIN() and MAX() this
    will just be the same as the transfn. SUM() is similar for many types, more
    complex for others. I've quite likely just borrowed SUM(BIGINT)'s transfer
    functions to allow COUNT()'s to be combined.
    
    More time does need spent inventing the new combining functions that don't
    currently exist, but that shouldn't matter as it can be done later.
    
    Commitfest link to patch here https://commitfest.postgresql.org/5/131/
    
    I see you've signed up to review it!
    
    Regards
    
    David Rowley
    
    --
     David Rowley                   http://www.2ndQuadrant.com/
    <http://www.2ndquadrant.com/>
     PostgreSQL Development, 24x7 Support, Training & Services
    

28. Re: upper planner path-ification

    Kouhei Kaigai <kaigai@ak.jp.nec.com> — 2015-06-23T08:41:07Z

    > -----Original Message-----
    > From: David Rowley [mailto:david.rowley@2ndquadrant.com]
    > Sent: Tuesday, June 23, 2015 2:06 PM
    > To: Kaigai Kouhei(海外 浩平)
    > Cc: Robert Haas; pgsql-hackers@postgresql.org; Tom Lane
    > Subject: Re: [HACKERS] upper planner path-ification
    > 
    > 
    > On 23 June 2015 at 13:55, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
    > 
    > 
    > 	Once we support to add aggregation path during path consideration,
    > 	we need to pay attention morphing of the final target-list according
    > 	to the intermediate path combination, tentatively chosen.
    > 	For example, if partial-aggregation makes sense from cost perspective;
    > 	like SUM(NRows) of partial COUNT(*) AS NRows instead of COUNT(*) on
    > 	billion rows, planner also has to adjust the final target-list according
    > 	to the interim paths. In this case, final output shall be SUM(), instead
    > 	of COUNT().
    > 
    > 
    > 
    > 
    > This sounds very much like what's been discussed here:
    > 
    > http://www.postgresql.org/message-id/CA+U5nMJ92azm0Yt8TT=hNxFP=VjFhDqFpaWfmj
    > +66-4zvCGv3w@mail.gmail.com
    > 
    > 
    > The basic concept is that we add another function set to aggregates that allow
    > the combination of 2 states. For the case of MIN() and MAX() this will just be
    > the same as the transfn. SUM() is similar for many types, more complex for others.
    > I've quite likely just borrowed SUM(BIGINT)'s transfer functions to allow
    > COUNT()'s to be combined.
    >
    STDDEV, VARIANCE and relevant can be constructed using nrows, sum(X) and sum(X^2).
    REGR_*, COVAR_* and relevant can be constructed using nrows, sum(X), sum(Y),
    sum(X^2), sum(Y^2) and sum(X*Y).
    
    Let me introduce a positive side effect of this approach.
    Because final aggregate function processes values already aggregated partially,
    the difference between the state value and transition value gets relatively small.
    It reduces accidental errors around floating-point calculation. :-)
    
    > More time does need spent inventing the new combining functions that don't
    > currently exist, but that shouldn't matter as it can be done later.
    > 
    > Commitfest link to patch here https://commitfest.postgresql.org/5/131/
    > 
    > I see you've signed up to review it!
    >
    Yes, all of us looks at same direction.
    
    Problem is, we have to cross the mountain of the planner enhancement to reach
    all the valuable:
     - parallel aggregation
     - aggregation before join
     - remote aggregation via FDW
    
    So, unless we don't find out a solution around planner, 2-phase aggregation is
    like a curry without rice....
    
    Thanks,
    --
    NEC Business Creation Division / PG-Strom Project
    KaiGai Kohei <kaigai@ak.jp.nec.com>
    
    
    

29. Re: upper planner path-ification

    Kouhei Kaigai <kaigai@ak.jp.nec.com> — 2015-06-23T09:05:43Z

    > -----Original Message-----
    > From: pgsql-hackers-owner@postgresql.org
    > [mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Tom Lane
    > Sent: Monday, May 18, 2015 1:12 AM
    > To: Robert Haas
    > Cc: pgsql-hackers@postgresql.org
    > Subject: Re: [HACKERS] upper planner path-ification
    > 
    > Robert Haas <robertmhaas@gmail.com> writes:
    > > So, getting back to this part, what's the value of returning a list of
    > > Paths rather than a list of Plans?
    > 
    > (1) less work, since we don't have to fill in details not needed for
    >     costing purposes;
    > (2) paths carry info that the planner wants but the executor doesn't,
    >     notably sort-order annotations.
    > 
    > > target lists are normally computed when paths are converted to plans,
    > > but for the higher-level plan nodes adding by grouping_planner, the
    > > path list is typically just passed in.  So would the new path types be
    > > expected to carry target lists of their own, or would they need to
    > > figure out the target list on the fly at plan generation time?
    > 
    > Yeah, that is something I've been struggling with while thinking about
    > this.  I don't really want to add tlists as such to Paths, but it's
    > not very clear how else to annotate a Path as to what it computes,
    > and that seems like an annotation we have to have in some form in order
    > to convert these planning steps into a Path universe.
    > 
    > There are other cases where it would be useful to have some notion of
    > this kind.  An example is that right now, if you have an expression index
    > on an expensive function and a query that wants the value of that function,
    > the planner is able to extract the value from the index --- but there is
    > nothing that gives any cost benefit to doing so, so it's just as likely
    > to choose some other index and eat the cost of recalculating the function.
    > It seems like the only way to fix that in a principled fashion is to have
    > some concept that the index-scan Path can produce the function value,
    > and then when we come to some appropriate costing step, penalize the other
    > paths for having to compute the value that's available for free from this
    > one.
    > 
    > Rather than adding tlists per se to Paths, I've been vaguely toying with
    > a notion of identifying all the "interesting" subexpressions in a query
    > (expensive functions, aggregates, etc), giving them indexes 1..n, and then
    > marking Paths with bitmapsets showing which interesting subexpressions
    > they can produce values for.  This would make things like "does this Path
    > compute all the needed aggregates" much cheaper to deal with than a raw
    > tlist representation would do.  But maybe that's still not the best way.
    >
    Hmm.... it seems to me a little bit complicated than flat expression node.
    
    > Another point is that a Path that computes aggregates is fundamentally
    > different from a Path that doesn't, because it doesn't even produce the
    > same number of rows.  So I'm not at all sure how to visualize the idea
    > of a Path that computes only some aggregates, or whether it's even a
    > sensible thing to worry about supporting.
    >
    I expect partial aggregate shall be done per a particular input stream,
    not per aggregate function. In other words, once planner determined
    a relation scan/join has advantage to run partial aggregate, all the
    aggregate functions that consume rows produced by this scan/join have
    to have partial aggregate / final aggregate form, doesn't it?
    If so, number of rows to be returned is associated with a Path.
    
    For example, when we break down a query below using 2-phase aggregation,
    
      SELECT t1.cat, avg(t2.x) FROM t1 JOIN t2 ON t1.id_1 = t2.id_2 GROUP BY t1.cat;
    
    expected plan is as shown below, isn't it?
    
      FinalAgg (nrows=100)
          tlist: t1.cat, avg(nrows, sum(t2.x))
          grouping key: t1.cat
       -> HashJoin (nrows=1000)
          tlist: t1.cat, count(t2.x) nrows, sum(t2.x)
           -> PartialAgg (nrows=1000)
              tlist: count(t2.x) nrows, sum(t2.x), t2.id_2
              grouping key: t2.id_2
               -> SeqScan on t2 (nrows=100000000)
           -> Hash
               -> SeqScan on t1 (nrows=100)
    
    It is clear that PartialAgg consumes 100000000 rows, then output 1000
    rows because of partial reduction. All the partial aggregation on this
    node will work in a coordinated manner.
    
    Do you have another vision for the partial aggregation behavior?
    
    
    > > One thing that seems like it might complicate things here is that a
    > > lot of planner functions take PlannerInfo *root as an argument.  But
    > > if we generate only paths in grouping_planner() and path-ify them
    > > later, the subquery's root will not be available when we're trying to
    > > do the Path -> Plan transformation.
    > 
    > Ah, you're wrong there, because we hang onto the subquery's root already
    > (I forget why exactly, but see PlannerGlobal.subroots for SubPlans, and
    > RelOptInfo.subroot for subquery-in-FROM).  So it would not be a
    > fundamental problem to postpone create_plan() for a subquery.
    > 
    > > I think grouping_planner() is badly in need of some refactoring just
    > > to make it shorter.  It's over 1000 lines of code, which IMHO is a
    > > fairly ridiculous length for a single function.
    > 
    > Amen to that.  But as I said to Andrew, I think this will be a side-effect
    > of path-ification in this area, and is probably not something to set out
    > to do first.
    >
    
    --
    NEC Business Creation Division / PG-Strom Project
    KaiGai Kohei <kaigai@ak.jp.nec.com>
    
    
    
    

30. Re: upper planner path-ification

    Robert Haas <robertmhaas@gmail.com> — 2015-06-23T13:18:06Z

    On Tue, Jun 23, 2015 at 4:41 AM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
    > So, unless we don't find out a solution around planner, 2-phase aggregation is
    > like a curry without rice....
    
    Simon and I spoke with Tom about this upper planner path-ification
    problem at PGCon, and he indicated that he intended to work on it
    soon, and that we should bug him about it if he doesn't.
    
    I'm pleased to here this as I seem to have a special talent in that area.
    
    -- 
    Robert Haas
    EnterpriseDB: http://www.enterprisedb.com
    The Enterprise PostgreSQL Company
    
    
    

31. Re: upper planner path-ification

    Kouhei Kaigai <kaigai@ak.jp.nec.com> — 2015-06-24T00:42:23Z

    > -----Original Message-----
    > From: pgsql-hackers-owner@postgresql.org
    > [mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Robert Haas
    > Sent: Tuesday, June 23, 2015 10:18 PM
    > To: Kaigai Kouhei(海外 浩平)
    > Cc: David Rowley; pgsql-hackers@postgresql.org; Tom Lane
    > Subject: Re: [HACKERS] upper planner path-ification
    > 
    > On Tue, Jun 23, 2015 at 4:41 AM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
    > > So, unless we don't find out a solution around planner, 2-phase aggregation is
    > > like a curry without rice....
    > 
    > Simon and I spoke with Tom about this upper planner path-ification
    > problem at PGCon, and he indicated that he intended to work on it
    > soon, and that we should bug him about it if he doesn't.
    > 
    > I'm pleased to here this as I seem to have a special talent in that area.
    >
    It's fantastic support arm.
    
    So, it may be more productive to pay my efforts for investigation
    of David Rowley's patch, based on the assumption if we can add
    partial/final-aggregation path node as if scan/join-paths.
    
    My interest also stands on his infrastructure.
      https://cs.uwaterloo.ca/research/tr/1993/46/file.pdf
    It is a bit old paper but good starting point.
    
    Thanks,
    --
    NEC Business Creation Division / PG-Strom Project
    KaiGai Kohei <kaigai@ak.jp.nec.com>