静态分析器设计

基数区间       生成的 API 形态
────────────────────────────────────────────────────────────────────
ExactlyZero    无值 / 类 unit 返回（查询保证为空）
ExactlyOne     非空单行对象
AtMostOne      可选单行对象
OneOrMore      保证非空的集合（或集合 + 契约）
ZeroOrMore     集合

SQL 文本 ──► Parse ──► Algebraize ──► Infer ──► ResultSet
               │            │              │
            sqlparser    AST+Catalog    RelationalExpr
                       → RelationalExpr → Metadata

infer(node):
    for each child of node:
        child_metadata = infer(child)
    return apply_operator_rules(node, child_metadata...)

类别            算子             记号       说明
──────────────────────────────────────────────────────────────────────
叶子节点         Scan             R          从基础表读取全部行
                Values           {r1,r2,..} 字面量行集（例如 SELECT 1, VALUES ...）

一元算子         Selection        σ(R)       按谓词过滤行
                Projection       π(R)       选择/计算输出列
                Aggregation      γ(R)       分组并应用聚合函数
                Window           ω(R)       在分区上计算窗口函数
                Distinct         δ(R)       去重
                Sort             τ(R)       按排序键排序
                Limit            λ(R)       限制行数（LIMIT / OFFSET）

别名            Alias            ρ(R)       重命名关系（派生表、CTE）

二元算子         Join             R ⋈ S      通过条件组合两侧关系
                SetOperation     R ∪ S      按集合论组合两侧关系

RelationalExpr =
    // 叶子节点
    | Scan(table)
    | Values(rows: [[ScalarExpr]])

    // 一元算子
    | Selection(input: RelationalExpr, condition: ScalarExpr)
    | Projection(input: RelationalExpr, columns: [ProjectionColumn])
    | Aggregation(input: RelationalExpr, group_by: [ScalarExpr], aggregates: [ProjectionColumn])
    | Window(input: RelationalExpr, window_exprs: [ProjectionColumn])
    | Distinct(input: RelationalExpr)
    | Sort(input: RelationalExpr, keys: [SortKey])
    | Limit(input: RelationalExpr, count?: ScalarExpr, offset?: ScalarExpr)

    // 别名
    | Alias(input: RelationalExpr, name: String)

    // 二元算子
    | Join(left: RelationalExpr, right: RelationalExpr, kind: JoinKind, condition?: JoinCondition)
    | SetOperation(left: RelationalExpr, right: RelationalExpr, op: SetOp, all: bool)

ProjectionColumn = {
    expr: ScalarExpr,
    alias?: String,
    visibility: Visible | Hidden
}

ScalarExpr =
    // 引用与字面量
    | ColumnRef(table?, column)          -- 限定名 (t.col) 或非限定名 (col)
    | Literal(NULL | Bool | Int | Float | String)

    // 运算符
    | BinaryOp(left: ScalarExpr, op, right: ScalarExpr)   -- +, -, =, <, AND, OR, LIKE, ...
    | UnaryOp(op, expr: ScalarExpr)                        -- NOT, -, +

    // 函数调用
    | Function(name, args: [ScalarExpr])                   -- 标量函数：UPPER, COALESCE, ...
    | AggregateCall(name, args: [ScalarExpr], distinct?)   -- COUNT, SUM, AVG, ...
    | WindowCall(name, args: [ScalarExpr], partition_by, order_by)  -- ROW_NUMBER, RANK, ...

    // 类型转换
    | Cast(expr: ScalarExpr, target_type)

    // 谓词
    | IsNull(expr: ScalarExpr, negated?)
    | InList(expr: ScalarExpr, list: [ScalarExpr], negated?)
    | Between(expr: ScalarExpr, low: ScalarExpr, high: ScalarExpr, negated?)

    // 条件表达式
    | Case(operand?: ScalarExpr, when_clauses: [(condition, result)], else?: ScalarExpr)

    // 子查询（在标量上下文中嵌入关系表达式）
    | ScalarSubquery(RelationalExpr)                       -- (SELECT max(x) FROM ...)
    | InSubquery(expr: ScalarExpr, RelationalExpr, negated?)
    | Exists(RelationalExpr, negated?)

    // 通配符（用于 SELECT *）
    | Wildcard
    | QualifiedWildcard(table)

