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

[ sorry for ridiculously slow response to this ]

Tomas Vondra <tomas(at)vondra(dot)me> writes:
> Here's a patch trying to do it more like this - by manipulating the
> lists describing the join problems, before it's passed the the actual
> join search algorithm (which is where the PoC patch did this).
> I wonder if this is roughly the place where you imagined this would be
> done, or if you envision some other issue with this approach.

Cool. This is proof-of-concept that manipulating the joinlist can
do what we need done. So we can move on to what heuristics we need
to use.

> I initially tried to manipulate the joinlist much earlier - pretty much
> right at the end of deconstruct_jointree. But that turned out to be way
> too early. To identify dimensions etc. we need to check stuff about
> foreign keys, join clauses, ... and that's not available that early.

> So I think this needs to happen much later in query_planner(), and the
> patch does it right before the make_one_rel() call. Maybe that's too
> late, but it needs to happen after match_foreign_keys_to_quals(), as it
> relies on some of the FK info built by that call. Maybe we could call
> match_foreign_keys_to_quals() earlier, but I don't quite see any
> benefits of doing that ...

I don't have a problem with doing it where you did it, but the comment
should explain the placement. What you do have in the comment mostly
belongs with the code, too; it's not the business of the caller. So
in planmain.c something like

+ /*
+ * Try to simplify the join search problem for starjoin-like joins.
+ * This step relies on info about FK relationships, so we can't do it
+ * till after match_foreign_keys_to_quals().
+ */

would be more appropriate IMO. I'd be slightly inclined to put the
GUC test there, too:

+ if (enable_starjoin_join_search)
+ joinlist = starjoin_adjust_joins(root, joinlist);

I agree that you need to worry about join order restrictions,
and that it's not immediately clear how to do that. join_is_legal
would work if we could call it, but the problem is that at this
stage we'll only have RelOptInfos for base rels not join rels.
If we have a joinlist (A B C D) and we are considering treating
C as a dimension table, then the questions we have to ask are:
(a) is it okay to build the (A B D) join without C?
(b) is it okay to join (A B D) to C?

In this simple case, I think (b) must be true if (a) is, but
I'm not quite sure that that's so in more complex cases with
multiple candidates for dimension tables. In any case,
join_is_legal won't help us if we don't have join RelOptInfos.

I'm inclined to start by using has_join_restriction: if that
says "false" for a candidate dimension table, it should be safe
to postpone the join to the dimension table. We might be able
to refine that later.

> The second example (create-2/select-2) is quite different, in that it's
> nor a starjoin schema. It still joins one "main" table with multiple
> "dimensions", but the FKs go in the other direction (to a single column
> in the main table). But it has a very similar bottleneck - the order of
> the joins is expensive, but it often does not matter very much, because
> the query matches just one row anyway. And even if it returns more rows,
> isn't the join order determined just by the selectivity of each join?
> Maybe the starjoin optimization could be made to work for this type too?

Yeah, I'm slightly itchy about relying on FKs in this heuristic at
all; it doesn't seem like quite the right thing. I think we do want
one side of the join to be joining to a PK or at least a unique index,
but I'm not sure we need to insist on there being an FK relationship.

A couple of minor coding notes:

* There's no point in doing anything (except recursing) if the joinlist
contains fewer than 3 items, and maybe as a further heuristic
this shouldn't kick in till later yet, like 5 or so items.
When there are just a few items, the possibility of missing the
best plan seems to outweigh the minimal savings in plan time.

* Joinlists never contain anything but RangeTblRefs and sub-lists.
See make_rel_from_joinlist.

* Your reconstructed joinlist is overly complicated. Instead of

+ newlist = list_make2(newlist, list_make1(lfirst(lc)));

you could just do

+ newlist = list_make2(newlist, lfirst(lc));

because a single-element subproblem is useless.

I notice that the patch doesn't apply cleanly anymore because of
the introduction of guc_parameters.dat. So here's a v3 that
rebases over that, and I took the liberty of fixing the joinlist
construction as above, but I didn't do anything else.

regards, tom lane