06-EFT.WP.Core.DataSpec v1.0 | 第6章 分区、索引与查询

目录 ／ 文档-技术白皮书 ／ 06-EFT.WP.Core.DataSpec v1.0

第6章 分区、索引与查询

I. 范围与对象

• 规定 D 的物理分区、逻辑索引与查询执行的统一口径，使 partition/build_index/query 在不同 fmt 与存储后端下保持一致的可预估延迟与可验证正确性。
• 适配时间、空间、路径 gamma(ell) 场景，并与 pk/idx_k、manifest、schema_version、CRS、unit(dim)、m ∈ {0,1} 协同。

II. 术语与目标

1. 目标：最小化扫描体积与 I/O 放大，最大化裁剪与命中率，保证 pk 与契约查询的确定性。
2. 术语：
   • K = [k1,k2,...,kd]（分区键序） ，B_i = card(partition on ki)。
   • sel(P) = |{ r ∈ R : P(r) }| / N（选择率）。
   • C_proj（投影列集），alpha = |C_proj| / |Fields_total|（投影率）。

III. 公设（P66-*)

• P66-1 分区优先公设：凡 sel(P) 稳定且远小于 1 的谓词，应提升为分区键 K 的前缀。
• P66-2 单调有序公设：ts 与 ell 在分区内应保持非降，便于区段裁剪与顺序扫描。
• P66-3 不二义公设：pk 在任意分区层级上全局唯一；跨分区更新须通过新 part 生效。
• P66-4 指标一致公设：索引与 manifest.stats 的区间 [min,max] 不得与数据冲突；发现冲突即回滚发布。

IV. 分区策略与命名规范

• 时间分区：date=YYYY-MM-DD/ 或 hour=YYYY-MM-DD-HH/，窗口宽度 Delta_t 与 fs 在 manifest 声明。
• 空间分区：crs=EPSG:xxxx/gh=p{p}/，其中 gh = geohash(lon,lat,p) 或等价 s2cell 编码。
• 路径分区：pid=<path id>/ell_bucket=[ell_lo,ell_hi)/ 与 L_gamma = ( ∫_gamma 1 d ell ) 一并记录。
• 标签分区：sid=<site>/tid=<trajectory>/ 等低基数维度用于二级分桶。
• 组合分区：K = [date, sid, pid]（自左至右递减选择率）。

V. 分区键选择的代价模型（S66-1）

1. 设顶层至第 d 层分区桶数向量 B = [B1,...,Bd]，谓词在各键上的匹配比例 f = [f1,...,fd]。
2. 近似独立时（显式 approx independence）：
   • E[parts(P)] approx prod_{i=1..d} ceil( fi * Bi )。
   • V_scan approx E[parts(P)] * avg_bytes_per_part * ( alpha / ratio_compress )。
   • L approx seek_cost * E[parts(P)] + V_scan / throughput_io。
3. 选键准则：在候选集上最小化 E[parts] 与 L，并约束 B_i 不超过目标元数据开销。

VI. 时间序列分区规范

• 均匀采样：每 part 覆盖固定 M * Delta_t，记录 { ts_start, ts_end, fs } 与缺失统计 gap_count。
• 非均匀采样：保证 non_decreasing(ts)；行组按时间区段对齐，启用区间统计 {min(ts), max(ts)}。
• 常用键序：K = [date, sid] 或 K = [hour, sid]（高并发写入）。

VII. 空间与路径分区规范

1. 空间：
   • gh = geohash(lon,lat,p)，格网角尺度近似 tile_deg ≈ 180 / 2^p；p 由期望空间选择率与热点分布确定。
   • 记录 CRS 且对 lon/lat/alt 使用 float64；跨 CRS 查询需归一化后再下推。
2. 路径 gamma(ell)：
   • 以 K = [pid, ell_bucket] 分区，并在行组层使用连续 ell 区段；
   • 对 T_arr 数据集保留两口径结果与 delta_form 字段，支持区段级聚合。

VIII. 目录与文件命名（与 manifest 对齐）

• 模板：.../dataset=DS/schema=S/version=vX.Y.Z/date=YYYY-MM-DD/sid=.../pid=.../ell=[a,b)/part-00000-of-000K.parquet。
• 每个 part 在 manifest.files[*] 中记录 { path, bytes, hash_sha256, row_count, row_group_count, min,max }。

IX. 索引类型与存储绑定

1. 主索引：
   pk 聚簇（按 pk 排序或哈希分桶），保证等值查询 O(log N) 或 O(1) 桶定位。
2. 二级索引（idx_k）：
   • B+tree：适合范围查询与有序扫描（ts、ell、数值区间）。
   • hash：高基数等值查询（uid、rid）。
   • bitmap：低基数维度（sid、质量标签、枚举）；支持位运算复合谓词。
   • inverted：文本与多值标签（tags[]）。