步骤    SQL 子句                    关系算子                      作用
────────────────────────────────────────────────────────────────────────────────
1st     FROM / JOIN                Scan, Join, Alias             建立输入关系
2nd     WHERE                      Selection                     在分组前过滤行
3rd     GROUP BY + aggregates*     Aggregation                  分组并聚合（*跨 SELECT/HAVING/ORDER BY 检测聚合）
4th     HAVING                     Selection                     过滤分组结果
5th     Window functions*          Window                        计算窗口表达式（*跨 SELECT/ORDER BY 检测）
6th     SELECT (+ hidden sort)     Projection                    构建可见输出列及可选隐藏排序列
7th     DISTINCT                   Distinct                      去重
8th     ORDER BY                   Sort                          对结果排序
9th     LIMIT / OFFSET             Limit                         限制输出行数
10th    FINAL OUTPUT               Projection                    丢弃隐藏列

algebraize_select(query):
    // Step 1: FROM → base relation
    expr = build_from(query.from)          // Scan, Join, Alias nodes

    // 预扫描各子句中的表达式类别
    agg_usage = collect_aggregate_usage(query.select, query.having, query.order_by)
    win_usage = collect_window_usage(query.select, query.order_by)

    // Step 2: WHERE → Selection
    if query.where:
        validate_no_aggregates(query.where)
        validate_no_window_functions(query.where)
        expr = Selection(expr, build_scalar(query.where))

    // Step 3: GROUP BY + aggregates → Aggregation
    if query.group_by or agg_usage.any:
        validate_grouping_rules(query)
        expr = Aggregation(expr, build_group_by(query), build_projections(query))

    // Step 4: HAVING → Selection
    if query.having:
        expr = Selection(expr, build_scalar(query.having))

    // Step 5: Window functions → Window
    if win_usage.any:
        expr = Window(expr, build_window_exprs(query))

    // Step 6.1: 构建可见 SELECT 投影列
    // （包括通配符展开：`*`、`t.*`）
    visible_cols = build_visible_projection_columns(query.select)

    // Step 6.2: ORDER BY 规划块
    {
        // 1) 解析 ORDER BY 引用（序号 / 别名 / 表达式等价）
        order_refs = resolve_order_by_refs(query.order_by, visible_cols)

        // 2) 校验 ORDER BY 约束（DISTINCT 限制、别名歧义等）
        validate_order_by_constraints(order_refs, query.distinct)

        // 3) 在允许时物化隐藏排序列，然后构建排序键
        hidden_sort_cols, rewritten_order_refs = materialize_hidden_sort_columns(
            order_refs,
            query.distinct
        )
        sort_keys = build_sort_keys(rewritten_order_refs)
    }

    // Step 6.3: SELECT + 可选隐藏 ORDER BY 表达式 → Projection
    expr = Projection(expr, visible_cols + hidden_sort_cols)

    // Step 7: DISTINCT → Distinct
    if query.distinct:
        expr = Distinct(expr)

    // Step 8: ORDER BY → Sort
    if query.order_by:
        expr = Sort(expr, sort_keys)

    // Step 9: LIMIT / OFFSET → Limit
    if query.limit or query.offset:
        expr = Limit(expr, query.limit, query.offset)

    // Step 10: 最终输出投影（丢弃隐藏列）
    if hidden_sort_cols not empty:
        expr = Projection(expr, visible_cols)

    return expr

SELECT u.name, COUNT(o.id) AS order_count
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
WHERE u.active = true
GROUP BY u.name
HAVING COUNT(o.id) > 5
ORDER BY order_count DESC
LIMIT 10

Limit(count=10)
  └─ Sort(order_count DESC)
       └─ Projection(u.name, COUNT(o.id) AS order_count)
            └─ Selection(COUNT(o.id) > 5)                    -- HAVING
                 └─ Aggregation(group_by=[u.name], aggs=[COUNT(o.id)])
                      └─ Selection(u.active = true)           -- WHERE
                           └─ Join(LEFT, ON u.id = o.user_id)
                                ├─ Alias("u")
                                │    └─ Scan(users)
                                └─ Alias("o")
                                     └─ Scan(orders)

RelationalMetadata = {
    columns: [ColumnMetadata],    -- 输出 schema
    cardinality: Cardinality      -- 行数上下界
}

ColumnMetadata = {
    table: String?,               -- 源表名（用于限定引用）
    name: String,                 -- 列名
    data_type: DataType,          -- 列的数据类型
    nullable: bool                -- 列是否可为 NULL
}

