בחירה בין Nested Loops, Merge Join, Hash Match בביצוע Join בין טבלאות

22/02/2014

אין תגובות

כשמתבצע Join בין טבלאות – המערכת יכולה לבחור באחד משלושה אלגוריתמים לביצוע המשימה באופן פיזי:

  • Nested Loops יתבצע כשיש לפחות טבלה אחת קטנה ובשניה יש אינדקס שמקל על החיפוש, ואז עבור כל שורה בראשונה – היא תחפש התאמות בשניה.
  • Merge Join שהוא האלגוריתם הכי יעיל יתבצע כששתי הטבלאות ממויינות או בעלות אינדקס מתאים, ואז המערכת עוברת במקביל על שתי הטבלאות ומחפשת התאמות.
  • Hash Match שהוא האלגוריתם הפחות יעיל יתבצע כשאין אינדקסים להיעזר בהם והטבלאות אינן ממויינות; ואז המערכת תחלק כל טבלה לקבוצות לפי שיטה מסויימת, ותחפש התאמות בין קבוצות מתאימות (מן הסתם תבצע בינהן Nested Loops).

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

ניצור שתי טבלאות ללא אינדקסים, לכל אחת נכניס שורה אחת מטבלה sys.messages (טבלה שאני מרבה להשתמש בה ליצירת דוגמאות טכניות כי יש בה כ-250,000 שורות החל מגרסה 2012), ונבצע Join בין הטבלאות (מקרה קצת פשטני בו מתבצע Join בין שתי טבלאות בנות שורה אחת כל אחת):

Use tempdb;

 

Select    Top 1 Row_number() Over(Order by Getdate()) N,

        *

Into    T1

From    sys.messages;

Alter Table T1 Alter Column N Int Not Null;

 

Create Table T2 (N Int);

Alter Table T2 Alter Column N Int Not Null;

 

Insert Into T2 Select N From T1 Where N=1;

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

כפי שאפשר לראות- המערכת בחרה לבצע Hash Match, שבמקרה זה אין לו משמעות רבה מכיוון שבוצעה השוואה בודדת של השורה מ-T2 עם השורה מ-T1, אך ברור שאם במצב כזה מתבצע Hash Match (אני מזכיר- אין אינדקסים!) – אזי כשיהיו יותר שורות בטח ובטח שיעשה שימוש באלגוריתם זה, שאולי אינו יעיל אך כאן הוא הרע במיעוט.
נכניס לטבלה T1 את כל 250,000 השורות מ-sys.messages, וכצפוי אותו אלגוריתם יבחר:

Truncate Table T1;

 

Insert

Into    T1

Select    Row_number() Over(Order by Getdate()) N,

        *

From    sys.messages;

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

המערכת משתמשת כאן ב-Parallelism לשליפת השורות מ-T1 במקביל, חלוקתן לקבוצות השונות, וההשוואה מול השורה הבודדת שב-T2; וכאמור- בעזרת Hash Match.

מה יקרה אם נוסיף לשתי הטבלאות אינדקסים מתאימים על עמודה N שעל פיה מתבצעת ההשוואה (במקרה של T2 זה ישפיע בהמשך כשנגדיל אותה אך כעת זה ישפיע רק על הטיפול ב-T1)?
ניצור בשתיהן Primary Key &Clustered Index ונבצע Join שוב:

Alter Table T1 Add Constraint PK_T1 Primary Key Clustered(N);

Alter Table T2 Add Constraint PK_T2 Primary Key Clustered(N);

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

הפעם המערכת בחרה ב-Nested Loops: היא לקחת את השורה הבודדת מ-T2 וחיפשה אותה ב-T1. מכיוון שב-T1 יש אינדקס מתאים – היא לא הייתה צריכה לבצע Clustered Index Scan על כולו, ויכלה להגיע ישירות לשורה המבוקשת בעזרת Seek.

גם אם נוסיף שורות ל-T2 המערכת תמשיך להשתמש ב-Nested Loops. נגדיל את מספר השורות בה ל-20,000 ונבדוק שוב:

Insert Into T2 Select N From T1 Where N Between 2 And 20000;

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

גם כשיש 20,000 שורות ב-T2 למערכת כדאי לעבור עליה שורה-שורה (Clustered Index Scan) ולחפש את ההתאמות ב-T1; אך לא לנצח- נוסיף עוד 9000 שורות ל-T2 וננסה שוב:

Insert Into T2 Select N From T1 Where N Between 20001 And 29000;

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

כעת, כששתי הטבלאות מספיק גדולות ולשתיהן אינדקסים מתאימים לביצוע ה-Join, המערכת בוחרת ב-Merge Join. היא תעבור במקביל על שתיהן (Clustered Index Scan) ותחפש התאמות, בערך כפי שהיינו אנו עושים לו קיבלנו שתי רשימות ממויינות על דף נייר, היינו שמים אצבע כאן ואצבע שם, וסורקים את שתיהן במקביל תוך שאנחנו מסנכרנים בין שתי האצבעות.
אי שם במעבר בין 20,000 ל-29,000 שורות בטבלה T2 (ספציפית במקרה זה- בין 26,150 ל-26,151 שהן קצת יותר מ-10% מהשורות), המערכת החליטה שבמקום לבצע כמה רבבות Index Seeks – כל אחד כשלעצמו זול אך כולם ביחד כבר לא – לעבור לביצוע Scan מלא על הטבלה ולקרוא כמה מאות אלפי שורות.
אם לאחת הטבלאות לא היה אינדקס מתאים – לא ניתן היה לבצע Merge Join (במקרים מסויימים המערכת "תשקול" למיין טבלה כזו אך לא הפעם). נבטל את האינדקס על T2:

Alter Table T2 Drop Constraint PK_T2;

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

המערכת חזרה ל-Nested Loops הישן והטוב מכיוון שכעת לא ניתן לבצע Merge Join (ומיון של T2 על 29,000 שורותיה יהיה יקר מדי).
לעבור שורה-שורה על T2 נטול האינדקס – זו אינה בעייה (המחיר של Table Scan ושל Clustered Index Scan הוא זהה), אבל לבצע 29,000 פעולות Seek על T1 – זה קצת יקר, וניתן לראות שזו עיקר העלות במקרה זה (98%). כשמספר השורות ב-T2 יגדל, הבחירה של המערכת תשתנה. נוסיף לה 1000 שורות:

Insert Into T2 Select N From T1 Where N Between 29001 And 30000;

 

Select    *

From    T1

Inner Join T2

        On T1.N=T2.N;

image

לבצע 30,000 פעולות Seek על T1 זה כנראה יותר מדי, והמערכת חזרה ל-Hash Match שבנסיבות הנוכחיות הוא האופציה העדיפה.

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *