数据查询核心原理

数据库实现查询的原理：遍历表/索引，判断是否满足where筛选条件，添加到结果集。简单通用。

对于选择表还是索引、如何遍历关联表、优先遍历哪个表、怎样提升遍历的效率，这个就是数据库查询复杂的地方。

1/**
2 * 查询命令实现查询的主要过程
3 * @see org.h2.command.dml.Select#queryFlat
4 */
5private void queryFlat(int columnCount, ResultTarget result, long limitRows) {
6    // 遍历单表 or 关联表。topTableFilter 可以简单理解为游标 cursor。
7    while (topTableFilter.next()) {
8        // 判断是否符合 where 筛选条件
9        if (condition == null || Boolean.TRUE.equals(condition.getBooleanValue(session))) {
10            Value[] row = new Value[columnCount];
11            // 填充select 需要的 columns ①
12            for (int i = 0; i < columnCount; i++) {
13                Expression expr = expressions.get(i);
14                row[i] = expr.getValue(session);
15            }
16            // 保存符合条件的数据，这个对应 resultSet
17            result.addRow(row);
18            // 没有 sort 语句的情况下，达到 limitRows， 终止 table scan ②
19            if ((sort == null || sortUsingIndex) && limitRows > 0 &&
20                    result.getRowCount() >= limitRows) {
21                break;
22            }
23        }
24    }
25}
26
27
28
29

Join 查询核心原理

基于状态机模式，实现多表嵌套循环遍历。

使用的 Join 算法是： Nested Loop Join。

状态变迁：BEFORE_FIRST --> FOUND --> AFTER_LAST

1/**
2 * Check if there are more rows to read.
3 * 遍历的数据 row 记录在当前 session 中，随时随地可以获取
4 *
5 * @return true if there are
6 * @see org.h2.table.TableFilter#next
7 */
8public boolean next() {
9    // 遍历结束，没有符合的条件的 row
10    if (state == AFTER_LAST) {
11        return false;
12    } else if (state == BEFORE_FIRST) {
13        // cursor 遍历初始化， 如果基于索引的游标，则可以提前锁定数据范围。③
14        cursor.find(session, indexConditions);
15        if (!cursor.isAlwaysFalse()) {
16            // 如果包含 join 表，重置关联表的状态机。
17            if (join != null) {
18                join.reset();
19            }
20        }
21    } else {
22        // state == FOUND || NULL_ROW 的情况
23        // 嵌套遍历 join 关联表。这是个递归调用关联表的过程。
24        if (join != null && join.next()) {
25            return true;
26        }
27    }
28    // 表/索引数据扫描，匹配filterCondition，直到找到符合的 row
29    while (true) {
30        if (cursor.isAlwaysFalse()) {
31            state = AFTER_LAST;
32        } else {
33            if (cursor.next()) {
34                currentSearchRow = cursor.getSearchRow();
35                current = null;
36                state = FOUND;
37            } else {
38                state = AFTER_LAST;
39            }
40        }
41        // where 条件判断
42        if (!isOk(filterCondition)) {
43            continue;
44        }
45        // 嵌套遍历 join 关联表。主表的每一行 row，需要遍历关联子表一次。④
46        if (join != null) {
47            join.reset();
48            if (!join.next()) {
49                continue;
50            }
51        }
52        // check if it's ok
53        if (state == NULL_ROW || joinConditionOk) {
54            return true;
55        }
56    }
57    state = AFTER_LAST;
58    return false;
59}
60
61
62
63

获取查询数据

从遍历的 row 中，获取 select 语句需要的 column 数据。

对应的 Cursor 实现是：org.h2.index.PageBtreeCursor

1/**
2 * 根据 columnId 获取对应的值
3 * @see org.h2.table.TableFilter#getValue
4 */
5public Value getValue(Column column) {
6	if (current == null) {
7		// 优先从当前遍历的 row 获取数据。
8        // 如果是索引中的 row，不会包含所有的行，会有取不到的情况
9		Value v = currentSearchRow.getValue(columnId);
10		if (v != null) {
11			return v;
12		}
13        // 如果没有，再尝试从原始表 row 存储中获取数据。⑤
14        // 对应的实现： currentRow = index.getRow(session, currentSearchRow.getKey());
15		current = cursor.get();
16		if (current == null) {
17			return ValueNull.INSTANCE;
18		}
19	}
20	return current.getValue(columnId);
21}
22
23
24
25

常用的 SQL 查询优化技巧

分别对应上述源代码注释的数字角标。

①避免使用 SELECT *：只选择需要的列

如果使用 select *, 即使使用了索引查询。也需要取原数据行的所有数据（⑤）。会进行数据的二次读取，也就是回表查询。影响了性能。

②避免使用 ORDER BY, 尽量使用LIMIT

使用 LIMIT：如果只需要部分结果，可以使用 LIMIT 子句限制返回的行数，避免检索整个结果集。

如上源代码，如果没有 Order By，有limit 限制情况下，可以中途结束表遍历。

如果有 Order By 的情况下，肯定要执行完成整个扫描遍历的过程，最终在 result 结果集中再一次进行排序计算。

③使用索引：确保表中的列上有适当的索引，以加快查询速度。

如果使用索引，在初始化扫描阶段，会给 cursor 一定的范围，避免全表扫描。极大的缩小的查询范围。

④减少连接的表的数量：如果可能，尽量减少查询中的表的数量。

无需多言，嵌套递归查询，理论上是所有表的笛卡尔积。

⑤使用覆盖索引：一个查询的所有列都包含在索引中。

这样查询可以只扫描索引而不需要回表。例如，如果你的查询是 SELECT id, name FROM users WHERE age = 30，那么在 age, id, name 上创建一个复合索引可以避免回表。

其他

Nested Loop Join

1// 用伪代码表示，可以更清晰理解上述 join 遍历的过程
2for (r in R) {
3    for (s in S) {
4        if (r satisfy condition s) {
5            output <r, s>;
6        }
7    }
8}
9
10
11
12

MySQL 中的Nested Loop Join

MySQL官方文档中提到，MySQL只支持Nested Loop Join这一种join algorithm.

MySQL resolves all joins using a nested-loop join method.

This means that MySQL reads a row from the first table, and then finds a matching row in the second table, the third table, and so on.

作者：京东物流杨攀

来源：京东云开发者社区自猿其说Tech 转载请注明来源

从 SQL 查询优化技巧去看 h2 数据库查询原理 | 京东物流技术团队