换个视角看SQL Join

导论

本文主要讨论Streaming Join。在Stream & Table Theory的基础上，我们给Classic SQL引入了时间维度，并提出了Time-Vary Relation，并认为“Streaming SQL可以全盘继承Classic SQL的所有Operator，并且得到的结果也是一样的”，SQL里最复杂的Join也不例外。

Streaming Join在Spark里分为了Stream - Static/Stream - Stream Join两类，Flink也大致如此；而在《设计数据密集型应用》一书中认为在Stream的世界里，Join分为了流流join、流表join、表表join，除此以外还需要考虑时间相关性，引入Window的概念。

在《Streaming Systems》一书中，将Join的理论模型做了更高程度的抽象（不考虑具体的实践）。在TVR的视角下，流流join、流表join、表表join和时间相关的Window的概念的诞生自然而然。

新视角下的Join

所有的Join本质是都是Streaming Join

Join过程可以理解为是两个不同Dataset中的元素根据相同的property（例如，Key）组合成同一个Group中的元素，Streaming & Table Theory认为所有的group操作都是消费Streaming后生成Table。因此，所有的Join本质上都是Streaming Join。

以Full Outer为例

在ANSI SQL定义中，Join可以分为FULL OUTER、 LEFT OUTER、 RIGHT OUTER、 INNER和 CROSS五种。五种类型的Join过程都非常类似，以Full Outer为例，便可一叶而知秋，其它的Join类型皆以此引申。假设在12:10的时候有两张表Right和Left。

12:10> SELECT TABLE * FROM Left;

12:10> SELECT TABLE * FROM Right;

在12 : 10运行Full Outer Join，将两张表组合在一起，会得到如下的结果：

12:10> SELECT TABLE  Left.Id as L,   
                     Right.Id as R,       
       FROM Left FULL OUTER JOIN Right   
       ON L.Num = R.Num; 

这是Table意义上的Join，但是回到12 : 10之前，从整个时间演变的过程中实现Full Outer Join，我们就会得到下面的变化：

1. 在12 : 01之前，两张表还没有数据，因此会得到一张空表。 [-inf, 12:01)： LR
2. 12:01到12:02时，Right表生成了一条数据，而Left表依然是空。 [12:01, 12:02)： LRnullR2
3. 12:02到12:03时，Left表产生了一条数据，但是与Right表没有相同的Key值。 [12:02, 12:03) : LRnullR2L1null
4. 12:03到12:04时，Left生成了L3这条记录，但是此刻Right的R3还没生成。 [12:03, 12:04): LRnullR2L1nullL3null
5. 12:04到12:05时，Right生成了R3，与Left的L3匹配。 [12:05, 12:06): LRnullR2L1nullL3R3nullR4
6. 12:05到12:06时，两张表的数据都已基本上完整，与12:10得到的结果无异。 [12:05, 12:06): LRL2R2L1nullL3R3nullR4

这就是加上了时间维度的Join，也就是TVR。

12:00> SELECT STREAM  Left.Id as L,        
              Right.Id as R,        
              CURRENT_TIMESTAMP as Time,      
              Sys.Undo as Undo       
       FROM Left FULL OUTER JOIN Right       
       ON L.Num = R.Num;

[12:00, 12:10]:

在《Streaming　SQL基础》一文中提到过，尽管Table、TVR、Stream视角产生的结果不一致, 但是上面的讨论给我们展示了这三个视角本质上描述的都是同一份数据。

the table snapshot shows us the overall dataset as it exists after all the data have arrived, and the TVR and stream versions capture (in their own ways) the evolution of the entire relation over the course of its existence.

结尾

我们可以发现，Stream的概念是自然而然地在Join中体现出来；在Dataflow模型中所使用时间推理工具（Window、Trigger、Watermark）都可以在Left和Right表中引入，只需要良好地处理Late Data即可。这就是高维角度下地Join过程，各种概念都应该是自然地推理出来，而不需要生硬地分类。

参考文章：

1. https://www.codeproject.com/Articles/33052/Visual-Representation-of-SQL-Joins
2. https://spark.apache.org/docs/latest/structured-streaming-programming-guide.html#join-operations
3. https://ci.apache.org/projects/flink/flink-docs-release-1.8/dev/table/sql.html#joins
4. https://ci.apache.org/projects/flink/flink-docs-release-1.8/dev/table/streaming/temporal_tables.html
5. https://ci.apache.org/projects/flink/flink-docs-release-1.8/dev/table/streaming/joins.html