SQLSERVER中KeyHashValue的作用（上）
SQLSERVER中KeyHashValue的作用（下）
原文的标題是：SQLSERVER在索引下如何找到哈希值的随想
現在知道KeyHashValue的作用了，是以就改了标題~
測試環境：SQLSERVER2005 開發者版
真的不好意思，我做實驗的時候到最後還是沒有找到這個問題的答案
問題是這樣的：
當通過聚集索引查找和非聚集索引查找的時候，通過哈希碼來比對，然後找到相應記錄的
既然通過哈希碼來比對，那麼就需要一個hash bucket把所有索引頁面的所有key/value全部加載到hash bucket
既然要全部加載到hash bucket就需要讀取所有的索引頁
我的測試腳本，我使用SET STATISTICS IO ON來測試是否有讀取索引頁的情況，但是到最後還是找不到規律
1 --sql在聚集索引下如何找到哈希值的随想
2
3 USE master
4 GO
5 --建立資料庫IAMDB
6 CREATE DATABASE SCANDB
7 GO
8
9 USE SCANDB
10 GO
11
12
13
14 --DROP TABLE clusteredtable
15 --DROP TABLE nonclusteredtable
16
17
18 --建立測試表
19 CREATE TABLE clusteredtable(c1 INT IDENTITY(1,1), c2 VARCHAR (900))
20 GO
21 CREATE TABLE nonclusteredtable(c1 INT IDENTITY(1,1), c2 VARCHAR (900))
22 GO
23
24
25 --建立索引
26 CREATE CLUSTERED INDEX cix_clusteredtable ON clusteredtable([C2])
27 GO
28 CREATE INDEX ix_nonclusteredtable ON nonclusteredtable([C2])
29 GO
30
31
32 --插入測試資料
33 DECLARE @a INT;
34 SELECT @a = 1;
35 WHILE (@a <= 100)
36 BEGIN
37 INSERT INTO clusteredtable VALUES ( CAST(@a AS NVARCHAR(2))+replicate('a', 880))
38 SELECT @a = @a + 1
39 END
40
41
42 DECLARE @a INT;
43 SELECT @a = 1;
44 WHILE (@a <= 100)
45 BEGIN
46 INSERT INTO nonclusteredtable VALUES ( CAST(@a AS NVARCHAR(2))+replicate('a', 880))
47 SELECT @a = @a + 1
48 END
49
50
51
52
53 --查詢資料
54 SELECT * FROM clusteredtable ORDER BY [c1] ASC
55 SELECT * FROM nonclusteredtable ORDER BY [c1] ASC
56
57
58 CREATE TABLE DBCCResult (
59 PageFID NVARCHAR(200),
60 PagePID NVARCHAR(200),
61 IAMFID NVARCHAR(200),
62 IAMPID NVARCHAR(200),
63 ObjectID NVARCHAR(200),
64 IndexID NVARCHAR(200),
65 PartitionNumber NVARCHAR(200),
66 PartitionID NVARCHAR(200),
67 iam_chain_type NVARCHAR(200),
68 PageType NVARCHAR(200),
69 IndexLevel NVARCHAR(200),
70 NextPageFID NVARCHAR(200),
71 NextPagePID NVARCHAR(200),
72 PrevPageFID NVARCHAR(200),
73 PrevPagePID NVARCHAR(200)
74 )
75
76 TRUNCATE TABLE [dbo].[DBCCResult]
77
78 INSERT INTO DBCCResult EXEC ('DBCC IND(SCANDB,nonclusteredtable,-1) ')
79
80 SELECT * FROM [dbo].[DBCCResult] ORDER BY [PageType] DESC
81
82 DBCC TRACEON(3604,-1)
83 GO
84 DBCC PAGE(SCANDB,1,89,3)
85 GO
86
87 checkpoint
88 DBCC DROPCLEANBUFFERS
89 DBCC freesystemcache('all')
90 GO
91 -----------------------------------
92 SET STATISTICS IO ON
93 GO
94 --聚集索引查找
95 SELECT * FROM clusteredtable WHERE [c2]='18aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
96 SET STATISTICS IO OFF
97 GO
98
99
100
101 (1 行受影響)
102 表 'clusteredtable'。掃描計數 1，邏輯讀取 4 次，實體讀取 2 次，預讀 0 次，lob 邏輯讀取 0 次，lob 實體讀取 0 次，lob 預讀 0 次。
103
104
105
106
107 ----------------------------------------------------------------------------------------
108 checkpoint
109 DBCC DROPCLEANBUFFERS
110 DBCC freesystemcache('all')
111 GO
112 -----------------------------------
113 SET STATISTICS IO ON
114 GO
115 --索引查找 、RID查找 、嵌套循環
116 SELECT * FROM nonclusteredtable WHERE [c2]='17aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
117 SET STATISTICS IO OFF
118 GO
119
120
121
122 (1 行受影響)
123 表 'nonclusteredtable'。掃描計數 1，邏輯讀取 5 次，實體讀取 1 次，預讀 0 次，lob 邏輯讀取 0 次，lob 實體讀取 0 次，lob 預讀 0 次。 View Code
聚集索引表的情況
非聚集索引表的情況
今天中午跟高文佳兄讨論了很長時間，我把關鍵讨論部分貼出來，大家參考參考，讨論的最後結果是：還沒有解釋到keyhashvalue字段實際的作用
感謝高文佳，頭腦非常靈活
ō笑東風ō 9:27:10
對了 你那個hash的問題
ō笑東風ō 9:27:21
感覺你研究的方向不對
ō笑東風ō 9:28:05
當通過聚集索引查找和非聚集索引查找的時候，通過哈希碼來比對，然後找到相應記錄的
桦少 9:28:53
請指教
ō笑東風ō 9:29:00
查找時不會使用hash來查找 因為hash值沒有排序 無法最快查找
桦少 9:29:18
ō笑東風ō 9:29:20 應該是按照key來查找
桦少 9:33:52
ō笑東風ō 9:29:20
應該是按照key來查找
桦少 9:33:55
說說你的思路
ō笑東風ō 9:34:18
在索引裡已經按照KEY排序 對吧
ō笑東風ō 9:34:34
而按照key排序 能最快找到想要的值
桦少 9:35:38
key排序有争議
桦少 9:35:42
又怎樣
桦少 9:35:58
你還沒有說清楚
ō笑東風ō 9:37:21
先說key查找的
我記得你有篇blog裡說過hashjoin
桦少 9:39:38
哪三個經典連接配接沒有寫
ō笑東風ō 9:40:56
反正我的觀點是key查找最快 無須再使用hash來定位
ō笑東風ō 9:41:26
而隻有在hash join才會用到hash
笑東風ō 9:40:56
桦少 12:50:35
你想好啦嗎
ō笑東風ō 12:51:57
嗯 我還是認為聚簇索引和非聚簇索引隻存在key lookup
桦少 12:55:46
key lookup
的原理是什麼
桦少 12:55:52
操作步驟是怎樣的
桦少 12:55:56
你知道嗎
ō笑東風ō 12:59:31
就是平衡樹的原理
桦少 13:00:31
好
ō笑東風ō 13:00:38
使用平衡樹 對上百萬的INT值進行查找隻需要4步
桦少 13:00:58
你查找的時候是否需要從磁盤讀取索引頁面到記憶體
ō笑東風ō 13:01:05
對
桦少 13:01:06
先不說他用多少步
桦少 13:01:08
性能有多好
桦少 13:01:26
從磁盤讀取整個表的索引頁面到記憶體
桦少 13:01:29
整個表
桦少 13:01:41
然後構成你說的所謂的平衡樹
桦少 13:01:46
對吧
ō笑東風ō 13:02:06
對
桦少 13:02:52
我的問題就是這個
桦少 13:03:01
我用statictis io
桦少 13:03:10
看不出他會讀取所有的索引頁面
ō笑東風ō 13:04:25
一次seek 當然不會讀取所有的頁面
ō笑東風ō 13:04:48
隻有scan才會讀取所有頁面
桦少 13:05:36
你還是不明白我問的問題
桦少 13:06:18
我說的是索引頁
桦少 13:06:26
不是資料頁
ō笑東風ō 13:06:45
索引也一樣
ō笑東風ō 13:06:50
等等我給你做個demo
桦少 13:08:00
還有 ō笑東風ō 13:08:30
我現在有[BackupTestDB].[dbo].[TB1] 表中資料有245461條
桦少 13:08:43
你說用二叉樹
ō笑東風ō 13:08:44
桦少 13:08:47
如果是這樣
桦少 13:08:59
那麼，keyhashvalue就沒有意義了
ō笑東風ō 13:09:06
不是二叉樹 是B樹
桦少 13:09:15
桦少 13:09:23
b樹 桦少 13:09:51
是以我從hash bucket的角度去思考
ō笑東風ō 13:10:22
hash桶這個概念是為了HASH JOIN才産生的
桦少 13:10:36
如果用b樹，從第一個最左邊的葉子節點開始從磁盤讀取索引頁面，組裝一棵B樹
ō笑東風ō 13:11:05
繼續
桦少 13:11:23
如果是這樣，keyhashvalue這個字段根本不需要
桦少 13:12:12
用到key
alue的都可以用桶這個概念啊
桦少 13:12:19
我覺得
桦少 13:12:47
我覺得不用死磕書本
桦少 13:13:06
死磕書本等于讀死書
ō笑東風ō 13:14:28
桦少 13:14:49
桦少 13:15:58
我以前做實驗的時候也看到過keyhashvalue全部為null
桦少 13:16:47
想寫在SQLSERVER聚集索引與非聚集索引的再次研究（上）文章的最後面的
桦少 13:16:58
但是因為解釋不了這個現象
桦少 13:17:01
最後沒有寫
桦少 13:19:42
為什麽我提出這個想法
桦少 13:19:52
其實我也是從性能和速度考慮的
ō笑東風ō 13:20:09
騷等
桦少 13:20:21
我的想法是：sqlserver有可能不用你剛才說的B樹來找記錄
ō笑東風ō 13:20:31
我懷疑這個HASHvalus是為了在seek時做比較用的
桦少 13:20:45
我畫圖給你看
桦少 13:22:42
當我用聚集索引查找的時候
桦少 13:23:11
key的字段是id
桦少 13:23:25
表中的字段是id
桦少 13:23:32
id是聚集索引字段
桦少 13:23:50
value是資料頁面号
桦少 13:24:12
我要找id為9的那條記錄
桦少 13:24:58
等一下
桦少 13:25:02
圖還沒畫好
桦少 13:26:27
桦少 13:26:51
我需要将索引頁69，88，102讀取到記憶體
桦少 13:26:57
構成一棵b樹
桦少 13:27:13
從左到右，從上到下查找
桦少 13:27:30
直至找到key為9那條記錄
桦少 13:27:59
如果我select的是id為3的那條記錄
桦少 13:28:17
我就不用讀取索引頁88，102讀取到記憶體
桦少 13:28:23
隻需要讀取索引頁面69
桦少 13:30:29
改一下，資料頁面編号沒有英文字母的
桦少 13:30:30
桦少 13:30:37
睡醒再聊
桦少 14:05:59
當我找id為9的記錄的時候
桦少 14:06:16
我需要掃描索引頁面69和索引頁面88
ō笑東風ō 14:06:28
不需要掃面69
ō笑東風ō 14:06:42
隻需要掃描88和102
桦少 14:06:43
說錯了
桦少 14:06:54
是的
桦少 14:07:15
但是你也需要從磁盤讀取索引頁面69吧
桦少 14:07:22
組裝出一棵b樹
桦少 14:08:56
逐行逐行掃描 索引頁面88和102裡的記錄
桦少 14:09:08
直到掃描到id為9的那條記錄才停止
桦少 14:09:14
我的想法是
桦少 14:09:51
我的想法是：sqlserver有可能不用你剛才說的B樹來找記錄
ō笑東風ō 14:09:53
頁面内掃描是這樣
桦少 14:10:59
将所有索引頁面的key列和value列放進去hash桶
桦少 14:11:07
ō笑東風ō 14:11:31
我剛在我本地跑了下你的腳本 SQL SERVER 2008 SP2
桦少 14:11:32
通過算法查找到id為9的那一條記錄
ō笑東風ō 14:11:38
沒有hashkey
ō笑東風ō 14:11:59
你的平台是什麼
桦少 14:12:04
這樣就不用掃描：索引頁面88和102裡的記錄
桦少 14:12:32
這個過程當中，也是需要讀取頁面69，88，102
桦少 14:12:39 但是他就不用掃描
桦少 14:12:47 sql2005
ō笑東風ō 14:13:14
我到時有一種猜測
桦少 14:13:57
不然無辦法解釋keyhashvalue這個字段
ō笑東風ō 14:14:07
當比如較大字元串的時候 如果将字元串先hash後比較hash值 如果hash值相同 在比較字元串 這樣效率會高一些
桦少 14:16:54
這種方法有一個缺點
ō笑東風ō 14:17:17
什麼缺點
桦少 14:18:10
如果我select的是id為3的那條記錄 他都會把所有索引頁面讀取到記憶體
桦少 14:18:20
而不像B樹
桦少 14:18:36
桦少 14:18:43
因為他需要在桶裡面找
ō笑東風ō 14:19:53
如果按照你所想的這樣 無法快讀定位某一個值的行
ō笑東風ō 14:20:03
必須掃描所有頁
ō笑東風ō 14:20:17
除非對hashvalue進行排序
桦少 14:21:01
掃描所有索引頁面
桦少 14:21:20
把所有索引頁面裡的keyhashvalue讀取到桶裡面
桦少 14:21:22
然後查找
ō笑東風ō 14:26:27
而且到hash桶後 還需要排序 如果不排序 需要全部周遊
桦少 14:27:33
嗯嗯
桦少 14:27:43
是以我的文章标題是：随想
ō笑東風ō 14:29:36
我知道有一種程式設計 是這樣做的 就是對大字段做hash 然後對hash作為一列存儲 對hash列建立索引
ō笑東風ō 14:30:04
這樣做等值查詢時能提高查詢效率
桦少 14:32:58
高兄你是不是想偏了
桦少 14:33:09
不是隻有大字段才有hash
ō笑東風ō 14:33:38
我隻是說這是一種設計思路
桦少 14:33:39
ō笑東風ō 14:34:14
任何資料都可以被hash
桦少 14:34:37
不過這裡好像說不過去
ō笑東風ō 14:36:10
而且林兄你看到的這些都是非葉子節點哈
桦少 14:50:22
當然是非葉子節點啦
桦少 14:50:33
葉子節點就是資料頁面
ō笑東風ō 14:51:28
這個hashvalue應該跟seek無關
桦少 14:52:39
是以我才說無辦法解釋嘛
ō笑東風ō 14:59:25
嗯嗯