Index

讀取索引嵌套循環連接的磁碟頁面

  • December 10, 2016

如果這是發布此問題的錯誤位置,我深表歉意。

在我正在學習的高級數據庫課程中,我們被告知,當您有足夠的緩衝區空間容納 3 個頁面時,執行索引嵌套循環連接時完成的磁碟頁面讀取次數為:

**R INLJ S = |Pages(R)|**的磁碟頁面讀取 + |R|.Depth(S 上的索引) + |R Join S|

我知道我們需要讀取 R 的所有頁面作為外循環,然後我們必須遍歷 B+ 樹的深度以獲取葉子頁面(並執行此操作 |R| 次)但是為什麼我們需要添加R 加入 S 的次數?

我從來沒有上過這樣的課,但我相信這個想法是當你通過索引找到匹配的行時,它需要額外的讀取來獲取數據頁。讓我們在 SQL Server 中執行一個快速測試,看看我們得到的數字是否接近您的公式。

首先,我將創建表並將範例數據插入其中。我想測試三個不同的查詢:一個返回 0 行,一個返回 5000 行,一個返回 10000 行。

-- create tables
CREATE TABLE X_OUTER_TABLE (NUM INT);
CREATE TABLE X_INNER_TABLE_0_MATCHES (NUM INT, FILLER VARCHAR(100));
CREATE INDEX IX_X_INNER_TABLE_0_MATCHES ON X_INNER_TABLE_0_MATCHES (NUM);

CREATE TABLE X_INNER_TABLE_5000_MATCHES (NUM INT, FILLER VARCHAR(100));
CREATE INDEX IX_X_INNER_TABLE_5000_MATCHES ON X_INNER_TABLE_5000_MATCHES (NUM);

CREATE TABLE X_INNER_TABLE_10000_MATCHES (NUM INT, FILLER VARCHAR(100));
CREATE INDEX IX_X_INNER_TABLE_10000_MATCHES ON X_INNER_TABLE_10000_MATCHES (NUM);

-- populate data
WITH E00(N) AS (SELECT 1 UNION ALL SELECT 1),
       E02(N) AS (SELECT 1 FROM E00 a, E00 b),
       E04(N) AS (SELECT 1 FROM E02 a, E02 b),
       E08(N) AS (SELECT 1 FROM E04 a, E04 b),
       E16(N) AS (SELECT 1 FROM E08 a, E08 b),
       E32(N) AS (SELECT 1 FROM E16 a, E16 b),
  cteTally(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY N) FROM E32)
INSERT INTO X_OUTER_TABLE WITH (TABLOCK)
select N from cteTally where N BETWEEN 1 AND 10000;

WITH E00(N) AS (SELECT 1 UNION ALL SELECT 1),
       E02(N) AS (SELECT 1 FROM E00 a, E00 b),
       E04(N) AS (SELECT 1 FROM E02 a, E02 b),
       E08(N) AS (SELECT 1 FROM E04 a, E04 b),
       E16(N) AS (SELECT 1 FROM E08 a, E08 b),
       E32(N) AS (SELECT 1 FROM E16 a, E16 b),
  cteTally(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY N) FROM E32)
INSERT INTO X_INNER_TABLE_0_MATCHES WITH (TABLOCK)
select N, REPLICATE('Z', 100) from cteTally where N BETWEEN 10001 AND 60000;

WITH E00(N) AS (SELECT 1 UNION ALL SELECT 1),
       E02(N) AS (SELECT 1 FROM E00 a, E00 b),
       E04(N) AS (SELECT 1 FROM E02 a, E02 b),
       E08(N) AS (SELECT 1 FROM E04 a, E04 b),
       E16(N) AS (SELECT 1 FROM E08 a, E08 b),
       E32(N) AS (SELECT 1 FROM E16 a, E16 b),
  cteTally(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY N) FROM E32)
INSERT INTO X_INNER_TABLE_5000_MATCHES WITH (TABLOCK)
select N, REPLICATE('Z', 100) from cteTally where N BETWEEN 5001 AND 65000;

WITH E00(N) AS (SELECT 1 UNION ALL SELECT 1),
       E02(N) AS (SELECT 1 FROM E00 a, E00 b),
       E04(N) AS (SELECT 1 FROM E02 a, E02 b),
       E08(N) AS (SELECT 1 FROM E04 a, E04 b),
       E16(N) AS (SELECT 1 FROM E08 a, E08 b),
       E32(N) AS (SELECT 1 FROM E16 a, E16 b),
  cteTally(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY N) FROM E32)
INSERT INTO X_INNER_TABLE_10000_MATCHES WITH (TABLOCK)
select N, REPLICATE('Z', 100) from cteTally where N BETWEEN 1 AND 50000;

我需要獲取有關索引深度和表中頁數的一些資訊,並進行一些額外的設置以獲得更清晰的數字:

-- index depth of 2
SELECT INDEXPROPERTY ( object_ID('X_INNER_TABLE_10000_MATCHES'), 'IX_X_INNER_TABLE_10000_MATCHES' , 'IndexDepth');

-- 19 used pages, 26 reserved
SELECT OBJECT_NAME(s.object_id) table_name,
       SUM(s.used_page_count) used_pages,
       SUM(s.reserved_page_count) reserved_pages
FROM    sys.dm_db_partition_stats s
WHERE OBJECT_NAME(s.object_id) IN ('X_OUTER_TABLE')
GROUP BY s.object_id;

-- get logical reads after query execution
SET STATISTICS IO ON;

-- Trace flag 8744: Disable pre-fetching for ranges
DBCC TRACEON(8744);

根據公式,我期望以下結果:

將 X_OUTER_TABLE 加入 X_INNER_TABLE_0_MATCHES:19 + 2 * 10000 + 0 = 20019

將 X_OUTER_TABLE 加入 X_INNER_TABLE_5000_MATCHES:19 + 2 * 10000 + 5000 = 25019

將 X_OUTER_TABLE 加入 X_INNER_TABLE_10000_MATCHES:19 + 2 * 10000 + 10000 = 30019

執行 SELECT 查詢:

SELECT INNER_TABLE.FILLER
FROM X_OUTER_TABLE OUTER_TABLE
INNER LOOP JOIN X_INNER_TABLE_0_MATCHES INNER_TABLE ON OUTER_TABLE.NUM = INNER_TABLE.NUM;

/*
(0 row(s) affected)
Table 'X_INNER_TABLE_0_MATCHES'. Scan count 10000, logical reads 20000, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'X_OUTER_TABLE'. Scan count 1, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
*/


SELECT INNER_TABLE.FILLER
FROM X_OUTER_TABLE OUTER_TABLE
INNER LOOP JOIN X_INNER_TABLE_5000_MATCHES INNER_TABLE ON OUTER_TABLE.NUM = INNER_TABLE.NUM;

/*
(5000 row(s) affected)
Table 'X_INNER_TABLE_5000_MATCHES'. Scan count 10000, logical reads 25022, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'X_OUTER_TABLE'. Scan count 1, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
*/


SELECT INNER_TABLE.FILLER
FROM X_OUTER_TABLE OUTER_TABLE
INNER LOOP JOIN X_INNER_TABLE_10000_MATCHES INNER_TABLE ON OUTER_TABLE.NUM = INNER_TABLE.NUM;

/*
(10000 row(s) affected)
Table 'X_INNER_TABLE_10000_MATCHES'. Scan count 10000, logical reads 30044, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'X_OUTER_TABLE'. Scan count 1, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
*/

實際結果:

將 X_OUTER_TABLE 加入 X_INNER_TABLE_0_MATCHES:20017 年(預測 20019 年)

將 X_OUTER_TABLE 加入 X_INNER_TABLE_5000_MATCHES:25039(預測為 25019)

將 X_OUTER_TABLE 加入 X_INNER_TABLE_10000_MATCHES:30061(預測為 30019)

我認為這非常接近!

清理腳本的完整性:

DBCC TRACEOFF(8744);

DROP TABLE X_OUTER_TABLE;
DROP TABLE X_INNER_TABLE_0_MATCHES;
DROP TABLE X_INNER_TABLE_5000_MATCHES;
DROP TABLE X_INNER_TABLE_10000_MATCHES;

引用自:https://dba.stackexchange.com/questions/157684