hash - 在合并语句中使用散列键作为比较列

Question

我必须在雪花数据库中实现合并语句。 Target 表中将有超过 60 亿行。比较的列有20个左右。我想在Snowflake中的所有20个列的基础上使用HASH函数生成哈希键。但是我读了文档 hash其中提到在 40 亿行之后很可能会得到重复的哈希键。我的理解对吗？那么我应该避免使用哈希键来比较记录并使用所有列吗？或者可以使用 hexa 128 位的 md5 或任何自定义的哈希函数。请提出建议。

Answer 1

TL;DR 版本:根据您的行数，使用 HASH 函数可让您有 62% 的机会两行的哈希值发生冲突。使用 MD5 而不是 HASH 会将您发生冲突的可能性降低到百分之几。在同样大小的仓库中，计算 MD5 比计算哈希需要多出大约 24% 的时间。建议:如果不能容忍非常罕见的冲突，则匹配 1) MD5 或 2) 散列和列比较。选项 2 会更快，但如果架构随时间发生变化，则需要更多维护。

在合并中使用散列的主题有其自己的立场文件，我相信已经写了很多。我们将重点关注您的具体情况以及 Snowflake 的回应。

让我们从您引用的文档部分开始。当唯一的输入导致相同的散列值时，它被称为冲突。这是数学和计算中的经典问题，称为生日问题 (https://en.wikipedia.org/wiki/Birthday_problem)。有大量关于该主题的文章，因此我们将坚持与您的情况相关的内容。

如果您在 60 亿行的表上使用 64 位散列，则发生冲突的概率约为 62%。不过，这仍然是一个可管理的问题，我们将在稍后探讨。

如果您对 60 亿个输入使用 128 位散列(例如 MD5)，则概率四舍五入为零。即使您的表增长到行数的 1000 倍，发生冲突的概率也将为 0.0000000000053%。

虽然从表面上看这似乎解决了碰撞问题，但它引入了一个新问题。 MD5 函数比散列函数的计算成本更高。我们可以通过对中型仓库进行一些简单的测试来确定多少。

select count(md5((concat(*)))) 
from "SNOWFLAKE_SAMPLE_DATA"."TPCH_SF10000"."ORDERS"; -- 18m 41s

select count(hash((concat(*)))) 
from "SNOWFLAKE_SAMPLE_DATA"."TPCH_SF10000"."ORDERS"; -- 15m 6s

我使用计数来消除结果收集时间，但它仍在计算 MD5 和哈希值。 MD5 的计算时间比散列长约 24%。

这将我们带到了 TL;DR 讨论的最后一部分，使用散列函数和列比较。这是更快的选择，也是唯一保证不发生碰撞的选择。它更快，因为伪代码中的这个操作:

条件 1 和条件 2

在此表达式中，如果第一部分失败，则无需测试第二部分。我还没有在 Snowflake 合并匹配子句中(还)对此进行实验性测试，但看不出它会在匹配行时测试表达式的第二部分。这样实际上所有的匹配都可以通过比较哈希来快速处理，只有极少数情况下还必须测试列匹配。

最后一个想法:相对于表的大小，每次合并的行数越少，MD5 的额外计算时间就越不重要。您已经为表中的 MD5 值支付了额外的计算时间。如果您要合并几千行，计算 MD5 的 24% 额外时间是无关紧要的，并且使您不必在匹配子句中维护列列表。