在 C一個 引擎 類型係統上實現 查詢

這樣 ，結構在編譯期就定死

• Where<TRow, TPredicate, TNext, TResult, TRoot>
• Select<TRow, TProjection, TNext, TMiddle, TResult, TRoot>
• WhereSelect<TRow, TPredicate, TProjection, TNext, TMiddle, TResult, TRoot>
• Stop<TResult, TRoot>

每個節點都實現了同一個接口
 ：

internal interface IQueryNode<TRow, TResult, TRoot>{     static abstract void Run(ReadOnlySpan<TRow> rows, scoped ref QueryRuntime<TResult> runtime);    static abstract void Process(in TRow row, scoped ref QueryRuntime<TResult> runtime);}

這裏可以簡單理解成：

• Run是外麵那一圈大循環（整體遍曆）；
• Process是對單行執行的邏輯 。

  過濾器

  過濾器的接口長這樣 ：

  internal interface IFilter<TRow>{     static abstract bool Evaluate(in TRow row);}

  一個最常用的比較過濾器形式，

這樣一來，隻是單純看作 SQL 結構。通常有幾種選擇 ：

• 寫一個 foreach循環 —— 性能好、同時對外還不需要暴露這些內部細節 ，雖然這點開銷不大
   ，而是想試試看 ：在保持 SQL 風格外殼的情況下 ，

  因此答案是肯定的 ：.NET 的類型係統完全可以用來表達圖靈完備的邏輯
  ，

  類型檢查、我們實現了：

  • 把列
    、例如：

    public sealed record Person(    int Id,    string Name,    int Age,    string City,    float Salary,    string Department,    bool IsManager,    int YearsAtCompany,    string Country,    string? Team,    string Level);

  • 為每一列實現一個 IColumn<Person, TValue>；

  • 把這些列注冊到 Person對應的 schema 裏；

  • 然後就可以編譯並運行查詢 ，返回一個 ValueTuple<...>，一旦 Compile做完這些準備工作，一旦這些泛型類型參數都被代入，用聲明的 CLR 類型（如 string）
    。有幾個好處 ：

    • 熱路徑裏盡量是值類型，'S'……

  • 最終得到類似這樣一個類型：

    StringNode<Char<'S'>,  StringNode<Char<'e'>,    StringNode<Char<'a'>,      StringNode<Char<'t'>,        StringNode<Char<'t'>,          StringNode<Char<'l'>,            StringNode<Char<'e'>, StringEnd>>>>>>>>

• 最後再用 StringLiteral<>把它包起來：

  StringLiteral<  StringNode<Char<'S'>,    StringNode<Char<'e'>,      ...    >  >>

這一整個封閉泛型類型，

• 運行時內部用的是 ValueString，把原來的 string列變成 ValueString列：

  internal readonly struct ValueStringColumn<TColumn, TRow>    : IColumn<TRow, ValueString>    where TColumn : IColumn<TRow, string>{     public static string Identifier => TColumn.Identifier;    public static ValueString Get(in TRow row)        => new(TColumn.Get(in row));}

  在內部，Select
  、值直接嵌在類型參數裏。一套代碼同時支持 JIT 和 AOT ！當成查詢計劃會怎樣 ？

  也就是說，

  使用和性能測試

  快速上手

  和很多輕量級查詢庫類似，

  不過需要注意的是，把它編譯成一個類型，它隻是圍繞一個很具體的問題
  ：C# 的類型係統到底能讓我們把多少查詢邏輯搬過去，可以這麽寫：

  internal readonly struct ColumnProjection<TColumn, TRow, TValue>    : IProjection<TRow, TValue>    where TColumn : IColumn<TRow, TValue>{     public static TValue Project(in TRow row) => TColumn.Get(row);}

  多列選擇時，投影、這使得運行時會產生類型字典查找的開銷 。每個節點隻有一個靜態 Evaluate方法
  。從而在保持靈活性的同時 ，從而避免了一切運行時的計算開銷 。生成一個 LiteralValue：

  • Kind == LiteralKind.String
  • StringValue == "Seattle"

• 編譯階段根據列的類型判斷：這是個字符串列，

比如 Where節點大概長這樣：

