Re: Key joins

Hi,

I took a quick look at the patch over the past couple days. I don't have
a perfect understanding of how it works, but let me share what I have so
far, before I get distracted by other stuff.

I'm interested in this patch because there seems to be a possible
overlap with the overlap with the starjoin planning (in that maybe we
could try reusing some of the derived information for that).

It's a mix of random thoughts, high/low level, important/superficial in
no particular order.

1) It does not compile, ATExecSetRowSecurity seems to be missing
prev_rls or something like that. I simply commented this out, to get it
to compile.

2) fk_referenced_selected in find_key_join_match should be marked as
PG_USED_FOR_ASSERTS_ONLY, to fix compiler warning

3) It'd be helpful if the commit message for 0001 explained why this
change is needed. More clearly than now, I mean. The initial message in
this thread points at another thread as the source of this, but that
thread is huge so how are reviewers expected to find the explanation?

Don't explain just what the commit does, but why it's needed. Say, give
an example of how the old code fails.

4) I think there needs to be a README explaining how the feature works,
i.e. the design and trade offs. Alternatively, it could be explained in
a comment at the beginning of some .c file, but a README seems easier to
find. Without this, reviewers have to piece it from the sgml "user"
docs, and random comments all over the place.

5) It might be helpful if the README defined a couple terms introduced
by the patch, but not really defined anywhere. I mean terms like: join
point, proof, proof graph, fact, surface, "relation visible from". I can
guess what each of these means, but maybe I got it wrong.

Although, I now see "join point" was used in the docs before, so maybe
it's a well-known term?

6) Does it always have to be a "foreign key traversal"? Consider an
example like this:

create table dim (id serial primary key);
create table f (id serial primary key, did int);
select * from f left join dim for key (id) <- f(did);

Currently this fails because of no matching foreign key constraint, but
isn't that pretty much the same thing as if the table actually had the
foreign key (at least considering the cardinality of the join - it won't
change it by adding/removing rows).

I realize that'd contradict the "FOR KEY" part of this patch, but it's
also one of the things that might be beneficial for the starjoin
planning (in that we could maybe extend it to more cases). Although,
maybe we could check those constraints during planning, just like we
check the fkey_list.

7) The patch invents a new "FILTER" clause for joins:

[ FILTER (WHERE join_filter) ]

I understand why it's done - there may be additional join conditions, on
top of the FK equality. But I think it'll be rather confusing. We
already have a "Join Filter", which is used for join clauses that happen
to not be used as "proper" join conditions (e.g. Hash/Merge Cond), and
has to be evaluated "after" the join itself. And now we'd have another
kind of "join filter" ...

Is there a different that'd make this work without the FILTER? For
example, we might encode the "key join" information in the existing ON
(...) clause:

ON (KEY (oi.order_id) -> (o.id) AND ... other clauses ...)

but it seems not as readable. Or maybe just use something else than
"FILTER"? Not sure.

8) I don't understand this change in functioncmds:

/* Routine kind cannot change for an existing pg_proc OID. */
Assert(procForm->prokind != PROKIND_AGGREGATE);

The comment says we can't change OID, but the assert checks it's not an
aggregate functions. Isn't that misleading?

9) DefineView now adjusts the query ID. Why is that needed? Isn't that a
bit weird?

10) checkWellFormedRecursionWalker now recurses, but why is that needed?

11) It's not clear to me why we need p_creating_stored_object, and it's
not explained anywhere. Maybe it's obvious, but not to me.

12) I'm very skeptical anyone can meaningfully review parse_key_join.c.
It's 150KB with ~5200 lines (very dense, with pretty minimal comments).
That's a massive file. The chance of me declaring this committable is
about 0%, simply because I wouldn't believe I understand it.

I think it needs to be broken up into smaller pieces, somehow. I don't
know how, but perhaps it's possible to extract a "minimal feature"
handling some limited subset of cases, and then gradually expand it?

Furthermore, it seems a lot of that file is duplicate with code we
already have elsewhere. For example, couldn't it use a bunch of list
functions instead of writing a local version?

list_contains_equal_node -> list_member
append_dependencies_unique -> list_concat_unique
append_dependency_unique -> list_append_unique
...

There may be more such cases, I haven't looked for them.

13) I think the main question is whether parse-analyze is the right
place to handle this. I don't know. I assume one of the reasons for
doing that is to get an error when defining a view, or when altering an
object - e.g. like when dropping a function used by a view. Which seems
reasonable, people would not like views silently broken by DDL.

But it seems to be this also leads to a lot of code duplication, because
the parse analysis now has to "reimplement" a lot of the stuff already
done in later stages, after parse analyze. For example, we have the
root->fkey_list thing, but that's not available yet.

There's probably more such information - like innerrel_is_unique,
rel_is_distinct_for, relation_has_unique_index_for etc.

Maybe it's not worth it? What if we did this in the planner instead? How
much simpler would it get? My intuition is it'd get much smaller, but
maybe I'm wrong.

It'd probably mean it's not necessary to expand views during parse,
which was one of the problems mentioned at the beginning of this thread.

I suppose we'd need to keep additional information in the plan to know
which joins to check, etc.

14) If we wanted to use some of this for the starjoin planning stuff,
we'd need to propagate more information too, I think. But I'm not sure
about this - we already have the information about foreign keys, so if
key joins are tied to foreign keys, there would not be no new useful
information I suppose.

Plus, I don't want to make that patch dependent on people using new
syntax. If that can give us *additional* information, that would be a
different thing.

15) I'm not sure about using dependencies to store "proofs". Maybe it's
fine, but the existing deptypes are only about DROP behavior - whether
it's OK to drop either side automatically, etc.). But the new deptype
DEPENDENCY_KEYJOIN also carries additional meaning (i.e. it means this
is a proof). I don't see an immediate issue with it, though.

16) I was wondering what performance impact this has, roughly. So I
created a simple 4-way join with fact + 3 dimensions:

create table dim1 (id serial primary key, val text);
create table dim2 (id serial primary key, val text);
create table dim3 (id serial primary key, val text);
create table f (id serial primary key,
d1 int not null references dim1(id),
d2 int not null references dim2(id),
d3 int not null references dim3(id));

and then measured throughput with 2 queries

select * from f
join dim1 on (dim1.id = d1)
join dim2 on (dim2.id = d2)
join dim3 on (dim3.id = d3);

select * from f
join dim1 for key (id) <- f (d1)
join dim2 for key (id) <- f (d2)
join dim3 for key (id) <- f (d3);

which is the same query, except for the FOR KEY syntax. And I got this
(under explain, to only do the planning):

patched master
-----------------------------
join 25251 24906
keyjoin 17159

So that's ~30% regression compared to master / regular joins. I also
tried with join_collapse_limit=1 to eliminate the join order planning:

patched master
-----------------------------
join 31476 31252
keyjoin 19353

That's 40% regression. Of course, this is just explain - once there is
data in the table, and actual execution, the differences will be much
smaller. Still, it's not great.

I haven't looked very closely, but based on some quick profiling it
seems ensure_key_join_surface_facts / compute_key_join_relation_facts is
doing expensive stuff like findNotNullConstraintAttnum or
get_index_constraint, both of which do systable scans. That should
probably go through syscache or something like that.

regards

--
Tomas Vondra