@
yjhatfdu2 #19 我用 SQLite 试了下,感觉用普通 SQL ,也勉强能满足这个需求。
## 结果
- 数据:4000 标签,1 亿数据,50 标签/数据(即,倒排索引中,约 50 亿数据 ID )
- 性能:0.8s 查询一个标签,拥有的 625W 数据 ID ,升序输出
- 体积:倒排索引表,约 11 GB
## 环境
- SYS:Win11
- CPU:i7-4790
- MEM:16 GB ,1600 MHz
- HDD:顺序读 150 MB/s ,4K 随机读 0.65 MB/s
## 多标签呢?
SQLite 不支持 Sort Merge Join ,多个标签一起查时,很慢。。
需要物化每个标签的结果,再由 SQLite 进行布隆匹配、B 树二分查找。。
(测前,都用 RamMap 清除了,系统对文件的缓存)
2 个 625W 数据 ID 的标签,结果 250W ,耗时 4.9 秒,
3 个 625W 数据 ID 的标签,结果 205W ,耗时 8.5 秒,
4 个 625W 数据 ID 的标签,结果 120W ,耗时 11.9 秒。。
不知道能不能用 Virtual Table ,写个表值函数(知道有,没写过),自己实现:
- Sort Merge Join 的效果,流式匹配所有标签,免除物化表、上千万次 B 树匹配的开销
- 提速读取数据 ID ( SQL 中,若写为 `SELECT COUNT(*)`,不计算具体数据 ID ,会提速到 0.1s )
## 倒排索引结构
- 表结构:`(<标签 ID ,高位数据 ID >,低 11 位数据 ID 集合 BLOB )`
- 若 > 146 个低位数据 ID ,第 3 列视为 293 字节的 Bitmap ,但每字节最高位弃用( SQLite 中没有便捷转换 128~255 为单字节 BLOB 的方法)
- 否则,每个低位数据 ID ,转为二字节 UTF-8 字符串( 0~127 需后补 `x'00'`),并串联起来。
## 测试数据
- 标签 ID:`[0, 3999]`
- 数据 ID:`[1, 1e8]`
- 每个数据拥有的标签 ID:`[(数据 ID * 1) % 4000, (数据 ID * 2) % 4000, ..., (数据 ID * 50) % 4000]`
- 标签 ID 为 400 、1600 、2800 、3600 时,拥有的数据 ID 最多,都为 625W 个
## 查询 SQL
```sql
-- V 站吞空格,缩进改为全角空格了
WITH
t1 AS MATERIALIZED (
SELECT (data_hi_id << 11) |
CASE WHEN i.stop = 7 THEN -- 低位数据 ID 量 <= 146 ,逐 2 字节翻译
IFNULL(unicode(substr(data_lo_ids, j.value, 2)), 0)
WHEN j.stop & (1 << (6 + j.value)) THEN -- Bitmap ,逐 bit 翻译
i.value + j.value - 1
END AS data_id
FROM tag_data
JOIN generate_series(7, IIF(length(data_lo_ids) < 293, 1, 293) * 7, 7) i
JOIN generate_series(
IIF(i.stop > 7, -6, 1),
IIF(i.stop > 7, unicode(substr(data_lo_ids, i.value / 7, 1)), length(data_lo_ids)),
IIF(i.stop > 7, 1, 2)) j
WHERE tag_id = '《第一个标签 ID 》'
-- 这句加了好慢。。怀疑是反复计算 data_id 导致
-- AND data_id IS NOT NULL
),
-- 以下结构类似,省略了
t2 AS (...),
t3 AS (...),
t4 AS (...)
-- 写成 COUNT(*) 且仅 t1 时,飞快
-- 估计是不用算具体 data_id 了
SELECT COUNT(data_id)
FROM t1
JOIN t2 USING(data_id)
JOIN t3 USING(data_id)
JOIN t4 USING(data_id)
-- 匹配到后面,预计数据量很少时,可采用这种方式:
/*
WHERE EXISTS (
SELECT 1
FROM tag_data
WHERE tag_id = '《第四个标签 ID 》'
AND data_hi_id = data_id >> 11
AND CASE WHEN octet_length(data_lo_ids) <= 292 THEN
instr(data_lo_ids, IIF(data_id & 0x780, char(data_id & 0x7FF), char(data_id & 0x7FF, 0)))
ELSE
unicode(substr(data_lo_ids, (data_id & 0x7FF) / 7 + 1, 1)) & (1 << (data_id & 0x7FF) % 7)
END)
*/
```
## 增删改
用触发器实现。但很慢。。
C++ 新人,正好练练手,生成倒排索引库(这都要花十几分钟。。):
```c++
// 同上,缩进是全角空格
#include <string>
#include <vector>
#include <iostream>
#include <string_view>
#include "sqlite_modern_cpp.h"
constexpr size_t MAX_DATA_ID = 1e8;
constexpr size_t MAX_TAG_COUNT = 50;
constexpr size_t MAX_TAG_ID = 4000 - 1;
constexpr size_t MAX_MEMORY = 8ull << 30;
constexpr auto DB_PATH = "D:/out.db";
int main() {
struct TagData {
struct {
uint8_t data_lo_ids[(2048 + 6) / 7]{};
} data_hi_ids[(MAX_DATA_ID >> 11) + 1]{};
};
constexpr int tag_steps = MAX_MEMORY / sizeof(TagData);
sqlite::database db(DB_PATH);
db << "CREATE TABLE IF NOT EXISTS tag_data ("
" tag_id INT,"
" data_hi_id INT,"
" count INT,"
" data_lo_ids BLOB,"
" PRIMARY KEY (tag_id, data_hi_id)"
") WITHOUT ROWID";
std::string blob_buf;
std::vector<uint16_t> data_lo_ids;
auto insert_stmt = db << "INSERT INTO tag_data VALUES (?, ?, ?, CAST(? AS BLOB))";
for (size_t tag_id_beg = 0; tag_id_beg <= MAX_TAG_ID; tag_id_beg += tag_steps) {
auto tag_id_end = (std::min)(tag_id_beg + tag_steps - 1, MAX_TAG_ID);
auto tags = std::make_unique<TagData[]>(tag_id_end - tag_id_beg + 1);
db << "BEGIN";
std::cout
<< "正在计算 1~" << MAX_DATA_ID << ",每个数的 1~" << MAX_TAG_COUNT << " 倍,÷" << MAX_TAG_ID + 1
<< " 后的余数,是否在 [" << tag_id_beg << ", " << tag_id_end << "] 范围内……" << std::endl;
for (size_t data_id = 1; data_id <= MAX_DATA_ID; data_id++) {
for (size_t times = 1; times <= MAX_TAG_COUNT; times++) {
size_t tag_id = (data_id * times) % (MAX_TAG_ID + 1);
if (tag_id >= tag_id_beg && tag_id <= tag_id_end)
tags[tag_id - tag_id_beg]
.data_hi_ids[data_id >> 11]
.data_lo_ids[(data_id & 0x7FF) / 7] |= 1 << ((data_id & 0x7FF) % 7);
}
}
for (size_t tag_id = tag_id_beg; tag_id <= tag_id_end; tag_id++) {
auto& tag = tags[tag_id - tag_id_beg];
std::cout << "正在写入 tag_id = " << tag_id << " 至数据库……\r";
for (auto& data_hi: tag.data_hi_ids) {
data_lo_ids.clear();
for (size_t i = 0; i < sizeof data_hi.data_lo_ids; i++)
if (data_hi.data_lo_ids[i])
for (size_t j = 0; j < 7; j++)
if (data_hi.data_lo_ids[i] & (1 << j))
data_lo_ids.push_back(i * 7 + j);
if (data_lo_ids.size() > 292 / 2)
insert_stmt
<< tag_id << (&data_hi - tag.data_hi_ids) << data_lo_ids.size()
<< std::string_view((char *) data_hi.data_lo_ids, sizeof data_hi.data_lo_ids)
>> []{};
else if (!data_lo_ids.empty()) {
blob_buf.clear();
for (auto lo_id: data_lo_ids)
if (lo_id > 127)
blob_buf.append({char(0xC0 | (lo_id >> 6)), char(0x80 | (lo_id & 0x3F))});
else
blob_buf.append({char(lo_id), 0});
insert_stmt
<< tag_id << (&data_hi - tag.data_hi_ids) << data_lo_ids.size() << blob_buf
>> []{};
}
}
}
db << "COMMIT";
}
}
```