מערכות נתונים - טכנולוגיות ואלגוריתמים

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

שלבי עיבוד שאילתה

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

שלבים מרכזיים בתהליך:

ניתוח (Parsing): השאילתה נבדקת תחבירית ולקסיקלית.
אימות (Validation): בדיקה סמנטית – האם הטבלאות, העמודות וההרשאות קיימות ותקפות.
אופטימיזציה לוגית (Logical Optimization): שינוי עץ השאילתה ללא שינוי התוצאה, אך באופן שעשוי לשפר את הביצועים. לדוגמה, דחיפת סלקציות מוקדם ככל האפשר.
אופטימיזציה פיזית (Physical Optimization): בחירת אלגוריתמי ביצוע ספציפיים (לדוגמה, איזה אלגוריתם Join להשתמש) ובחירת נתיבי גישה (לדוגמה, האם להשתמש באינדקס).
יצירת תוכנית ביצוע (Execution Plan Generation): בניית עץ אופרטורים קונקרטי לביצוע.
ביצוע (Execution): הרצת תוכנית הביצוע והחזרת התוצאות.

תוכנית לוגית (Logical Plan): ייצוג של השאילתה במונחי אופרטורים של האלגברה הרלציונית, ללא התייחסות לאופן המימוש הפיזי.

תוכנית פיזית (Physical Plan): ייצוג קונקרטי של השאילתה, הכולל את בחירת אלגוריתמי הביצוע ונתיבי הגישה לנתונים.

אופטימיזציה לוגית

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

אופטימיזציה פיזית

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

תוכניות ביצוע ואופרטורים

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

אופרטורים נפוצים:

Scan (סריקה): גישה לנתונים. יכול להיות Table Scan (סריקה מלאה של טבלה) או Index Scan (שימוש באינדקס).
Select (בחירה): סינון שורות לפי תנאי מסוים.
Project (הטלה): בחירת עמודות מסוימות והסרת כפילויות (אם נדרש).
Join (צירוף): שילוב שורות משתי טבלאות או יותר על בסיס תנאי צירוף.
Sort (מיון): מיון הנתונים לפי עמודה או קבוצת עמודות.
Group By (קיבוץ): קיבוץ שורות בעלות ערכים זהים בעמודות מסוימות וביצוע פונקציות אגרגציה.

עץ ביצוע (Execution Tree): ייצוג גרפי של תוכנית הביצוע, כאשר העלים הם פעולות גישה לנתונים והצמתים הפנימיים הם אופרטורים המעבדים את הקלט מילדיהם.

אופטימיזציה מבוססת עלות

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

כיצד מחושבת עלות?

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

מודל עלות (Cost Model): קבוצת נוסחאות המשמשות להערכת העלות (לרוב I/O) של ביצוע אופרטור מסוים או תוכנית ביצוע שלמה, בהינתן סטטיסטיקות על הנתונים.

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

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

אלגוריתמים נפוצים וחישוב עלותם

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

אלגוריתמי Join עיקריים:

Nested Loop Join

עבור כל שורה בטבלה החיצונית (R), סרוק את כל השורות בטבלה הפנימית (S). פשוט ליישום אך יקר מאוד עבור טבלאות גדולות. עלות: B(R) + |R| * B(S) קריאות בלוקים.

Block Nested Loop Join

גרסה משופרת של Nested Loop. טוען בלוקים שלמים מהטבלה החיצונית לזיכרון, ועבור כל בלוק כזה, סורק את כל הטבלה הפנימית. עלות: B(R) + B(R) * B(S) / M קריאות בלוקים (כאשר M הוא מספר הבלוקים בזיכרון).

Sort-Merge Join

ממיין את שתי הטבלאות לפי עמודת ה-Join, ואז מבצע מיזוג ליניארי של הטבלאות הממוינות. יעיל מאוד אם הטבלאות כבר ממוינות או אם המיון זול. עלות: עלות מיון R + עלות מיון S + B(R) + B(S) (ללא עלות מיון אם כבר ממוין).

Hash Join

בשלב הבנייה (Build Phase), בונה טבלת גיבוב (Hash Table) בזיכרון עבור הטבלה הקטנה יותר. בשלב הבדיקה (Probe Phase), סורק את הטבלה השנייה ומשתמש בטבלת הגיבוב למציאת התאמות. יעיל מאוד עבור צירופי שוויון. עלות: B(R) + B(S) (במקרה אידיאלי שכל טבלת הגיבוב נכנסת לזיכרון).

אלגוריתמים נוספים:

External Sort: אלגוריתם מיון המיועד לנתונים שאינם נכנסים כולם לזיכרון הראשי, ומשתמש בדיסק כזיכרון עזר. עלותו מחושבת במספר שלבי המיזוג הנדרשים.
Selection Algorithms: סריקת טבלה מלאה (Table Scan) מול שימוש באינדקס (Index Scan) – עלותם תלויה בסלקטיביות התנאי ובסוג האינדקס (B+Tree, Hash Index).

שאלות לדיון

נתחו את השלבים העיקריים בעיבוד שאילתה והסבירו את ההבדל בין אופטימיזציה לוגית לפיזית. תנו דוגמה לטרנספורמציה לוגית.
הסבירו מדוע עלות I/O נחשבת לגורם המרכזי בחישוב עלות תוכניות ביצוע. באילו מקרים עלות CPU או זיכרון עשויה להיות משמעותית יותר?
השוו בין שלושה אלגוריתמי Join שונים (לדוגמה, Nested Loop, Sort-Merge, Hash Join) במונחי עלות תיאורטית, יתרונות וחסרונות. מתי תבחרו בכל אחד מהם?
כיצד סטטיסטיקות על הנתונים משפיעות על החלטות האופטימיזטור? תנו דוגמה כיצד סטטיסטיקות שגויות עלולות להוביל לתוכנית ביצוע לא יעילה.

נקודות לתשובת מודל

שלבי עיבוד: פירוט שלבי הניתוח, אימות, אופטימיזציה (לוגית ופיזית), בניית תוכנית וביצוע. הדגשת ההבדל בין שינוי מבנה לוגי לבחירת מימוש פיזי.
עלות I/O: הסבר ש-I/O הוא הפעולה האיטית ביותר במערכת, ולכן מזעור קריאות הדיסק הוא המטרה העליונה. התייחסות למקרים חריגים (למשל, חישובים מורכבים ב-CPU, זיכרון מוגבל מאוד).
השוואת Join: הצגת כל אלגוריתם עם תיאור קצר, נוסחת עלות בסיסית (B(R), B(S), M), יתרונות (למשל, Hash Join ל-equijoin, Sort-Merge למידע ממוין) וחסרונות (למשל, Nested Loop יקר מאוד).
חשיבות סטטיסטיקות: הסבר כי סטטיסטיקות מאפשרות לאופטימיזטור להעריך את גודל תוצאות הביניים ואת הסלקטיביות של תנאים, ובכך לבחור את האלגוריתם והאינדקס המתאימים. דוגמה: הערכת חסר של גודל תוצאה עלולה לגרום לבחירת אלגוריתם שדורש פחות זיכרון אך יקר יותר ב-I/O.

מצאתם טעות או שחסר משהו?