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

On Tue, 2025-02-04 at 15:00 +0100, Tomas Vondra wrote:

This is a surprisingly common query pattern in OLTP applications,
thanks
to normalization.

+1. Creating a small lookup table should be encouraged rather than
penalized.

Your test data includes a fact table with 10k rows and no index on the
filter condition. In OLTP applications the fact table might often fit
in memory, but I'd still expect it to have an index on the filter
condition. That might not change your overall point, but I'm curious
why you constructed the test that way?

There's a lot of stuff that could / should be improved on the current
patch. For (1) we might add support for more complex cases with
snowflake schemas [3] or with multiple fact tables. At the same time
(1)
needs to be very cheap, so that it does not regress every non-
starjoin
query.

The patch only considers the largest table as the fact table, which is
a good heuristic of course. However, I'm curious if other approaches
might work. For instance, could we consider the table involved in the
most join conditions to be the fact table?

If you base it on the join conditions rather than the size of the
table, then detection of the star join would be based purely on the
query structure (not stats), which would be nice for predictability.

But the bigger question is whether it makes sense to have such fast-
path
modes for certain query shapes.

We should explore what kinds of surprising cases it might create, or
what maintenance headaches might come up with future planner changes.
But the performance numbers you posted suggest that we should do
something here.

Regards,
Jeff Davis

On 2/4/25 20:43, Jeff Davis wrote:

On Tue, 2025-02-04 at 15:00 +0100, Tomas Vondra wrote:

This is a surprisingly common query pattern in OLTP applications,
thanks
to normalization.

+1. Creating a small lookup table should be encouraged rather than
penalized.

Your test data includes a fact table with 10k rows and no index on the
filter condition. In OLTP applications the fact table might often fit
in memory, but I'd still expect it to have an index on the filter
condition. That might not change your overall point, but I'm curious
why you constructed the test that way?

No particular reason. I think I intended to make it a lookup by PK
(which would match the use case examples), and I forgot about that. But
yeah, I would expect an index too.

There's a lot of stuff that could / should be improved on the current
patch. For (1) we might add support for more complex cases with
snowflake schemas [3] or with multiple fact tables. At the same time
(1)
needs to be very cheap, so that it does not regress every non-
starjoin
query.

The patch only considers the largest table as the fact table, which is
a good heuristic of course. However, I'm curious if other approaches
might work. For instance, could we consider the table involved in the
most join conditions to be the fact table?

If you base it on the join conditions rather than the size of the
table, then detection of the star join would be based purely on the
query structure (not stats), which would be nice for predictability.

Right, there may be other (possibly better) ways to detect the star join
shape. I was thinking about also requiring for foreign keys on the join
clauses - in DWH systems FKeys are sometimes omitted, which would break
the heuristics, but in OLTP it's common to still have them.

I think the cost of the heuristic will be an important metric - I don't
know if the number of join conditions is more expensive to determine
than what the patch does now, though.

But the bigger question is whether it makes sense to have such fast-
path
modes for certain query shapes.

We should explore what kinds of surprising cases it might create, or
what maintenance headaches might come up with future planner changes.
But the performance numbers you posted suggest that we should do
something here.

Yes, it seems like an interesting opportunity for starjoin queries. It's
a pretty common query pattern, but it also happens to be very expensive
to plan because the dimensions can be reordered almost arbitrarily.

regards

--
Tomas Vondra

Tomas Vondra <tomas@vondra.me> writes:

On 2/4/25 20:43, Jeff Davis wrote:

If you base it on the join conditions rather than the size of the
table, then detection of the star join would be based purely on the
query structure (not stats), which would be nice for predictability.

Right, there may be other (possibly better) ways to detect the star join
shape. I was thinking about also requiring for foreign keys on the join
clauses - in DWH systems FKeys are sometimes omitted, which would break
the heuristics, but in OLTP it's common to still have them.

I think you need to insist on foreign keys. Otherwise you don't know
whether the joins will eliminate fact-table rows. If that's a
possibility then it's no longer sensible to ignore different join
orders.

I'm kind of imagining a planner rule like "if table X is joined to
using a match of a foreign-key column to its PK (so that the join
removes no rows from the other table) and there are not other
restriction conditions on table X, then force X to be joined last.
And if there are multiple such tables X, it doesn't matter what
order they are joined in as long as they're last."

The interesting thing about this is we pretty much have all the
infrastructure for detecting such FK-related join conditions
already. Possibly the join order forcing could be done with
existing infrastructure too (by manipulating the joinlist).

regards, tom lane

On 2/4/25 09:00, Tomas Vondra wrote:

