מידול הירארכיה בשיטת Nested Sets ב-SQL Server

02/01/2012

צח פניגשטיין

clip_image00612_thumb[1]

יועץ SQL בכיר, בעל 10 שנות נסיון בתחום התוכנה, ר"צ DBA בפרוייקט ממשלתי מטעם נאיה טכנולוגיות


Nested Sets היא שיטה למידול הירארכיה, השונה מהשיטה המקובלת. השיטה המקובלת למידול הירארכיה מתייחסת אל ההירארכיה כאל כעץ. ייצוג זה מכונה Adjacency List Model (ניתן לייצג בעזרתו גרפים, ולא רק עצים, אבל זה כבר דיון אחר). כל צומת בעץ (רשומה) מכילה את הנתונים הרלוונטיים לאובייקט, בתוספת מצביע לצומת אחר בעץ, שמשמש כ"אב" לצומת. הצומת העליונה ביותר בעץ מכילה הצבעה ריקה, והיא שרש העץ או הרמה הגבוהה ביותר בהירארכיה.

למשל, בדוגמה הבאה, עמודת Parent_ID מייצגת את רשומת האב ע"י ציון ערך ה-ID שלה. ברשומת המנכ"ל  (ID=1) הנמצא בראש הירארכיה עמודה זאת היא NULL.

clip_image002  image

 

בניגוד לשיטה זו, Nested Sets (NS) מייצג את ההירארכיה בעזרת קבוצות (Sets). כל צומת בהירארכיה היא קבוצה, כאשר כל קבוצה מכילה בתוכה את כל הקבוצות הכפופות לה. במקום להכיל הצבעה לרמת האב, כל רשומה מכילה שתי עמודות, L (Left)  ו-R(Right), המגדירות את גבול הקבוצה. אם קבוצה א' היא בעלת גבול שמאלי הקטן מזה של קבוצה ב' והגבול הימני של קבוצה א' גדול מזה של קבוצה ב' אזי קבוצה א' מכילה את קבוצה ב'.

דוגמה לכך בטבלה ובתרשים הבא:

clip_image005clip_image004

 

