Re: PATCH: generate fractional cheapest paths in generate_orderedappend_path

 Hi!

> From: Tomas Vondra <tomas.vondra@enterprisedb.com>
> Subject: Re: PATCH: generate fractional cheapest paths in generate_orderedappend_path
>  
> test-# SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2)
> ORDER BY id1 ASC, id2 ASC LIMIT 10;
>                                    QUERY PLAN
>
> ------------------------------------------------------------------------------
>   Limit
>     ->  Merge Left Join
>           Merge Cond: ((x.id1 = y.id1) AND (x.id2 = y.id2))
>           ->  Append
>                 ->  Index Only Scan using fract_t0_id1_id2_idx on
>                                           fract_t0 x_1
>                 ->  Incremental Sort
>                       Sort Key: x_2.id1, x_2.id2
>                       Presorted Key: x_2.id1
>                       ->  Index Scan using fract_t1_pkey on fract_t1 x_2
>           ->  Materialize
>                 ->  Append
>                       ->  Incremental Sort
>                             Sort Key: y_1.id1, y_1.id2
>                             Presorted Key: y_1.id1
>                             ->  Index Scan using fract_t0_pkey on
>                                                  fract_t0 y_1
>                                   Index Cond: (id1 = id1)
>                                   Filter: (id2 = id2)
>                       ->  Incremental Sort
>                             Sort Key: y_2.id1, y_2.id2
>                             Presorted Key: y_2.id1
>                             ->  Index Scan using fract_t1_pkey on
>                                                  fract_t1 y_2
>                                   Index Cond: (id1 = id1)
>                                   Filter: (id2 = id2)
> (23 rows)
> [...]
> So that seems reasonable

Maybe I'm just slow, but that doesn't seem reasonable to me. It doesn't look like a valid plan to me. Sure all the nodes are arranged like I'd like them to be. But what are the id1/id2 bound we have in the index and filter conditions?

> [...]but there's a couple issues too:
>
> 1) Planning works (hence we can run explain), but execution fails
> because of segfault in CheckVarSlotCompatibility - it gets NULL slot for
> some reason. I haven't looked into the details, but I'd guess we need to
> pass a different rel to create_incrementalsort_path, not childrel.

In case my above concern is valid, maybe the executor is just as confused as I am. Such conditions should generate VarSlots, no? If so, where should they come from?

Sadly I don't have time to debug that in depth today.

> 2) enable_partitionwisejoin=on seems to cause some confusion, because it
> results in picking a different plan with higher cost. But that's clearly
> not because of this patch.

Short version: I'd neither conceptually expect costs to be lower in any case, nor would that be desirable, because our estimates aren't perfect.

Long version: What do you mean by confusion. The plan I get with the patch doesn't seem to confusing to me. Generally something like that is to be expected. enable_partitionwisejoin changes the way this planing works by rewriting the entire query effectively rule based. So we end up with a completely different query. I'd in particular expect slightly different startup costs.
So if we activate this we consider completely different plans, I struggle to come up with a meaningful example where there is any overlap at all. Thus it doesn't surprise me conceptually.
From practical experience I'd say: If they are about the same plan, the costs estimates work somewhat okish.
If we change the way we compose the nodes together, we sometimes end up with radical different costs for doing the same. While I suspect there are a lot of corner cases causing this, I've seen quite a few where this was due to the fact, that our planer often has insignificant statistics to know something and takes a guess. This has gotten way better of recent years, but it's in particular for non-trivial joins still a problem in practice.

> 3) I'm still a bit skeptical about the cost of this implementation - it
> builds the incrementalsort path, just to throw most of the paths away.
> It'd be much better to just calculate the cost, which should be much
> cheaper, and only do the heavy work for the one "best" path.

Maybe we should profile this to get a rough estimate, how much time we spend building these incremental paths. From a code perspective it's non trivial to me where the time is lost.

> 4) One thing I did not realize before is what pathkeys we even consider
> here. Imagine you have two tables:
>
>     CREATE TABLE t1 (a int, b int, primary key (a));
>     CREATE TABLE t2 (a int, b int, primary key (a));
>
> and query
>
>     SELECT * FROM t1 JOIN t2 USING (a,b);
>
> It seems reasonable to also consider pathkeys (a,b) because that's make
> e.g. mergejoin much cheaper, right? But no, we'll not do that - we only
> consider pathkeys that at least one child relation has, so in this case
> it's just (a). Which means we'll never consider incremental sort for
> this particular example.
>
> It's a bit strange, because it's enough to create index on (a,b) for
> just one of the relations, and it'll suddenly consider building
> incremental sort on both sides.

I don't find that surprising, because the single index *might* make the incremental sort cheaper for the join *without* considering any external sort order.
So we would be switching up the incremental sort and the mergejoin, in case we need to sort anyways. That would mean considering also the sort order, that might be relevant on the outside. Sounds like an interesting idea for a later patch.

> I don't plan to pursue this further at this point, so I pushed the first
> part because that's a fairly simple improvement over what we have now.
> But it seems like a fairly promising area for improvements.

I think 1) is pretty important, so we should sort that out sooner than later. Apart form that: :+1:
Thank you!

Regards
Arne