There's a lot of stuff that could / should be improved on the current
patch. For (1) we might add support for more complex cases with
snowflake schemas [3] or with multiple fact tables. At the same time (1)
needs to be very cheap, so that it does not regress every non-starjoin
query.

For (2) it might pick a particular order we join the dimensions (by
size, selectivity, ...), and it might consider whether to join them
before/after the other relations.

FWIW I suspect there's a fair amount of research papers looking at
starjoins and what is the optimal plan for such queries, but I didn't
have time to look at that yet. Pointers welcome!

But the bigger question is whether it makes sense to have such fast-path
modes for certain query shapes. The patch "hard-codes" the planning for
starjoin queries, but we clearly can't do that for every possible join
shape (because then why have dynamic join search at all?).

+    /*
+     * Try simplified planning for starjoin. If it succeeds, we should
+     * continue at level startlev.
+     */
+    startlev = starjoin_join_search(root, initial_rels, 2);

(I should probably don a flame retardant suit, but...)

This sounds like an interesting idea, but it makes me wonder if we
should have a more generic mechanism here so that if "some pattern is
matched" then "use some simplified planning method" -- of which the
starjoin is the first and builtin example, but allowing for others to be
plugged in via extensions.

--
Joe Conway
PostgreSQL Contributors Team
RDS Open Source Databases
Amazon Web Services: https://aws.amazon.com

On 2/4/25 21:34, Joe Conway wrote:

On 2/4/25 09:00, Tomas Vondra wrote:

There's a lot of stuff that could / should be improved on the current
patch. For (1) we might add support for more complex cases with
snowflake schemas [3] or with multiple fact tables. At the same time (1)
needs to be very cheap, so that it does not regress every non-starjoin
query.

For (2) it might pick a particular order we join the dimensions (by
size, selectivity, ...), and it might consider whether to join them
before/after the other relations.

FWIW I suspect there's a fair amount of research papers looking at
starjoins and what is the optimal plan for such queries, but I didn't
have time to look at that yet. Pointers welcome!

But the bigger question is whether it makes sense to have such fast-path
modes for certain query shapes. The patch "hard-codes" the planning for
starjoin queries, but we clearly can't do that for every possible join
shape (because then why have dynamic join search at all?).

+    /*
+     * Try simplified planning for starjoin. If it succeeds, we should
+     * continue at level startlev.
+     */
+    startlev = starjoin_join_search(root, initial_rels, 2);

(I should probably don a flame retardant suit, but...)

This sounds like an interesting idea, but it makes me wonder if we
should have a more generic mechanism here so that if "some pattern is
matched" then "use some simplified planning method" -- of which the
starjoin is the first and builtin example, but allowing for others to be
plugged in via extensions.

We already have join_search_hook_type. I haven't used that in the PoC,
because I wanted to use joinrels.c functions defined as static, etc.

The main challenge would be handling queries that have multiple of such
patterns. The current hook is expected to process the whole list, while
what we'd need is more like splitting the list into chunks (one chunk
per query pattern), and then calling the hooks to handle the chunks in
some order.

But I don't think the patch should be required to invent this. We don't
even have an example of a second pattern.

regards

--
Tomas Vondra

On 2/4/25 21:23, Tom Lane wrote:

Tomas Vondra <tomas@vondra.me> writes:

On 2/4/25 20:43, Jeff Davis wrote:

If you base it on the join conditions rather than the size of the
table, then detection of the star join would be based purely on the
query structure (not stats), which would be nice for predictability.

Right, there may be other (possibly better) ways to detect the star join
shape. I was thinking about also requiring for foreign keys on the join
clauses - in DWH systems FKeys are sometimes omitted, which would break
the heuristics, but in OLTP it's common to still have them.

I think you need to insist on foreign keys. Otherwise you don't know
whether the joins will eliminate fact-table rows. If that's a
possibility then it's no longer sensible to ignore different join
orders.

Hmmm, yeah. But that's only for the INNER JOIN case. But I've seen many
of these star join queries with LEFT JOIN too, and then the FKs are not
needed. All you need is a PK / unique index on the other side.

Perhaps requiring (INNER JOIN + FK) or (LEFT JOIN + PK) would be enough
to make this work for most cases, and then the rest would simply use the
regular join order algorithm.

I was thinking that if we allow the dimensions to eliminate rows in the
fact table, we'd simply join them starting from the most selective ones.
But that doesn't work if the joins might have different per-row costs
(e.g. because some dimensions are much larger etc). Doing something
smarter would likely end up fairly close to the regular join order
algorithm ...

