Re: should we have a fast-path planning for OLTP starjoins?

On 5/30/26 20:18, Bruce Momjian wrote:
> On Fri, May 29, 2026 at 12:11:32AM +0200, Tomas Vondra wrote:
>> But re-reading the old thread, this doesn't seem to be why it got stuck.
>> We already can identify dimensions joined on foreign keys, and that
>> seems like a good start.
>>
>> IIRC the thing that worried me was that just sticking the joins at the
>> end is pretty heavy-handed. It can easily end up making the plan worse,
>> if one of the other joins increases the cardinality. Would that be
>> common? Probably not, but it seems unnecessarily risky.
>
> Right.
>
>> Ideally, we'd do join that reduce cardinality first (with the regular DP
>> join search), then join all the dimensions, and finally do all joins
>> that expand cardinality (again, using the regular DP). But the earlier
>> patches worked by adjusting the join tree in query_planner(), i.e. way
>> before we get to calculate join cardinalities.
>
> Yes, I remember discussing that.
>
>> It works like this:
>>
>> 1) query_planner()
>>
>> Determine if the query includes a starjoin (or multiple), and remember
>> the relids included in the starjoin cluster. Pick a "canonical" join
>> order for each starjoin cluster we found (e.g. with dimensions in relid
>> order).
>>
>> 2) standard_join_search()/join_search_one_level()
>>
>> When constructing the join rels (e.g. in make_join_rel or right before
>> it's called), check that the new rel would violate the canonical order.
>> If it would, refuse to create it, just like we do for various other join
>> restrictions.
>
> This is how you avoid the factorial explosion of plan options, right?
>

Yes, exactly.

>> The new join restriction is that if the join result includes a subset of
>> the starjoin cluster, then it has to include the fact + prefix of the
>> list of dimensions (which is the canonical join order).
>
> Sorry, I got lost here. What is "prefix?" I looked at the patch and
> also could not understand it.

Apologies, it may not be obvious from the code / comments (I'll try to
improve that in the next version).

Let's say we're joining "F" with dimensions D1, D2, D3. Then the
starjoins_canonicalize() finds the cluster, and picks a canonical join
order. Could be [F, D1, D2, D3] - in this order. Or whatever other
permutation of the dimensions, it's all equal.

Then starjoin_order_invalid() ensures that whatever join relation we
produce, it only even contains a prefix of this list. So a join relation
can contain [F], [F, D1], [F, D1, D2], [F, D1, D2, D3]. But it can't
contain e.g. [F, D2], because that skips the D1 - it's not a prefix.

The patch only applies this to relations from the cluster. There can be
other relations in the join "in between" the dimensions - that does not
make the join order "invalid".

So for example there may be joins to non-dimensions A and B, and we will
consider joins [F, A, D1, B, D2, D3] and so on as valid. The joins to A
and B joins can increase/decrease cardinality, but thanks to this we
should find the right place to join the dimensions.

We could even make it a bit stricter, and require that all dimensions
join "at once". I.e. after joining a dimension, only dimensions can be
joined (until all dimensions are joined). So [F, D1, A, D2] would not be
allowed. This would further reduce the number of join orders considered.

>
>> Note: It should be possible to make the restriction even more strict, if
>> needed (e.g. to effectively join all dimensions at once, with no other
>> joins in between).
>
> The patch is quite small.
>
>> Attached are a couple charts from a test with 1-15 dimensions (scripts
>> attached too). I was wondering how geqo affects this, so I tried with
>> geqo=on/off, and with join_collapse_limit=1/8/16.
>>
>> With join_collapse_limit=1 there's no difference between any of the runs
>> (master, patches with on/off). Here's an example of results:
>>
>> dims master(1) master sj/off sj/on master sj/off sj/on
>> -------------------------------------------------------------------
>> 1 49485 48797 48966 49118 99% 99% 99%
>> 3 26886 22003 21319 24322 82% 79% 90%
>> 5 17759 7923 7634 15434 45% 43% 87%
>> 7 13110 2122 2071 11290 16% 16% 86%
>> 9 10390 462 445 8709 4% 4% 84%
>> 11 7781 87 86 6488 1% 1% 83%
>> 13 5948 14 14 5749 0% 0% 97%
>> 15 5237 1 1 4227 0% 0% 81%
>
> Impressive.
>

Indeed. I like how it fits into the existing approach. It's a bit like
having yet another "join order restriction".

regards

--
Tomas Vondra