3. 列式辅索：
   • 区段统计（zone map）：[min_i,max_i]；若与谓词区间不相交则裁剪。
   • Bloom 过滤：对热列启用；假阳率 p_fp approx ( 1 - exp( -k * n_elem / m_bits ) )^k。
   • 字典与游程编码：提升位图与范围剪枝效果。

X. 复合索引与前缀规则（S66-2）

• 复合键顺序与 K 一致：idx(k1,k2,...)。
• 前缀可用性：谓词覆盖前缀 k1,...,kj 时可直接利用索引；跳过前缀将退化为全扫描或次优查找。
• 覆盖索引：若 idx 同时包含 C_proj，则可“索引仅扫描”，跳过数据页。

XI. 查询规范与下推顺序

1. 谓词标准形：P = CNF( conj_i disj_{i,j} pred_{i,j} )，字段与常量单位须通过 unit(dim) 归一。
2. 下推顺序：
   • 分区裁剪（基于目录键与 manifest.stats）。
   • 列区段裁剪（zone map 与 Bloom）。
   • 二级索引查找（idx_k 命中）。
   • 行过滤与 m=1 掩码应用。
   • 投影 C_proj 与聚合。
3. 质量过滤惯例：WHERE m = 1 AND q_score >= q_min。

XII. 典型查询模板

1. pk 等值：SELECT * WHERE pk = rid，路径：idx(pk) → 定位 → 单行返回。
2. 时间窗：SELECT C_proj WHERE ts ∈ [t0,t1)，路径：分区裁剪 date/hour → zone map → 行过滤。
3. 空间窗：SELECT * WHERE gh IN {tiles} AND CRS = ref，路径：格网集合裁剪 → 二级索引或行过滤。
4. 路径段：SELECT C_proj WHERE pid = p AND ell ∈ [a,b)，路径：K=[pid,ell_bucket] 裁剪 → B+tree(pid,ell) 扫描。
5. T_arr 区段聚合：
   • T_arr(factored) = ( 1 / c_ref ) * ( ∑ over rows n_eff * Δell )；
   • T_arr(general) = ( ∑ over rows ( n_eff / c_ref ) * Δell )；
   • delta_form = | T_arr(factored) - T_arr(general) | 并断言 delta_form ≤ tol_Tarr。

XIII. 一致性与契约检查

• 分区一致：assert unique(pk) 跨全体分区成立；non_decreasing(ts) 与 non_decreasing(ell) 在分区内成立。
• 索引一致：count(idx_lookup(all)) == N；idx 覆盖列的区间统计与实际数据一致。
• 量纲一致：check_dim(expr) 通过，涉及方程时单位统一。

XIV. 流程 Mx-4（分区与索引构建）

• 负载剖面：估计 sel(P)、热点与写入并发，候选 K 集合生成。
• 代价评估：用 S66-1 估算 E[parts]、V_scan、L，选定 K 与桶数 B。
• 物理落盘：按 K 写入 part-*，生成 manifest.files 与区段统计。
• 索引构建：build_index(ds, keys) 生成 pk 与 idx_k；必要时预构 Bloom。
• 契约校验：assert_contract 运行唯一性、时间/路径单调、m 与 q_score 规则。
• 发布与冻结：export_manifest、attach_provenance、freeze_release(ds, tag)。

XV. 运行参数与基线建议

• 宽表分析：K=[date,sid]，列式启用统计与 Bloom，row_group_size_bytes ≈ 128 MiB。
• 路径重载：K=[pid,ell_bucket]，ell_bucket 选取使每分区 V_scan 与延迟目标匹配。
• 空间热点：提高 p 于热点区，或启用层级格网（多级 gh）。
• 等值高基数：优先 hash 或 pk 聚簇；范围混合等值：B+tree。

XVI. 实现绑定（I60 对齐）

• partition(ds:any, by:list[str]) -> dict[str, any]：依据 K 输出分区映射与统计。
• build_index(ds:any, keys:list[str]) -> IRef：生成 pk/idx_k，返回引用。
• query(ds:any, expr:str) -> any：执行标准形查询，遵循“分区裁剪 → 索引 → 过滤 → 投影”。

XVII. manifest 扩展字段（分区与索引）

• partitioning：{ keys: K, buckets: {k1:B1,...}, strategy, notes }。
• indexes：[ { name, keys, type, covered_cols, bloom: {enabled, p_fp_target} } ]。
• stats：按 part 与列的 { min, max, null_count, distinct_est }。

XVIII. 变更与兼容

• 变更分区方案或索引类型属破坏性更改，需 schema_version 的 major+1 与迁移清单。
• 兼容适配层：提供旧 K 到新 K' 的查询重写与路由表，直至历史数据回填完成。