I'm kind of imagining a planner rule like "if table X is joined to
using a match of a foreign-key column to its PK (so that the join
removes no rows from the other table) and there are not other
restriction conditions on table X, then force X to be joined last.
And if there are multiple such tables X, it doesn't matter what
order they are joined in as long as they're last."

I think it'd need to be a bit smarter, to handle (a) snowflake schemas
and (b) additional joins referencing the starjoin result.

The (a) shouldn't be too hard, except that it needs to check the
'secondary dimension' is also joined by FK and has no restrictions, and
then do that join later.

For (b), I don't have numbers but I've seen queries that first do a
starjoin and then add more data to that, e.g. by joining to a
combination of attributes from multiple dimensions (think region +
payment type). Or by joining to some "summary" table that does not have
an explicit FK. Still, we could leave at least some of the joins until
the very end, I guess. But even for the dimensions joined earlier the
order does not really matter.

I think (a) is something we should definitely handle. (b) is more a
DWH/BI thing, not really an OLTP query (which is what this thread is about).

The interesting thing about this is we pretty much have all the
infrastructure for detecting such FK-related join conditions
already. Possibly the join order forcing could be done with
existing infrastructure too (by manipulating the joinlist).

Maybe, interesting. I've ruled out relying on the FKeys early in the
coding, but I'm sure there's infrastructure the patch could use. It'd
still need to check the transitive FK relationships for snowflake joins
to work, ofc. Which is not something we need to consider right now.

What kind of "manipulation" of the joinlist you have in mind?

regards

--
Tomas Vondra

Tomas Vondra <tomas@vondra.me> writes:

The interesting thing about this is we pretty much have all the
infrastructure for detecting such FK-related join conditions
already. Possibly the join order forcing could be done with
existing infrastructure too (by manipulating the joinlist).

Maybe, interesting. I've ruled out relying on the FKeys early in the
coding, but I'm sure there's infrastructure the patch could use.

It would be very sad to do that work twice in a patch that purports
to reduce planning time. If it's done too late to suit you now,
could we move it to happen earlier?

What kind of "manipulation" of the joinlist you have in mind?

Right now, if we have four tables to join, we have a joinlist
(A B C D). (Really they're integer relids, but let's use names here.)
If we decide to force C to be joined last, it should be sufficient to
convert this to ((A B D) C). If C and D both look like candidates for
this treatment, we can make it be (((A B) C) D) or (((A B) D) C).
This is pretty much the same thing that happens if you set
join_collapse_limit to 1 and use JOIN syntax to force a join order.
In fact, IIRC we start out with nested joinlists and there is some
code that normally flattens them until it decides it'd be creating
too large a sub-problem. I'm suggesting selectively reversing the
flattening.

regards, tom lane

On Tue, Feb 4, 2025 at 3:42 PM Tomas Vondra <tomas@vondra.me> wrote:

On 2/4/25 21:23, Tom Lane wrote:

Tomas Vondra <tomas@vondra.me> writes:

On 2/4/25 20:43, Jeff Davis wrote:

If you base it on the join conditions rather than the size of the
table, then detection of the star join would be based purely on the
query structure (not stats), which would be nice for predictability.

Right, there may be other (possibly better) ways to detect the star join
shape. I was thinking about also requiring for foreign keys on the join
clauses - in DWH systems FKeys are sometimes omitted, which would break
the heuristics, but in OLTP it's common to still have them.

I think you need to insist on foreign keys. Otherwise you don't know
whether the joins will eliminate fact-table rows. If that's a
possibility then it's no longer sensible to ignore different join
orders.

Hmmm, yeah. But that's only for the INNER JOIN case. But I've seen many
of these star join queries with LEFT JOIN too, and then the FKs are not
needed. All you need is a PK / unique index on the other side.

Perhaps requiring (INNER JOIN + FK) or (LEFT JOIN + PK) would be enough
to make this work for most cases, and then the rest would simply use the
regular join order algorithm.

I was thinking that if we allow the dimensions to eliminate rows in the
fact table, we'd simply join them starting from the most selective ones.
But that doesn't work if the joins might have different per-row costs
(e.g. because some dimensions are much larger etc). Doing something
smarter would likely end up fairly close to the regular join order
algorithm ...

As long as the join is still happening there doesn't appear to be a
correctness issue here, so I'm not sure mandating FKs makes sense.

The reason this matters is that highly concurrent FK checks can get VERY
expensive (due to the cost of creating multiXacts). While it'd be great to
fix that issue the reality today is it's not uncommon for people to remove
FKs because of the high performance penalty.

Jim Nasby <jnasby@upgrade.com> writes:

On Tue, Feb 4, 2025 at 3:42 PM Tomas Vondra <tomas@vondra.me> wrote:

