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

26/05/2010

CTE רקורסיבי

Filed under: Uncategorized — תגיות: , , , , — גרי רשף @ 13:10

CTE = Common Table Expression הוצג ב-SQL Server 2005, ומדובר בסינטקס שמאפשר ליצור אובייקטים אד-הוק במהלך השליפה;
וזו חלופה מתאימה לשאילתות משנה.
ל-מ-ש-ל: אנחנו רוצים לשלוף את שמות הטבלאות בעלות השם הכי ארוך. לכאורה ניתן לשלוף את ((Max(Len(name מתוך sys.tables, אבל אם יש מספר טבלאות בעלות אותו אורך מקסימלי- נקבל רק אחת.
ניתן, איפוא, להיעזר בשליפה משנית כך:

Select    *

From    (Select    Max(Len(name)) Over() Oreh,

                *

        From    sys.objects) T

Where    Len(name)=Oreh;

לחילופין ניתן להיעזר ב-CTE כך:

With T As

(Select    Max(Len(name)) Over() Oreh,

        *

From    sys.objects)

Select    *

From    T

Where    Len(name)=Oreh;

הסבר: מגדירים אובייקט בשם T ולאחר מכן שולפים ממנו את מה שמתאים.

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

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

לא ניתן לקנן ביטויי CTE זה בתוך זה, אך ניתן לשרשר אותם, בערך כך:

With T1 As

(Select    ..

From    ..

Where    ..),

T2 As

(Select    ..

From    ..

Where    ..)

Select    ..

From    T1

Inner Join T2

    On ..;

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

יש להדגיש ש-T1 ו-T2 הנ"ל קיימים רק במהלך השליפה, ולאחר מכן כבר לא.

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

With T As

(Select    1 N

Union All

Select    N+1

From    T

Where    N<100)

Select    *

From    T

Option (MaxRecursion 0);

כפי שאפשר לראות- האובייקט T כולל שתי שליפות המשורשרות בעזרת Union All.

הראשונה היא העוגן (Anchor) וכוללת רק את המספר 1,

והשניה היא הזנב (Tail) והיא שולפת מתוך T – האובייקט בתוכו היא נמצאת – את N+1 כל עוד הוא קטן מ-100.

שורת הסיום (Option (MaxRecursion נועדה לשליפות שרמת הרקורסיה בהן גדולה מ-100 (ברירת המחדל המקסימלית).

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

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

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

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

למשל, אם נרצה לשרשר את שמות האובייקטים בטבלת המערכת sys.objects, נוכל לעשות זאת כך:

With T As

(Select Row_Number() Over(Order By name) Mispar,

        name

From    sys.objects),

Tbl As

(Select    1 N,

        Cast(name As Varchar(Max)) name

From    T

Where    Mispar=1

Union All

Select    N+1,

        Cast(Tbl.name+','+T.name As Varchar(Max))

From    Tbl

Inner Join T

        On Tbl.N+1=T.Mispar)

Select    *

From    Tbl;

ה"עוגן" שולף את שם האובייקט הראשון,

ובהמשך, ב"זנב", כל רשומה משרשרת את שם האובייקט למה שנצבר עד אליה.

מי שירצה לקבל רק את השורה האחרונה עם השירשור המלא- ישלוף בשורה לפני האחרונה את (Max(name במקום *.

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

יחד עם זאת, בתוך ה-CTE הרקורסיבי הרשומות מטופלות באופן סדרתי ולא ניתן להתייחס לכולן יחד כסט; ומסיבה זו לא ניתן ב"זנב" לבצע Group By על אובייקט ה-CTE בתוכו נמצאים או לפנות אליו בעזרת אופרטורים כמו In או Exists שמצריכים פנייה אל הסט כולו.

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

With T As

(Select    1 N,

        Min(1) Over() [Min]

Union All

Select    N+1,

        Min(N) Over() [Min]

From    T

Where    N<100)

Select    *

From    T

Option (MaxRecursion 0);

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

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

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

מה קורה כשל-CTE הרקורסיבי אין זנב אחד אלא זנביים?

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

נשלוף, כדוגמה, את המספרים עד 10 בעזרת "זנב" כפול:

With T As

(Select    1 N

Union All

Select    N+1

From    T

Where    N<10

Union All

Select    N+1

From    T

Where    N<10)

Select    *

From    T

Option (MaxRecursion 0);

השליפה מחזירה 1023 רשומות שלא במקרה זה שווה ל- 20+21+..+29=1-210 , כלומר- המספר 1 נוצר על ידי ה"עוגן", כל אחד מה"זנבות" יוצר את 2, כל אחד משני ה-2 הופך ל-3 על ידי כל אחד מה"זנבות" (כלומר- ארבע פעמים 3) וכך הלאה.

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

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

With T As

(Select 1 N,

        1 N1,

        1 N2,

        Cast('' As Varchar(Max)) S

Union All

Select    N+1,

        N1+1,

        N2,

        Cast(S+'('+Cast(N As VarChar)+','+Cast(N1 As VarChar)+','+Cast(N2 As VarChar)+')' As Varchar(Max)) S

From    T

Where    N1<3

Union All

Select    N+1,

        N1,

        N2+1,

        Cast(S+'('+Cast(N As VarChar)+','+Cast(N1 As VarChar)+','+Cast(N2 As VarChar)+')' As Varchar(Max)) S

From    T

Where    N2<3)

Select    *

From    T;

והפלט נראה כך:

image

ה"זנב" הראשון מגדיל את העמודה N1 ב-1 בכל פעם,

ה"זנב" השני מגדיל את העמודה N2 ב-1 בכל פעם,

ושניהם מגדילים את N ב-1 ומשרשרים ב-S את הנתיב שלהם בעץ המסתעף של התוצאות.

כך, למשל, השורה האחרונה – 19 – התחילה כמו כולם ב"עוגן" (1,1,1), המשיכה ל"זנב" הראשון (2,2,1), המשיכה שוב ל"זנב" הראשון (3,3,1), המשיכה ל"זנב" השני לאחר שתנאי ה-Where של הראשון מנע ממנה להמשיך שם (4,3,2), וסיימה ב"זנב" השני עם התוצאות 5,3,3.

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

image

חץ אדום מציין את ה"זנב" הראשון,

וחץ כחול את ה"זנב" השני.

האלגוריתם יוצר אם כך את הרשומה הראשונה ב"זנב" הראשון, לאחר מכן פונה ל"זנב" השני ופורש שם את העץ כולו, ולבסוף חוזר ל"זנב" הראשון ומשלים שם את המלאכה;

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

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

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s

בלוג בוורדפרס.קום.

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