הבלוג של גרי רשף

29/11/2010

אינדקסים וספריית אוניברסיטת חיפה

בדרך כלל כשאני מתבקש להסביר מהו אינדקס, אילו סוגי אינדקסים קיימים, למה הם משמשים ואילו אופציות קיימות בהם- אני פותח ב-"שערו נא בנפשכם ש.." ואז ממשיל את הטבלה לספריה או אולי לספר טלפונים או אפילו לתוכן עניינים של ספר או רשימת קניות התלויה על המקרר; והמאזין בטוח שהעגבניות ברשימת הקניות הן Clusterd Index, הספרנית הממושקפת מהספריה היא הסטטיסטיקה, ו-"כהן אבי" מספר הטלפונים הוא Index Scan.. בקיצור- לך תסביר מה המשל ומה הנמשל!

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

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

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

קל להבין מכך ש-Clustered Index יש רק אחד, מכיוון שאת הספרים ניתן היה לסדר בצורה אחת ולא בכמה אופנים בו זמנית.

מדי פעם מדגישים המדקדקים ש-Clustered Index אינו סידור פיזי במשמעותו הפשטנית מכיוון שהשורות בטבלה אינן נשמרות על הדיסק בצורה של טבלה בשורות ועמודות אלא ב-Extents וב-Pages, וגם הספרים בספריה מסודרים בארונות שלכל אחד מספר מקטעים אנכיים שבכל אחד מספר מדפים, אבל התיאור באופן כללי נכון.

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

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

אם לשם שינוי היינו מחפשים את כל הספרים של מאיר שלו (בספריית האוניברסיטה או בטבלה עם ה-Clustered Index)- היינו מבצעים Seek למקום בו מאיר שלו מתחיל, ומשם מבצעים Scan – סורקים – ומוצאים את כל מה שהוא כתב.

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

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

הכרטיסיה הידנית נמשלה לאינדקס שנבנה על הטבלה, ובניגוד ל-Clusterd Index שהוא הטבלה עצמה ולא אובייקט נפרד – הכרטיסיה היא כן אובייקט נפרד, ופעולת החיפוש שביצענו אנאלוגית לפעולת Index Seek (חיפוש באינדקס) ו-Look Up (פניה לטבלה עצמה או ל-Clustered Index עצמו למציאת השורה שאליה האינדקס מצביע).

מה היה קורא לו חיפשנו את כל הספרים המתחילים באות ה' (כולל לגשת לספר הפיזי על המדף)? לכאורה כמו בדוגמה הנ"ל עם הנסיך: ניגש לכרטיסיה, נמצא את תחילת האות ה', ונבצע Index Scan ו-LookUp; אלא שזה נראה מאוד לא יעיל: אחוז משמעותי מרבבות הכרכים בספריה שמם מתחיל באות ה', וכנראה שהיה יעיל יותר לוותר על האינדקס ולבצע Clustered Index Scan על כל המדפים של הספריה.. נכון- גם זו משימה קשה, אבל לא נצטרך לרוץ הלוך ושוב מהכרטיסיה למדפים ולהיפך אינספור פעמים.

ההחלטה שלנו במקרה זה התבססה על השכל הישר והנסיון שלנו, ואילו בדטבייס- ההחלטה לבצע Clusterd Index Scan במקום Index Seek ו-Look Up תתבסס על הסטטיסטיקה שמייצגת את הנסיון של המערכת והידע הסטטיסטי שהיא צברה.

אפשר "להכריח" את המערכת להשתמש באינדקס גם אם לפי שיקול דעתה הוא מיותר וזאת בעזרת Hints מתאימים בפקודת ה-Select, אולם ברוב המקרים זה רק יפגע בביצועים.

בכרטיסיה לא היה כתוב רק שם הספר ומיקומו הפיזי בספריה, אלא גם פרטים כמו שם המחבר, המתרגם, שנת ההוצאה, מספר העמודים, מהדורה וכו'; ולכן היא לא הייתה סתם אינדקס אלא Covered Index, כלומר- אינדקס שכולל (Include) פרטים חשובים נוספים וכך ניתן להימנע מלגשת למדף ולבצע Look Up ולהסתפק ב-Index Seek, אלא אם כן נדרשנו למצוא מידע שאינו בכרטיסיה (למשל- משפט הפתיחה של כל ספר)

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

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

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

במקום העבודה – למשל – אני מחזיק מספר ספרי מחשב פרטיים על המדף, בערך עשרה ספרים. הספרים אינם מסודרים בצורה הגיונית, והדבר כלל אינו מפריע לי מכיוון שלאתר ספר אחד מתוך עשרה זו משימה קלה למדי, ולשם כך אינני צריך שהם יהיו מסודרים בסדר אלפא-ביתי. אני מתאר לעצמי שגם אם הייתה לי טבלה בת עשר שורות שאינה קשורה לאף טבלה אחרת ביחסי גומלין מסוג 1:N – לא היה טעם לאנדקס אותה, והמערכת הייתה מצליחה לבצע עליה פעולות DML בזריזות ללא אינדקסים.

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

זאת ועוד- מי מבטיח שכשיצא ספר חדש למאיר שלו יהיה לו מקום על המדף? כנראה שלא תיווצר בעייה כזו והספרנים הרואים את הנולד הניחו את הספרים כך שנותר מקום פנוי בכל מדף. בטבלה עם Clustered Index – יש להגדיר מראש Fill Factor שקובע כמה מקום פנוי באחוזים להשאיר עבור שורות שיתווספו בעתיד, כי אם לא יהיה מקום פנוי או אם הוא יגמר- במקרה של הטבלה זה יגרום לפרגמנטציה, הטבלה תהיה לא רציפה פיזית, וקטעים שונים ישמרו במקומות שונים. בספריה של האוניברסיטה לא כל כך סביר שנמצא פתק בסגנון "בשל היעדר מקום – ספרו החדש של מאיר שלו מאוחסן בארון X מדף Y", והספרנים יצטרכו לארגן את המדפים מחדש.

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

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

במונחי הדטבייס הרלציוני היינו קוראים לזה Filtered Index, כלומר- אינדקס שנוצר רק על חלק מהשורות בטבלה ולא על כולן.

למען הדיוק יש לציין שגם ה-Clustered Index של הספריה היה בעצם Filtered מכיוון ששיטת הסידור לפי שם מחבר ושם ספר הייתה נכונה רק לספרי קריאה ולא לספרים מקצועיים כדוגמת ספרי מחשבים, ספרי לימוד וכו', שהיו מסודרים לפי נושאים ותת נושאים.

ב-SQL Server לא ניתן ליצור Filtered Clustered Index, וכשחושבים על זה מבינים שזה בעייתי ואולי מופרך לוגית.

מודעות פרסומת

2 תגובות »

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

    תגובה של roni — 29/11/2010 @ 16:45


RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: