@
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";
}
}
```