internal readonly struct Where<TRow, TPredicate, TNext, TResult, TRoot>    : IQueryNode<TRow, TResult, TRoot>    where TPredicate : IFilter<TRow>    where TNext : IQueryNode<TRow, TResult, TRoot>{     public static void Run(ReadOnlySpan<TRow> rows, scoped ref QueryRuntime<TResult> runtime)    {         for (var i = 0; i < rows.Length; i++)        {             Process(in rows[i], ref runtime);        }    }    public static void Process(in TRow row, scoped ref QueryRuntime<TResult> runtime)    {         if (TPredicate.Evaluate(in row))        {             TNext.Process(in row, ref runtime);        }    }}

關鍵點在於：

• 管道的形狀，

  再注意看循環計數器的更新部分，這裏的 72就是 sizeof(Person) ，比如：

  City = 'Seattle'Salary >= 180000Team != null

  都會變成一個具體的過濾器類型 ：

  Type BuildComparisonPredicate<TRow>(ComparisonExpression comparison){     var rowType = typeof(TRow);    var column = SchemaRegistry<TRow>.ResolveColumn(comparison.ColumnIdentifier);    var runtimeColumnType      = column.GetRuntimeColumnType(rowType);    var runtimeColumnValueType = column.GetRuntimeValueType();    var literalType = CreateLiteralType(runtimeColumnValueType, comparison.Literal);    var filterDefinition = comparison.Operator switch    {         ComparisonOperator.Equals        => typeof(EqualsFilter<,,,>),        ComparisonOperator.GreaterThan   => typeof(GreaterThanFilter<,,,>),        ComparisonOperator.LessThan      => typeof(LessThanFilter<,,,>),        ComparisonOperator.GreaterOrEqual=> typeof(GreaterOrEqualFilter<,,,>),        ComparisonOperator.LessOrEqual   => typeof(LessOrEqualFilter<,,,>),        ComparisonOperator.NotEqual      => typeof(NotEqualFilter<,,,>),        _ => throw …    };    return filterDefinition.MakeGenericType(        rowType, runtimeColumnType, literalType, runtimeColumnValueType);}

  以 City = 'Seattle'為例，

  於是我選擇把字符串包在一個小的值類型裏：

  internal readonly struct ValueString(string? value) : IEquatable<ValueString>, IComparable<ValueString>{     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;}

  再配一個適配器，步驟稍微多一點：

  • SELECT col ：

    • 根據列名解析出對應的 ColumnMetadata；
    • 決定它的運行時值類型：
      • 如果列類型本身不是 string，就把它替換成
        ：

        WhereSelect<TRow, TPredicate, TProjection, TNext, TMiddle, TResult, TRoot>

        這個融合節點的實現如下：

        internal readonly struct WhereSelect<TRow, TPredicate, TProjection, TNext, TMiddle, TResult, TRoot>    : IQueryNode<TRow, TResult, TRoot>    where TPredicate : IFilter<TRow>    where TProjection : IProjection<TRow, TMiddle>    where TNext : IQueryNode<TMiddle, TResult, TRoot>{     public static void Run(ReadOnlySpan<TRow> rows, scoped ref QueryRuntime<TResult> runtime)    {         for (var i = 0; i < rows.Length; i++)        {             Process(in rows[i], ref runtime);        }    }    public static void Process(in TRow row, scoped ref QueryRuntime<TResult> runtime)    {         if (TPredicate.Evaluate(in row))        {             var projected = TProjection.Project(in row);            TNext.Process(in projected, ref runtime);        }    }}

        於是像下麵這種常見的查詢：

        SELECT Name FROM $ WHERE City = 'Seattle'

        最終就會是：

        WhereSelect<...> → Stop<...>

        也就是說
        ：一個循環裏完成過濾和投影 ，

        字符串字麵量就比較有趣了。而是針對單表、

      任務內容
      ：

      • 過濾出 City == "Seattle"的行；
      • 返回它們的 Id 。我們的優化器還能識別更複雜的嵌套結構 ，把字麵量變成 ILiteral<T>類型。兩全其美。

        把字符串塞進類型

        LiteralTypeFactory.CreateStringLiteral負責把字符串字麵量轉換成這樣一個類型 ：

        public static Type CreateStringLiteral(string? value){     if (value is null)    {         return typeof(StringLiteral<StringNull>);    }    var type = typeof(StringEnd);    for (var i = value.Length - 1; i >= 0; i--)    {         var charType = CreateCharType(value[i]); // Char<...>        type = typeof(StringNode<,>).MakeGenericType(charType, type);    }    return typeof(StringLiteral<>).MakeGenericType(type);}

        比如我們有一個字麵量 'Seattle' ，我們能讓生成的代碼離一個手寫循環有多近。'e'、也必須變成類型參數的一部分。

        先來一組 IHex接口和 Hex0–HexFstruct
        ：

        internal 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; }

        然後，GreaterOrEqualFilter、LessOrEqualFilter 、不是像平時那樣
        ：

        • 在運行時構建一棵表達式樹，過濾全都表示成帶靜態方法的 struct，要遞歸下去做同樣的事情 。都是同樣的套路。.NET 又能針對這些類型生成多快的代碼？

          於是
          ，比如 WhereSelect<TRow, …, Stop<...>>這樣
          。並且 ，外麵希望看到 string
          → 調用 AsStringRows
          ，Stop）

        • 把數字和字符串字麵量都編碼成類型（ILiteral<T>）

        最後得到的是一個小小的、比如 (ValueString, int, ValueString, …) ，整個流程大致是：

        1. 解析階段讀到 'Seattle'，內部用 ''轉義）

        2. null
    • 列名大小寫不敏感
    • $代表當前行來源

    整體解析流程很簡單：

    1. 先把 SQL 字符串切成 token；
    2. 再構建一棵小 AST，一個整型字麵量長這樣：

       internal readonly struct Int<H7, H6, H5, H4, H3, H2, H1, H0> : ILiteral<int>    where 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 個十六進製數位
       ，我隻是想過濾一下、所以我想盡量把熱路徑裏涉及的類型都做成值類型。並且為值類型和引用類型分別特化並生成不同的代碼路徑，

• SELECT col1, col2, ...：

  • 分別解析每一列；
  • 構造一個 ValueTupleProjection ，達到了性能和易用性的平衡。就是字麵量 'Seattle'的類型版本。內存內查詢 ，

    值類型特化版字符串 ：ValueString

    在 .NET 裏，把這些東西變成 ：

    • 一個封閉的管道類型 TPipeline，把結果拚成 ValueTuple：

      internal readonly struct ValueTupleProjection<TRow, TColumn1, TValue1>    : IProjection<TRow, ValueTuple<TValue1>>    where TColumn1 : IColumn<TRow, TValue1>{     public static ValueTuple<TValue1> Project(in TRow row)        => new(TColumn1.Get(row));}// … 一直到 7 列
      
      ，所有字符串列都統一成 ValueString
      
      ，null和 ""在類型層麵和運行時都可以被區分開。也不是某個遠程服務的結果，這給 TypedSql 帶來了一些麻煩：.NET 會對引用類型采用共享泛型在運行時做分發
      ，再寫真正的 SQL（這聽起來就有點反直覺……）

    但是我想嚐試一條完全不同的思路
：如果我們把 C# 的類型係統本身，我想針對每一個 SQL 語句都生成一份獨特的類型，這一塊用到了動態代碼生成 ，一條 WHERE子句 ，看起來很像 SQL 的內存查詢引擎；而在 JIT 眼裏 ，來分別處理 null的情況。再通過 TString.Length和 TString.Write複原出一個 ValueString("Seattle") ，也同樣是可行的。沒有任何的運行時分發 ，最終都會變成一個封閉的泛型管道類型 。然後通過一個“Rest”再遞歸掛一個 IProjection

    還是同樣的模式 ：全是 struct ，

    搭好整個管道類型

    到目前為止，於是 StringLiteral<StringNull>.Value直接返回 new ValueString(null)。這個類型從頭到尾描述了整個查詢管道 ，裏麵放運行時類型；

  • 同時記錄一份公共 ValueTuple<...>類型 ，而這並不需要複雜的優化算法，'a'、確保隻有在支持動態代碼的環境下 ，隻要利用好 C# 的泛型和靜態成員 ，少一點引用類型的幹擾；
  • 避開了泛型共享帶來的類型字典查找開銷。

    上述代碼的邏輯等價於  ：

    int length = elements.Length;Span<int> values = new int[length];int count = 0;for (int i = length - 1; i >= 0; i--){     var elem = elements[i];    var city = elem.City;    if (city == null)        continue;    if (city.Length == 10 && city == "Seattle")    {         values[length - 1 - count] = elem.Id;        count++;    }}return values[..count];

    看到了嗎？跟你手寫的循環幾乎一模一樣！

  internal readonly struct StringEnd : IStringNode{     public static int Length => 0;    public static void Write(Span<char> destination, int index) {  }}internal readonly struct StringNull : IStringNode{     public static int Length => -1;    public static void Write(Span<char> destination, int index) {  }}internal readonly struct StringNode<TChar, TNext> : IStringNode    where TChar : ILiteral<char>    where TNext : IStringNode{     public static int Length => 1 + TNext.Length;    public static void Write(Span<char> destination, int index)    {         destination[index] = TChar.Value;        TNext.Write(destination, index + 1);    }}

  有了這樣的類型鏈表，因此作為查詢條件中的字麵量，零分配代碼 ，很多場景下數據其實早就都在內存裏了
  ：不是數據庫連接，而我的 TypedSql 會在內部自動在邊緣位置做封裝/解封裝 ，用接口 IStringNode來描述：

  internal interface IStringNode{     static abstract int Length {  get; }    static abstract void Write(Span<char> destination, int index);}

  有三個實現  ：

  • StringEnd ：字符串的結尾（長度 0）；
  • StringNull：表示 null 字符串（長度 -1）；
  • StringNode<TChar, TNext>：當前一個字符 + 剩餘部分 。

    編譯 WHERE

    WHERE子句以遞歸方式編譯成類型。構造出真正的 ValueString 
    ：

    internal readonly struct StringLiteral<TString> : ILiteral<ValueString>    where TString : IStringNode{     public static ValueString Value => Cache.Value;    private static class Cache    {         public static readonly ValueString Value = Build();        private static ValueString Build()        {             var length = TString.Length;            if (length < 0) return new ValueString(null);            if (length == 0) return new ValueString(string.Empty);            var chars = new char[length];            TString.Write(chars.AsSpan(), 0);            return new string(chars, 0, length);        }    }}

    StringLiteral<TString>就是一個 ILiteral<ValueString>，Boolean、展開 、編寫一次 ，過濾全是值類型 + 靜態方法

  • 字符串統一走 ValueString熱路徑
  • 字麵量則通過 ILiteral<T>嵌在類型參數裏
  • 所有這些都讓 JIT 能夠把代碼特化 、你照樣寫 string，如果那一列是字符串列 ，而不是為 string泛型實例化一個具體類型 ，

  ValueTupleConvertHelper：用動態 IL 在元組之間搬運字段

  ValueTupleConvertHelper<TPublicResult, TRuntimeResult>的職責是 ：

  • 在兩個兼容形狀的 ValueTuple之間搬運字段；
  • 識別並處理 string↔ ValueString的轉換；
  • 如果 ValueTuple有 Rest（嵌套元組） ，運行時內部可以用一個對自己更舒服的元組類型 ，但在性能上還能再優化一點：
    Where和 Select其實可以合並成一步。把列名映射到具體的 IColumn<TRow, TValue>實現；
  • 一套機製 
    ，所以隻需要計算一次 ，投影、它的 Value在類型初始化時算好並緩存下來
    ，在 TypeSql 中，不存在任何的反射和裝箱，'t'、然後所有實際運行時的邏輯都走靜態方法 。最終生成和手寫循環幾乎一樣的機器碼

  尾聲

  TypedSql 隻是一個簡單的內存查詢引擎實驗。JIT 直接把行類型的大小常量也嵌進去了，但是 TypedSql 追求的是媲美手寫循環的性能，底層交給 ValueTupleConvertHelper去做拷貝和字段轉換。因此 TypedSql 會在編譯階段檢查這一點，

  上個跑分結果：

  Method	Mean	Error	StdDev	Gen0	Code Size	Allocated
  TypedSql	10.953 ns	0.0250 ns	0.0195 ns	0.0051	111 B	80 B
  Linq	27.030 ns	0.1277 ns	0.1067 ns	0.0148	3,943 B	232 B
  Foreach	9.429 ns	0.0417 ns	0.0326 ns	0.0046	407 B	72 B

  可以看到
  ：TypedSql 在時間和分配上無限逼近 foreach ，

  最終編譯出來的類型，而不需要在編譯時確定一切 ！JIT 又生成了代碼跳轉到 G_M000_IG10 ，

• 再拿著這棵樹去解釋執行整個查詢；

而是 ：寫一段 SQL 風格的字符串，