Perhaps requiring (INNER JOIN + FK) or (LEFT JOIN + PK) would be enough
to make this work for most cases, and then the rest would simply use the
regular join order algorithm.

As long as the join is still happening there doesn't appear to be a
correctness issue here, so I'm not sure mandating FKs makes sense.
The reason this matters is that highly concurrent FK checks can get VERY
expensive (due to the cost of creating multiXacts). While it'd be great to
fix that issue the reality today is it's not uncommon for people to remove
FKs because of the high performance penalty.

Meh. If we don't apply this optimization when there's no FK, we have
not made those folks' life any worse. If we apply it despite there
being no FK, we might choose a materially worse plan than before, and
that *will* make their lives worse.

regards, tom lane

On Wed, Feb 5, 2025 at 5:42 AM Tomas Vondra <tomas@vondra.me> wrote:

Hmmm, yeah. But that's only for the INNER JOIN case. But I've seen many
of these star join queries with LEFT JOIN too, and then the FKs are not
needed. All you need is a PK / unique index on the other side.

Perhaps requiring (INNER JOIN + FK) or (LEFT JOIN + PK) would be enough
to make this work for most cases, and then the rest would simply use the
regular join order algorithm.

I was thinking that if we allow the dimensions to eliminate rows in the
fact table, we'd simply join them starting from the most selective ones.
But that doesn't work if the joins might have different per-row costs
(e.g. because some dimensions are much larger etc). Doing something
smarter would likely end up fairly close to the regular join order
algorithm ...

Yeah, we need to ensure that the joins to the fact table don't affect
its rows; otherwise, the join order matters for the final query plan,
and we'd better run the regular join search algorithm in this case.

For inner joins, using the foreign key seems ideal for this. For left
joins, we might be able to leverage rel_is_distinct_for() to handle
that.

Thanks
Richard

On Wed, Feb 5, 2025 at 5:55 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Right now, if we have four tables to join, we have a joinlist
(A B C D). (Really they're integer relids, but let's use names here.)
If we decide to force C to be joined last, it should be sufficient to
convert this to ((A B D) C). If C and D both look like candidates for
this treatment, we can make it be (((A B) C) D) or (((A B) D) C).
This is pretty much the same thing that happens if you set
join_collapse_limit to 1 and use JOIN syntax to force a join order.
In fact, IIRC we start out with nested joinlists and there is some
code that normally flattens them until it decides it'd be creating
too large a sub-problem. I'm suggesting selectively reversing the
flattening.

This should not be too difficult to implement. Outer joins seem to
add some complexity, though. We need to ensure that the resulting
joins in each sub-list are legal given the query's join order
constraints. For example, if we make the joinlist be (((A B) C) D),
we need to ensure that the A/B join and the (A/B)/C join are legal.

Thanks
Richard

On 2/5/25 09:27, Richard Guo wrote:

On Wed, Feb 5, 2025 at 5:55 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Right now, if we have four tables to join, we have a joinlist
(A B C D). (Really they're integer relids, but let's use names here.)
If we decide to force C to be joined last, it should be sufficient to
convert this to ((A B D) C). If C and D both look like candidates for
this treatment, we can make it be (((A B) C) D) or (((A B) D) C).
This is pretty much the same thing that happens if you set
join_collapse_limit to 1 and use JOIN syntax to force a join order.
In fact, IIRC we start out with nested joinlists and there is some
code that normally flattens them until it decides it'd be creating
too large a sub-problem. I'm suggesting selectively reversing the
flattening.

This should not be too difficult to implement. Outer joins seem to
add some complexity, though. We need to ensure that the resulting
joins in each sub-list are legal given the query's join order
constraints. For example, if we make the joinlist be (((A B) C) D),
we need to ensure that the A/B join and the (A/B)/C join are legal.

If the requirement is that all "dimensions" only join to the fact table
(which in this example would be "A" I think) through a FK, then why
would these joins be illegal?

We'd also need to require either an outer (left) join, or "NOT NULL" on
the fact table side, right? IIRC we already do that when using the FKeys
for join estimates.

Essentially, this defines a "dimension" as a relation that is joined
through a PK, without any other restrictions, both of which seems fairly
simple to check, and it's a "local" feature. And we'd simply mark those
as "join at the very end, in arbitrary order". Easy enough, I guess.

I'm thinking about some more complex cases:

