sql: support lateral joins

[knz]

A join is "lateral" when its right operand depends on the left operand.

Lateral joins are one of the ways a subquery or relational expression can be correlated.

Lateral joins occur:

• in the regular join syntax with the keyword "LATERAL", e.g. SELECT * FROM a, LATERAL b
• implicitly when using a SRF in the select render position and one of the SRF argument uses a column name from one of the existing FROM tables, e.g. SELECT generate_series(v) FROM kv
• also needed for common uses of jsonb_object_keys(), see sql: cannot project json_object_keys() on a json column #26110

Note: LATERAL in the join syntax changes the name resolution rules!

For example, the following two queries have very different behavior:

SELECT
   (SELECT a FROM db1.ab, LATERAL (SELECT * FROM kv WHERE v = b))
          -- v = b refers to "b" in db1.ab
FROM db2.ab

vs.

SELECT
   (SELECT a FROM db1.ab, (SELECT * FROM kv WHERE v = b))
          -- v = b refers to "b" in db2.ab!
FROM db2.ab

[knz]

@benesch found this:

LATERAL can also precede a function-call FROM item, but in this case it is a noise word, because the function expression can refer to earlier FROM items in any case.

https://www.postgresql.org/docs/current/static/sql-select.html

In other words, a join with a SRF is always lateral.

[justinj]

I think this is mostly straightforward, save for one minor hiccup, which is that we build our join trees right-to-left:

select * from a, b, c is a join (b join c)

however, the semantics here imply that they're built left-to-right: an expression with lateral (implicit or explicit) must be in a right subtree of an apply join with everything to the left of it as its left subtree:

select * from a, b, lateral c needs to mean (a join b) apply join c

It's not really possible to globally change the direction we build our joins until we have more thorough join ordering (because it can make hand-optimized queries much slower), so I think we would have to conditionally restructure the join tree in the presence of lateral.

[jordanlewis]

@justinj what's left to do after #36613?

[justinj]

Explicit (using the JOIN keyword) joins that use the LATERAL keyword

[awoods187]

How big a project is this to complete?

[justinj]

Pretty small, I just need to find the time to wrap it up

[awoods187]

That's exciting! Looking forward to this.

[yuzefovich]

Is this done now that #40945 has been merged? cc @justinj

[justinj]

I believe so!