交叉联接、比较值和选择最接近匹配-更有效的方法

Question

我有两个有2列的表。我交叉连接并减去值。然后，我找到由减法排序的row_number，并选择其中row=1。我正在寻找与t1.id 值最接近的t2.id

这些桌子很大。row_number函数是否通过在1之后对所有内容进行排序来完成许多额外的不必要的工作？我只需要排名最低的一排。。有没有更有效的方法来写这篇文章？

表1

id	val
A1	0.123456
A2	1.123456
A3	-0.712345

运行速度可能更快-这取决于t1、t2中有多少行，以及添加索引等的灵活性。

正如@Chris所说，排序(尤其是多次排序)可能是一个杀手。随着排序的值数量呈指数级(几何级数？)增加，排序成本也会变得越来越差。如果t2只有两行，那么排序很容易，并且您的原始方法可能是最有效的。然而，如果t2有许多行，那么它将变得更加困难。然后，如果t1有很多行，并且你对每一行都进行排序，这也会乘以成本。

因此，出于测试目的，我在下面的t1和t2中分别使用了1000行。

下面我比较了几种速度和处理的方法和指标。)(剧透提醒)如果你可以预先排序(就像@Chris的建议)，那么你可以得到一些大的改进。

我不使用数据块(抱歉)，也无法在它们上测量速度等。因此，以下内容是在SQL server中编写和测试的，但我想可以很容易地修改为在数据块中工作。我认为主要的区别是这里使用的OUTER APPLY-我相信Databricks将是一个INNER JOIN LATERAL(例如，如何在Spark sql中使用outer apply-但请注意，我认为他们错了。outer apply相当于INNER ZOIN LATERAL，而CROSS apply等同于LEFT JOIN LATEAL)。

我创建了这两个表，并在其中各填充了1000行。

CREATE TABLE #t1 (A_id nvarchar(10) PRIMARY KEY, val decimal(10,8));
CREATE TABLE #t2 (B_id nvarchar(10) PRIMARY KEY, val decimal(10,8));

原始方法-对所有行进行排序

您的原始查询只需要读取很少的数据，但成本是它需要进行的排序量。因为ROW_NUMBER()对所有行进行排序，然后您只需要1，所以这是您的主要成本(正如@Chris所说)。

-- Original query
with cj as (
select 
#t1.A_id, #t2.B_id,  
row_number() over (partition by #t1.A_id order by abs(#t1.val - #t2.val)) as rw
from #t1
cross join #t2
)
select * from cj where rw = 1;

在我的电脑上，这花费了1600毫秒的CPU时间。

方法2-取MIN()值

但是，由于您只需要最小的一行，因此不需要真正对其他行进行排序。取一个"min"只需要对t1中的每个数据点扫描一次数据，然后选择最小的值。

但是，一旦有了最小的值，就需要再次引用t2来获得相关的t2 ID。

换句话说，这是的逻辑

• 只确定最小的绝对差异所花费的时间更少(而不是将它们全部排序)
• 花费更多的读取和更多的时间来找出t2的哪个值得到了绝对差

-- Using MIN() to find smallest difference
with cj as (
select 
#t1.A_id, #t1.val,
MIN(abs(#t1.val - #t2.val)) AS minvaldif
from #t1
cross join #t2
GROUP BY #t1.A_id, #t1.val
)
select cj.A_ID,
#t2.B_id
FROM    cj
CROSS JOIN #t2
WHERE   abs(cj.val - #t2.val) = minvaldif;

这花了我电脑大约一半的时间——大约800毫秒的电脑时间——但它读取的数据量是原来的两倍多。还要注意，如果t2中有值的重复，它可以返回几行。

方法3-横向连接

在这种情况下，您执行一个横向联接(在SQL Server中，它是一个"OUTER APPLY")，只选择所需的最小值1。与上面类似，您可以找到最小值，但您可以为t1中的每一行单独执行此操作。因此，您需要执行1000个"min"值，而不是1000个排序。

-- Lateral join with min difference
SELECT  #t1.A_id, t2_calc.B_id
FROM    #t1
OUTER APPLY 
(SELECT TOP (1) #t2.B_Id
FROM #T2
ORDER BY abs(#t1.val - #t2.val)
) AS t2_calc;

这是迄今为止效率最高的一次，读取次数很少，计算时间只有300毫秒。如果你不能添加索引，这可能是你能做的最好的事情

选项4-使用索引对数据进行预排序

如果你可以使用索引对数据进行预排序，那么你可以大大提高效率。

CREATE NONCLUSTERED INDEX #IX_t2_val ON #t2 (val);

问题是，即使你在t2.val上有一个索引，数据库也会有min(abs(t1.val - t2.val))的问题——它们通常仍然需要读取所有数据，而不是使用索引。

然而，你可以使用你在问题中确定的逻辑——min(abs(difference))值是t1.val最接近t2.val的值

在下面的方法中

1. 对于每个t1.val，找到最近的t2行，该行小于或等于，但不超过
2. 还可以找到，对于每个t1.val，它上面最近的t2行
3. 然后使用你在原始答案中的逻辑，找到其中最接近的一个

这也使用横向视图

-- Using indexes
with cj as 
(SELECT #t1.A_id, #t1.val AS A_val, t2_lessthan.B_id, t2_lessthan.val AS B_val
FROM    #t1
CROSS APPLY 
(SELECT TOP (1) #t2.B_Id, #t2.val
FROM #T2
WHERE #t2.val <= #t1.val
ORDER BY #t2.val DESC
) AS t2_lessthan
UNION ALL
SELECT  #t1.A_id, #t1.val AS A_val, t2_greaterthan.B_id, t2_greaterthan.val AS B_val
FROM    #t1
CROSS APPLY 
(SELECT TOP (1) #t2.B_Id, #t2.val
FROM #T2
WHERE #t2.val > #t1.val
ORDER BY #t2.val
) AS t2_greaterthan     
),
cj_rn AS
(SELECT A_id, B_id,
row_number() over (partition by A_id order by abs(A_val - B_val)) as rw
FROM cj
)
select * from cj_rn where rw = 1;

计算时间：4ms。

对于t1中的每个值，它只需在t2中进行2次索引查找，并对这两个值进行"排序"(这非常容易)。因此，在这种情况下，速度要快几个数量级。

所以。。。实际上，最好的方法是，如果你可以对数据进行预排序(在这种情况下，通过添加索引)，然后确保你利用了这种排序

在这种情况下，过程代码比SQL中使用的集合逻辑更好。如果在表1&表2(分别)都是由val排序的，您可以利用排序的优势不比较As和Bs的每个组合。

使用表2作为主要变量，通过将表1中的第一个(最低)值读入变量FirstA，将表1的第二个值读入变量SecondA来启动"泵"。

首先循环，而下一个B<FirstA。输出B&FirstA，因为之后的每个A都会更远，因为列表是有序的。

现在使用Table2光标形成一个循环，依次读取每个B值。而B>SecondA，将SecondA移动到FirstA，并将表1中的另一个值读取到SecondA或光标末尾。现在B在FirstA和SecondA之间；其中一个最接近，比较abs(差值)并输出最低值，然后进行下一个循环迭代。

这就是它的全部内容。耗时的部分是在它们的游标内对两个表进行排序，即O(nlog(n))和O(mlog(m))。两者的比较是线性的[O(n+m)]。

希望您的数据库管理器有一种过程性脚本语言，可以让这一切变得简单。