我有一个包含用户名（约1000行）的表，称为“潜在用户”，另一个表称为“实际用户”（约1000万行）。所有记录仅由[a-z]字符组成，没有空格。另外，我知道所有潜在的\u用户都不在实际的\u users表中。
我想能够计算出潜在用户的每一行，根据levenshtein距离，实际用户中最近的记录是多少。例如：
| potential_users|
|----------------|
| user1 |
| kajd |
| bbbbb |和
| actual_users |
|--------------|
| kaj |
| bbbbbbb |
| user |将返回：
| potential_users | actual_users | levenshtein_distance |
|-----------------|--------------|----------------------|
| user1 | user | 1 |
| kajd | kaj | 1 |
| bbbbb | bbbbbbb | 2 |如果表很短，我可以做一个交叉连接，为潜在用户中的每条记录计算实际用户中的levenshtein距离，然后返回值最低的一个。但是，在我的例子中，这将创建一个1000 x 10000行的中间表，这有点不切实际。
有没有一种更干净的方法来创建交叉连接来执行这样的操作？
2条答案
按热度按时间rqdpfwrv1#
我认为你不能用一个简单的连接来完成，有完整的算法来计算。这篇文章展示了levenshtein距离算法在sql中的实现：
https://www.sqlteam.com/forums/topic.asp?topic_id=51540&whichpage=1
xt0899hw2#
不幸的是，没有交叉连接是不可能做到的。最后，每个潜在用户都需要与每个实际用户进行测试。
然而，presto将在多个线程和机器上并行执行join，因此只要有足够的硬件，它就可以非常快速地执行。注意，在presto中，中间结果是从一个操作符流到另一个操作符的，因此对于这个查询没有10mx1k行的“中间表”。
对于这样的查询
这是查询计划：
特别是，对于这个部分，一旦交叉连接产生一行，它就被输入到投影操作符中，该操作符计算两个值之间的levenshtein距离，然后输入到聚合中，聚合中每个“潜在”用户只存储一个组。因此，此查询所需的内存量应该较低。