Cardinality = {
    min: MinRows,                -- 下界
    max: MaxRows                 -- 上界
}

MinRows = Zero | One
MaxRows = Zero | One | Many
    -- 不变式：min <= max

别名：
    ExactlyZero = [Zero, Zero]
    ExactlyOne  = [One, One]
    AtMostOne   = [Zero, One]
    OneOrMore   = [One, Many]
    ZeroOrMore  = [Zero, Many]

infer(expr):
    match expr:
        Scan(table)                  → infer_scan(table)
        Values(rows)                 → infer_values(rows)
        Selection(input, cond)       → infer_selection(infer(input), cond)
        Projection(input, cols)      → infer_projection(infer(input), cols)
        Aggregation(input, gb, aggs) → infer_aggregation(infer(input), gb, aggs)
        Window(input, exprs)         → infer_window(infer(input), exprs)
        Distinct(input)              → infer_distinct(infer(input))
        Sort(input, keys)            → infer_sort(infer(input))
        Limit(input, count, offset)  → infer_limit(infer(input), count, offset)
        Alias(input, name)           → infer_alias(infer(input), name)
        Join(left, right, kind, cond)→ infer_join(infer(left), infer(right), kind, cond)
        SetOperation(left, right, op, all)→ infer_set_op(infer(left), infer(right), op, all)

[min, max]
min ∈ {Zero, One}
max ∈ {Zero, One, Many}
约束：min <= max

ExactlyZero = [Zero, Zero]
ExactlyOne  = [One, One]
AtMostOne   = [Zero, One]
OneOrMore   = [One, Many]
ZeroOrMore  = [Zero, Many]

drop_lower_bound([m, M]) = [Zero, M]

constrain_at_most_one([m, M]) = [m, min(M, One)]

upper_min(a, b):   max 域最小值（Zero < One < Many）
upper_add(a, b):   Zero+Zero=Zero, Zero+One=One, One+One=Many, Many+x=Many
upper_mul(a, b):   Zero*x=Zero, One*One=One, 其他情况为 Many
lower_or(a, b):    任一侧为 One 则 One，否则 Zero
lower_and(a, b):   两侧都为 One 才是 One，否则 Zero

条件模式                                              影响
──────────────────────────────────────────────────────────────────────
WHERE false / WHERE 1=0                               → ExactlyZero
WHERE 输入主键全部列都被等值约束                         → AtMostOne
WHERE 输入唯一键全部列都被等值约束                       → AtMostOne
WHERE 完整输入键 IN (<single tuple>)                    → AtMostOne
WHERE 完整且已证明 NOT NULL 的输入键被约束为 NULL        → ExactlyZero
WHERE key 列 IS NULL 且 key 可空性为 nullable/unknown    → 不细化
WHERE c1 = ? AND c2 = ?（AND 覆盖完整输入 PK/UK）       → AtMostOne
WHERE c = v AND c = w（v != w）                         → ExactlyZero
WHERE ... OR ...                                       → 不细化（保守）
其他                                                   → 不细化

analyze_selection_cardinality(input_cardinality, condition, input_constraints):

    if is_always_false(condition):
        return ExactlyZero

    // Step 1: 矛盾和不可能谓词检查
    if has_contradictory_equalities(condition):
        return ExactlyZero

    if has_full_key_is_null_on_proven_non_nullable_key(condition, input_constraints):
        return ExactlyZero

    // 保守规则：不跨 OR 析取做细化
    if contains_or(condition):
        return input_cardinality

    // Step 2: 收集来自等值和 single-tuple IN 的键约束
    eq_columns = extract_equality_columns(condition)            // 被 "=" 约束的列
    in_single_tuple_keys = extract_single_tuple_in_keys(condition) // 被 IN(single tuple) 约束的键列
    constrained_columns = union(eq_columns, in_single_tuple_keys)

    // Step 3: 覆盖完整主键 => 最多一行
    if covers_any_primary_key(constrained_columns, input_constraints):
        return constrain_at_most_one(input_cardinality)

    // Step 4: 覆盖完整唯一键 => 最多一行
    if covers_any_unique_key(constrained_columns, input_constraints):
        return constrain_at_most_one(input_cardinality)

    return input_cardinality  // 无法继续细化

