ordbog

Ordbog

这是一个提供单一特殊用途的损失压缩码的小型crate，旨在作为数据库存储的“扫描加速器”使用。此类码不是底层值的替代品；相反，它们提供对谓词的廉价近似答案，这些答案可能足以省略访问底层数据，类似于布隆过滤器可以省略查找，但支持更通用的谓词（例如，制表、范围查询）。

换句话说：将底层数据值的查询重写为码的查询可能会产生假阳性（需要二次查询底层数据），但不会有假阴性。并且对于给定字典中一半的码（“精确”码，分配给高频输入），它们也不会产生假阳性。

这些码“廉价”（即实际上对加速有用）有三个原因：

1. 它们很小，因此节省内存带宽：每个码1或2个字节，而底层浮点数/u64值是8个字节，字符串、高分辨率时间戳、uuid或大型小数类型则更多。

2. 它们是简单的整数，而底层数据可能更昂贵处理。

3. 它们是SIMD友好的：AVX2扫描一次可以查看16或32个码，而GPU扫描一次可以查看数百个。

此crate对于数值、文本或分类数据同样可用。它只需要有序的。它包括浮点数的包装类型。

它产生的码具有以下特性：

1. 每个码值在逻辑上是8或16位（取决于Mode枚举）。用户决定是否以8或16位操作：8位码应用于仅内存扫描，以省略64字节缓存行访问；16位码应用于磁盘扫描，以省略4k页面访问。

2. 码值0未使用，因此后续压缩可以使用它作为哨兵或缺失值码。

3. 所有其他码在偶数/精确（表示输入中的特定值）和奇数/不精确（表示可能输入值的开放区间）之间交替。因此，值1和0xff（或0xffff，或字典中最后的奇数码）编码了一侧的开区间。

4. 代码被分配给覆盖用户提供的样本，该样本在内部排序后，然后被划分为等大小的桶，包括重复项。然后计算每个桶内重复项的序列。每个桶内最长序列的样本值（即频率最高的样本值）被赋予一个（偶数）精确代码。然后，每个样本值之间的样本值开放区间被赋予一个（奇数）不精确代码。因此，提供的样本应该足够大，足以代表整个输入；但如果它不具备代表性，编码仍然有效，只是效率降低。

5. 分配的代码意味着顺序并保留等价性，具体来说

   • code(a) < code(b) 意味着 a < b
   • a < b 意味着 code(a) <= code(b)
   • a == b 意味着 code(a) == code(b)

参考

Brian Hentschel，Michael S. Kester，和Stratos Idreos. 2018. Column Sketches：一个用于快速和鲁棒的谓词评估的扫描加速器。在2018年国际数据管理会议（SIGMOD '18）的论文中。纽约，美国纽约，纽约州，美国计算机协会，857-872。

DOI：https://doi.org/10.1145/3183713.3196911

https://stratos.seas.harvard.edu/files/stratos/files/sketches.pdf

名称

维基词典（丹麦语）

名词：或dbog（单数确定或dbogen，复数不确定或dbøger）

1. 词典，词汇表

词源：来自ord（“词”）+‎ bog（“书”）。与瑞典语ordbok，英语wordbook，德语Wörterbuch比较。

许可证：MIT OR Apache-2.0