Add support for SQL APPLY operation

[ashvina]

Related Substrait issues #119 #206

APPLY [1], introduced in SQL Server in 2005, is frequently used in practice. In Calcite the operation is LATERAL [2]. This operator looks similar to a JOIN, i.e. it executes an expression on the two input relations. However it is semantically different. In a JOIN, both sets to be joined must be self-sufficient. Otherwise it may result in errors like "multi-part identifier could not be bound". If dependencies between sets exists, a user can use correlated-subqueries. However, nested subqueries result in recursive evaluation strategies which incur O(n2) runtime [3].

Example [4]:
Intent: For each row from table1 select first rowcount rows from table2, ordered by table2.id

Query using APPLY
SELECT * FROM table1, CROSS APPLY ( SELECT TOP (table1.rowcount) * FROM table2 ORDER BY id ) t2

Queries without using APPLY

SELECT  * FROM 
table1 t1 JOIN ( SELECT  t2o.*, ROW_NUMBER() OVER (ORDER BY id) AS rn FROM    table2 t2o ) t2 
ON t2.rn <= t1.rowcount

As benchmarked in [4], execution of query with APPLY in SQL Server is 2 orders of magnitude faster than the query without apply. I.e. APPLY yields efficiency and is not replaceable with traditional JOINs.

Currently APPLY operation cannot be represented in Substrait. Which means, optimizations in various engines cannot be leveraged if APPLY like operations are deconstructed and mapped into existing operations supported by Substrait. To efficiently support full SQL, operation for APPLY is needed in Substrait. De-correlation should not be enforced.

CC: @jcamachor

[1] https://www.mssqltips.com/sqlservertip/1958/sql-server-cross-apply-and-outer-apply/
[2] CALCITE-1472
[3] https://15721.courses.cs.cmu.edu/spring2018/papers/16-optimizer2/hyperjoins-btw2017.pdf
[4] https://explainextended.com/2009/07/16/inner-join-vs-cross-apply/

[ashvina]

The difference between the join and APPLY operator becomes evident there is a table-valued expression on the right side and the table-valued expression is to be evaluated for each row from the left relation.