(a) Query with multiple starjoins (a special case of that is snowflake
schema) - but I guess this is not too difficult, it just needs to
consider the FKs as "transitive" (a bit like Dijkstra's algorithm). In
the worst case we might need to "split" the whole query into multiple
smaller subproblems.

(b) Joining additional stuff to the dimensions (not through a FK,
possibly to multiple dimensions, ...). Imagine a "diamond join" with
some summary table, etc. IMHO this is a fairly rare case / expensive
enough to make the planning part less important.

I'm also wondering how this should interact with join_collapse_limit. It
would seems ideal to do this optimization before splitting the join list
into subproblems (so that the "dimensions" are do not even count against
the limit, pretty much). But that would mean join_collapse_limit can no
longer be used to enforce a join order like today ...

regards

--
Tomas Vondra

Hmmm, yeah. But that's only for the INNER JOIN case. But I've seen many
of these star join queries with LEFT JOIN too, and then the FKs are not
needed. All you need is a PK / unique index on the other side.

Indeed, many installations specifically _remove_ foreign keys because of
the dreaded RI check on delete. Basically, if you delete one or more rows
in dim1 then the referencing fact1 must be scanned to ensure that it does
not contain a reference to the deleted row. Often the referencing field on
fact1 is not indexed, because the index is almost never useful in an actual
select query, so even if you did index it several unused index metrics will
identify it as a candidate for deletion. What you get is one sequential
scan of fact1 for every row deleted from dim1. Now, we could get around
this by changing how we do delete RI checks, either by moving to statement
level triggers or bypassing triggers entirely, but until we do so, it is
likely that many customers avoid otherwise useful FK references.

On Wed, Feb 5, 2025 at 4:23 AM Tomas Vondra <tomas@vondra.me> wrote:

If the requirement is that all "dimensions" only join to the fact table
(which in this example would be "A" I think) through a FK, then why
would these joins be illegal?

...
Essentially, this defines a "dimension" as a relation that is joined
through a PK, without any other restrictions, both of which seems fairly
simple to check, and it's a "local" feature. And we'd simply mark those
as "join at the very end, in arbitrary order". Easy enough, I guess.

As I understand your proposal, you want to detect queries that join a
large number, N, of tables -- which means doing an exhaustive search
of all possible join orders is expensive -- where N - 1 of the tables
do not join to each other, but join only to the Nth table.

PostgreSQL already falls back on geqo when it hits some heuristic that
says exhaustive search is too expensive, but you're proposing an
additional, better heuristic.

Say we have F JOIN D1 JOIN D2 ... JOIN D(N-1). In the example you
gave, the single-table predicate on F makes it small enough, I think,
that F will be the "build" side of any Hash Join, right? You're
assuming, I think, that the cardinality |F| = 1, after applying the
filter to F. And so, |F JOIN Dk| will be approximately 1, for any 1 <=
k < N. So then the join order does not matter. I think this is what
you mean by "OLTP star join."

For *OLAP* star joins, Oracle's Star Transformation [1]https://blogs.oracle.com/optimizer/post/optimizer-transformations-star-transformation works
reasonably well, where Oracle scans D1, ..., D(N-1) first, constructs
Bloom filters, etc., and then "pushes" the N-1 joins down into the Seq
Scan on F.

So, I suggest:
1. Add an *OLTP* optimization similar to what you described, but
instead of classifying the largest table as fact F, look for the "hub"
of the star and classify it as F. And then enable your optimization if
and only if the estimated nrows for F is very small.

2. For an *OLAP* optimization, do something like Oracle's Star Transformation.

Re "OLTP" vs. "OLAP": the join order does not matter for *OLTP* star
queries, because the fact table F is *small* (post-filtering). And
because F is small, it doesn't matter so much in what order you join
the dimension tables, because the result is "likely" to be small as
well.

Tom correctly points out that you really need foreign key constraints
to ensure the previous sentence's "likely," but since your
optimization is just intended to avoid considering unnecessary join
orders, you may be able to get away with asking the optimizer what it
thinks the cardinality |(... (F JOIN D1) ... JOIN Dk)| would be, and
just fall back on the existing join-search logic when the optimizer
thinks that Dk will create lots of rows (and so the join order
matters...).

So much for the OLTP case. For completeness, some discussion about the
OLAP case; fwiw, let me start by plugging my "credentials" [2]https://patents.google.com/patent/US20150088856A1/en.

The OLAP case is more complicated than the OLTP case, in that the bad
thing about *OLAP* star joins is that joins are pairwise. With OLAP
star joins, you assume that |F| is always much larger than |Dk|, and
by extension |(... (F JOIN D1) ... JOIN Dk)| is generally larger than
|D(k+1)|. And the problem for OLAP is that while every Dk potentially
filters rows out from F, you have to join to the Dk's one at a time,
so you never get as much filtering as you'd like.

For OLAP, you can take the Cartesian product of D1, ..., DN , and then
scan F to aggregate into the resulting cube; see [3]https://docs.oracle.com/en/database/oracle/oracle-database/12.2/inmem/optimizing-in-memory-aggregation.html . (Link [2]https://patents.google.com/patent/US20150088856A1/en is
related to transformation.)

