殷龙飞的博客

基于Java的高性能轻量化数据库设计与实现 第六篇：查询优化器实现

 数据库/设计  1658  4 分钟
1. 引言

在前五篇中，我们完成了JDBC驱动、存储引擎和事务管理器的实现，支持了SQL执行、数据存储和事务一致性。本篇将聚焦查询优化器（query-optimizer模块）的实现，设计基于成本的优化策略，优化SQL查询的执行计划，确保高性能和资源效率。查询优化器将处理复杂查询（如JOIN、子查询），并与执行引擎和存储引擎集成。

2. 查询优化器的目标与功能
2.1 目标
  • 优化SQL查询的执行计划，减少计算和I/O成本。
  • 支持SQL ANSI 92标准的复杂查询（如JOIN、GROUP BY）。
  • 提供高效的查询性能，超越嵌入式数据库（如H2、SQLite）。
  • 与存储引擎协作，利用索引和统计信息。
2.2 功能
  • 计划生成：生成多种可能的执行计划。
  • 成本估算：基于统计信息评估计划成本。
  • 计划选择：选择最低成本的执行计划。
  • 优化规则：应用谓词下推、JOIN顺序调整等优化。
3. 查询优化器的核心设计
3.1 数据结构

  • 查询计划（QueryPlan）：

    • 表示执行计划的树形结构。
    1
2
3
4

    public abstract class QueryPlan {
    abstract double estimateCost();
    abstract List<Map<String, Object>> execute(StorageEngine storage, long txId);
}

  • 操作符（Operator）：

    • 包括扫描（Scan）、过滤（Filter）、连接（Join）等。
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    public class ScanOperator extends QueryPlan {
    private String tableName;
    private double rowCount; // 统计信息

    public ScanOperator(String tableName, double rowCount) {
        this.tableName = tableName;
        this.rowCount = rowCount;
    }

    @Override
    double estimateCost() { return rowCount; }

    @Override
    List<Map<String, Object>> execute(StorageEngine storage, long txId) {
        return storage.scanTable(tableName, txId);
    }
}
3.2 成本模型
  • 成本因子：
    • 扫描成本：表行数。
    • 过滤成本：选择率（selectivity）。
    • 连接成本：笛卡尔积大小和索引使用情况。
  • 统计信息：
    • 存储在MetadataManager中，包括行数、列选择率和索引信息。
3.3 优化策略
  • 规则优化：谓词下推（push down predicates）。
  • 成本优化：动态规划选择最优JOIN顺序。
4. 查询优化器实现

以下是QueryOptimizer类的核心实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

package com.yinlongfei.lightweight.database.optimizer;

import com.yinlongfei.lightweight.database.execution.SelectStatement;
import com.yinlongfei.lightweight.database.metadata.MetadataManager;
import com.yinlongfei.lightweight.database.storage.StorageEngine;

import java.util.*;

public class QueryOptimizer {
    private final MetadataManager metadataManager;
    private final StorageEngine storage;

    public QueryOptimizer(MetadataManager metadataManager, StorageEngine storage) {
        this.metadataManager = metadataManager;
        this.storage = storage;
    }

    public QueryPlan optimize(SelectStatement stmt, long txId) {
        List<QueryPlan> plans = generatePlans(stmt);
        return plans.stream()
                .min(Comparator.comparingDouble(QueryPlan::estimateCost))
                .orElseThrow(() -> new RuntimeException("No valid plan generated"));
    }

    private List<QueryPlan> generatePlans(SelectStatement stmt) {
        List<QueryPlan> plans = new ArrayList<>();
        String tableName = stmt.getTableName();
        double rowCount = metadataManager.getRowCount(tableName);

        // 基本计划：扫描 + 过滤
        QueryPlan scan = new ScanOperator(tableName, rowCount);
        QueryPlan filter = stmt.getWhereClause() != null 
                ? new FilterOperator(scan, stmt.getWhereClause()) 
                : scan;
        plans.add(filter);

        // 如果有索引，生成索引扫描计划
        List<String> indexedColumns = metadataManager.getIndexedColumns(tableName);
        if (stmt.getWhereClause() != null && indexedColumns.contains(stmt.getWhereClause().getColumn())) {
            plans.add(new IndexScanOperator(tableName, stmt.getWhereClause()));
        }

        // TODO: 支持JOIN和子查询计划
        return plans;
    }
}

class FilterOperator extends QueryPlan {
    private final QueryPlan child;
    private final Condition condition;
    private static final double SELECTIVITY = 0.1; // 默认选择率

