Re: should we have a fast-path planning for OLTP starjoins? - Mailing list pgsql-hackers

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] 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].

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.

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