Or, you can scan D1, ..., DN first, without joining anything,
constructing Hash tables and Bloom filters from your scans; then push
the Bloom filters down to the scan of F; and finally join the
(Bloom-filtered) F back to D1, ..., DN. This is what link [1]https://blogs.oracle.com/optimizer/post/optimizer-transformations-star-transformation
describes. Note that [1]https://blogs.oracle.com/optimizer/post/optimizer-transformations-star-transformation came out before [3]https://docs.oracle.com/en/database/oracle/oracle-database/12.2/inmem/optimizing-in-memory-aggregation.html.

However... for OLAP, you see from the above discussion that it's not
compilation that takes too long, but rather execution. So the
optimizations require significant changes to the SQL executor.

What you're proposing, IIUC, is a nice optimization to compilation
times, which is why (I think) you're focused on the OLTP use case. In
that case, I suggest focusing on an OLTP-specific solution, maybe a
straw man like:
1. I see a query where N-1 relations join to the Nth relation, but not
to each other (except transitively, of course).
2. Estimated cardinality for F, after pushing down single table
predicates, is very small.
3. OK, let's start joining tables D1, ..., D(N-1) in order, since
we're assuming (thanks to (1) and (2)) that the join order won't
matter.
4. Continue joining tables in this fixed (arbitrary) order, unless we
come to a Dk where the optimizer thinks joining to Dk will generate a
significant number of rows.
5. Either we join all tables in order (fast compilation!); or we hit
the case in (4), so we just fall back on the existing join logic.

Thanks,
James

[1]: https://blogs.oracle.com/optimizer/post/optimizer-transformations-star-transformation
[2]: https://patents.google.com/patent/US20150088856A1/en
[3]: https://docs.oracle.com/en/database/oracle/oracle-database/12.2/inmem/optimizing-in-memory-aggregation.html

On 2/7/25 20:11, James Hunter wrote:

On Wed, Feb 5, 2025 at 4:23 AM Tomas Vondra <tomas@vondra.me> wrote:

If the requirement is that all "dimensions" only join to the fact table
(which in this example would be "A" I think) through a FK, then why
would these joins be illegal?

...
Essentially, this defines a "dimension" as a relation that is joined
through a PK, without any other restrictions, both of which seems fairly
simple to check, and it's a "local" feature. And we'd simply mark those
as "join at the very end, in arbitrary order". Easy enough, I guess.

As I understand your proposal, you want to detect queries that join a
large number, N, of tables -- which means doing an exhaustive search
of all possible join orders is expensive -- where N - 1 of the tables
do not join to each other, but join only to the Nth table.

Yes. Essentially, it reduces the size of the problem by ignoring joins
for which we know the optimal order. We know the dimensions can be
joined last, and it does not matter in which exact order we join them.

The starjoins are a bit of the "worst case" for our heuristics, because
there are no dependencies between the dimensions, and we end up
exploring the n! possible join orders, more or less. For other joins we
quickly prune the space.

PostgreSQL already falls back on geqo when it hits some heuristic that
says exhaustive search is too expensive, but you're proposing an
additional, better heuristic.

True, but most people will never actually hit the GEQO, because the
default threshold are set like this:

join_collapse_limit = 8
geqo_threshold = 12

So the planner will not "create" join search problems with more than 8
relations, but geqo only kicks in at 12. Most systems run with the
default values for these GUCs, so they don't really use GEQO.

FWIW I don't know a lot about the GEQO internals, but I heard it doesn't
work all that well for the join order problem anyway. Not sure.

Say we have F JOIN D1 JOIN D2 ... JOIN D(N-1). In the example you
gave, the single-table predicate on F makes it small enough, I think,
that F will be the "build" side of any Hash Join, right? You're
assuming, I think, that the cardinality |F| = 1, after applying the
filter to F. And so, |F JOIN Dk| will be approximately 1, for any 1 <=
k < N. So then the join order does not matter. I think this is what
you mean by "OLTP star join."

