第24课：查询优化器

实战项目 第24课 / 共25课

📖 课程概述

查询优化器是数据库的"大脑"，它从众多等价计划中选择最优执行方案。本课实现一个完整的查询优化器，包含RBO规则优化和CBO代价估算，支持连接重排序、谓词下推和索引选择。

💻 C语言实现：查询优化器

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_TABLES  8
#define MAX_COLS    16
#define MAX_PLAN    64

// ===== 统计信息 =====
typedef struct {
    char   name[32];
    int    num_rows;
    int    num_pages;
    int    has_index;
    double avg_selectivity;
} TableStats;

TableStats catalog[] = {
    {"users",    100000, 4000, 1, 0.1},
    {"orders",   1000000, 16000, 1, 0.05},
    {"products", 10000, 640, 1, 0.2},
    {"reviews",  500000, 12000, 0, 0.15},
};
int num_catalog = 4;

TableStats* get_stats(const char* name) {
    for (int i=0; itype = type;
    return op;
}

// ===== RBO规则 =====

// 规则1: 谓词下推
LogOp* rule_push_filter(LogOp* plan) {
    if (!plan) return NULL;
    plan->left = rule_push_filter(plan->left);
    plan->right = rule_push_filter(plan->right);

    if (plan->type != L_FILTER) return plan;

    LogOp* filter = plan;
    LogOp* child = plan->left;

    // Filter over Join → 尝试下推
    if (child && (child->type == L_HASH_JOIN || child->type == L_NL_JOIN)) {
        // 简化：假设谓词只涉及左表
        if (child->left && child->left->type == L_SCAN) {
            LogOp* pushed = log_op_create(L_FILTER);
            strcpy(pushed->predicate, filter->predicate);
            pushed->left = child->left;
            child->left = pushed;
            printf("  [RBO] 谓词下推: %s → Join左子树\n", filter->predicate);
            return child;
        }
    }
    return plan;
}

// 规则2: Scan → IndexScan
LogOp* rule_use_index(LogOp* plan) {
    if (!plan) return NULL;
    plan->left = rule_use_index(plan->left);
    plan->right = rule_use_index(plan->right);

    if (plan->type == L_FILTER && plan->left && plan->left->type == L_SCAN) {
        TableStats* s = get_stats(plan->left->table);
        if (s && s->has_index) {
            LogOp* idx_scan = log_op_create(L_IDX_SCAN);
            strcpy(idx_scan->table, plan->left->table);
            strcpy(idx_scan->predicate, plan->predicate);
            idx_scan->left = plan->left->left;
            printf("  [RBO] Scan → IndexScan(%s)\n", plan->left->table);
            free(plan->left);
            plan->left = idx_scan;
        }
    }
    return plan;
}

// 规则3: 冗余Project消除
LogOp* rule_elim_project(LogOp* plan) {
    if (!plan) return NULL;
    plan->left = rule_elim_project(plan->left);
    plan->right = rule_elim_project(plan->right);

    if (plan->type == L_PROJECT && plan->left && plan->left->type == L_PROJECT) {
        printf("  [RBO] 消除冗余Project\n");
        LogOp* inner = plan->left;
        plan->left = inner->left;
        free(inner);
    }
    return plan;
}

// ===== CBO代价模型 =====
double cost_scan(TableStats* s) {
    return s ? (double)s->num_pages : 1000;
}

double cost_idx_scan(TableStats* s, double sel) {
    if (!s) return 50;
    return 3.0 + s->num_pages * sel * 0.5;
}

double cost_hash_join(LogOp* left, LogOp* right) {
    double build = left->est_rows * 0.001;
    double probe = right->est_rows * 0.001;
    return left->est_cost + right->est_cost + build + probe;
}

double cost_nl_join(LogOp* left, LogOp* right) {
    return left->est_cost + left->est_rows * (right->est_cost + 0.001);
}

double cost_sort(LogOp* child) {
    double n = child->est_rows;
    return child->est_cost + (n > 1 ? n * log2(n) * 0.0001 : 0);
}

double compute_plan_cost(LogOp* plan) {
    if (!plan) return 0;
    double lc = compute_plan_cost(plan->left);
    double rc = compute_plan_cost(plan->right);

    switch (plan->type) {
    case L_SCAN: {
        TableStats* s = get_stats(plan->table);
        plan->est_cost = cost_scan(s);
        plan->est_rows = s ? s->num_rows : 10000;
        break;
    }
    case L_IDX_SCAN: {
        TableStats* s = get_stats(plan->table);
        double sel = s ? s->avg_selectivity : 0.1;
        plan->est_cost = cost_idx_scan(s, sel);
        plan->est_rows = s ? (int)(s->num_rows * sel) : 1000;
        break;
    }
    case L_FILTER: {
        plan->est_cost = lc + plan->left->est_rows * 0.0001;
        plan->est_rows = plan->left->est_rows * 0.3;
        break;
    }
    case L_PROJECT: {
        plan->est_cost = lc + plan->left->est_rows * 0.00001;
        plan->est_rows = plan->left->est_rows;
        break;
    }
    case L_HASH_JOIN: {
        plan->est_cost = cost_hash_join(plan->left, plan->right);
        plan->est_rows = plan->left->est_rows * plan->right->est_rows * 0.01;
        break;
    }
    case L_NL_JOIN: {
        plan->est_cost = cost_nl_join(plan->left, plan->right);
        plan->est_rows = plan->left->est_rows * plan->right->est_rows * 0.01;
        break;
    }
    case L_SORT: {
        plan->est_cost = cost_sort(plan->left);
        plan->est_rows = plan->left->est_rows;
        break;
    }
    case L_LIMIT: {
        plan->est_cost = lc;
        plan->est_rows = 10;
        break;
    }
    default:
        plan->est_cost = lc + rc;
        break;
    }
    return plan->est_cost;
}

// CBO: 选择最优连接方式
LogOp* cbo_choose_join(LogOp* plan) {
    if (!plan) return NULL;
    plan->left = cbo_choose_join(plan->left);
    plan->right = cbo_choose_join(plan->right);

    if (plan->type != L_NL_JOIN && plan->type != L_HASH_JOIN) return plan;

    // 尝试两种连接方式
    LogOp* hash_plan = log_op_create(L_HASH_JOIN);
    hash_plan->left = plan->left; hash_plan->right = plan->right;
    double hash_cost = compute_plan_cost(hash_plan);

    LogOp* nl_plan = log_op_create(L_NL_JOIN);
    nl_plan->left = plan->left; nl_plan->right = plan->right;
    double nl_cost = compute_plan_cost(nl_plan);

    if (hash_cost < nl_cost) {
        printf("  [CBO] 选择HashJoin (代价%.1f < NLJoin%.1f)\n", hash_cost, nl_cost);
        free(nl_plan);
        hash_plan->est_rows = plan->est_rows;
        return hash_plan;
    } else {
        printf("  [CBO] 选择NLJoin (代价%.1f < HashJoin%.1f)\n", nl_cost, hash_cost);
        free(hash_plan);
        nl_plan->est_rows = plan->est_rows;
        return nl_plan;
    }
}

// CBO: 连接顺序枚举
LogOp* cbo_reorder(LogOp* plan) {
    if (!plan) return NULL;
    if (plan->type != L_HASH_JOIN && plan->type != L_NL_JOIN) return plan;

    // 尝试交换
    LogOp* swapped = log_op_create(plan->type);
    swapped->left = plan->right;
    swapped->right = plan->left;

    double orig = compute_plan_cost(plan);
    double swap = compute_plan_cost(swapped);

    if (swap < orig) {
        printf("  [CBO] 连接重排序 (代价%.1f→%.1f)\n", orig, swap);
        free(plan);
        return swapped;
    }
    free(swapped);
    return plan;
}

// 打印计划
void print_plan(LogOp* p, int depth) {
    if (!p) return;
    printf("%*s%s", depth*2, "", op_names[p->type]);
    if (p->table[0]) printf("(%s)", p->table);
    if (p->predicate[0]) printf("[%s]", p->predicate);
    printf(" rows=%.0f cost=%.1f\n", p->est_rows, p->est_cost);
    print_plan(p->left, depth+1);
    print_plan(p->right, depth+1);
}

int main() {
    printf("╔══════════════════════════════════════╗\n");
    printf("║   查询优化器                         ║\n");
    printf("╚══════════════════════════════════════╝\n\n");

    // 查询: SELECT u.name FROM users u JOIN orders o ON u.id=o.uid
    //        WHERE u.age > 25 ORDER BY u.name LIMIT 10

    printf("--- 初始逻辑计划 ---\n");
    LogOp* limit = log_op_create(L_LIMIT);
    LogOp* sort = log_op_create(L_SORT);
    LogOp* project = log_op_create(L_PROJECT);
    strcpy(project->columns[0], "name"); project->num_cols=1;
    LogOp* filter = log_op_create(L_FILTER);
    strcpy(filter->predicate, "age > 25");
    LogOp* join = log_op_create(L_NL_JOIN);
    LogOp* scan_u = log_op_create(L_SCAN); strcpy(scan_u->table, "users");
    LogOp* scan_o = log_op_create(L_SCAN); strcpy(scan_o->table, "orders");

    join->left = scan_u; join->right = scan_o;
    filter->left = join;
    project->left = filter;
    sort->left = project;
    limit->left = sort;

    compute_plan_cost(limit);
    print_plan(limit, 0);
    printf("  总代价: %.1f\n", limit->est_cost);

    // RBO优化
    printf("\n--- RBO优化 ---\n");
    limit->left = rule_push_filter(limit->left);
    limit->left = rule_use_index(limit->left);
    limit->left = rule_elim_project(limit->left);
    compute_plan_cost(limit);
    print_plan(limit, 0);
    printf("  总代价: %.1f\n", limit->est_cost);

    // CBO优化
    printf("\n--- CBO优化 ---\n");
    limit->left = cbo_choose_join(limit->left);
    limit->left = cbo_reorder(limit->left);
    compute_plan_cost(limit);
    print_plan(limit, 0);
    printf("  总代价: %.1f\n", limit->est_cost);

    printf("\n✅ 查询优化器运行完成\n");
    return 0;
}

🔑 关键概念总结