קבוצה 2 (סמנכ"ל כספים) הוא בעלת גבול שמאלי 2 וגבול ימני 5.
קבוצה 1 מכילה את קבוצה 2, מפני שהגבול השמאלי של קבוצה 1 (=1) קטן יותר מהגבול השמאלי של קבוצה 2 (=2), והגבול הימני של קבוצה 1 (=8) גדול יותר מהגבול הימני של קבוצה 2 (=5).

על פי אותו עיקרון קבוצה 2 (סמנכ"ל כספים) מכילה את קבוצה 4 (חשב).
קבוצה 3 וקבוצה 2 הן קבוצות אחיות, היות ושתיהן מוכלות על ידי קבוצה מספר 1, והן באותה הרמה.

חשוב לציין, שבמודל זה אין מימד של עומק, כמו במודל העץ, ולכן לא ניתן לדעת האם קבוצות מסוימות הן באותה הרמה או לא. מודל ה-Nested Sets מְשָטֵחַ את הרמות וממיר אותן לקבוצות.

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

לדוגמה, כדי למצוא את כל האבות של פרט 4 (חשב), יש להריץ את השאילתה הבאה:

SELECT      NS.ID, NS.Name

FROM        EmployeeTbl N

            INNER JOIN EmployeeTbl NS

                 ON NS.L < N.L AND NS.R > N.R

WHERE       N.ID = 4 חשב  

 clip_image007

 

במקרה הזה ישנן כמובן שתי סריקות. אחת כדי למצוא את גבולות L/R של פרט 4 (בתנאי ה-WHERE), וסריקה נוספת, אחת בלבד, למציאת כל האבות שלו בענף.

כלומר, תנאי ה WHERE גורם לכך שמטבלהN  חוזרת רק רשומת החשב. לרשומה הזו אנו "מצמידים" בחלק ה JOIN את כל הרשומות שהגבול השמאלי שלהן קטן מזה של הרשומה שבחרנו, וגם שהגבול הימני שלהן גדול מזה של הרשומה שבחרנו (פעולה זו יכול להתבצע בעזרת סריקה אחת של הטבלה). הרשומות שעומדות בצמד התנאים הללו הן הקבוצות המכילות את הקבוצה "חשב" (=4), ולכן הן רשומות שמבחינה הירארכית, הן עליונות (או "מכילות", אם נשתמש בטרמינולוגיה של NS) לרשומה "חשב". במקרה שלנו אלו רשומות 2 ו-1 (סמנכ"ל הכספים והמנכ"ל, בהתאמה).

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

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

1.       עדכון של המבנה ההירארכי המיוצג בעזרת מודל זה הוא תהליך מורכב. לדוגמה, אם נרצה להוסיף רמה נוספת תחת הרמה של "סמנכ"ל כ"א" (3), נאלץ לעדכן גם את הגבול הימני של כל הרשומות שמכילות את הרשומה החדשה (הרשומה תיכנס עם גבול שמאלי 7 וגבול ימני 8. ולכן יש לעדכן את הגבול הימני של רשומה 3 ל-9, ואת הגבול הימני של רשומה 1 ל-10).

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

 

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

 

הבעיה נובעת מכך שמודל NS, כפי שהוזכר, מְשָטֵחַ לחלוטין את ההירארכיה. כדי למצוא "עומק" של קבוצה צריך לספור את הקבוצות שמכילות אותו. מדובר בפעולה יקרה, במידה שמבצעים אותה על מספר רב של קבוצות. חשוב לציין שקיימת גירסה מתקדמת יותר שלNS  המכילה גם מידע לגבי עומק הקבוצה. שינוי זה מאפשר לבצע שאילתות התלויות בעומק בצורה יעילה ופשוטה.

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

Nested Sets במבחן

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

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

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

פתרון יעיל יותר, אם כי עדין רקורסיבי, יהיה למצוא את כל היחידות שיש להן הרשאה לבצע X, ולטפס מהן כלפי מעלה. בצורה זו נקבל את כל היחידות שיש להן הרשאה לבצע את פעולה X  או שהן ירשו את ההרשאה הזו מבנותיהן. וזאת השאילתה הבאה העושה שימוש ב-Common Table Expression (CTE) לאיחזור רקורסיבי:

;WITH CTE AS

(

      SELECT      ID, BaseID

      FROM        [Infrastructure].[UserMng_OrganizationUnit]

      WHERE       TypeID = 4

     

      UNION ALL

     

      SELECT      OU.ID, OU.BaseID

      FROM        [Infrastructure].[UserMng_OrganizationUnit] OU

                  INNER JOIN CTE ON OU.ID = CTE.BaseID

)

SELECT      DISTINCT ID

FROM        CTE

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

עוד על CTE ב-SQL Server ועל עקרון השימוש בו ראו בקישור זה.

נבחן את נתוני הביצוע (בעזרת STATISTICS IO וע"י הצגת Actual Execution Plan):

STATISTICS IO

Table 'Worktable'. Scan count 2, logical reads 47, physical reads 0, . . . .

Table 'UserMng_OrganizationUnit'. Scan count 1, logical reads 17, physical reads 0, . . .

במקרה זה ישנן 3 גישות (scan count) לטבלאות שונות: worktable (טבלה זמנית פנימית) וטבלת המקור, וכן 64 קריאות של דפים בסה"כ (logical reads).

Actual Execution Plan

image

פתרון זה הרבה יותר יעיל מהפתרון הקודם (של ירידה מלמעלה), אך גם הוא אינו זול במיוחד, מאחר שאנו מחזירים כפילויות רבות. שימו לב גם למספר הפעמים שבהן נגענו בטבלה (Number Of Execution = 8).

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

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

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

SELECT  OU.ID

FROM    [Infrastructure].[UserMng_OrganizationUnit] OU

        INNER JOIN [Infrastructure].[UserMng_OrganizationUnit] nsOU

                  ON OU.NestedSetsL <= nsOU.NestedSetsL

                    AND OU.NestedSetsR >= nsOU.NestedSetsR           

WHERE   nsOU.TypeiD = 4

נבחן גם כאן את נתוני הביצוע:

STATISTICS IO

Table 'UserMng_OrganizationUnit'. Scan count 3, logical reads 6, physical reads 0, . . .

ניתן לראות שבסה"כ ביצענו אותו מספר של גישות לטבלה (scan count= 3), אך פחות מ-10% ממספר הקריאות  (logical reads): 6 לעומת 64 במקרה הקודם.

 Actual Execution Plan

image

שימו לב לפשטות תוכנית הביצוע. עלות התוכנית הזו היא כ-25% מעלות השאילתה הרקורסיבית.

השפעה כללית

לצורך השוואה ובדיקות, שוכתבה הפרוצדורה המרכזית שפונה לטבלת היחידות האירגוניות. ובוצעו 3 הרצות לצמד הפרוצדורות (GetUsers2 משתמשת בעמודות ה-Nested Sets לצורך החיפוש), ובכל הרצה, הועברה קבוצה פרמטרים אופיינית אחרת:

image

קל לראות ש- GetUsers2המשתמשת במידול Nested Sets מציגה באופן משמעותי ביצועים טובים יותר.

סיכום

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

קריאה נוספת

הסברים נוספים, הוראות מימוש ואלגוריתם לעדכון עמודות ה-NS , ניתן למצוא בקישור הבא:

http://www.codeproject.com/KB/database/nestedsets.aspx

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

להגיב על ליאור קינג לבטל

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

3 תגובות

  1. גרי רשף05/01/2012 ב 20:30

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

    יצא לך לכתוב גם על איך מעדכנים?
    זו באמת בעייה..

    הגב
  2. צח פניגשטיין06/01/2012 ב 20:15

    היי גרי,
    אני שמח שנהנת מהקריאה.
    כפי שציינת, עדכון הגבולות של הסטים יכולה להתגלות כבעיה רצינית.
    ניסיתי כל מיני שיטות לעדכון (פרוצדורות רקורסיביות, עדכונים חלקיים ע"פ נקודת הכניסה לעדכון ועוד).
    אחרי כל הנסיונות, גיליתי שהדרך היעילה ביותר היא פשוט לעדכן את כל העץ, בעזרת האלגוריתם שמפורט בפוסט תחת "קריאה נוספת".
    העדכון על טבלה כ"כ קטנה אורך כ-200 מילישניות. מדובר בטבלה סטטית כמעט לחלוטין, כך שאין לי בעיה לשלם את המחיר של עדכון כל העץ בכל פעם שמעדכנים את הטבלה (להערכתי יעדכנו אותה פעם בשנה-שנתיים… אולי…)
    חשוב לציין שניסיתי להשתמש ב-NS גם בטבלה גדולה יחסית. הטבלה המדוברת מכילה שלושה עצים, כאשר כל עץ מכיל כ-12K רשומות.
    במקרה הזה עדכון של כל העצים לקח כשלוש דקות(!), וההשטחה בעזרת מודל ה-NS לא הפגינה ביצועים עדיפים על hierarcyid או Path Enumeration.

    הגב
  3. ליאור קינג29/02/2012 ב 19:09

    אכן שיטה מוכרת ומומלצת לשאילתות מסוג "מי כל ה-nodes מעל node כלשהו בעץ" וכן "מי כל ה-nodes מתחת node כלשהו"
    מומלץ להוסיף לזה גם עמודת level שתכיל את הרמה בעץ של כל node בנוסף לעמודות L ו-R.
    זה יאפשר להאיץ שאילתות כמו למשל "מי הנכדים של node מסויים". במקרה כזה אפשר להוסיף תנאי השוואה בין ערכי ה-level של nodes בעץ.
    חשוב כמובן לשמור במקביל גם המבנה ההיררכי הקלאסי (לצד עמודות L R ו-LEVEL) כדי לכסות שאילתות של traversing סטנדרטי על העץ מ-subnode משתנה.

    הגב