I don't think it matters very much on which side of the join the F will
end up (or if it's a hash join, it can easily be NL). It will definitely
be in the first join, though, because all other dimensions join to it
(assuming this is just a starjoin, with only fact + dimensions).

It also doesn't really matter what's the exact cardinality of |F|. The
example used a PK lookup, so that would be 1 row, but the point is that
this is (much) cheaper than the planning. E.g. the planning might take
3ms while the execution only takes 1ms, etc. In the OLAP cases this is
usually not the case, because the queries are processing a lot of data
from the fact table, and the planning is negligible.

For *OLAP* star joins, Oracle's Star Transformation [1] works
reasonably well, where Oracle scans D1, ..., D(N-1) first, constructs
Bloom filters, etc., and then "pushes" the N-1 joins down into the Seq
Scan on F.

I don't care about OLAP star joins, at least no in this patch. It's a
completely different / separate use case, and it affects very different
parts of the planner (and also the executor, which this patch does not
need to touch at all).

So, I suggest:
1. Add an *OLTP* optimization similar to what you described, but
instead of classifying the largest table as fact F, look for the "hub"
of the star and classify it as F. And then enable your optimization if
and only if the estimated nrows for F is very small.

Right. I believe this is mostly what looking for FKs (as suggested by
Tom) would end up doing. It doesn't need to consider the cardinality of
F at all.

2. For an *OLAP* optimization, do something like Oracle's Star
Transformation.

I consider that well outside the scope of this patch.

Re "OLTP" vs. "OLAP": the join order does not matter for *OLTP* star
queries, because the fact table F is *small* (post-filtering). And
because F is small, it doesn't matter so much in what order you join
the dimension tables, because the result is "likely" to be small as
well.

I don't think that's quite true. The order of dimension joins does not
matter because the joins do not affect the join size at all. The size of
|F| has nothing to do with that, I think. We'll do the same number of
lookups against the dimensions no matter in what order we join them. And
we know it's best to join them as late as possible, after all the joins
that reduce the size (and before joins that "add" rows, I think).

Tom correctly points out that you really need foreign key constraints
to ensure the previous sentence's "likely," but since your
optimization is just intended to avoid considering unnecessary join
orders, you may be able to get away with asking the optimizer what it
thinks the cardinality |(... (F JOIN D1) ... JOIN Dk)| would be, and
just fall back on the existing join-search logic when the optimizer
thinks that Dk will create lots of rows (and so the join order
matters...).

Possibly, but TBH the join cardinality estimates can be quite dubious
pretty easily. The FK is a much more reliable (definitive) information.

So much for the OLTP case. For completeness, some discussion about the
OLAP case; fwiw, let me start by plugging my "credentials" [2].

Thanks ;-)

The OLAP case is more complicated than the OLTP case, in that the bad
thing about *OLAP* star joins is that joins are pairwise. With OLAP
star joins, you assume that |F| is always much larger than |Dk|, and
by extension |(... (F JOIN D1) ... JOIN Dk)| is generally larger than
|D(k+1)|. And the problem for OLAP is that while every Dk potentially
filters rows out from F, you have to join to the Dk's one at a time,
so you never get as much filtering as you'd like.

For OLAP, you can take the Cartesian product of D1, ..., DN , and then
scan F to aggregate into the resulting cube; see [3] . (Link [2] is
related to transformation.)

Or, you can scan D1, ..., DN first, without joining anything,
constructing Hash tables and Bloom filters from your scans; then push
the Bloom filters down to the scan of F; and finally join the
(Bloom-filtered) F back to D1, ..., DN. This is what link [1]
describes. Note that [1] came out before [3].

However... for OLAP, you see from the above discussion that it's not
compilation that takes too long, but rather execution. So the
optimizations require significant changes to the SQL executor.

Agreed. I'm not against improving the OLAP case too, but it's not what
this thread was about. It seems it'll need changes in very different
places, etc.

What you're proposing, IIUC, is a nice optimization to compilation
times, which is why (I think) you're focused on the OLTP use case. In
that case, I suggest focusing on an OLTP-specific solution, maybe a
straw man like:
1. I see a query where N-1 relations join to the Nth relation, but not
to each other (except transitively, of course).
2. Estimated cardinality for F, after pushing down single table
predicates, is very small.
3. OK, let's start joining tables D1, ..., D(N-1) in order, since
we're assuming (thanks to (1) and (2)) that the join order won't
matter.
4. Continue joining tables in this fixed (arbitrary) order, unless we
come to a Dk where the optimizer thinks joining to Dk will generate a
significant number of rows.
5. Either we join all tables in order (fast compilation!); or we hit
the case in (4), so we just fall back on the existing join logic.

Yes, I think that's pretty much the idea. Except that I don't think we
need to look at the |F| at all - it will have more impact for small |F|,
of course, but it doesn't hurt for large |F|.

I think it'll probably need to consider which joins increase/decrease
the cardinality, and "inject" the dimension joins in between those.

