Thread

1. MergeAppend costing

   Robert Haas <robertmhaas@gmail.com> — 2010-11-17T19:04:37Z

   See the attached test case.  With that setup, this uses MergeAppend:
   
   explain select * from ma_parent order by id limit 10;
   
   But this one does not:
   
   explain select * from ma_parent order by name limit 10;
   
   ...which seems odd, because the index on ma_child1 and sorting the
   other two ought to still be better than appending all three and
   sorting the whole thing.  If you drop ma_child2, you get MergeAppend
   again:
   
   begin;
   drop table ma_child2;
   explain select * from ma_parent order by name limit 10;
   rollback;
   
   ...which makes me wonder if our costing model is off?
   
   -- 
   Robert Haas
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   

2. Re: MergeAppend costing

   Tom Lane <tgl@sss.pgh.pa.us> — 2010-11-17T23:11:15Z

   Robert Haas <robertmhaas@gmail.com> writes:
   > See the attached test case.  With that setup, this uses MergeAppend:
   > explain select * from ma_parent order by id limit 10;
   
   > But this one does not:
   
   > explain select * from ma_parent order by name limit 10;
   
   > ...which seems odd, because the index on ma_child1 and sorting the
   > other two ought to still be better than appending all three and
   > sorting the whole thing.
   
   Not really; what you're not accounting for is that the top-level sort
   is a lot cheaper than a full sort of the large child relation would be,
   because it gets hacked to do a top-N sort instead of a full sort.
   
   What this example suggests is that we should consider ways to pass
   down the top-N-ness to sorts executed as part of a MergeAppend tree.
   That seems a tad messy though, both in the executor and the planner.
   
   			regards, tom lane
   
   

3. Re: MergeAppend costing

   Tom Lane <tgl@sss.pgh.pa.us> — 2010-11-18T03:54:34Z

   I wrote:
   > What this example suggests is that we should consider ways to pass
   > down the top-N-ness to sorts executed as part of a MergeAppend tree.
   > That seems a tad messy though, both in the executor and the planner.
   
   Actually the executor side of it doesn't seem too bad.  A Limit node
   already pokes the limit value into its child Sort node, and if that
   doesn't make you gag, then recursing down through MergeAppend to poke
   grandchild Sort nodes shouldn't either.
   
   The planner is a bit messier: we really need to know the effective limit
   value in create_merge_append_path in order to generate the right path
   cost estimates, and that's many call levels removed from where the limit
   is currently available.  I think the least invasive way to do it is to
   add the constant limit value (if known) as a field in PlannerInfo.
   If that's set, *and* the MergeAppendPath is being made for the only "base
   relation" in the query (ie, no joins allowed) then apply the limit while
   costing any sorts needed.
   
   Any objections to that approach?
   
   BTW, while looking at this I came to the conclusion that the limit value
   is being improperly applied in query_planner() ATM.  We factor it into
   a cost_sort call there, even in cases where the query has GROUP BY or
   DISTINCT; but in such cases the tuples emitted from the join tree don't
   necessarily each produce a result tuple, so it's wrong to assume that
   "LIMIT n" means we can stop after n tuples.  The effects of this are
   probably relatively marginal, but it could cause us to make the wrong
   decision about whether sorting is cheaper than a presorted path.
   
   			regards, tom lane