On Tue, Feb 04, 2025 at 03:00:49PM +0100, Tomas Vondra wrote:
I'm late to this party. I have apps that do start queries like this a
lot. These apps fall into this type:
> Or maybe the fact table is "users" and the dimensions have all kinds of
> info about the user (address, primary e-mail address, balance, ...).
In my case the schema is an EAV schema, but essentially it stores users,
groups, and many other such things -- the sorts you expect to find in a
directory service.
Some unsolicited advice:
- the table source with the longest index key prefix (or full key)
determined by WHERE clause terms is the table that should lead the
query plan
This is really important for the case where the query is a VIEW and
the WHERE clause terms can get pushed into it, then:
SELECT ...
FROM t0
JOIN t1 ON ...
JOIN t2 ON ...
..
JOIN tN ON ...
-- tX's PK is (a, b, c), or maybe (a, b, c, d), but (a, b, c) is a
-- very selective prefix of that PK index, so the query plan should
-- start with tX
WHERE tX.a = ... AND tX.b = ... AND tX.c = ...
- if there is no such table source then we're asking for "all the
data", and we might as well start with a full table scan of some
table source, but, which? my answer: the lexically first one in the
query! (why? because it gives the query author the power to pick
which table goes first in this case)
SELECT ...
FROM t0
JOIN ...
...; -- no WHERE clause or no terms that provide values for prefixes
-- of indices that we could use to find a good choice of
-- starting table, so start with t0
> Anyway, this pattern is quite common, yet it performs quite poorly.
Yes.
> But for starjoins, a lot of this is not really needed. In the simplest
> case (no conditions on dimensions etc) it does not really matter in what
> order we join those, and filters on dimensions make it only a little bit
But here you can just use the order that the SQL uses. It gives the
author some power.
> more complicated (join the most selective first).
Yes.
> So I've been wondering how difficult would it be to have a special
> fast-path mode for starjoins, completely skipping most of this. I
> cobbled together a WIP/PoC patch (attached) on the way from FOSDEM, and
> it seems to help quite a bit.
Yay! _Thank you_!
> So that about triples the throughput. If you bump join_collapse_limit to
> 12, it gets even clearer
>
> build 1 16
> --------------------------------------
> master 200 2000
> patched 4500 48000
>
> That's a 20x improvement - not bad. Sure, this is on a tiny dataset, and
> with larger data sets it might need to do I/O, diminishing the benefits.
> It's just an example to demonstrate the benefits.
Fantastic! I can't wait to use this in prod.
> 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?).
IMO: Yes for starjoins. The reason is:
> I do think starjoins might be sufficiently unique / special to justify
> this, but maybe it would be possible to instead improve the regular join
> order search to handle this case better? I don't have a very clear idea
> what would that look like, though :-(
If you're not pessimizing other cases and you're getting a 4x to 20x
improvement then the uniqueness of the starjoin case and the frequent
use of starjoin queries makes this fast-path worthwhile.
Moreover, I think in general if you can cheaply determine a "kind" of
query and then apply query plan searches / optimizations that are most
relevant to the query's "kind" then I think that's a good way to unlock
more useful optimizations.
> I did check what do some other databases do, and they often have some
> sort of "hint" to nudge the let the optimizer know this is a starjoin.
I don't think a hint is needed here.
BTW, I like hints, but only out-of-band, not embedded in the SQL.
Unfortunately out-of-band hinting is not really viable because to
introduce it one would need new APIs (and possibly protocol work).
Nico
--