regards

--
Tomas Vondra

On Fri, Feb 7, 2025 at 12:09 PM Tomas Vondra <tomas@vondra.me> wrote:

...
Yes, I think that's pretty much the idea. Except that I don't think we
need to look at the |F| at all - it will have more impact for small |F|,
of course, but it doesn't hurt for large |F|.

I think it'll probably need to consider which joins increase/decrease
the cardinality, and "inject" the dimension joins in between those.

YMMV, but I suspect you may find it much easier to look at |F|, |F
JOIN D1|, |(F JOIN D1) JOIN D2|, etc., than to consider |F JOIN D1| /
|F|, etc. (In other words, I suspect that considering absolute
cardinalities will end up easier/cleaner than considering ratios of
increases/decreases in cardinalities.) But I have not thought about
this much, so I am not putting too much weight on my suspicions.

James

On 2/7/25 23:43, James Hunter wrote:

On Fri, Feb 7, 2025 at 12:09 PM Tomas Vondra <tomas@vondra.me> wrote:

...
Yes, I think that's pretty much the idea. Except that I don't think we
need to look at the |F| at all - it will have more impact for small |F|,
of course, but it doesn't hurt for large |F|.

I think it'll probably need to consider which joins increase/decrease
the cardinality, and "inject" the dimension joins in between those.

YMMV, but I suspect you may find it much easier to look at |F|, |F
JOIN D1|, |(F JOIN D1) JOIN D2|, etc., than to consider |F JOIN D1| /
|F|, etc. (In other words, I suspect that considering absolute
cardinalities will end up easier/cleaner than considering ratios of
increases/decreases in cardinalities.) But I have not thought about
this much, so I am not putting too much weight on my suspicions.

That's not what I meant when I mentioned joins that increase/decrease
cardinality. That wasn't referring to the "dimension" joins, which we
expect to have FK and thus should not affect the cardinality at all.

Instead, I was thinking about the "other" joins (if there are any), that
may add or remove rows. AFAIK we want to join the dimensions at the
place with the lowest cardinality - the discussion mostly assumed the
joins would only reduce the cardinality, in which case we'd just leave
the dimensions until the very end.

But ISTM that may not be necessarily true. Let's say there's a join that
"multiplies" each row. It'll probably be done at the end, and the
dimension joins should probably happen right before it ... not sure.

cheers

--
Tomas Vondra

Tomas Vondra <tomas@vondra.me> writes:

Instead, I was thinking about the "other" joins (if there are any), that
may add or remove rows. AFAIK we want to join the dimensions at the
place with the lowest cardinality - the discussion mostly assumed the
joins would only reduce the cardinality, in which case we'd just leave
the dimensions until the very end.

But ISTM that may not be necessarily true. Let's say there's a join that
"multiplies" each row. It'll probably be done at the end, and the
dimension joins should probably happen right before it ... not sure.

I thought the idea here was to get rid of as much join order searching
as we could. Insisting that we get the best possible plan anyway
seems counterproductive, not to mention very messy to implement.
So I'd just push all these joins to the end and be done with it.

regards, tom lane

On 2/8/25 01:23, Tom Lane wrote:

Tomas Vondra <tomas@vondra.me> writes:

Instead, I was thinking about the "other" joins (if there are any), that
may add or remove rows. AFAIK we want to join the dimensions at the
place with the lowest cardinality - the discussion mostly assumed the
joins would only reduce the cardinality, in which case we'd just leave
the dimensions until the very end.

But ISTM that may not be necessarily true. Let's say there's a join that
"multiplies" each row. It'll probably be done at the end, and the
dimension joins should probably happen right before it ... not sure.

I thought the idea here was to get rid of as much join order searching
as we could. Insisting that we get the best possible plan anyway
seems counterproductive, not to mention very messy to implement.
So I'd just push all these joins to the end and be done with it.

Right, cutting down on the join order searching is the point. But most
of the savings comes (I think) from not considering different ordering
of the dimensions, because those are all essentially the same.

Consider a join with 16 relations, 10 of which are dimensions. There are
10! possible orders of the dimensions, but all of them behave pretty
much exactly the same. In a way, this behaves almost like a join with 7
relations, one of which represents all the 10 dimensions.

I think this "join group" abstraction (a relation representing a bunch
of relations in a particular order) would make this reasonably clean to
implement. I haven't tried yet, though.

Yes, this means we'd explore more orderings, compared to just pushing
all the dimensions to the end. In the example above, that'd be 7!/6!, so
up to ~7x orderings.

I don't know if this is worth the extra complexity, of course.

thanks

--
Tomas Vondra