sparksql使得请求连接两个Dataframe变得非常容易，并且有许多网页（例如1、2）描述了在执行器之间对数据进行洗牌的不同方式，以使连接对于具有不同大小和统计特性的数据集有效。然而，似乎很少讨论每个执行器中使用的核心算法的效率。
我的问题是，在Dataframe被洗牌到每个spark执行器之后，equi连接和不等式连接有什么复杂度类？
例如，如果我们假设每个执行器从左Dataframe接收n行，从右Dataframe接收m行，那么equi连接的简单实现将具有o（nm）的复杂度，但是类似map连接的实现将具有更低的o（n*log（m））的复杂度。
类似地，如果我们的连接条件

df0.join(df1, df0.col("key") >= df1.col("key"))

从理论上讲，可以找到所有行的位置 df1 它与中任意给定行的不等式条件相匹配 df0 成本为o（log（m）），而不是o（m）。
当然，在实践中，还会有许多其他因素影响执行连接所需的时间，特别是网络和磁盘带宽，因此，仅通过测量连接时间来回答这个问题可能是没有结果的。
是否有人知道任何权威文档（即不只是源代码！）关于spark的这些常见连接类型属于什么复杂类？