利用散列算法优化唯一索引性能(长文本字段的唯一索引优化)

时间:2022-12-11 21:19:17

问题

我们通常需要对一些长文本字段建立唯一索引,比如,我们自己的应用里面,经常会有 URL 或者 URI 字段,里面保存类似:

  http://www.pgsqldb.org/mwiki/index.php
http://www.eeeeworks.org/#post-27

这样的数据,并且要求唯一、不重复,常见的做法是创建一个唯一索引:

  create unique index on urls using btree (url);

这样处理是可以用的,但是如果只是做唯一的用途的话,会产生相当大的索引,比如我们有个表的索引就达到了 2.4G bytes 的大小,这个大小是非常惊人的,几乎令系统无法全部缓冲索引。因此造成了系统性能的明显下降。

如何解决这个问题呢?这里的主要核心在于如何减少IO,减少IO就意味着要减少数据的宽度,URL通常都会比较宽,上面两个URL一般都已经超过了30个字节,所以核心的思维在于减少这个URL的宽度,那么URL自身我们当然不能动,但是考虑到我们只是想保证唯一,以及检索是否存在这样的需求,那么我们完全还是有别的办法的,这里首先跳进脑海里的就是 MD5了。

解法

我们可以对URL做MD5运算,算出其散列值,只要散列值唯一,就基本可以保证URL是唯一的。(注意:我知道MD5是可能碰撞的,不过我们自己的数据量恐怕没那么容易碰撞,所以,先相信之)。于是,我可以创建这么一个索引:

  create unique index on urls using btree(md5(url));

似乎好了?看了看索引大小,从2.4G缩小到了900M多,貌似还可以,但是是不是就真的OK了?非也。

仔细看看 postgresql 里头 md5()函数的定义,它返回的是 text 类型,也就是用hex转码后的文本流,其宽度是 32 bytes,其实也不小!而我们只要二进制数据就可以了,所以,我们还要继续优化!

仔细查阅文档,可以发现 decode() 可以把 hex 转码的文本流反转成二进制类型(bytea),所以,我们这么干:

  create unique index on urls using btree(decode(md5(url), 'hex'));

就可以实现md5的二进制上头的唯一索引,现在看看大小:475M!老天,我们节约了 2G 的空间(内存)!

这个时候,我们需要用下面的方法查询URL或者URI是否存在:

  select * from urls where decode(md5(url), 'hex') = decode(md5({输入的URL串}), 'hex');

虽然麻烦些,但是效率很高,这就是典型的付出 CPU复杂度,换取 IO 复杂度降低的案例。

后记

二进制 16 字节的散列算法可能还是有些杀鸡用牛刀了,因为一般我们的数据也就几千万上亿行,所以64位(8字节)的散列算法就挺好的了,这个时候,我们可以考虑使用一些外部包,比如看看贡献包Pgcrypto的digest函数,digest自身也支持md5,用法是:

 select digest(url, 'md5')

也支持sha等,担心MD5碰撞的朋友,可以使用这个贡献包的sha算法。

也可以找FNV算法来实现64位(8字节)的散列,这样前面475M的索引,在付出一定的碰撞概率增大的风险之后,有可能进一步缩小到290M左右!

总结

其实所有的优化归根结底都是IO的优化,说白了就是越小越好,IO小了,就会逐级映射到内存,缓存等等环节,最后导致惊人的质变。而IO优化则是从数据类型的宽度,数据的宽度开始,一点一滴,积少成多,聚流成河进化而来的。