    public FilterOperator(QueryPlan child, Condition condition) {
        this.child = child;
        this.condition = condition;
    }

    @Override
    double estimateCost() {
        return child.estimateCost() * SELECTIVITY;
    }

    @Override
    List<Map<String, Object>> execute(StorageEngine storage, long txId) {
        return child.execute(storage, txId).stream()
                .filter(row -> evaluateCondition(row, condition))
                .collect(Collectors.toList());
    }

    private boolean evaluateCondition(Map<String, Object> row, Condition cond) {
        Object value = row.get(cond.getColumn());
        switch (cond.getOperator()) {
            case ">": return ((Comparable) value).compareTo(cond.getValue()) > 0;
            case "=": return value.equals(cond.getValue());
            default: return false;
        }
    }
}

class IndexScanOperator extends QueryPlan {
    private final String tableName;
    private final Condition condition;

    public IndexScanOperator(String tableName, Condition condition) {
        this.tableName = tableName;
        this.condition = condition;
    }

    @Override
    double estimateCost() {
        return 10.0; // 假设索引扫描成本较低
    }

    @Override
    List<Map<String, Object>> execute(StorageEngine storage, long txId) {
        return storage.indexScan(tableName, condition, txId);
    }
}
5. 与其他模块的集成
  • 存储引擎：提供扫描和索引查询接口。
  • 元数据管理：获取表统计信息和索引定义。
  • 执行引擎：调用优化后的计划执行查询。

调整StorageEngine以支持索引扫描：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class StorageEngine {
    // ... 其他代码 ...

    public List<Map<String, Object>> indexScan(String tableName, Condition condition, long txId) {
        BPlusTree index = indexes.get(tableName + "_" + condition.getColumn());
        if (index != null) {
            List<Row> rows = index.search(condition.getValue());
            return rows.stream()
                    .filter(row -> txManager.isVisible(row, txId))
                    .map(Row::getColumns)
                    .collect(Collectors.toList());
        }
        return executeSelect(new SelectStatement(tableName, null, condition), txId);
    }

    public List<Map<String, Object>> scanTable(String tableName, long txId) {
        return memoryTables.getOrDefault(tableName, Collections.emptyList()).stream()
                .filter(row -> txManager.isVisible(row, txId))
                .map(Row::getColumns)
                .collect(Collectors.toList());
    }
}
6. 执行流程图

查询优化器的执行流程：

sequenceDiagram
    participant E as 执行引擎
    participant O as 查询优化器
    participant S as 存储引擎
    participant M as 元数据管理

    E->>O: optimize(stmt, txId)
    O->>M: getRowCount(table)
    M-->>O: rowCount
    O->>M: getIndexedColumns(table)
    M-->>O: indexedColumns
    O-->>E: QueryPlan
    E->>S: execute(plan, txId)
    S-->>E: List<Map>
  • 流程说明：
    1. 执行引擎调用优化器生成计划。
    2. 优化器从元数据管理获取统计信息。
    3. 返回最优计划，执行引擎调用存储引擎执行。
7. 测试示例
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

MetadataManager metadata = new MetadataManager();
StorageEngine storage = new StorageEngine("jdbc:lightweight:memory", metadata, txManager);
TransactionManager txManager = new TransactionManager(storage, logger);
QueryOptimizer optimizer = new QueryOptimizer(metadata, storage);

metadata.addTable("users", Arrays.asList("id", "name"), Collections.singletonList("id"), 1000);
InsertStatement insert = new InsertStatement("users", Arrays.asList("id", "name"), Arrays.asList(1, "Alice"));
storage.executeInsert(insert, txManager.begin(), logger);

SelectStatement select = new SelectStatement("users", null, new Condition("id", "=", 1));
QueryPlan plan = optimizer.optimize(select, txManager.getCurrentTxId());
List<Map<String, Object>> result = plan.execute(storage, txManager.getCurrentTxId());
System.out.println(result); // 输出 [{id=1, name=Alice}]
8. 下一步展望

下一篇文章将实现“元数据管理”，详细设计表结构和统计信息的存储与访问机制，进一步完善数据库功能。

总结

第六篇实现了查询优化器，通过基于成本的优化策略生成高效执行计划，支持索引利用和过滤优化。Mermaid图展示了优化流程，与存储引擎的集成提升了查询性能。后续将完善元数据支持。

updatedupdated2025-03-312025-03-31

相关文章：