[RFC] 7-sql: 原生 SQL 查询（表存储结构 + 查询编译到 rwir）

[miaobyte]

目标：把「用 kvlang 原生实现 SQL 查询」收敛成一个可落地的最小闭环 —— 先定表存储结构，再定查询怎么执行。
本 issue 是设计提案（RFC），产物是裁决记录 + spec 卷草案，不是实现 PR。

三条物理事实（后面所有取舍都由它们推出）

1. 只有 compact 数组（ARRAYND）是定宽连续 + O(1) 下标 + GetPart 零拷贝切片 + WriteInPlace 同尺寸就地改；
   memindex（storetype=index/extindex）只给"成员枚举"，stringkeymap 给不了随机访问。
2. 借用读是块粒度的（kvspaceGet 借整值 / GetPart 借切片）→ per-row / per-field 访问 = 一次后端往返。
3. kvspace 没有事务、没有 CAS：原子单位是单键写；另有 Cp* 子树复制与 Watch。

两处必须先立规，否则地基是虚的：kvspaceListLen/ListAt 契约未承诺枚举顺序（shm 实现是 ART 字典序，
那只是实现）；ARRAYND 的 head 只有 ndim+dims、没有 cap → 追加必重分配。

表结构提案：v1 用行存 map[key]struct

物理形态（实测，redis 后端）：

/tmp/t1              char/utf8·/lib/Row:   ← 表 = map 头（声明成员类型 = 行实例）
/tmp/t1·1            /lib/Row:             ← 行 = 实例根（容器，无 body）
/tmp/t1·1·id         int64:9               ← 字段 = 独立子键
/tmp/t1·1·val        int64:10

kvspace list '/tmp/t1·' → 0 /lib/Row / 1 /lib/Row / 2 /lib/Row（枚举可用）。
一行不是一个 XValue，而是 1 + N字段 个键 —— 这一条决定了它的强项与死穴。

为什么行存做 v1

SQL 操作	行存	列存（分块 compact）	判定
PK 点查	1 次路径解析（PK 编码进行 key）	索引定位 + 借段	行存更优
单行 UPDATE	1 次单键写	改 N 个列段	行存更优
INSERT / DELETE	N+1 键 / deltree 子树删（空间即时回收）	追加 N 段 / 墓碑 + VACUUM	行存更简单
NULL	成员缺失 = None（天然三值逻辑）	必须存在性位图	行存更简单，且不用零值冒充 NULL
变长字段（text）	原生长度	需字典编码	行存更简单
二级索引	Ptr → 行 key（变长路径，较贵）	定宽 rowid（4/8B）	列存更优
非索引谓词 / 全表扫	(N+1)·rows 次寻址	rows/chunk 次借用	列存差 3～5 个数量级
ORDER BY	每比较 2 次寻址（只可能走索引）	排定宽列	列存
Hash join / 聚合	逐行取字段	借键列直接 hash / 累加	列存
向量化 / GPU 后端绑定	无连续列可交	借列即交 tensor/GPU	列存
多键原子性	一行多键，无多键原子	单提交指针	列存更优
键总数	×(N+1)（1M 行×5 列 = 6M 键）	÷chunk（约 1000× 少）	列存

代价按「往返次数」算，依据是已测地板价（#204：每操作 KV 往返 ~0.7µs（shm）；redis 由 RTT 主导）。
行存键数爆炸还会撞上 shm 新键写随存活键数线性（实测 10k 23µs → 120k 495µs）。

结论（唯一路径）

• v1 = 行存 + 索引：表 = map（成员 = 行实例）；PK = 行 key；范围/排序交给唯一的有序来源 = 索引
  （idx/<name>：order-preserving 编码 + Ptr 到行）。v1 只承诺：点查、单行 CRUD、PK 范围扫描、小表嵌套
  循环 join。
• 分析型另立一条派生线，不塞进行存：sql·materialize(row_table) -> col_table（借列分块向量化）。
  行存是写侧真相，列存是可重建的派生（地位同索引），因此不算「两份真相」。
• 文本列 v1 不做字典编码；ORDER BY/范围谓词只允许走索引（列内不承诺任何序）。

查询系统：SQL 前端 = 扩展编译器，产物 = rwir 树

SQL 文本 → 前端扩展：parse → AST → 逻辑计划 → 物理计划
        → 产出 kvlang rwir 树（落 kvspace，可 dump 审查；EXPLAIN 免费）
        → runtime 执行；重算子（sort/hash/spill）由后端算子绑定兑现（runtime-c 多核 / op-gpu）

• 表达式求值无需新机制：runtime 的 opcode 两级查找（int64·add → add）本就是「类型化算子 + 后端
  绑定 + 版本化」，SQL 的 <ret>·fn 直接落进去。
• 算子落点：Scan / Filter（选择向量）/ Project / Aggregate / Limit / Distinct → runtime-c 批量列算子；
  Sort / Hash* / spill / 大 join → 扩展（新增 myrwircaps）；GPU → op-gpu 后端绑定。

前置缺陷（本 issue 的硬前提，实测证据）

1. struct·new(...) -> map·*k（动态成员键）静默产空行。三种写法实测：

   写法	结果
   struct·new("/lib/Row", "id", 5) -> /tmp/t4·k1（静态键）	✅ t4·k1·id = 5
   7 -> /tmp/t4·k1·id（字段写）	✅ 生效
   string·formatint(2) -> kk 后 struct·new(...) -> /tmp/t4·*kk	❌ 成员根 /tmp/t4·2 建出来（kind /lib/Row），·id/·val 全是 nil

   最小复现：

   struct Row { id:int64=0 val:int64=0 }
   rwfunc test() -> () {
       /tmp/t4:[]char/utf8·/lib/Row = {}
       string·formatint(2) -> kk
       struct·new("/lib/Row", "id", 8, "val", 9) -> /tmp/t4·*kk
       /tmp/t4·2·id -> c
       println("dyn-key=", c)
   }

   → 打印空（None），无任何诊断。SQL 的主键天然是动态键（WHERE id = ?），直接踩中。按 p1 必须二选一：
   修好，或显式禁止该形态并只留 cpdir 一条路（把行建在临时位置 → 取路径串 → cpdir 到
   表·键；cpdir 收路径串，预期可行，未实测）。

2. 枚举顺序未承诺 → 范围扫描地基缺失：要么把「前缀枚举有序」立进 spec，要么索引段自带序。

3. 一行多键无原子性 → 需提交协议（先写字段、最后写 ‥commit，或统一走 cpdir）。

需要补的 kvlang 能力

1. 前缀枚举有序（或索引段自带序）——判据：spec 承诺 + 三后端一致。
2. sort / hash / 选择向量位图——现有 myrwircaps 里一个都没有（array·append/slice/scatter/compact
   只是构造器）。
3. 批量列算子（借列 + 分块 + 输出段）——现在只有 per-element xv·at/set。
4. 三值比较器 + 类型化比较（跨类型 error，不隐式提升）。
5. 表/行/索引的 dump 往返（对齐既有 dump 习惯）。

明确不做（v1）

行存副本、B+tree 引擎、隐式类型转换、NULL 零值冒充、DECIMAL/时区、后台 autovacuum、多写者事务、
列存与行存同时作为一等存储（列存只作派生）。

参考

• SQLite：VDBE 字节码 ≈ 本仓 rwir（同构对照）；WITHOUT ROWID = 有序键即表；它有 pager/WAL，我们没有 →
  用提交指针。
• FoundationDB（tuple 层 + SQL Layer）：KV 之上做关系层、order-preserving 键编码、单键原子提交，最贴。
• DuckDB：向量化执行（借列分块）——materialize 线参考。
• C-Store/MonetDB：列存为唯一形态、列无序+投影有序。
• Arrow/Parquet：零拷贝列格式 ↔ GetPart 借用 + @ext 冷列。
• PostgreSQL：严格类型 + 三值逻辑的 camp（按「五语言对齐」规矩记录）。

验收

• 表存储结构、类型映射、NULL 语义、提交协议、索引键编码各自落 spec 条款（新卷 stdlib/sql/spec/）。
• 3 个 tutorial 锚例：单表 scan+filter+agg / 索引范围扫描 / 两表 join。
• 前置缺陷 1 有明确裁决（修 / 禁），2 有 spec 承诺。

关联：#273（编译器在扩展，SQL 前端是它的第一个真实大用例）、#189 / #346（调度）、#54（GRANT 用 rwx+uid/gid）、
#305（指针解引用语义已落）。