כמה מילים על אינדקסים ועל Reverse Key Index
בפוסט הקודם שלי כתבתי על יצירה במקביל של אינדקסים על אותן עמודות וציינתי בין היתר שניתן ליצור את האינדקסים רק אם משנים חלק ממאפייני הרקע שלהם. כדוגמה נתתי את Reverse Key Index ונשאלתי במה מדובר.
מכוון שהאינדקס הזה נמצא איתנו כבר לא מעט זמן (אורקל 8 אם אני זוכר נכון) הוא עדיין לא מאוד נפוץ והרגשתי שזה יהיה מעניין לכתוב קצת על אינדקסים באופן כללי ועל האינדקס הזה בפרט.
אינדקס "רגיל"
אז כדי להסביר מה זה Reverse Key Index, נתחיל קודם בהסבר קצר על מה זה אינדקסים ומה הבעיה שהסוג הזה בא לפתור.
אינדקס "רגיל" באורקל הוא מבנה נתונים ממוין מסוג B*Tree. כאשר אנחנו מחליטים ליצור אינדקס על עמודה, ה-database יוצר לנו עץ של ערכים.
העץ מורכב משני חלקים:
- רשימה של כל הערכים שבעמודה והצבעה בחזרה לרשומות במבנה הנתונים הראשי שלנו שהוא הטבלה (ההצבעה מתבצעת על ידי שימוש ב-rowid). לרשימה הממוינת הזו עם המצביעים אנחנו קוראים העלים של האינדקס (leafs).
- מראש העץ ועד לעלים נוצרים לנו צמתים שעוזרים לנו לנווט בתוך העץ.
כשאנחנו באים לחפש נתון באמצעות שימוש בעמודה, לאופטימייזר יש כמה אפשרויות:
- הוא יכול לסרוק את הטבלה כולה כדי למצוא את הנתון (Full Table Scan) אבל זו גישה לא מאוד יעילה במרבית המקרים
- אם קיים אינדקס אז אפשר "לטייל" בתוך הצמתים שבאינדקס כדי למצוא את הרשומות שעונות על התנאי ולהחזיר אותן מתוך הטבלה באמצעות שימוש במצביע. אם במקרה יש לנו יותר מרשומה אחת שעונה על התנאי, האופטימייזר מגיע עד הרשומה הראשונה שעונה על התנאי דרך הצמתים וסורק רק את העלים של האינדקס כדי להחזיר את כל הרשומות הרלוונטיות (Index Range Scan).
דרך אגב, שווה להזכיר שה-B ב-B*Tree לא בא לציין את הבינאריות של העץ אלא את העובדה שהעץ הזה מאוזן (Balanced) תמיד – המרחק מראש העץ ועד לעלים הוא אותו הדבר לכל עלה – ולכן הגובה שלו צריך להיות מספר נמוך יחסית. למעשה, גובה האינדקס אמור להיות 3-4 רמות לטבלאות שיש בהן פחות מכמה מאות מיליונים רשומות.
הבעיה
כאשר אנחנו מוספים רשומות לטבלה, האינדקס שלנו מתעדכן באופן אוטומטי ביחד עם הטבלה – הרשומה נוספת לבלוק העלה הרלוונטי ברשימת העלים ואם יש צורך לאזן מחדש את הענף הזה בעץ אז זה מתבצע באופן אוטומטי. הבעיה מתחילה כשאנחנו מחליטים ליצור אינדקס על עמודה שמכילה מספרים רצים שעולים כל הזמן (לדוגמה, sequence או identity column). מכוון שהמספרים כל הזמן עולים, העלה שכל הזמן מקבל רשומות חדשות הוא העלה הכי ימני באינדקס (כלומר, זה שהתווסף אחרון). ברגע שיש לנו כמה תהליכים שכותבים רשומות, נוצרות לנו המתנות על הבלוק הזה – הבלוק הזה הופך להיות הבלוק הכי "חם" במערכת – כולם רוצים אותו כל הזמן.
המצב הזה מכונה "אינדקס עם הטיה לימין" – כל הרשומות רוצות להיכנס לבלוק הכי ימני באינדקס. מה שנוצר לנו בפועל זה בעיה של index block contention – נעילה מצד ה-index. מצד המערכת אנחנו נתחיל לראות wait-ים של buffer busy waits ו-read by other session על הסגמנט של האינדקס וזה יאט את המערכת. בנוסף נוצרת לנו בעיה של איזון העץ (כי יש הטיה קבועה) – אורקל יטפל במקרה בצורה אוטומטית אבל זה עלול לעלות לנו בזמן שיקח ל-insert-ים.
שווה לשים לב: אם אנחנו נהיה בסביבה של RAC אז המצב יחמיר משמעותית מכוון שהבלוק החם הופך להיות גם חבר במועדון הנוסע המתמיד: הוא יתחיל לטייל בין ה-Node-ים כדי לסנכרן אותו בין ה-SGA-ים השונים.
אז מה עושים…?
Reverse Key Index
הפתרון לבעיה המאוד ספציפית הזו הוא Reverse Key Index.
אם המספרים שלנו הם מספרים רצים, ולכן סדר ההכנסה לטבלה הוא סדר הבלוקים באינדקס אז מה שהיינו רוצים שיקרה זה שהבלוקים של האינדקס יתפזרו בצורה מאוזנת בתוך העץ. אם זה יקרה אז הבלוק האחרון לא יהיה הבלוק החם ואורקל לא יצטרך לאזן את העץ שלו כל הזמן.
כדי שהדבר הזה יקרה אורקל מספקים לנו אינדקס שקורא את המספר שנתנו לו מהסוף להתחלה. לדוגמה, אם הרשומה מכילה את המספר 1234 אז הוא יאנדקס 4321. הרשומה הבאה תהיה 1235 והוא יאנדקס 5321 וכן הלאה. נרוץ קצת קדימה ונראה שרק כאשר נעבור אלף מספרים (2234) נקבל רשומה שהיא צמודה לרשומה הראשונה שלנו (4322).
למעשה, ככל שהמספר שלנו גדול יותר כך הסבירות לקבל שתי רשומות שנכנסות בצורה צמודה לאותו בלוק יורד ולכן אין יותר בלוק חם.
איך יוצרים אינדקס כזה? פשוט מאוד!
Create index idx_rev on Zohar.rev_table_example (id) reverse;
הפתרון הזה מעולה כשאנחנו צריכים לקרוא רשומות על פי שוויון לעמודה – האופטימייזר יטייל בתוך הצמתים וימצא לנו את העלה הרלוונטי. לעומת זאת, אם האופטימייזר מזהה שהשליפה דורשת איזשהו range scan על האינדקס (לדוגמה אם אנחנו משתמשים ב-BETWEEN, <, >, <=, >=, LIKE וכדומה) אז האינדקס הזה מחוץ למשחק ולא ניתן להשתמש בו. הסיבה היא פשוטה – range scan רגיל מגיע לרשומה הראשונה בעלים ומתחיל לסרוק את העלים שאחריו כדי להביא את שאר הערכים. זה לא המקרה פה – הרשומות שלנו באינדקס לא ממוינות ככה אז אין טעם לסרוק את העלים כדי להחזיר את הערכים הבאים.
סיכום
נושא האינדקסים הוא נושא מרתק – כתבתי פה בכמה מילים גם על אינדקסים "רגילים" וגם על ReverseKey Indexes אבל אפילו לא הזכרתי את שאר הסוגים של האינדקסים: Bitmap, Function based וכו'. לירון אמיצי כתב סדרת מאמרים על אינדקסים ואיך הם עובדים – שווה ללכת ולקרוא אותם אם הנושא מעניין אתכם (וגם יש ציורים שאני התעצלתי להכין… 🙂 )
נושא חשוב ומעניין מאוד!