צירופי האש

Hash joins

Alexander Chigrik
chigrik@hotmail.com

 

SQL Server תומך בשלושה טיפוסים של פעולות צירוף (Join) :

  • צירוף לולאות מקוננות (Nested loops joins)
  • צירוף מיזוג (Merge joins)
  • צירוף האש (Hash joins)

 

במאמר זה אדון בפעולת הצירוף השלישית - צירוף האש :אילו טיפוסים של צירופי האש קיימים, ובאילו תנאים  SQL Server יבחר בטיפוסים האלו של צירופי האש.

השימוש בצירופי האש יעשה במצבים בהם לא קיימים אינדקסים הולמים בעמודות הצירוף. זהו מצב גרוע ביותר. במצב מסוג זה, תיווצר טבלת האש. צירופי האש הם יעילים ביותר למקרים שגודלה של אחת מהטבלאות  שונה בצורה משמעותית מגודלה של האחרת. 

מייעל השאילתות (query Optimizer) יוצר צירוף האש בשני שלבים :

  1. שלב הבנייה (Build)
  2. שלב הבדיקה (Probe)

לכן לצירוף האש קיימים שני קלטים: קלט הבנייה וקלט החקירה.


בשלב הבנייה, תוצר  טבלת האש ע"י סריקת כל ערך בקלט הבנייה ויישום אלגוריתם ההאשינג למפתח.

על מנת להמחיש את צירוף ההאש אשתמש בדוגמה עבור שתי טבלאות :

הדוגמא:

if object_id('dbo.Table1') is not null drop table Table1
GO
CREATE TABLE Table1 (id int, Name char(10))
GO
if object_id('dbo.Table2') is not null drop table Table2
GO
CREATE TABLE Table1 (id int, Name char(20))
GO

DECLARE @i int
SELECT @i = 1
WHILE @i < 1000
  BEGIN
    INSERT INTO Table1 VALUES (@i, LTRIM(str(@i)))
    SELECT @i = @i + 1
  END
GO

DECLARE @i int
SELECT @i = 1
WHILE @i < 1000
  BEGIN
    INSERT INTO Table2 VALUES (@i, LTRIM(str(@i)))
    SELECT @i = @i + 1
  END
GO

SET SHOWPLAN_TEXT ON
GO
SELECT a.Name FROM Table1 a INNER JOIN Table2 b
  ON a.Name = b.Name
GO
SET SHOWPLAN_TEXT OFF
GO

התוצאה : 

StmtText
---------------------------------------------
  |--Hash Match(Inner Join, HASH:([a].[Name])=([b].[Name]), 
RESIDUAL:([a].[Name]=[b].[Name]))
       |--Table Scan(OBJECT:([pubs].[dbo].[Table1] AS [a]))
       |--Table Scan(OBJECT:([pubs].[dbo].[Table2] AS [b]))

 

הטבלה הקטנה יותר תיבנה כקלט בנייה, האחרת – קלט בדיקה. שמות השדות (העמודות שיוצרות את הצירוף בין הטבלאות(   נקראים "מפתח האש" (hash key) . טבלת ההאש מורכבת מרשימות מקושרות הנקראות "דליי האש" (hash buckets) . התוצאה של הפעלת פונקצית האש על מפתח האש נקראת "ערך האש"  (hash value) . ערך האש ומזהה השורה (row identifier) ימוקמו לתוך טבלת האש.

ערך האש חייב להיות קטן יותר ממפתח האש. לכן, מעבד השאילתא (Query Processor) חוסך בגודל של טבלת ההאש.  דוגמא ממשית של האשינג היא ספר טלפונים. ביכולתך לפתוח ספר טלפונים בעמוד המתאים ולסרוק את כל שמות המשפחה על מנת למצוא את הנחוצים. כלומר, ספר הטלפונים בדוגמא הוא בעצם טבלת ההאש והעמודים המתאימים הם דליי ההאש.

במהלך שלב החקירה, כל קלט החקירה נסרק, ועבור כל שורת קלט מחושב ערך ההאש הזהה במפתח ההאש על מנת למצוא התאמות בגליי ההאש המתאימים.

ישנם שני סוגים עיקריים של צירופי האש:

  1. צירוף האש תוך- זיכרון (In-memory Hash join)
  2. צרוף האש מפואר (Grace Hash join)

שימוש בסוג הראשון יעשה במקרים בהם כל קלט הבנייה יכול להיות מאוחסן בזיכרון.

שימוש בסוג השני יעשה כאשר אין בשרת מספיק זיכרון על מנת לאחסן את כל קלט הבנייה. במקרה זה, מעבד השאילתא יוצר צירוף האש במספר שלבים (טבלת ההאש תחולק למספר חלקים והחלק הרלוונטי יוטען  לפי הצורך) .

בשל הסיבה שמייעל השאילתא בוחר בדרך כלל בתוכנית ההרצה (execution plan)  הטובה ביותר עבור הצהרת Select נתונה, אין צורך לשנות את סוג הצירוף, אולם לעיתים דבר זה יכול להיות שימושי.  ביכולתך לכפות את טיפוס הצירוף הרצוי באמצעות OPTION clause .

זוהי דוגמא הממחישה כפייה של צירוף האש:

הדוגמא:

USE pubs
GO
SET SHOWPLAN_TEXT ON
GO
SELECT a.au_id FROM authors a JOIN titleauthor b
   ON a.au_id = b.au_id OPTION (HASH JOIN)
GO
SET SHOWPLAN_TEXT OFF
GO

התוצאה : 

StmtText
-----------------------------------------------
SELECT a.au_id FROM authors a JOIN titleauthor b
   ON a.au_id = b.au_id OPTION (HASH JOIN)

(1 row(s) affected)

StmtText
-----------------------------------------------
|--Hash Match(Inner Join, HASH:([a].[au_id])=([b].[au_id]), 
RESIDUAL:([a].[au_id]=[b].[au_id]))
|--Index Scan(OBJECT:([pubs].[dbo].[authors].[aunmind] AS [a]))
|--Index Scan(OBJECT:([pubs].[dbo].[titleauthor].[titleidind] AS 
[b]))

(3 row(s) affected)



  חזרה למאמרים נבחרים


  פרקים
  מבוא
  ניהול השרת
  אבטחה
  גיבוי והתאוששות
  קונפיגורציה ואופטימיזציה
  כלים
  שפת שאילתות מובנות
  יצוא/יבוא מידע
  נספחים
  התקנת השרת
  מילון מונחים
  מאמרים נבחרים
  מידע נוסף ברשת