当ID是知识而非地址时会发生什么
地址什么都不知道
要在数据库中找到李舜臣,你需要一个ID。
在Wikidata中,李舜臣的ID是 Q50184。
这个数字指向李舜臣。
但字符串 Q50184 本身什么都不知道。
它不知道这是一个人还是一座建筑。 它不知道这是韩国人还是法国公民。 它不知道这是16世纪的人物还是21世纪的人物。 它不知道此人是生是死。
Q50184 是一个地址。
送信的邮递员完全不知道信封里写了什么。
他只是看信封上的地址然后投递。
UUID也是如此。550e8400-e29b-41d4-a716-446655440000。
128位随机数。唯一性只是为了避免碰撞——
它不告诉你任何关于所指对象的信息。
过去五十年来,数据库ID都是这样工作的。 ID是地址,要了解任何信息,你必须跟着地址去读取数据。
必须跟过去才能知道
为什么这是个问题?
假设你想找"19世纪出生的德国男性哲学家"。
在传统数据库中,流程是这样的:
1. 从persons表筛选 gender = 'male'
2. JOIN nationalities表并筛选 country = 'Germany'
3. JOIN birth_dates表并筛选 year BETWEEN 1800 AND 1899
4. JOIN occupations表并筛选 occupation = 'philosopher'
四次JOIN操作。 每次JOIN比较两个表的行。 如果表很大,需要遍历索引;如果没有索引,就执行全表扫描。 十亿条记录的情况下,这个过程需要数秒到数十秒。
为什么如此复杂?
因为ID什么都不知道。
看着 Q50184,你无法判断这是德国人还是韩国人,
所以必须去另一个表检索该信息。
每个问题都必须跟着ID指向的地方去查。 这就是数据库五十年来一直在支付的成本。
如果ID本身就知道呢?
让我们翻转前提。
如果ID本身就包含关键信息呢?
如果只需看ID, 就能判断它指的是人类、来自哪个国家、 属于哪个时代、如何分类呢?
要找"19世纪德国男性哲学家", JOIN变得不必要了。
扫描十亿个ID, 通过检查其比特就能立即判断每个是否匹配。
这就是语义对齐索引的核心思想。
将意义对齐到ID中
SIDX(Semantically-Aligned Index)是构建这种ID的研究。 GEUL语法中已经有用SIDX指向对象的Reference位置(GEUL-SIDX)。 但宽度和分配方式尚未确定,将根据积累的使用统计来决定。 下面为了说明,以64位为例。
SIDX的位不是随机数。 每一位的位置都被赋予了意义。
高位存放最重要的信息。 这是什么类型的实体?人、地点、事件,还是概念?
接下来的位存放分类信息。 如果是人,是哪个时代的人?哪个地区的人?
越往低位,信息越具体。
核心在于:
位的顺序就是信息重要性的顺序。
最根本的分类在最高位, 最细微的区分在最低位。
这不是简单的排序。 这是一种设计哲学。
从十亿到一万,一次扫描
SIDX的实际威力体现在数字上。
假设有十亿个实体,每个实体的SIDX是64位。 总容量:10亿 × 8字节 = 8GB。
这8GB可以整个装入内存。
想找"是人且来自东亚的实体"。 如果高位里有"人"的标志和"东亚"的代码, 一个位掩码就能完成筛选。
mask = 0xFF00_0000_0000_0000 (高8位:类型+地区)
target = 0x8100_0000_0000_0000 (人+东亚)
for each sidx in 10亿个:
if (sidx & mask) == target:
加入候选
这个运算可以用SIMD并行化。 瓶颈不在计算,而在内存带宽。 在为SILK做的预先测量中,用掩码扫描1亿个128位签名(1.6GB),Go 8线程约需27毫秒。 按同样的比例,10亿个64位SIDX(8GB)需要0.1秒多一点。
十亿条记录缩小到一万条。 在一万条中做详细筛选,转瞬即成。
JOIN零次。 索引树遍历零次。 只是一次位与运算。
宽度应该是多少
一开始,我以为需要更大的空间。
32字节(256位)。32维的FP16向量。 想把实体的所有关键属性都塞进ID里。 是否为人、性别、国籍、时代、职业、地区、生死、分类路径……
但我意识到了一件事。
ID不需要知道一切。
只要把十亿条缩小到一万条就够了。 剩下的交给精确核对。
这就像检查站。 在高速公路收费站,根据车牌判断 “这辆车开往京畿道方向”, 不需要知道车里装了什么。
那么,64位也许就够了。 用高位抓住类型和大类, 用低位抓住细分类, 把十亿条缩小到一万条看起来绰绰有余。 64位 = 4个16位字。在流中也很轻。
但这仍然是假设。 GEUL不在书桌前决定宽度。 以4 WORD(64位)、16 WORD等为候选,根据实际使用统计来决定。 在决定之前,用按顺序编号的ID指向对象, 分配SIDX之后,再把两个ID连接为同一个对象。
优雅降级:比特截断后意义依然存在
语义对齐的另一个优势是其降级特性。
因为SIDX的比特按从重要到次要的顺序排列, 即使低位损坏或被截断, 高位中的核心信息依然被保留。
完整64位: "李舜臣,16世纪朝鲜海军将领"
48位: "16世纪朝鲜军事将领"
32位: "16世纪东亚人类"
16位: "人类"
8位: "物理实体"
随着信息被截断,具体性丧失, 但最基本的分类保留到了最后。
这是"优雅降级"原则在比特层面的实现。
即使网络中断只传递了部分数据, 系统知道"我不确定这是谁,但至少这是一个关于人类的故事" 并可以继续推理。
模糊的轮廓胜过完全的沉默。 部分理解胜过完全失败。
查询变成ID
语义对齐索引开启的最有趣的可能性是:
如果能把自然语言查询变成一个临时SIDX呢?
用户问:“壬辰倭乱时击败日军的将军是谁?”
编码器分析这个问题。 是人。东亚。16世纪。与军事有关。 把这些属性组装成位,就得到一个临时SIDX。
用这个临时SIDX扫描十亿个SIDX。 位模式最相似的实体浮现为候选。 李舜臣、元均、权栗、李亿祺……
再核对详细信息,就得出最终答案。
检索和实体链接(entity linking)可以成为同一个机制。 无需单独的搜索引擎, 无需单独的NER(命名实体识别)流水线, 只需一次SIDX比较。
为什么不用B树?
传统数据库使用B树索引。
B树擅长在已排序的数据中以O(log n)找到特定值。 对于"找到Q50184",它是最优的。
但对于"找出所有是人且来自东亚的实体",它就很弱。 复合条件检索需要对多个索引求交集, 而交集的代价随数据规模急剧增长。
SIDX + SIMD全量扫描是另一种思路。
如果说B树是快速回答"这个地址住着谁"的电话簿, 那么SIDX扫描就是快速回答"谁具有这些特征"的画像。
问题的种类不同,最优的数据结构也就不同。
| 问题类型 | B树 | SIDX扫描 |
|---|---|---|
| 按特定ID查询 | O(log n),最优 | 不需要(用哈希解决) |
| 复合条件筛选 | 需要JOIN,慢 | 一次位与,快 |
| 相似实体检索 | 不可能 | 可用位相似度 |
| 插入 | O(log n),需重新平衡 | O(1),追加 |
| 实现复杂度 | 高 | 低 |
两者不是竞争,而是分工。 如今SILK用有序run和二分查找处理"谓词为P106、宾语为Q169470的文档"这类精确查询。 位签名扫描作为它前面的第一道过滤器,计划在下一步实现。
简单、粗暴、快速。
霍夫曼的智慧
SIDX的位分配遵循霍夫曼编码的原理。
霍夫曼编码给频繁出现的符号分配短码, 给很少出现的符号分配长码。
在SIDX中,最常需要的分类信息放在高位, 很少需要的细节放在低位。
GEUL语法的Codec分配也是同样的原理。 频率已经确认的形式获得TAG WORD内的短直接码, 少用的形式则归入带扩展TAG的Issuer形式。
霍夫曼的智慧贯穿整个设计。 把最低的代价给最常用的东西。
总结
传统的ID是地址。地址什么都不知道。
- ID不懂意义,就每次都得顺着它去读数据。这就是JOIN。
- 在十亿条记录上做四次JOIN很慢。
- SIDX是把意义对齐编码进ID本身的研究。
- 一次位掩码与运算就能把十亿条缩小到一万条。JOIN零次。
- ID不需要知道一切,只要缩小候选即可。宽度根据使用统计来定。
- 重要信息在高位,所以即使位被截断,核心意义也能保留。
- 如果能把自然语言查询变成临时SIDX,检索就变成位运算。
当ID不再是地址而成为知识的那一刻, 数据库的规则就改变了。