Thread: Re: Disabling options lowers the estimated cost of a query

On 2/26/21 4:00 AM, Tom Lane wrote:
> Arne Roland <A.Roland@index.de> writes:
>> I want to examine the exhaustive search and not the geqo here. I'd
>> expect the exhaustive search to give the plan with the lowest cost,
>> but apparently it doesn't. I have found a few dozen different
>> querys where that isn't the case. I attached one straight forward
>> example. For the join of two partitions a row first approach would
>> have been reasonable.
> 
> Hmm.  While the search should be exhaustive, there are pretty
> aggressive pruning heuristics (mostly in and around add_path()) that
> can cause us to drop paths that don't seem to be enough better than
> other alternatives. I suspect that the seqscan plan may have beaten
> out the other one at some earlier stage that didn't think that the
> startup-cost advantage was sufficient reason to keep it.
> 
> It's also possible that you've found a bug.  I notice that both plans
> are using incremental sort, which has been, um, rather buggy. Hard to
> tell without a concrete test case to poke at.
> 

Well, it's true incremental sort was not exactly bug free. But I very
much doubt it's causing this issue, for two reasons:

(a) It's trivial to simplify the reproducer further, so that there are
no incremental sort nodes. See the attached script, which has just a
single partition.

(b) The incremental sort patch does not really tweak the costing or
add_path in ways that would break this.

(c) PostgreSQL 12 has the same issue.


It seems the whole problem is in generate_orderedappend_paths(), which
simply considers two cases - paths with minimal startup cost and paths
with minimal total costs. But with LIMIT that does not work, of course.

With the simplified reproducer, I get these two plans:


                               QUERY PLAN
  -------------------------------------------------------------------
   Limit  (cost=9748.11..10228.11 rows=10000 width=8)
     ->  Merge Left Join (cost=9748.11..14548.11 rows=100000 width=8)
           Merge Cond: (a.id = b.id)
           ->  Index Only Scan Backward using a0_pkey on a0 a
               (cost=0.29..3050.29 rows=100000 width=8)
           ->  Sort  (cost=9747.82..9997.82 rows=100000 width=8)
                 Sort Key: b.id DESC
                 ->  Seq Scan on b0 b
                     (cost=0.00..1443.00 rows=100000 width=8)
  (7 rows)

                               QUERY PLAN
  -------------------------------------------------------------------
   Limit  (cost=0.58..3793.16 rows=10000 width=8)
     ->  Nested Loop Left Join (cost=0.58..37926.29 rows=100000 ...)
           ->  Index Only Scan Backward using a0_pkey on a0 a
               (cost=0.29..3050.29 rows=100000 width=8)
           ->  Index Only Scan using b0_pkey on b0 b
               (cost=0.29..0.34 rows=1 width=8)
                 Index Cond: (id = a.id)
  (5 rows)


The reason is quite simple - we get multiple join paths for each child
(not visible in the plans, because there's just a single partition),
with these costs:

    A: nestloop_path   startup 0.585000    total 35708.292500
    B: nestloop_path   startup 0.292500    total 150004297.292500
    C: mergejoin_path  startup 9748.112737 total 14102.092737

The one we'd like is the nestloop (A), and with disabled partition-wise
join that's what we pick. But generate_orderedappend_paths calls
get_cheapest_path_for_pathkeys for startup/total cost, and gets the two
other paths. Clearly, nestlop (B) is pretty terrible for LIMIT, because
of the high total cost, and mergejoin (C) is what we end up with.

Not sure how to fix this without making generate_orderedappend_paths way
more complicated ...


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Tomas Vondra <tomas.vondra@enterprisedb.com> writes:
> On 2/26/21 4:00 AM, Tom Lane wrote:
>> Hmm.  While the search should be exhaustive, there are pretty
>> aggressive pruning heuristics (mostly in and around add_path()) that
>> can cause us to drop paths that don't seem to be enough better than
>> other alternatives. I suspect that the seqscan plan may have beaten
>> out the other one at some earlier stage that didn't think that the
>> startup-cost advantage was sufficient reason to keep it.

> It seems the whole problem is in generate_orderedappend_paths(), which
> simply considers two cases - paths with minimal startup cost and paths
> with minimal total costs. But with LIMIT that does not work, of course.

Ah, I see.

> Not sure how to fix this without making generate_orderedappend_paths way
> more complicated ...

You could, if root->tuple_fraction is > 0, also make a set of paths that
are optimized for that fetch fraction.  This is cheating to some extent,
because it's only entirely accurate when your rel is the only one, but it
seems better than ignoring the issue altogether.  The code to select the
right child path would be approximately like get_cheapest_fractional_path,
except that you need to restrict it to paths with the right sort order.

            regards, tom lane

I wrote:
> ... The code to select the
> right child path would be approximately like get_cheapest_fractional_path,
> except that you need to restrict it to paths with the right sort order.

Duh, I forgot about get_cheapest_fractional_path_for_pathkeys().

            regards, tom lane

Hi,

On 4/16/21 3:09 PM, Tom Lane wrote:
> I wrote:
>> ... The code to select the
>> right child path would be approximately like get_cheapest_fractional_path,
>> except that you need to restrict it to paths with the right sort order.
> 
> Duh, I forgot about get_cheapest_fractional_path_for_pathkeys().
> 
>             regards, tom lane
> 

The attached patch does fix the issue for me, producing the same plans
with and without partition-wise joins.

It probably needs a bit more work, though:

1) If get_cheapest_fractional_path_for_pathkeys returns NULL, it's not
clear whether to use cheapest_startup or cheapest_total with Sort on
top. Or maybe consider an incremental sort?

2) Same for the cheapest_total - maybe there's a partially sorted path,
and using it with incremental sort on top would be better than using
cheapest_total_path + sort.

3) Not sure if get_cheapest_fractional_path_for_pathkeys should worry
about require_parallel_safe too.


Doesn't seem like an urgent issue (has been there for a while, not sure
we even want to backpatch it). I'll add this to the next CF.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company