TypedSql：在 C# 类型系统上实现一个 SQL 查询引擎

NET 里写查询的时候很多场景下数据其实早就都在内存里了不是数据库连接也不是某个远程服务的结果而就是一个数组或者 List。我只是想过滤一下、投影一下。这时候通常有几种选择写一个 foreach 循环 —— 性能好、可控但代码稍微有点啰嗦用 LINQ —— 写起来舒服看起来也优雅就是有迭代器、委托带来的那点开销要么干脆极端一点把数据塞进数据库再写真正的 SQL这听起来就有点反直觉……但是我想尝试一条完全不同的思路如果我们把 C# 的类型系统本身当成查询计划会怎样也就是说不是像平时那样在运行时构建一棵表达式树再拿着这棵树去解释执行整个查询而是写一段 SQL 风格的字符串把它编译成一个类型这个类型从头到尾描述了整个查询管道然后所有实际运行时的逻辑都走静态方法。这个想法最终促成了 TypedSql —— 一个用 C# 类型系统实现的内存内 SQL 查询引擎。1000016101把查询变成嵌套的泛型类型#TypedSql 的核心想法看上去非常简单一个查询其实可以是一串嵌套的泛型类型比如 WhereSelectTRow, …, Stop… 这样。顺着这个想法再往下推几步会自然落到一套具体的设计上。把执行计划塞进类型系统#在 TypedSql 里每一个编译好的查询最终都会变成一个封闭的泛型管道类型。这个管道是由一些基础节点拼出来的比如WhereTRow, TPredicate, TNext, TResult, TRootSelectTRow, TProjection, TNext, TMiddle, TResult, TRootWhereSelectTRow, TPredicate, TProjection, TNext, TMiddle, TResult, TRootStopTResult, TRoot每个节点都实现了同一个接口Copyinternal interface IQueryNodeTRow, TResult, TRoot{static abstract void Run(ReadOnlySpan rows, scoped ref QueryRuntime runtime);static abstract void Process(in TRow row, scoped ref QueryRuntimeTResult runtime);}这里可以简单理解成Run 是外面那一圈大循环整体遍历Process 是对单行执行的逻辑。比如 Where 节点大概长这样Copyinternal readonly struct WhereTRow, TPredicate, TNext, TResult, TRoot: IQueryNodeTRow, TResult, TRootwhere TPredicate : IFilterwhere TNext : IQueryNodeTRow, TResult, TRoot{public static void Run(ReadOnlySpan rows, scoped ref QueryRuntime runtime){for (var i 0; i rows.Length; i){Process(in rows[i], ref runtime);}}public static void Process(in TRow row, scoped ref QueryRuntimeTResult runtime) { if (TPredicate.Evaluate(in row)) { TNext.Process(in row, ref runtime); } }}关键点在于管道的形状完全藏在这些类型参数里面每个节点是一个只有静态方法的 struct —— 不需要创建实例没有虚调用。对 JIT 来说一旦这些泛型类型参数都被代入这就是一张普通的静态调用图而已。列和投影#查询总得运行在某种行类型 TRow 上这通常是你自己定义的一个 record/class/struct。每一列会实现这样一个接口Copyinternal interface IColumnTRow, TValue{static abstract string Identifier { get; }static abstract TValue Get(in TRow row);}举个简单的例子Copyinternal readonly struct PersonNameColumn : IColumnPerson, string{public static string Identifier “Name”;public static string Get(in Person row) row.Name;}而投影SELECT 后面那部分则实现Copyinternal interface IProjectionTRow, TResult{static abstract TResult Project(in TRow row);}将选出某一列本身做成一个投影可以这么写Copyinternal readonly struct ColumnProjectionTColumn, TRow, TValue: IProjectionTRow, TValuewhere TColumn : IColumnTRow, TValue{public static TValue Project(in TRow row) TColumn.Get(row);}多列选择时TypedSql 会构造专门的投影把结果拼成 ValueTupleCopyinternal readonly struct ValueTupleProjectionTRow, TColumn1, TValue1: IProjectionTRow, ValueTuplewhere TColumn1 : IColumnTRow, TValue1{public static ValueTuple Project(in TRow row) new(TColumn1.Get(row));}// … 一直到 7 列然后通过一个“Rest”再递归挂一个 IProjection还是同样的模式全是 struct全是静态方法。过滤器#过滤器的接口长这样Copyinternal interface IFilter{static abstract bool Evaluate(in TRow row);}一个最常用的比较过滤器形式是列 字面量Copyinternal readonly struct EqualsFilterTRow, TColumn, TLiteral, TValue : IFilterwhere TColumn : IColumnTRow, TValuewhere TLiteral : ILiteralwhere TValue : IEquatable, IComparable{[MethodImpl(MethodImplOptions.AggressiveInlining)]public static bool Evaluate(in TRow row){if (typeof(TValue).IsValueType){return TColumn.Get(row).Equals(TLiteral.Value);}else{var left TColumn.Get(row);var right TLiteral.Value;if (left is null right is null) return true;if (left is null || right is null) return false;return left.Equals(right);}}}这里我们通过判断 TValue 是值类型还是引用类型来分别处理 null 的情况。.NET 的 JIT 能够识别这种模式并且为值类型和引用类型分别特化并生成不同的代码路径从而实际上并不存在任何的分支开销。GreaterThanFilter、LessThanFilter、GreaterOrEqualFilter、LessOrEqualFilter、NotEqualFilter 等等都是同样的套路。逻辑运算也是在类型层面组合的Copyinternal readonly struct AndFilterTRow, TLeft, TRight : IFilterwhere TLeft : IFilterwhere TRight : IFilter{public static bool Evaluate(in TRow row) TLeft.Evaluate(in row) TRight.Evaluate(in row);}internal readonly struct OrFilterTRow, TLeft, TRight : IFilterwhere TLeft : IFilterwhere TRight : IFilter{public static bool Evaluate(in TRow row) TLeft.Evaluate(in row) || TRight.Evaluate(in row);}internal readonly struct NotFilterTRow, TPredicate : IFilterwhere TPredicate : IFilter{public static bool Evaluate(in TRow row) !TPredicate.Evaluate(in row);}所以一条 WHERE 子句最终就会变成一棵泛型过滤器类型树每个节点只有一个静态 Evaluate 方法。值类型特化版字符串ValueString#在 .NET 里string 是一个引用类型这给 TypedSql 带来了一些麻烦.NET 会对引用类型采用共享泛型在运行时做分发而不是为 string 泛型实例化一个具体类型这使得运行时会产生类型字典查找的开销。虽然这点开销不大但是 TypedSql 追求的是媲美手写循环的性能所以我想尽量把热路径里涉及的类型都做成值类型。于是我选择把字符串包在一个小的值类型里Copyinternal readonly struct ValueString(string? value) : IEquatable, IComparable{public readonly string? Value value;public int CompareTo(ValueString other) string.Compare(Value, other.Value, StringComparison.Ordinal); public bool Equals(ValueString other) { return string.Equals(Value, other.Value, StringComparison.Ordinal); } public override string? ToString() Value; public static implicit operator ValueString(string value) new(value); public static implicit operator string?(ValueString value) value.Value;}再配一个适配器把原来的 string 列变成 ValueString 列Copyinternal readonly struct ValueStringColumnTColumn, TRow: IColumnTRow, ValueStringwhere TColumn : IColumnTRow, string{public static string Identifier TColumn.Identifier;public static ValueString Get(in TRow row) new(TColumn.Get(in row));}在内部所有字符串列都统一成 ValueString有几个好处热路径里尽量是值类型少一点引用类型的干扰避开了泛型共享带来的类型字典查找开销。对使用者来说你照样写 string而我的 TypedSql 会在内部自动在边缘位置做封装/解封装所以完全透明。实现一个 SQL 子集#TypedSql 并不打算做成一个大而全的 SQL 引擎而是针对单表、内存内查询设计了一个很小的 SQL 方言支持这些语句SELECT * FROM $SELECT col FROM $SELECT col1, col2, … FROM $WHERE 支持比较, !, , , , 布尔AND, OR, NOT括号字面量支持整数如 42浮点数如 123.45布尔true / false单引号字符串‘Seattle’内部用 ‘’ 转义null列名大小写不敏感$ 代表当前行来源整体解析流程很简单先把 SQL 字符串切成 token再构建一棵小 AST包含ParsedQuery整体查询SelectionSelectAll 或者列名列表WhereExpression筛选表达式ComparisonExpression比较AndExpression与OrExpression或NotExpression非LiteralValue字面量LiteralKind.Integer IntValueLiteralKind.Float FloatValueLiteralKind.Boolean BoolValueLiteralKind.String StringValuestring?LiteralKind.Null在这个阶段整个系统其实完全不知道 C# 里面的类型是什么样的列又是什么只是单纯看作 SQL 结构。类型检查、以及这个字面量能不能用在那一列上之类的问题会留到后面的编译阶段去做。把字面量变成类型 —— 包括字符串#在这里我想针对每一个 SQL 语句都生成一份独特的类型因此作为查询条件中的字面量也必须变成类型参数的一部分。于是在 TypeSql 中所有的字面量类型都实现同一个接口Copyinternal interface ILiteral{static abstract T Value { get; }}适用范围包括整数int浮点数float字符char布尔bool字符串这里是 ValueString内部包 string?……未来还可以扩展更多数值字面量#数值字面量的编码方式很直接用 16 进制和位运算拼出来。先来一组 IHex 接口和 Hex0–HexF structCopyinternal interface IHex { static abstract int Value { get; } }internal readonly struct Hex0 : IHex { public static int Value 0; }// …internal readonly struct HexF : IHex { public static int Value 15; }然后一个整型字面量长这样Copyinternal readonly struct IntH7, H6, H5, H4, H3, H2, H1, H0 : ILiteralwhere H7 : IHex// …where H0 : IHex{public static int Value (H7.Value 28)| (H6.Value 24)| (H5.Value 20)| (H4.Value 16)| (H3.Value 12)| (H2.Value 8)| (H1.Value 4)| H0.Value;}浮点数也是一样的 8 个十六进制数位只不过最后用 Unsafe.BitCastint, float 转回 floatCopyinternal readonly struct FloatH7, H6, H5, H4, H3, H2, H1, H0 : ILiteralwhere H7 : IHex// …{public static float Value Unsafe.BitCastint, float((H7.Value 28)| (H6.Value 24)| (H5.Value 20)| (H4.Value 16)| (H3.Value 12)| (H2.Value 8)| (H1.Value 4)| H0.Value);}字符则是 4 个十六进制数位Copyinternal readonly struct CharH3, H2, H1, H0 : ILiteralwhere H3 : IHex// …{public static char Value (char)((H3.Value 12)| (H2.Value 8)| (H1.Value 4)| H0.Value);}