資料查詢核心原理

資料庫實現查詢的原理：遍歷表/索引，判斷是否滿足where篩選條件，新增到結果集。簡單通用。

對於選擇表還是索引、如何遍歷關聯表、優先遍歷哪個表、怎樣提升遍歷的效率，這個就是資料庫查詢複雜的地方。

/**
 * 查詢命令實現查詢的主要過程
 * @see org.h2.command.dml.Select#queryFlat
 */
private void queryFlat(int columnCount, ResultTarget result, long limitRows) {
    // 遍歷單表 or 關聯表。topTableFilter 可以簡單理解為遊標 cursor。
    while (topTableFilter.next()) {
        // 判斷是否符合 where 篩選條件
        if (condition == null || Boolean.TRUE.equals(condition.getBooleanValue(session))) {
            Value[] row = new Value[columnCount];
            // 填充select 需要的 columns ①
            for (int i = 0; i < columnCount; i++) {
                Expression expr = expressions.get(i);
                row[i] = expr.getValue(session);
            }
            // 儲存符合條件的資料，這個對應 resultSet
            result.addRow(row);
            // 沒有 sort 語句的情況下，達到 limitRows， 終止 table scan ②
            if ((sort == null || sortUsingIndex) && limitRows > 0 &&
                    result.getRowCount() >= limitRows) {
                break;
            }
        }
    }
}

Join 查詢核心原理

基於狀態機模式，實現多表巢狀迴圈遍歷。

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

狀態變遷：BEFORE_FIRST --> FOUND --> AFTER_LAST

/**
 * Check if there are more rows to read.
 * 遍歷的資料 row 記錄在當前 session 中，隨時隨地可以獲取
 *
 * @return true if there are
 * @see org.h2.table.TableFilter#next
 */
public boolean next() {
    // 遍歷結束，沒有符合的條件的 row
    if (state == AFTER_LAST) {
        return false;
    } else if (state == BEFORE_FIRST) {
        // cursor 遍歷初始化， 如果基於索引的遊標，則可以提前鎖定資料範圍。③
        cursor.find(session, indexConditions);
        if (!cursor.isAlwaysFalse()) {
            // 如果包含 join 表，重置關聯表的狀態機。
            if (join != null) {
                join.reset();
            }
        }
    } else {
        // state == FOUND || NULL_ROW 的情況
        // 巢狀遍歷 join 關聯表。這是個遞迴呼叫關聯表的過程。
        if (join != null && join.next()) {
            return true;
        }
    }
    // 表/索引資料掃描，匹配filterCondition，直到找到符合的 row
    while (true) {
        if (cursor.isAlwaysFalse()) {
            state = AFTER_LAST;
        } else {
            if (cursor.next()) {
                currentSearchRow = cursor.getSearchRow();
                current = null;
                state = FOUND;
            } else {
                state = AFTER_LAST;
            }
        }
        // where 條件判斷
        if (!isOk(filterCondition)) {
            continue;
        }
        // 巢狀遍歷 join 關聯表。主表的每一行 row，需要遍歷關聯子表一次。④
        if (join != null) {
            join.reset();
            if (!join.next()) {
                continue;
            }
        }
        // check if it's ok
        if (state == NULL_ROW || joinConditionOk) {
            return true;
        }
    }
    state = AFTER_LAST;
    return false;
}

獲取查詢資料

從遍歷的 row 中，獲取 select 語句需要的 column 資料。

對應的 Cursor 實現是：org.h2.index.PageBtreeCursor

/**
 * 根據 columnId 獲取對應的值
 * @see org.h2.table.TableFilter#getValue
 */
public Value getValue(Column column) {
	if (current == null) {
		// 優先從當前遍歷的 row 獲取資料。
        // 如果是索引中的 row，不會包含所有的行，會有取不到的情況
		Value v = currentSearchRow.getValue(columnId);
		if (v != null) {
			return v;
		}
        // 如果沒有，再嘗試從原始表 row 儲存中獲取資料。⑤
        // 對應的實現： currentRow = index.getRow(session, currentSearchRow.getKey());
		current = cursor.get();
		if (current == null) {
			return ValueNull.INSTANCE;
		}
	}
	return current.getValue(columnId);
}

常用的 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

// 用虛擬碼錶示，可以更清晰理解上述 join 遍歷的過程
for (r in R) {
    for (s in S) {
        if (r satisfy condition s) {
            output <r, s>;
        }
    }
}

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 資料庫查詢原理