LIMIT 0                → ExactlyZero（空结果）
LIMIT 1                → constrain_at_most_one(input)
LIMIT n (n > 1)        → input（无有效细化）
OFFSET > 0             → 若 input.max <= One 则 ExactlyZero，否则 drop_lower_bound(input)
LIMIT 1 + OFFSET > 0   → 若 input.max <= One 则 ExactlyZero，否则 AtMostOne

连接类型      可空性变换
──────────────────────────────────────────────────────────────
Inner         保持两侧原样
Cross         保持两侧原样
Left          保持左侧，右侧强制可空
Right         保持右侧，左侧强制可空
Full          两侧都强制可空

guaranteed_match_from_left(on, left, right, catalog):
    if !is_pure_equi_join_conjunction(on):
        return false
    // 拒绝除等值键对之外的任何 ON 谓词
    if has_extra_on_predicates(on):
        return false

    pairs = extract_equijoin_pairs(on)
    if !covers_full_fk_not_null(left -> right, pairs, catalog):
        return false

    if !covers_full_unique_or_pk(right, pairs, catalog):
        return false

    return true

at_most_one_right_per_left(on, left, right, catalog):
    if !is_pure_equi_join_conjunction(on):
        return false
    pairs = extract_equijoin_pairs(on)
    return covers_full_unique_or_pk_not_null(right, pairs, catalog)

表达式                   数据类型                          可空性
──────────────────────────────────────────────────────────────────────────
ColumnRef(t, c)          来自 catalog/输入 schema          来自 catalog/输入 schema
Literal(NULL)            Unknown                           true
Literal(Bool/Int/...)    来自字面量类型                     false
BinaryOp(l, op, r)      来自运算符规则                      nullable(l) OR nullable(r)
UnaryOp(NOT, e)          Bool                              nullable(e)
UnaryOp(-, e)            type(e)                           nullable(e)
Function(name, args)     来自函数注册表                     来自函数注册表
AggregateCall(name, ..)  来自函数注册表                     来自函数注册表
WindowCall(name, ...)    来自函数注册表                     函数特定并受 frame 影响
Cast(e, target)          target                            nullable(e)
IsNull(e)                Bool                              false（IS NULL 永不返回 NULL）
InList(e, list)          Bool                              nullable(e) OR list 中任一项可空
InSubquery(e, q)         Bool                              nullable(e) OR 子查询输出表达式可空
Between(e, lo, hi)       Bool                              nullable(e) OR nullable(lo) OR nullable(hi)
Case(...)                见下文                             见下文
ScalarSubquery(q)        来自子查询单列类型                  true（子查询可能无行）
Exists(q)                Bool                              false
Wildcard / QualifiedWildcard  在 Algebraize 投影构建期间展开

CASE WHEN c1 THEN r1 WHEN c2 THEN r2 ELSE e END

数据类型:  common_type(r1, r2, e)  -- 所有分支的类型提升
可空性:    nullable(r1) OR nullable(r2) OR nullable(e)
            OR（无 ELSE 子句 → 隐式 ELSE NULL → 必然可空）

类别           示例                               上下文
────────────────────────────────────────────────────────────────────
Scalar         UPPER, LOWER, COALESCE, IF,        任意表达式位置
               CONCAT, ABS, ROUND, CAST, ...

Aggregate      COUNT, SUM, AVG, MIN, MAX,         仅可在 Aggregation 中，或
               GROUP_CONCAT, ARRAY_AGG, ...        配合 OVER（转为窗口）

Window         ROW_NUMBER, RANK, DENSE_RANK,      仅可与 OVER 子句一起使用
               NTILE, LAG, LEAD, FIRST_VALUE, ...

function_def = {
    name: String,
    arity: Exact(n) | Range(min, max) | AtLeast(n) | Any,
    return_type: Fixed(type) | SameAsArg(index) | NumericPromotion | Custom(fn),
    nullability: AnyArgNullable | AlwaysNullable | NeverNullable | Custom(fn)
}

模式                含义                                  示例
────────────────────────────────────────────────────────────────────
AnyArgNullable      任一参数可空则可空                     UPPER(x), ABS(x), x + y
AlwaysNullable      与参数无关，总是可空                   仅返回可空值的实现相关函数
NeverNullable       与参数无关，永不可空                   COUNT, EXISTS
Custom              函数专属逻辑                           IF, CASE, IFNULL, COALESCE