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

On Wed, Nov 12, 2025 at 04:39:50PM +0100, Tomas Vondra wrote:
> Hi,
>
> Here's a v5, addressing some (but not all) of the things discussed
> earlier in this thread.
>
> This does nothing about the "opposite" type of join, with many small
> tables linking to a single "central" table. I'm not convinced it makes
> sense to handle that together with starjoins. But I haven't tried yet.

I read this thread and the patch. I have a few questions which might
have already been answered but they used terminology I might not have
understood. I want to explain what I think is happening and perhaps
someone can tell me if these ideas are new or are already covered.

So, assume a fact table with a primary-key first column, and ten more
columns, each with its own dimension table.

So, a star join would query the fact table with some filter, and then
join each of the ten columns to its own dimension table, e.g.,

fact.col2 joins to dim2.primary_key
fact.col3 joins to dim3.primary_key
...

and the problem is that the dimension tables don't join to each other,
but only to the fact table, and our existing optimizer considers join
orders of:

F to D2
F to D3
...

and then

F to D3
F to D4
...

and there are 10! possible combinations, and Tomas is saying that the
dimension tables are almost all the same in their affect on the row
count, so why bother to consider all 10! join orders. Also, some joins
might increase the row count, so a foreign key guarantees only one row
will be matched in the dimension.

I found this code comment in the recent patch which is helpful:

+ * The query may involve joins to additional (non-dimension) tables, and
+ * those may alter cardinality in either direction. In principle, it'd be
+ * best to first perform all the joins that reduce join size, then join all
+ * the dimensions, and finally perform joins that may increase the join
+ * size. Imagine a joinlist:
+ *
+ * (D1, D2, A, B, F)
+ *
+ * with fact F, dimensions D1 and D2, and non-dimensions A and B. If A
+ * increases cardinality, and B does not (or even reduces it), we could
+ * use this join tree:
+ *
+ * (A, (D2, (D1, (B, F))))
+ *
+ * For now we simply leave the dimension joins at the end, assuming
+ * that the earlier joins did not inflate the join too much.

And then there is the problem of detecting when this happens.

I think my big question is, when we join A->B->C->D, we do a lot of work
in the optimizer to figure out what order to use, but when we do A->B,
A->C, A->D, why are we spending the same amount of optimizer effort?

Could we just order B, C, D in order of which have restrictions, or
based on size? I assume we can't because we don't know if A->C or
another join would increase the number of rows, and this patch is saying
if there is a foreign key relationship, they can't increase the rows so
just short-circuit and order them simply. Is that accurate?

Crazy question, if we have A->B, A->C, and A->D, why can't we just sort
B,C,D based in increasing order of adding rows to the result, and just
use that ordering, without requiring foreign keys?

I am very glad someone is working on this problem.

--
Bruce Momjian <bruce(at)momjian(dot)us> https://momjian.us
EDB https://enterprisedb.com

Do not let urgent matters crowd out time for investment in the future.