תגית: Performance

Microbenchmarking 101

ספריית Jackson היא ספריה פופולרית בעולם ה JVM ליצירה / פענוח של JSON (וגם XML) – פעולה חשובה ושימושית.

במדריך הביצועים של הספרייה מצוין בכלל מספר 1:
בגלל שמדובר בכלל הראשון ברשימה, אני מניח שהוא חשוב – ומתחיל לבצע reuse בקוד ל ObjectMapper, כפי שהמליצו.
  • עד כמה זה חשוב? עד כמה זה משמעותי?
  • האם עלי להימנע לגמרי מיצירה של מופעים ב ObjectMapper באותה המחלקה?
  • האם כדאי ללכת צעד אחד הלאה, ולשתף את המופע בין מחלקות שונות ?(כאן נוספת תלות בין מחלקות – מחיר לאיכות הקוד שאעדיף מאוד שלא לשלם)
טוב… ברוכים הבאים לעולם המתעתע והחמקמק של microbenchmarks (לצורף הפוסט: מדידונים).

  • כאשר אנחנו רוצים למדוד ביצועים של מערכת / מודול / ספריה – אנו עושים בדיקת ביצועים.
  • כאשר אנחנו רוצים למדוד ביצועים של פעולה קטנה / נקודתית – אנו משתמשים במדידון.

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

אז איך בונים מבחני-ביצועים טובים ויעילים, או במקרה שלנו: מדידונים טובים ויעילים לסביבת ה JVM?

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

העצה הזו היא טובה – אך לא שימושית ל 99% ויותר מהאוכלוסייה.
עוד עצה טובה ומקובלת היא לבחון את ה Byte Code שהופק מהמדידון – גם עליה כ 98% מהאוכלוסייה תוותר.

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

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

מדידון – הבסיס

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

מדידון לא-מושלם מאחד הפוסטים האחרונים. כבר במעבר ראשון עולות כמה נקודות לשיפור.
  1. לעבוד עם כמות גדולה של איטרציות, על מנת לקבל תוצאה חזקה יותר סטטיסטית ולבטל במידת האפשר רעשי-מדידה.
    1. למשל: שעון החומרה המספק את הזמן, והבאת הערך ממנו, יכולה לספק טעות מסויימת. מקרה נדיר אך אפשרי הוא NTP שפועל תוך כדי המדידה ומשנה את השעון בעשרות מילי-שניות, ויותר.
    2. כלל האצבע הוא להריץ בדיקה שתארוך כמה שניות לפחות – על מנת לבטל טעויות שעון בבטחה.
  2. כל פעולה שאיננה קשורה לבדיקה, למשל אתחולים או הכנת נתונים – יש להכין לפני.
    1. נקודה לשיפור בדוגמה: גם את היצירה של a,b ו map – היה כדאי לייצר מחוץ למדידה.
  3. לרוץ על הנתונים לפחות פעם אחת על מנת “לחמם” caches. בשפה כמו C – מעבר פשוט על המערך הוא מספיק. בשפת JVM זה לא מספיק, ויש שתי “תקלות” בחימום הזה:
    1. נקודה חשובה לשיפור בדוגמה: להריץ יותר מפעם אחת, ולהריץ את הקוד המלא בכל המסלולים האפשריים – על מנת לתת ל JVM לבצע אופטימיזציות לפני שאנו מתחילים למדוד. אוי.
    2. נקודה חשובה לשיפור בדוגמה: אין קריאה של הנתונים מחוץ ללולאה, וה compiler עלול להסיר את הלולאה הזו לגמרי מהקוד (כי אין לה השפעה על כלל המערכת). אאוץ.
  4. למדוד את זמן הריצה: mesureTimeMillis היא פונקציה פשוטה בקוטלין שמקבלת למבדה, לוקחת שעות לפני, מריצה, אחרי – ומחזירה את ההפרש בין השעונים.
    1. נקודה קטנה לשיפור בדוגמה: למרות ששימוש ב ()System.currentTimeMillis נשמע מספיק טוב, עדיף להשתמש ב ()System.nanoTime.
      Milis – מתאימה לזמן השעון, פחות מדויקת, וזמן השעון עלול להשתנות בזמן הריצה (למשל NTP).
      nano – לא באמת מחזירה רזולוציה של nanos (תלוי בחומרה + זה רק ה scale של המספר), ולא מבטיחה שאכן מדובר בשעה המדויקת (לכן חסרה את המילה current). בכל זאת: יותר מדויקת, ומתאימה יותר למדידות ביצועים.
      אם אתם מתעניינים – הנה נתונים נוספים.
  5. לצמצם את ה overhead של האיטרציה במידת האפשר.
    1. נקודה קטנה לשיפור בדוגמה: היה עדיף לרוץ ב index-based for loop, היעילה יותר מעבודה עם iterator.
    2. ספציפית בקוטלין איטרציה על Range או מערך דווקא כן מתרגמת ל index-based loop. במקרה שלנו מדובר ב collection.
  6. להריץ את כל ה benchmark כמה פעמים. כפי שניתן לראות מה comments, הייתה שונות בין של עשרות אחוזים כבר בין כמה הרצות בודדות.
סה”כ זהו מדידון בינוני מבחינת דיוק. על כן צוין בכתבה המקורית:

ניתן היה לכתוב מדידון נכון יותר.

הסכנות שבמדידון על גבי ה JVM

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

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

סביבת ה JVM היא סביבה קשה במיוחד עבור מדידונים.

הנה דוגמאות עיקריות לבעיות, וכיצד ניתן להתמודד עימן:

  • ה JVM יראה את אופן ריצת הקוד ויבצע שיפורים והתאמות (deoptimization, recompilation effects, וכו’) תוך כדי ריצה.
    mitigation: הרצת המדידה עצמה, בשלב ה warmup – על מנת שה JIT יעשה את השיפורים שם ולא בזמן המדידה. כלל האצבע: לעשות כמה עשרות אלפי איטרציות (כלומר: בלולאה) בשלב החימום. כל מסלול קוד אפשרי – צריך להתבצע עוד בשלב החימום.
    שווה גם להשתמש ב XX:+AggressiveOpts- על מנת שהאופטימיזציות יקרו מהר. אתם ממש תראו איך בכמה cycles של ה warmup יש שיפור – ואז יציבות. (ואם לא – הגדילו את ה warmups).
  • עשויות להתבצע פעולות קומפילציה ו/או GC בזמן הרצת המדידון – פעולות שישבשו את התוצאות.
    mitigation השתמשו ב XX:+PrintCompilation- ו verbose:gc- + הדפסה לפני ואחרי המדידה, על מנת שאם זה קרה זה יודפס בזמן ההרצה ותדאו להתעלם מהתוצאות.

    • כמובן שאתם יודעים שהדפסה בפעם הראשונה בתהליך JVM אחראי לחלק מהתאחולים במערכת – וחשוב שהדפסה ראשונה תהיה בשלב החימום.
  • חשוב לרוץ על סביבה נקיה, בה ה JVM “שקט” ככל האפשר.
    mitigation: נסו שהמדידון יהיה ה JVM היחידי, השתמשו ב Xbatch- על מנת שהקומפילציה תפעל רק לפני ההרצה, ו -XX:CICompilerCount=1 שלא יפעל במקביל, דאגו של JVM יש מספיק זכרון ושלא יהיה עליו להקצות בזמן הבדיקה. (Xmx==Mxs). מומלץ גם לקרוא ל ()System.gc בין הבדיקות. יש גם גישה שאומרת: הפעילו JVM חדש בכל הרצת בדיקה.
  • ישנן אופטימיזציות רבות על לולאות, למשל: hoisting של קוד מתוך הלולאה על מנת להפחית את ה overhead שלה. במקרים מסוימים פי 10 הרצות – יגרמו לאופטימיזציה לפעול, ולקוד לרוץ יותר מהר.
    mitigation: להריץ הרבה מאוד איטרציות בדי להנות מכל אופטימיזציה אפשרית. הרבה יותר קשה: לא להשתמש בלולאות של השפה, אלא לקרוא לפונקציה ב reflection ולמדוד את ההרצה בניקוי זמן הקריאה לפונקציה. בעיקרון קריאה לפונקציה, למרות התקורה הגבוהה יותר, נחשבת הדרך המדוייקת יותר לביצוע בדיקות. הנה דוגמה למקרה בו המעבר לפונקציה הפך בדיקה מחסרת חשיבות (אותה תוצאה להרצה ריקה מול הרצת לוגיקה) – למשמעותית.
  • Dead Code elimination: קוד שלא באמת בשימוש, ואין לו השפעה חיצונית – יבוטל ע”י אופטימיזציות של ה JVM.
    mitigation: חשוב שכל משתנה ששמנו בו ערך, יקרא לפחות פעם אחת – אחרת הקומפיילר עשוי “לסלק” את כל הקוד שרק מבצע השמה.
  • Constant Folding optimization – אם המעבד חישוב המבוסס על ערכים שלא משתנים, הוא יכול לשמור את תוצאות החישוב ולהשתמש בה שוב. האופטימיזציה הזו תקרה כאשר קוראים לאותו קוד שוב ושוב, ופחות בתסריט אמיתי ומורכב.
    mitigation: לא קל. עלינו לבלבל את ה JVM שלא יוכל לעשות את האופטימיזציה הזו…
  • אם הקוד צפוי, יהיו אופטימזציות אחרות של ה JVM ושל המעבד, שינצלו pipelining ארוך ו branch prediction.
    mitigation: דורשת מומחיות ברמת ה JVM… אין פתרון קל.
בקיצור: אם אתם לא מחליפים מקצוע למומחי בדיקות-ביצועים, אבל עדיין רוצים להריץ פה ושם מדידונים, מומלץ:
  • להתייחס בזהירות לתוצאות של מדידונים.
    • להסתמך בעיקר על מגמות (“x מהיר משמעותית מ y” או “x מהיר רק מעט יותר מ y”) – ולא על מספרים מדויקים (“x מהיר ב 10ns” או “x מהיר ב 10%”, הן מסקנות לא חזקות לניבוי תוצאות בהרצה בסביבה אפילו מעט שונה).
    • לזכור שהתוצאות הן לחומרה ספציפית, מערכת הפעלה ספציפית, וגרסת תוכנה ספציפית (כל הרכיבים השונים). לא בהכרח התוצאות יתורגמו בצורה טובה למערכות אחרות.
    • להיות תמיד פתוחים לכך שהמדידון בעצם איננו מתאר את המצב במדיוק, ויש לשקול שנית את המסקנות (בעיקר כאשר ההבדלים בין ההרצות אינם שונים בסדר גודל).
  • להשתמש ב Framework שיגן עליכם בפני חלק גדול מהטעויות וההטיות האפשריות. ספיציפית: jmh.
    • jmh מסייע להתמודד עם כל הבעיות המסומנות בירוק למעלה. חלקן דורשות מעט חשיבה והתייחסות בקוד – אבל זה עולם אחר לגמרי מלנסות להתמודד איתן לבד.
    • יש גם את Caliper, אבל הוא נחשב פחות מדויק. הנה הסבר מפורט מדוע.

חזרה לשאלה המקורית: כמה “יקר“ ליצור מופע של ObjectMapper בכל שימוש?

הכל התחיל מכך שרצינו לדעת כמה משמעותי הוא לעשות caching למופע של ObjectMapper מול יצירה של מופע עבור כל פעולת de/)serialization). כפי שאמרנו, בדיקה מספרית היא לא מדוייקת ולא נכון להשתמש בנתון המספרי כמדויק. למשל: “יצירה של מופע ObjectMapper אורך כ 10 מיקרו-שניות”

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

אם יצירה של מופע ObjectMapper אורכת כ 10 מילי-שניות (פלוס מינוס), אזי ברור לי שכדאי לצמצם מופעים באותו סדר גודל של דחיפות של צמצום פעולות לבסיס הנתונים – וזו כנראה תהיה עבודה קלה הרבה יותר.

בואו נצא לדרך:

  1. המפתח לשימוש ב jmh הוא ה Annotation בשם Benchmark@. הוא יגרום ל jmh לג’נרט את קוד הבדיקה בצורה “בטוחה מהטיות”, במידת האפשר.
    פעם אחת (newMapper) אני בודק יצירה של mapper ושימוש בו.
    בפעם אחרת (reuseMapper) שימוש-חוזר ב mapper ואז שימוש בו.
    השתמשתי בפונקציה בשם ()improvedJsonMapper בה אנחנו משתמשים ליצור ObjectMapper ולהגדיר עליו כמה מודולים והגדרות נוסופות. אם כבר – אז כבר.

    1. שימו לב לאובייקט Blackhole, המוזר לכאורה. הוא מסייע לי לבטל אופטימיזציות של Dead code elimination שהזכרנו למעלה, ותפקידו הוא לא-לספק ל JIT שום מידע האם בערך שהועבר אליו נעשה שימוש.
    2. אני מנסה לתת הקשר יותר הגיוני לבדיקה, ולא רק לייצר מופע ל ObjectMapper. כל מופע דורש שימוש. אם השימוש היה יקר בסדרי גודל מהיצירה – לא משנה לי כמה היצירה היא יקרה. זה יהיה “בטל בשישים”.
    3. יצרתי שימוש קטן (tiny) ושימוש קטן (small). ראיתי בינהם הבדל לא מוסבר תוצאות (עוד בהמשך), ולכן הוספתי מקרה עם הרבה נתונים (large).
      מבחני-ביצועים הם, בפוטנציה – מחקר בלתי-נגמר.
      דיונים בתוצאות מבחני-ביצועים – עלולים להיגרר לדיון בלתי-נגמר.
      לכן, כדאי לזכור מה רוצים להשיג – ולשים גבולות לזמן המושקע.
  2. אנחנו מעבירים גם אובייקט state המגיע מבחוץ על מנת להתמודד עם אופטימיזציית Constant Folding. חשוב  שכל הפרמטרים שבשימש יועברו מבחוץ ובאופן זהה. למשל: גם לבדיקה newMapper העברתי את ה mapper הגלובאלי שנוצר – על מנת “ליישר קו”.
    1. בחרתי ב scope גלובאלי (Benchmark) כי אין פה נושא של מקביליות. שימוש ב scope של thread יצר שונות גדולה יותר בתוצאות הבדיקות, כנראה בגלל אתחולים נוספים של ה state.
    2. Params@ הם המקבילים ב Parameterized Tests של JUnit – לכל ערך תרוץ איטרציה נפרדת של הבדיקה עם הערך הנתון. הפרמטרים תמיד יוגדרו כמחרוזות, אך יומרו לטיפוס של השדה.
      שמות משמעותיים – עוזרים לעקוב ולהבין את התוצאות.
    3. את אתחול ה state מומלץ לעשות במתודת Setup@ – המובטח שתקרא מחוץ ל scope של המדידות.
      ישנן שלוש רמות של הרצה:

      1. trial – כל ההרצות של Benchmark@ לפי Param@ (הרמה הגבוהה ביותר).
      2. iteration – כל הפעלה של warm-up או מדידה אמיתית בתוך ה trial
      3. invocation – הקריאה הבודדת לקוד שב Benchmark@
  3. בצל התוצאות המעט מוזרות, וגם כדי להראות שימוש ביכולת ה TearDown – רציתי לוודא שהבדיקה רצה כפי שהתווכנתי. מה יותר טבעי מהדפסה?
    בכדי לא להפריע, את ההדפסה עושים מחוץ לזמן הבדיקות. הנתונים אכן כפי שציפיתי שיהיו.
  4. כמה הגדרות אחרונות ששוה להזכיר:
    1. אני רוצה למדוד זמן ריצה ממוצע. גישה אחרת היא למדוד Throughput, ויש גם אפשרויות נוספות.
    2. בקלט של הבדיקה נוח לעבוד עם מידת זמן בסדר גודל רלוונטי. במקרה שלנו : מיקרו-שניות.
    3. ה hint ל JIT מבקש ממנו לא לעשות inline לקוד. הוא לא נדרש בבדיקה הזו ספציפית – אך זה הרגל טוב.
    4. שימו לב שה class צריך להיות פתוח (ברירת המחדל ב Java) – על מנת שה generated code יוכל לרשת ממנו.
והנה התוצאה:

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

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

אתמקד בצורך שהביא אותי לכאן: האם / באיזו מידה אני רוצה לעשות שימוש חוזר ב ObjectMapper?
אני יכול להגיע כבר להחלטה שאני מרגיש נוח איתה:

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

את הקוד של ה benchmark, כולל הגדרות maven שלקח לי קצת זמן להגיע אליהן בכדי להריץ את הקוד בקוטלין ניתן למצוא ב github.
ב repository גם תמצאו קובץ shell script שבו אני משתמש להרצה, עם הגדרות ברירת-מחדל שאני מאמין שהן טובות למדי.
שווה לציין שיש plugin ל IntelliJ ל jmh, אבל הוא לא עובד עם קוטלין, ובכלל – אני מאמין שנכון וטוב יותר להריץ את jmh מתוך java -jar.

שיהיה בהצלחה!

תודה מיוחדת לחיים ידיד, מומחה ביצועים מהמעלה הראשונה, חבר, ואיש תוכנה בכלל – שנתן כמה הערות מועילות.

—-

קישורים רלוונטיים

המדריך המועדף עלי ל jmh
JVM Anatomy Park – מדריך לאופטימיזציות השונות של ה JVM
קישור למצגת מאת Aleksey Shipilёv (מומחה עולמי בתחום ה microbenchmarking) שמסבירה ומדגימה כמה בעיות אפשריות בביצוע מדידונים

מה *לא* לימדו אותנו באוניברסיטה על מבני-נתונים? חלק ב’

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

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

  • מדוע HashTable לא באמת פועל ב (Θ(1?
  • מדוע עבודה על איברים בודדים במערך ממוין – מהירה יותר מעבודה על מערך לא ממוין?
  • כיצד Regular Expressions עלולים להוסיף סיבוכיות מיותרת?
  • מהו אלגוריתם המיון היעיל והנפוץ ביותר – שאתם כנראה לא מכירים?
בואו נתחיל!
לא כל ה hashtables נולדו שווים. זמני הכנסה של מיליוני איברים.

מיתוס: HashTable מכניס ושולף איברים ב (Θ(1

בקורס מבני-נתונים כנראה ולימדו אותנו ש HashTable מכניס/מוחק/שולף איברים בזמן קבוע – ולכן ניתן להסיק שזה זמן טוב מאוד.

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

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

זמן הריצה של ה hash function איננו אפסי. פונקציית hash אורכות זמן, בד”כ כפונקציה יחסית לקלט.
אם נניח, לצורך הפשטות, שהמפתח (key) ב HashTable הוא מחרוזת, אזי יהיה נכון לומר שזמן הכנסה של איבר הוא (Θ(k כאשר הוא k תלוי באופן ישיר באורך המחרוזת. זמן הביצוע תלוי גם בפונקציית ה hash הספציפית שנבחרה, ופונקציות hash “איכותיות” המספקות פיזור קרוב יותר לאחיד – רצות לאורך זמן רב יותר.

במקרה והמפתח של ה HashTable הוא אובייקט מורכב – ייתכן וזמן הריצה יהיה משמעותי.

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

נניח ועלינו לשלוף מתוך סט של M איברים – כ m איברים. עומדות לפנינו 2 ברירות:

  • לשלוף m איברים מתוך HashTable, בזה אחר זה.
  • לסרוק את כל המערך בגודל M ולמצוא את האיברים.
    • להזכיר: ה HashTable משתמש במערך, מאחורי הקלעים.

בהסתכלות נאיבית נראה שהבחירה היא בין (Θ(M לבין (Θ(m (כאשר M > m) – בחירה קלה למדי.

בפועל הבחירה היא בין (Θ(M לבין (Θ(m*k, כאשר סביר להניח ש k (זמן הריצה של ה hash function כתלות באורך הקלט) יהיה גדול בעשרת מונים, לכל הפחות, מפעולת שליפה של איבר בודד ממערך.
בסריקה סדרתית של המערך, כפי שאנו יודעים – אנו נהנים גם Data locality של הנתונים. בלוקי-הזיכרון יובאו לזיכרון פעם אחת, וינוצלו במלואם.

אפשר לומר שאם M/m < 10 – אזי בוודאי עדיף לסרוק את המערך.
הדבר עשוי להיות נכון גם ל M/m < 100 ואולי אף יותר – יש לבדוק כל מקרה לגופו.

מכאן, כדאי לזכור:

  • כאשר יש לנו בעיות ביצועים, במיוחד בלולאה ששולפת ומכניסה ל HashTable – אל תניחו שזמן השליפה מתוך ה HashTable הוא זניח.
  • שימוש באובייקט עסקי (למשל: Customer) בתור מפתח ל HashTable עשוי להיות מיפוי עסקי מבריק.
    • כאשר חוק המספרים הקטנים פועל – אין בעיה.
    • כאשר אנו נדרשים לספק ביצועים גבוהים על כמויות גדולות של נתונים – אובייקט גדול כמפתח עשוי להיות רעה חולה.
  • שווה גם להזכיר את העניין הידוע בג’אווה שאם אתם דורסים את מתודת ()equals עליכם לדרוס גם את ()hashCode, וליהפך.
Benchmark פשוט שהרצתי כמה פעמים בכדי להראות שהכנסה ל HashTable היא לא כמו הכנסה ל ArrayList. להמחשה בלבד.

חזרה ל Data Locality

נושא מרכזי שעסקתי בו בפוסט הקודם היה Data Locality: איזו יתרון יש, בארכיטקטורת מחשבים בת-זמננו, לגישה לזיכרון רציף כך שהנתונים יוגשו מה Caches הקרובים ביותר (L1>L2>L3). אנו רוצים לצמצם ככל האפשר גישות לזיכרון הראשי או (חס וחלילה!) לדיסק.

כ 85% משטח ה CPU המודרני מוקצה ל Caches, וכמעט כל השטח קשור באופן ישיר לאכסון או העברה יעילה של נתונים. Data Locality איננו פרט שולי – אלא עקרון מרכזי בארכיטקטורה של מעבדים מודרנים.

הנה הרצאה של Herb Sutter (מחבר סדרת הספרים ++Exceptional C) בנושא.
עוד מקור מוצלח הוא המצגת Pitfalls of OO Programming – המיועדת במקור למפתחי מנועי משחקי-מחשב, היכן שהשיקולים הללו הם מלאכה יום-יומית.

החשיבה על Data Locality איננה נכונה רק למבני-נתונים, אלא לכל רצף ארוך של פעולות שאנו מבצעים. פעולות כאלו לרוב יכללו מבני-נתונים – אך לא תמיד.

עקרון ה Locality מגיע בשני אופנים:

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

למשל: כשעוברים על מערך דו-מימדי עדיף הרבה יותר לעבור שורה-שורה (כלומר: על איברים במערך הפנימי ברצף) מאשר לעבור על הטורים ו”לקפוץ” כל פעם בין המערכים הרציפים שהוקצו.

יעילות ה cache בשני מימושים דומים. סדר הגישה העדיף כמובן תלוי במימוש הספציפי של שפת התכנות / סביבת הריצה שאנו עובדים בה.


דוגמה עדכנית נוספת יכולה להיות Streams:

  • כל הפעולות ב Stream יפעלו ברצף איבר-איבר. הדבר מאפשר מקומיות זמנית ברמה הגבוהה ביותר של caching, ב registers של המעבד (ה cache המהיר ביותר) – מה ברוב הפעמים יתרום לביצועים.
  • כאשר יש ברצף הפעולות פעולות “רוחביות” (כגון sorting) אזי דווקא עדיף להשתמש ב collection ולא ב stream – בכדי ליהנות ממקומיות מרחבית.
בשפת קוטלין ברירת המחדש היא עבודה ב collections, ועל מנת לבחור ב stream יש להשתמש ב ()asSequence.
כמובן שכל היתרונות הללו בטלים בשישים – כאשר מדובר בחוק המספרים הקטנים. כלומר: אל תחשבו עליהם אפילו – אם מדובר במאות איברים או פחות.
כאשר אנו עובדים על כמות קטנה של נתונים – הם ככל הנראה יתאימו ל cache, גם אם יוגשו מעשרות בלוקים שונים של זיכרון. הדבר כן עשוי לידי ביטוי אם אנו מבצעים את הפעולה הזו שוב ושוב – עבור נתונים שונים.

מדוע עבודה על איברים בודדים במערך ממוין – מהירה יותר מעבודה על מערך לא ממוין?

כמובן שזה לא המקרה תמיד, אבל זה בהחלט עשוי לקרות.

הביטו שניה בקוד הבא ונסו לחשוב כיצד הדבר קורה:

העניין פה הוא אופטימיזציה ברמת המעבד הנקראת Branch Prediction.

בגדול, ה CPU עובד ב pipeline ארוך של פעולות. כלומר: הפעלת רצף פעולות יעלה רק מעט יותר מהפעלה של פעולה בודדת.
כאשר יש להמתין לתשובה בבחירת הפעולה הבאה – הרצף נשבר, והיתרון בהפעלה של pipeline ״באוטומט״ – אובד.

מתי זה שימושי?
למשל כאשר יש משפטי if בולאנים ולאחריהם פעולה פשוטה. בזמן שממתינים לתוצאה של תנאי ה if – המעבד יכול לבצע כבר פעולה נוספת באותו ה pipeline.

במקרה שלנו יש Branch prediction על הפעולה : (if (data[c] >= 128.
השורה העוקבת היא פעולה פשוטה שהמעבד יכול להפעיל בזמן שהוא ממתין לתוצאת ה if. האלטרנטיבה (תחילת איטרציה חדשה) – היא כבר פעולה כבדה יותר. מכאן סביר שהמעבד יבחר בשורה העוקבת ו״ידחוף״ אותה ל pipeline.

אם הוא צדק בניחוש – הוא ייקח את תוצאת החישוב שאליה הגיע (התוצאה של הפעלת ()data[c].toLong)  – וישתמש בה.
אם טעה – לא נורא. הוא “יזרוק” את מה שהכין – וימשיך ב branch השני (במקרה הזה – קידום הלולאה). בכל מקרה הוא לא היה מסוגל לפעול מהר יותר.

כאשר המערך ממוין, ובמיוחד במקרה כמו שלנו בו יש טווח מאוד מצומצם של 256*2 ערכים אפשריים – הניחושים של ה CPU עומדים להיות טובים מאוד (אפשר לומר: על סף האופטימליים).

לכן, כאשר המערך ממוין, הטרנספורמציה ל long מתרחשת בתוך אותו ה pipeline כמעט תמיד ובעלות זניחה, בעוד כאשר המערך לא ממוין, זה יקרה רק לפעמים (כ 50% מהמקרים).
כפי שניתן לראות – הפערים בזמני הביצוע הם משמעותיים למדי (ב ++C הפערים מגיעים לכמעט פי 10).

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

מילה על Regular Expression

Regex אינם מבני-נתונים. מה הם עושים כאן בפוסט?!

הכללתי את הנושא, כי הוא כולל אלמנטים משיקים.
פגשתי לא פעם אנשי-תוכנה שהיו משוכנעים שאם הם יגדירו ביטוי כ Regex ו״יעברו שלב קומפילציה” (בניית ה matcher) – אזי מובטח להם שה Regex יהיה יעיל יותר מקוד שיכתבו.

Regex הוא בגדול כלי productivity: לכתוב ביטוי Regex ייקח, ברוב הפעמים, פחות זמן מלכתוב קוד מקביל שיבצע פעולה דומה.
זמני הריצה של ה RegEx תלויים מאוד בביטוי, כאשר ביטויים מסוימים מחושבים ב (O(1, אחרים ב (O(n, אולי (O(n^2 ועד סיבוכיות שלא ניתן לתאר. הם בהחלט לא חייבים להיות (O(n.

למשל, לפני זמן לא רב נתקלתי ב Unit Test שזמן הריצה שלו עלה מ ms בודדים – לשלוש דקות בגלל הרצה של Regex מסובך למדי.
הנה סיפור על Regex שרץ לאורך 5 יממות – והוחלף ע”י כלי אחר שעשה את העבודה ב 15 דקות (פשוט ירידה בסיבוכיות – אין כאן קסמים).

בקיצור:

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

בקצרה: מבני-נתונים ואלגוריתמים מקובלים – שכדאי להיות מודעים אליהם

מיון

שתי שפות התכנות הנפוצות ביותר בעולם כיום הן, ככל הנראה: ג’אווה ופייטון [א].

מה אלגוריתם החיפוש של הספריה הסטנדרטית שלהן?

  • QuickSort (היה נכון פעם ל ++C) – לא.    עדכון: פרמיטיביים בג’אווה ממוינים בעזרת DualPivotQuicksort. יש לו עניין של instability – אך זה לא רלוונטי לפרמיטביים.
  • MergeSort (פעם היה בג’אווה) – לא.
  • BubbleSort? – אל תהיו מצחיקים!
אז מה? איזה אלגוריתם חיפוש הוא, אחד הרצים בעולם ואחד המוכרים פחות?
TimSort!
אל תתביישו אם לא שמעתם עליו – אבל כדאי להכיר.
בתיאוריה, קיימת הוכחה מתמטית לפיה כל אלגוריתם מיון שאין לו ידע על התפלגות הקלט (למשל: רק מספרים בטווח מסוים) לא יוכל להיות יעיל יותר מ (Θ(n*lgn.
לא קל להגיע לזמן ביצוע של (Θ(n*lgn – ובד”כ זה בא במחירים אחרים. למשל: זיכרון (כמו MergeSort).
TimSort מצליח “לנצח” את התאוריה במקרים מסוימים (Best Case), ובממוצע להציג שיפור לא רע, בזכות הנחה מעניינת אך בסיסית על הפלגות הנתונים: שהיא לא אקראית לחלוטין. ככל שהיא תהיה פחות אקראית – כך הביצועים שלו יהיו טובים יותר.
TimSort (שקרוי על שם מי שפיתח אותו, טים פיטר, ממפתחי פייטון – זה לא אלגוריתם שהגיע מהאקדמיה) בבסיסו מריץ MergeSort (אלגוריתם שלרוב מבצע טוב מהרגיל) בעוד הוא משתמש ב batches קטנים ב Insertion Sort (גרסה משופרת של ה BubbleSort) – היעיל במיוחד למיון קבוצות קטנות של נתונים.
בנתונים מהעולם האמיתי המידע לא מפוזר באופן אקראי לחלוטין. בעצם: קשה מאוד לייצר נתונים אקראיים לחלוטין. בנתונים ״רגילים״ של מערכים יש בו רצפים, גדולים או קטנים, של איברים ממוינים.
TimSort פועל בגדול באופן הבא:
  1. סריקה של הנתונים ואיתור רצפים עולים ורצפים יורדים. אם הרצף יורד – הוא פשוט יהפוך אותו.
    1. הנתונים כבר ממוינים? סיימנו ב (O(n. לא נשמע חוכמה, אבל QuickSort ו MergeSort יבזבזו כאן (O(n*lgn, זה יכול להתתרגם לפי 10 או פי 100 – יותר זמן ריצה.
  2. קבוצות של עד 64 איברים – ממיינים בעזרת Insertion Sort, היעיל לקבוצות קטנות של נתונים וגם נהנה מ Data Locality.
  3. שימוש ב Merge Sort על מנת למיין את הקבוצות הממוינות – כאשר נשמר איזון בין הקבוצות בעקבות המיון המוקדם.
שווה להכיר בקיומו: KD-TreeKD-Tree הוא מבנה נתונים דיי שימושי (אני השתמשתי כמה פעמים) המאפשר לאנדקס נתונים בכמה מימדים.
בעיקרון הוא מקרה כללי של Binary Search Tree (הרץ על מימד אחד), אבל מאפשר לרוץ על כמה מימדים.
אם אנו רוצים לאנדקס 2 מימדים – אז כל שכבה זוגית תבצע חיתוך על ציר x וכל שכבה אי-זוגית על ציר y.
את אותו רעיון אפשר להרחיב ל 3, 4 מימדים ויותר.

במקרה הזה הצומת הראשי מפצל את המרחב על ציר x, ואז הקודוד מתחתיו את ציר y, וחוזר חלילה.

KD-Trees משמשים בבסיסי נתונים, ובכלל, לאינדוקס מרחבים geospatial (“גאוגרפיים”). עצי KD-Tree מסדר 2 מתארים מרחב גאוגרפי (x ו y), בעוד עד מדרגה 3 למשל, עשוי לתאר מרחב + זמן (למשל: היכן הייתה כל מונית בכל רגע נתון).

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

מבנה נתונים מקביל ל KD-Tree הוא ה R-Tree. בניגוד ל KD-Tree שבו כל node חוצה מרחב, ב R-Tree כל node מתאם מרחב תחום (Rectangle, ומכאן השם) ומכאן למרחבים שלו יכולים להיות חפיפות.

שווה להכיר בקיומו: Skip List

רשימת דילוג (Skip List) היא וריאציה של LinkedList הדומה יותר לעץ מאוזן (כמו עץ אדום-שחור או AVL) – אך המימוש שלה פשוט יותר.

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

הייחודיות של ה Skip List היא ביכולת שלו לשרת כמבנה נתונים מוצלח למדי לעבודה מקבילית – תחום שהולך והופך חשוב ושימושי עם ריבוי ה cores בתעשייה.

בבסיס, רשימת דילוג היא כמו רשימה משורשרת. התבוננו רק על הרמה הראשונה (L1) – זו ממש רשימה משורשרת.
מה הבעיה ברשימה משורשרת (מלבד עוינות ל caches)? – שמציאת איבר ברשימה אורכת (O(n וזה יכול להיות יותר מדי.

הפתרון הוא להוסיף רמות דלילות לרשימה – שיאפשרו התקדמות מהירה בעת “סריקת” הרשימה.

הנה תסריט “צמיחת הרמה השנייה”: כאשר אנו מוסיפים nodes לרשימה, אנו מבצעים הגרלה של 1:2 כמו הטלת מטבע. אם יצא “עץ” (במקור: “heads”) נוסיף node גם ברמה השניה. כך תיווצר לנו רמה שניה דלילה יותר.
באופן דומה אם יש לנו 3 רמות, node שנוסף והוגרל להיות חבר ברמה 2, יוגרל שוב ביחס 1:2 להיות חבר גם ברמה 3.

מספר הרמות ברשימת הדילוג, ייקבע ביחס למספר האיברים שבה. גם ההגרלה (״רמת הדלילות״) לא חייבת להיות 1:2. היא יכולה, למשל, להיות 1:4 – רשימה דלילה יותר.

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

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

מקביליות

מכיוון שההחלטה כמה רמות להוסיף ל node חדש היא מבוססת על אקראיות (ולא תלויה בשאר המבנה של הרשימה) ל SkipList יש יתרון בהכנסה מקבילית של איברים, שבאמת יכולות להיות פעולה מקבילית ברמה גבוהה (כלומר: לאפשר הרבה מקביליות). במימוש בג’אווה (ConcurrentSkipListMap) משתמשים ב AtomicReference על מנת להגן על הקשר לשאר הרשימה – היכן שיכול להיות race condition. מעבר לכך אין צורך בשימוש ב synchronization או מנעולים (שמגבילים מאוד את כמות המקביליות).

חשוב לציין שהמבנה הזה אינו אידאלי לכל תסריט מקבילי. בג’אווה ה ConcurrentHashMap – מימוש HashTable עם מנעולים על טווחים על המערך שמאחורי-הקלעים, אולי לא יכול לעמוד באותה כמות מקבילית של הכנסות, אך שליפה של איבר היא פעולה מהירה בהרבה (O(k (מול (O(lgn ברשימת הדילוג).
אם למשל, המקביליות היא רק בקריאה – אזי HashMap רגיל יהיה היעיל ביותר.
בקיצור: מקביליות היא עניין מורכב, ולא נכסה אותו כאן…

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

סיכום

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

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

שיהיה בהצלחה!

—–

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

ראשית הוא ממיין ע״פ סדר לקסיקוגרפי, גם מערך של מספרים:

[7, 44, 3].sort() = [3, 44, 7]
עד ממש לאחרונה, מנוע V8 הסופר-פופולארי לא היה יציב. כלומר: הוא עשוי היה, באופן אקראי, להחליף בין ערכים שהם זהים. זה לא מפריע במספרים – אך עשוי להפריע באובייקטים מורכבים.
דוגמה אחרונה, וחמורה למדי, היא זו:

בעוד מומחים בתחום טוענים בתוקף שהביצה היא זו שקדמה לתרנגולת. למשל: ביצי דינוזאור.

מה *לא* לימדו אותנו באוניברסיטה על מבני-נתונים?

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

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

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

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

הכלל הראשון שארצה להדגיש הוא זה:

כלל חשוב לחיים המקצועיים!

כדי להסביר את הכלל, אפתח בדוגמה משעשעת של אלגוריתם חיפוש בשם Sleep Sort:

ע״פ האלגוריתם הזה, יש רשימת מקור (הקלט) ורשימת יעד (התוצאה). בעת ההרצה אנו סורקים את רשימת המקור ולכל איבר מפעילים פונקציה (למשל: co-routine) שתכניס את האיבר לרשימת היעד בעוד n שניות, כאשר n הוא גודל האיבר.

אם רשימת המקור היא 2, 4, ו 3 אזי האיבר 2 יכנס לרשימת היעד לאחר שתי שניות, האיבר ארבע לאחר 4 שניות, והאיבר 3 – לאחר 3 שניות. והנה ביצענו מיון!

ע״פ גישה תאורטית פשטנית, זמן הריצה של האלגוריתם הוא (O(n – כי בחנו כל איבר רק פעם אחת. לא התייחסנו למחיר זמן ההמתנה (sleep) – מה שבעצם הופך את היוצרות.

למשל, עבור קלט של המספרים 2 ו 1,000,000,000 האלגוריתם ירוץ במשך כמעט 32 שנים – מה שבהחלט פחות יעיל אפילו מ Bubble Sort. 

מה היה לנו כאן? מחיר אמיתי מאוד, ומשמעותי מאוד, שלא לקחנו בחשבון בהערכת הזמן של האלגוריתם. יכולנו בהתאם לשכלל את התאוריה שלנו ולנסח זמן ריצה בנוסח:
(O(max(item_size) * sec) +n – כאשר בעיקרון אפשר להזניח את n.

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

  • HashTable
  • LinkedList
  • Binary Search Tree
  • Graphs

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

חוק המספרים הקטנים

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

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

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

כלומר: אם אתם עוסקים בעשרות, מאות, או אפילו אלפי איברים – סיבוכיות האלגוריתם לא ממש משנה. כל גישה בודדת לדיסק או לרשת – תעלה הרבה יותר.

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

חשוב לציין שלא כל “פקודת מחשב” מתבצעת ע”י cycle בודד של מעבד. ליהפך: תנאי if פשוט לכאורה, עלול בקלות להתתרגם לעשרות ומאות CPU cycles. כאמצעי ביטחון אפשר לחשוב על ה CPU כמבצע עשרות-מיליוני פעולות בשנייה בלבד.

“מספרים שכל מתכנת חייב להכיר” (2012). איפה הייתם בקורס מבני-נתונים?!

המחיר הנוסף

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

  • גישה לדיסק היא מאוד מאוד יקרה (לפני עידן ה SSD היא הייתה מאוד מאוד מאוד יקרה).
  • גישה לזיכרון היא יקרה, ובהחלט לא אקראית – על אף השם “Random Access Memory = RAM”.
  • נתונים, גם מהרשת, גם מהדיסק, וגם משכבות הזיכרון השונות מוגשות בבלוקים רציפים. העלות להביא את הבלוק היא החלק היקר, בעוד ההבדל בין סריקה של בית בודד או את כל הבלוק – הוא לרוב משני עד זניח.
    • אפשר לראות את ההתנהגות הזו בנתונים למעלה, כאשר קריאה של בית בודד מ SSD תיקח 0.15ms בעוד קריאה של מיליון בתים מ SSD (עשרות עד מאות בלוקים) – תיקח רק מעט יותר: כ 1.0ms.
    • שווה מאוד לקרוא ולטפל בנתונים ברציפות, ולא בסדר אקראי
  • למעבדים יש היררכיה של זיכרונות Cache. נתון שלא נמצא ב Cache יובא קודם ל L3 ואז ל L2 ואז ל L1, ולכל הבאה שכזו, יקדם חיפוש ברחבי ה Cache Level שהנתון אכן לא שם.
    • זה בזבוז להביא מילה בודדת בזיכרון, ולכן כל פעם מביאים בלוק זיכרון רציף. גודל הבלוק – תלוי בארכיטקטורת המעבד.
נתחיל בתכלס, ונראה איך זה משפיע עלינו.

קרב ראשון: Vector/ArrayList מול LinkedList

אנחנו מעונינים להוסיף דינאמית איברית לרשימה. איזה מבנה-נתונים הכי מתאים? Vector (אשתמש בשם הקדום ב ++C) או רשימה משורשרת?

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

רשימה משורשרת פשוט מוסיפה עוד ועוד ערכים במחיר (O(1 לכל פעולה.

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

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

בואו נראה מה קורה בפועל:

הממ… לא בדיוק.

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

  • כל אלמנט ברשימה המשורשרת תופס יותר זיכרון: צריך להכניס לזיכרון גם את הערך וגם את המצביע לאלמנט הבא. כנ”ל אם הערך הוא מצביע לאובייקט ולא Int. זה אותו הדבר.
  • בתאוריה: העתקה של מרחבי זיכרון רציפים היא עלות (O(n או משהו יקר אחר.
    בפועל: במעבדים מודרניים יש פקודה יעילה למדי להעתקה של בלוקים של זיכרון. זו איננה פעולה יקרה כ”כ.
  • חיפוש המקום להכנסה ברשימה משורשרת הוא הנקודה החלשה הבולטת של הרשימה המשורשרת: ה nodes של הרשימה מפוזרים אקראית במרחב הזיכרון. כשאנו סורקים את הרשימה (בממוצע n/4 איברים בכל פעם) אנחנו “חוטפים” עוד ועוד cache misses הדורשים לעדכן את זיכרון המטמון.
    • כאשר אנחנו סורקים את הוקטור, ככמט כל בלוק של זיכרון שנביא ל cache – ינוצל במלואו.
    • במקרה של שימוש ב virtual memory (לא נכלל בגרף) – המקרה גרוע הרבה יותר: ייתכן ובגלל קפיצות בין דפים שונים של ה main memory “נחטוף” Page Fault ויהיה עלינו להביא את דף הזיכרון מהדיסק, רחמנא ליצלן!

שיפור עמודות לטובת הרשימה-המשורשרת

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

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

עד כמה עומדת הרשימה המשורשרת למחוץ את הוקטור? בתיאוריה זה אמור להיות אכזרי כלפי הוקטור. בואו נראה בפועל:

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

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

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

בעולם הג’אווה – המשחק משתנה

הדוגמאות מלמעלה הן ב ++C, וכנראה מייצגות גם את מה שמתרחש ב Rust או Go. שפות שעובדות עם הזיכרון מול מערכת ההפעלה ומושפעות ישירות מארכיטקטורת המעבד.
בג’אווה (או #C) ואולי גם בפייטון / רובי – הדברים מעט שונים. יש מפרשן או JVM/CLR שנמצאים בין מערכת ההפעלה לקוד. יש שימוש מאסיבי ב Heap – שאינו רציף.
איך הדברים נראים בג’אווה? אולי שם ההבדל בין וקטור לרשימה משורשרת נמחק?
בואו נבדוק שוב את המקרה של הכנסת איבר למקום הממוין ברשימה.

אין לי גרף מתאים (הנה המקור לנתונים), אבל מאיסוף ידני של הנתונים ממבחן ב ++C, ב 20,000 איברים היו התוצאות 617 מילישניות לרשימה משורשרת, ו 234 מילישניות לוקטור – שזה יחס דומה.

ה DynamicIntArray, אם תהיתם, הוא מימוש של ArrayList המאחסן איברים מסוג int (פרמיטיב) ולא ב Integer (אובייקט) – ולכן הוא ידידותי באמת ל cache. הנתונים באמת שמורים במערך רציף (כמו ב ++C) והם לא reference לאובייקט שתלוי ב Heap (שאותו ג’אווה אכן משתדלת למלא בצורה רציפה).

המבחנים הנ”ל בוצעו על חומרה ישנה בת כמעט עשור. בואו נראה מה קורה על חומרה עדכנית:

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

את זה לא סיפרו לי בקורס מבני-נתונים!

סיכום ביניים

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

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

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

מה עושים?

במקום עצי חיפוש בינריים, משתמשים ב B-Tree. עץ חיפוש שבו כל node מותאם לגודל בלוק בדיסק (ומכאן: כמה בלוקים של זיכרון, בהתאמה). כל בלוק מכיל רשימה של מצביעים רלוונטיים. האופטימיזציה היא לצמצום הגישה לבלוקים, כך שכל פעם טוענים בלוק מהדיסק / זיכרון – מנצלים אותו ביעילות ע”י שימוש בסריקה רציפה.

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

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

פעם נתקלתי במימוש שבאמת הייתה בו חשיבות לשימוש ברשימה משורשרת. מה עשינו? הקצנו את הזיכרון עבור כל הרשימה בצורה רציפה (כמו וקטור) והשתמשנו רק בו. דבר דומה עשה חבר שדיברתי איתו – מה שגרם לי להבין שזה common sense ולא המצאה גדולה. חיפוש פשוט בגוגל העלה מימוש שכזה כקוד פתוח.
אלטרנטיבה אחרת, וקצת יותר ידועה: Unrolled Linked List.

מה עושים בגרפים? אני לא מכיר באופן אישי, אבל אני מניח שגם Neo4J או AWS Neptune מצאו את הדרך שלהם לבנות את מבנה הנתונים החשוב והנהדר הזה Graph – בצורה שאיננה עוינת לזיכרון. או לפחות: עוינת פחות ככל האפשר.

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

שיהיה בצלחה!

קישורים רלוונטיים:

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

לקחת את הביצועים ברצינות, בעזרת MySQL Performance Schema

פוסטים בסדרה:
“תסביר לי” – גרסת ה SQL
לקחת את הביצועים ברצינות, בעזרת MySQL Performance Schema
נושאים מתקדמים ב MySQL: חלק א’ – עבודה עם JSON
נושאים מתקדמים ב MySQL: חלק ב’ – json_each  ו Generated Columns

—-

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

איך יודעים אלו שאילתות רצות לאט?

הדרך הנפוצה ביותר היא בעזרת ה slow-log.

MySQL slow Query Log

  • בכדי להפעיל אותו יש לקבוע 1 בפרמטר slow_query_log. הוא ירשום כל שאילתה שארכה יותר מ 10 שניות.
  • ניתן לקבוע סף אחר בעזרת הפרמטר long_query_time, בו ניתן לקבוע גם ערכים שאינם מספרים שלמים, למשל “0.6”.
    • אם תקבעו בפרמטר ערך של 0 – סביר להניח שכתיבה ללוג תהיה החלק האטי במערכת שלכם 😀.
    • שינוי הפרמטר ישפיע רק על connections חדשים ל DB, כך שאם שיניתם את הערך ושרת סורר מחזיק חיבורים פתוחים בעזרת ה connection pool שלו, שאילתות שעמודות בסף החדש שנקבע – לא ירשמו ללוג.
  • בכדי לשלוף ערכים מה slow log פשוט בצעו שאילתה על הטבלה mysql.slow_log.
    • למשל: SELECT * FROM mysql.slow_log ORDER BY start_time DESC limit 50;
    • אני לא זוכר מה הם ערכי ברירת המחדל, ייתכן וצריך לשנות עוד קונפיגורציה בכדי שהלוג ייכתב לטבלה.

התוצאה נראית כך:

  • user_host (הסתרתי את כתובות ה IP) – עוזר להבין איזה צרכן יצר את השאילתה. זה חשוב ב DB מונולטיים – המשרתים צרכנים רבים ומגוונים.
  • lock_time (בשניות) – הזמן בו ממתינים ל”תפיסת מנעול” על מנת להתחיל ולהריץ את השאילתה. למשל: הטבלה נעולה ע”י פעולה אחרת.
  • query_time (בשניות) – זמן הריצה הכולל.
    • הרצה עוקבת של אותה שאילתה אמורה להיות מהירה יותר – כאשר הנתונים טעונים כבר ל buffer pool.
    • כמובן שגם השפעות חיצוניות שונות (שאילתות אחרות שרצות ברקע ומתחרות על משאבי ה DB Server) – ישפיעו על זמני הריצה. אני לא מכיר דרך פשוטה להוסיף מדדים כמו cpu ו/או disk_queue_depth לשאילתה, בכדי לקשר את זמני הביצוע שלה למה שהתרחש ב DB Server באותו הרגע.
  • מספר שורות שנשלח / נסרק – בשונה מפקודת ה Explain, זהו המספר בפועל ולא הערכה.
    • ייתכנו מקרים בהם Explain יעריך תוכנית אחת – אך ה slow log יראה שבוצע משהו אחר (יקר יותר) בפועל. זה עלול לקרות.
  • db – שם בסיס הנתונים (= סכמה) שבה בוצעה השאילתה.
    • למשל, אני יכול לבחור לפלטר את הסכמה של redash – כי רצות שהם הרבה שאילתות אטיות, וזה בסדר מבחינתי.

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

ה Performance Schema

אפשרות מודרנית יותר לאתר שאילתות אטיות היא על בסיס ה Performance Schema (בקיצור: ps)

מאז MySQL 5.6 ה ps מופעלת כברירת מחדל, אבל אם אתם רצים על AWS RDS – יהיה עליכם להדליק אותה ולבצע restart לשרת, לפני שתוכלו להשתמש בה.

השאילתה ה”קצרה” לשלוף נתונים של שאילתות אטיות מה ps היא:

SELECT * FROM sys.statements_with_runtimes_in_95th_percentile;

שאילתה זו מציגה את 5% השאילתות האטיות ביותר, ללא קשר כמה זמן אבסולוטית הן ארכו (סף שניות כזה או אחר).

אתם שמים לב, בוודאי, שאנו קוראים ל system_schema  (השימוש ב FROM sys) ולא ל ps (השימוש ב FROM performance_schema).
ה ps חושפת כמות אדירה של נתונים (+ כמות גדולה של קונפיגורציה מה לאסוף ובאיזו רזולוציה) – מה שמקשה על השימוש בה עבור רוב המשתמשים.
ה system schema משמשת כשכבת הפשטה המציגה רשימה של views המרכזים מידע מתוך ה ps (וכמה מקומות אחרים) – ומנגישים את המידע המורכב למשתמש הפשוט.

נ.ב. –  על גרסה שהותקנה כ 5.7 ה system schema מגיעה כברירת-מחדל. על גרסאות ישנות יותר – ייתכן ותצטרכו להתקין אותה.

הנה תוצאה לדוגמה:

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

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

נ.ב: לא לדאוג לגבי “5 שעות שרת”, גם בהינתן שזה מידע של כשבוע: השרת מריץ הרבה שאילתות במקביל. הנתונים הנ״ל נלקחו משרת שפועל בעצימות נמוכה יחסית.

את המידע הזה אני שולף בעזרת השאילתה הבאה:

SELECT `schema_name` AS db,
digest_text AS query,
IF (( ( `stmts`.`sum_no_good_index_used` > 0 )
OR ( `stmts`.`sum_no_index_used` > 0 ) ), ‘*’, ”) AS `full_scan`,
Format(count_star, 0) AS events_count,
sys.Format_time(sum_timer_wait) AS total_latency,
sys.Format_time(avg_timer_wait) AS avg_latency,
sys.Format_time(max_timer_wait) AS max_latency,
Format(sum_rows_examined, 0) AS rows_scanned_sum,
Format(Round(Ifnull(( `stmts`.`sum_rows_examined` /
Nullif(`stmts`.`count_star`, 0) ), 0), 0), 0) AS `rows_scanned_avg`,
Format(Round(Ifnull(( `stmts`.`sum_rows_sent` /
Nullif(`stmts`.`count_star`, 0) ), 0), 0), 0) AS `rows_sent_avg`,
Format(sum_no_index_used, 0) AS rows_no_index_sum,
last_seen,
digest
FROM   performance_schema.events_statements_summary_by_digest AS `stmts`
WHERE  last_seen > ( Curdate() – INTERVAL 15 day )
ORDER  BY sum_timer_wait DESC;
השאילתה הזו ממיינת את התוצאה ע”פ sum_timer_wait, כלומר – זמן ההמתנה הכולל לכל המופעים של אותה השאילתה.
השאילתה הנ״ל תשמיט מהתוצאה שאילתות שלא נראו מופעים שלהן ב 15 הימים האחרונים. מה שנפתר / השתנה – כבר לא מעניין.

ניתוח ריצה של שאילתות

שלב הבא אחרי איתור שאילתה בעייתית הוא הרצה שלה, עם Explain וכלים נוספים.

כלי שימושי במיוחד של ה ps הוא הפרוצדורה trace_statement_digest. אנו מעתיקים את תוצאת ה digest (זיהוי ייחודי לדפוס של query) מתוך העמודה האחרונה של השאילתה הנ״ל, ומעתיקים אותה לתוך הביטוי הבא:

CALL sys.ps_trace_statement_digest(‘1149…405b’, 60, 0.1, TRUE, TRUE);

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

שימו לב שאתם זקוקים להרשאות אדמין בכדי להריץ את הפונקציה.

אם אין לכם הרשאות אדמין, הנה כלים נוספים שניתן להפעיל:

ראשית יש את ה optimizer trace שניתן להפעיל על שאילתה בודדת.

— Turn tracing on (it’s off by default):
SET optimizer_trace=“enabled=on”;

SELECT …; — your query here
SELECT * FROM information_schema.optimizer_trace;

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

ה trace ממש מציג את שלבי ההחלטה השונים של ה optimizer, איזה מידע ואלו אופציות עמדו לפניו, במה הוא בחר – ולמה. הנה דוגמה לחתיכה מתוך ה trace:

אם זו איננה מכונת פיתוח, חשוב לזכור ולסגור את ה optimizer_trace, שיש לו תקורה לא מבוטלת:

SET optimizer_trace=”enabled=off”;

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

SET profiling = 1;             — turn on profiling
SELECT …;                    — your query here
SHOW profiles;                 — list profiled queries
SHOW profile cpu FOR query 12; — place the proper query_id

בדרך ל profile הנכסף עליכם להפעיל את איסוף ה profiling, לבצע את השאילתה, לראות את השאילתות שנאספו – ולבחור את המספר השאילתה שלכם. התוצאה נראית כך:

“מה?? כמעט 5 שניות על שליחת נתונים בחזרה ללקוח? – אני מתקשר להוט!”

כמובן שכדאי גם לבדוק מה המשמעות של כל שורה. sending data כולל את קריאת הנתונים מהדיסק, העיבוד שלהם, והשליחה חזרה ל client.

בד”כ ה Sending Data יהיה החלק הארי, ודווקא כאשר סעיף אחר תופס נפח משמעותי – יש משהו חדש ללמוד מזה.

נ.ב – ניתן לבצע profiling גם על בסיס ה ps – מה שאמור להיות מדויק יותר, ו customizable – אבל מעולם לא השתמשתי ביכול הזו.

לבסוף, אל תשכחו לסגור את איסוף ה profiling:

SET profiling = 0;

עוד שאילתות שימושיות מתוך ה System Schema

הזכרנו את ה system schema, העוטפת את ה performance schema (ועוד קצת) בצורה נוחה יותר.

שווה להזכיר כמה שאילתות שימושיות:

SELECT * FROM sys.version;

הצגת גרסה מדויקת של שרת בסיס הנתונים, מתוך ממשק ה SQL.

SELECT * FROM sys.schema_tables_with_full_table_scans;

הצגה של רשימת הטבלאות שסרקו בהן את כל הרשמות כחלק משאילתה.

SELECT * FROM sys.schema_table_statistics;
SELECT * FROM sys.schema_index_statistics;

פרטים על הטבלאות והאינדקסים השונים – כמה ״עובד״ כל אחד.

SELECT * FROM sys.schema_unused_indexes;
SELECT * FROM sys.schema_redundant_indexes;

דרך טובה למצוא אינדקסים לא נחוצים.
אינדקסים מיותרים גורמים להכנסות (insert/update) להיות אטיות יותר – כי צריך לעדכן גם את האינדקס.

SELECT * FROM sys.statements_with_errors_or_warnings;
SELECT * FROM sys.statements_with_temp_tables;

עוד נתונים שכדאי להסתכל עליהם מדי-פעם.

SELECT * FROM sys.io_global_by_wait_by_latency;
SELECT * FROM sys.io_global_by_file_by_latency;

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

בסיס נתונים מונוליטי

אתם בוודאי מכירים את המצב בו שרת בסיס נתונים אחד מריץ loads שונים ושונים של עבודה.
בד”כ זה יהיה בסיס נתונים של מערכת מונוליטית, שמשמש גם לעבודות BI כאלו או אחרות (הוא מונוליטי, וכל הנתונים נמצאים בו – למה להשתמש במערכת אחרת?)

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

כלי העבודה הבסיסי הוא השאילתה הזו:

SELECT * FROM sys.session ORDER BY command;

היא דרך טובה לדעת מי עושה מה. זוהי “גרסה משופרת” של השאילתה SHOW PROCESSLIST.
כעת נוכל לראות אלו משתמשים גורמים לעומס הרב ביותר / עומס חריג – ונתחיל לנטר אותם:

SELECT * FROM sys.user_summary;

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

SELECT * FROM sys.user_summary_by_statement_type;
SELECT * FROM sys.user_summary_by_statement_latency;
SELECT * FROM performance_schema.user_variables_by_thread;
מכאן ייתכן ונרצה לפרק את העבודה לרמת ה thread של בסיס הנתונים. אולי שרת ספציפי של האפליקציה גורם לעומס החריג?

SELECT * FROM sys.io_by_thread_by_latency;

לא מוצאים את השאילתה?

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

יש כנראה דרכים מתוחכמות יותר לעשות זאת, אך אני פשוט משתמש ב  general log:

SET global general_log = ‘ON’;
SELECT …; — your query here

SELECT *
FROM mysql.general_log
WHERE argument LIKE ‘/*%’
AND event_time >= ( Curdate() – INTERVAL 5 minute )
ORDER BY event_time DESC
LIMIT 50;
SET global general_log = ‘OFF’;

ה General Log יותר overhead כבד למדי על בסיס הנתונים, ולכן אם מדובר בסביבת production – אני מפעיל אותו לזמן קצר בלבד (בעזרת ‘general_log = ‘ON/OFF). על סביבת הפיתוח אני יכול לעבוד כשהוא דלוק כל הזמן.

נ.ב. גם כאן, ייתכן ותצטרכו לכוון את כתיבת הנתונים לטבלה בעזרת:

SET global log_output = ‘FILE,TABLE’;

מכיוון שה framework שאני עובד איתו, JDBI, מוסיף לשאילות מזהה המופיע כהערה בתחילת השאילתה “/* comment */” – הוספתי תנאי המסנן את הלוג לשאילות בהם מופיעה הערה (להלן …argument LIKE).

שיהיה בהצלחה!

"תסביר לי" – גרסת ה SQL

פוסטים בסדרה:
“תסביר לי” – גרסת ה SQL
לקחת את הביצועים ברצינות, בעזרת MySQL Performance Schema
נושאים מתקדמים ב MySQL: חלק א’ – עבודה עם JSON
נושאים מתקדמים ב MySQL: חלק ב’ – json_each  ו Generated Columns

יש מי שאמר:

“EXPLAIN היא הפקודה החשובה ביותר ב SQL, אחרי הפקודה SELECT”

בבסיס נתונים אנחנו רוצים:

  • לשמור נתונים (לאורך זמן, בצורה אמינה)
  • לשלוף נתונים / לבצע שאילתות.

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

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

אפשר להחליט שזהו. “בואי שרהל’ה, אנחנו אורזים ועוברים – ל Cassandra”.
מי אמר שעל קסנדרה יהיה טוב יותר?
כבר נתקלתי במקרים בהם גילוי שאילתה אטית לווה מיד בקריאות “ה DB איטי – בואו נעבור ל !” – עוד לפני שבוצע ניתוח בסיסי. זו כנראה הגרסה המודרנית לקריאה “!A Witch! – burn her“.

נתקלתי פעם בפרויקט שביצע מעבר ל Cassandra לאורך לשנה – ורק אז הסיק ש Cassandra היא no-go לצרכים שלו (הם היו זקוקים Graph Database… זו הייתה טעות בסיסית בזיהוי).

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

 

דוגמה בסיסית

אני מריץ את השאילתה הבאה, ואינני מרוצה מזמני הביצוע שלה.

SELECT `value` 
FROM `quote_job_execution_internals` 
WHERE `quote_job_id` = ( 
  SELECT `quote_job_id` 
  FROM `quote_job_execution_internals` 
  WHERE `key` = ‘some key’ AND `value` = ‘1290268’ 
) AND `key` = ‘other key’ 
;

מה אני יכול לעשות?

שניה!
בואו נתחיל בבקשה מבסיס הנתונים להסביר כיצד הוא מתכנן להריץ את השאילתה (להלן ה query plan):

EXPLAIN SELECT `value` 
FROM `quote…

התוצאה תראה משהו כזה:

 

אמנם זהו Query אחד – אך תוצאת ה Explain מציגה שורה עבור כל Select (בדוגמה שלנו: שניים).

ה Quickwin בטיפול ב Explain נמצא בשתי עמודות: key ו type

    • key – באיזה אינדקס נעשה שימוש בכדי להגיע לנתונים. לרוב נרצה שיהיה שימוש באינדקס.
      • נשאל: האם האינדקס מתאים?
        • אולי חסר אינדקס?
        • אולי תנאי ה WHERE מכיל 2 עמודות – אך האינדקס מכסה רק אחת מהן? (ואז כדאי לשנות אינדקס / להוסיף עמודות לאינדקס).
      • לפעמים יש מקרים “לא צפויים” בהם האומפטימייזר בוחר לא להשתמש באינדקס. 
          למשל: התנאי WHERE ref_number = 1023 לא גרם לשימוש באינדקס כי העמודה ref_number היא מסוג varchar. השאילתה תחזיר תשובה נכונה – אבל האופטימייזר מבצע השוואת טיפוסים ומפספס שיש אינדקס מתאים. שינוי התנאי ל
        • ‘WHERE ref_number = ‘1023 – יחולל שינוי דרמטי בזמני הריצה.
      • דוגמה נוספת:  ‘WHERE Lower(some_column) = ‘some_value…
        – לא ישתמש באינדקס על some_column (כי המידע לא מאונדקס ב lower_case) בעוד:(‘WHERE  some_column = Upper(‘some_value
        – דווקא כן. 
  • type – כיצד טענו את הנתונים מהטבלה? גם כשיש שימוש באינדקס, יש הבדל אם סורקים את כל האינדקס, רשומה אחר רשומה, או מצליחים להגיע לערכים הנכונים באינדקס מהר יותר.
    • בקירוב, אלו הערכים העיקריים שנראה, ממוינים מה”טוב” ל”רע”:
      • system / const – יש עמודה אחת רלוונטית לשליפה (למשל: טבלה עם רשומה בודדת).
      • eq_ref – יש תנאי ב WHERE המבטיח לנו איבר יחיד באינדקס שהוא רלוונטי – אנו ניגשים לאיבר יחיד באינדקס. למשל: כאשר העמודה היא UNIQUE + NOT NULL.
      • ref – אנו הולכים לסרוק איברים באינדקס כמספר הרשומות שנשלוף. הגישה לאינדקס היא “מדויקת”.
      • range – עלינו לסרוק טווח (או מספר טווחים) באינדקס – שכנראה יש בהם יותר איברים ממספר הרשומות שאנו עומדים לשלוף.
      • index – יש צורך לסרוק את כל האינדקס. 
      • ALL – יש צורך לסרוק את כל הרשומות בטבלה. 😱
    • ייתכנו מקרי-קצה בהם index ו ALL – יהיו עדיפים על range או ref. אפרט אותם בהמשך.
רק להזכיר: האינדקס הוא “טבלה” רזה יותר המכילה רק עמודה בודדת (או מספר עמודות בודדות) מהטבלה – וממוינת ע”פ הסדר הזה. לא נדיר שאינדקס הוא רזה פי 10 ויותר מהטבלה (במיוחד אם בטבלה יש שדות מטיפוס varchar) – ואז גם סריקה מלאה של האינדקס הוא טעינה של (נניח) 10MB מדיסק – מול 100MB או יותר של נתונים שיש לטעון עבור סריקה מלאה של הטבלה.

 

מצד שני, גישה לאינדקס היא רק הקדמה לגישה לטבלה.

למשל: 20% מהרשומות עלולה בקלות להתמפות ל 50% מהבלוקים בדיסק בהם מאוחסנת הטבלה (במיוחד כאשר הרשומות קטנות). רזולוציית השליפה היא בלוקים – ולא רשומות בודדות.

יתרה מכך: שליפת כל הבלוקים של הטבלה כקובץ רציף תהיה לרוב מהירה יותר משליפת חצי מהבלוקים – כקבצים “רנדומליים”.

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

 

זהו. אם רציתם לקבל 50% מה value בקריאת 20% מהפוסט – אתם יכולים לעצור כאן, ולהמשיך בעיסוקכם.
 

 

תזכורת

מידע נוסף שניתן לשאוב מתוך פקודת ה Explain

בואו נחזור לרגע למבנה ה output של הפקודה, ונעבור עליו סעיף אחר סעיף.

 

קבוצה #1: “איך הנתונים נשלפים”

שלושת העמודות הראשונות עוזרות לנו לקשר בין השורה ב output לחלק המתאים בשאילתה.
בד”כ תוצאה של explain תהיה שורה או שתיים – אך גם נתקלתי גם ב 6 או 7 שורות בשאילתות מורכבות במיוחד.

  • Select Type הוא שדה זה נועד לאתר סוג ה SELECT שאליו מתייחסת השורה: SIMPLE – כאשר אין קינון שאילתות או איחוד שלהן, PRIMARY – השאילתה החיצונית ביותר (כאשר יש קינון) או הראשונה (ב UNION), יש גם SUBQUERY, UNION וכו’.
    • מעבר למה שציינתי / מה שאינטואטיבי – חבל להשקיע בהבנת העמודה הזו. בהמשך אראה לכם מה עושים אם יש שאילתה מורכבת במיוחד.
  • table – הטבלה שעליה המתבצע ה Select. זה יכול להיות שם של טבלה, או ביטוי כגון <Union <table1, table2.
  • partition ה partition של הטבלה, במידה ויש כזה.
    • partition היא היכולת להגדיר שחלקים שונים של הטבלה יאוחסנו על הדיסק בנפרד זה מזה (על מנת לשפר ביצועים בגישה לחלק המסוים). לדוגמה: כל הרשומות של שנת 2018 נשמרות בנפרד מהרשומות של שנת 2017 – למרות שלוגית זו טבלה אחת. התוצאה: שאילתות בתוך שנה בודדת יהיו מהירות יותר – על חשבון שאילתות הדורשות נתונים מכמה שנים.

העמודה החשובה יותר היא type – אותה כבר הזכרנו. הנה כמה פרטים נוספים ששווה להכיר:

סריקת index יכולה להיות יעילה יותר מ range או ref

שימוש באינדקס נעשה לרוב ב-2 שלבים:
  1. האינדקס נסרק / נקרא, וממנו נשלפו מזהיי (primary key) הרשומות שיש לקרוא מהטבלה.
  2. נעשית גישה נוספת לטבלה על מנת לטעון את ערכי הרשומות המתאימות.

אם בעמודה “Extra” (האחרונה) מופיע הערך “Using Index” משמע שלא היה צורך בשלב 2 – כי ערכי העמודות שביקשנו – נמצאו כבר באינדקס.

למשל: ביקשנו SELECT x FROM table1 WHERE y = 4
אם יש לנו אינדקס על עמודות x ו y – הרי שניתן ניתן לספק את התשובה מתוך קריאת האינדקס בלבד – וללא גישה לטבלה. זהו מצב מצוין.

 

סריקת ALL עשויה להיות יעילה יותר מ index, range או ref

בהמשך להסבר של שני שלבי השליפה:

  1. כאשר הטבלאות מאוד קטנות (KBs מעטים) – טעינת האינדקס ואז טעינת הטבלה – דורשת לפחות שתי גישות לדיסק.
  2. במקרים כאלו עדיף כבר לטעון את תוכן הטבלה (“ALL”) ולסרוק אותה. העלות העיקרית היא מספר הגישות לדיסק – ולא הסריקה בזיכרון.
קבוצה #2: “אינדקסים”
 
  • possible_key – היא רשימת האינדקסים שמכילים את העמודות בתנאי ה WHERE / JOIN.
    האופטימייזר בוחר אינדקס ספציפי (זה שהופיע בעמודה key) ע”פ יוריסטיקות מסוימות – והוא עשוי גם לפספס.
    • אם אתם משוכנעים שהוא לא בחר נכון (הוא טועה פחות ממה שנדמה לנו) אתם יכולים להנחות אותו באיזה אינדקס להשתמש בעזרת ההנחיה (USE INDEX (idx המגדילה את ציון האינדקס באלגוריתם הבחירה.
    • אתם יכולים להשתמש גם ב  FORCE INDEX – אבל התוצאה עשויה להכאיב: מגיעה שאילתה (או אלפי מופעמים של שאילתה) שאין טעם באינדקס – אך האופטימייזר ישתמש באינדקס, כי אתם אמרתם.
    • הנחיה אחרונה שימושית היא IGNORE INDEX – אתם יכולים לקרוא עוד בנושא כאן.
  • key_len – נשמעת כמו עמודה משעממת עד חרפה, אך זה בכלל לא המצב!
    • key_len עוזרת לאתר בזריזות אינדקסים “שמנים”. 
      • למשל: בתמונה למעלה יש key באורך 3003 בתים. כיצד זה ייתכן?
      • כל Character ב Unicode היא 3 בתים (בייצוג של MySQL) אז 3*1000 = 3000 בתים. עוד שלושה בתים, כך נראה לי, מגיעים מכך שהשדה הוא Nullable (בד”כ Nullable מוסיף 1+ לגודל).
        כלומר: גודל האינדקס הוא כ 90% מגודל הטבלה.
      • אם יש לי שאילתות הסורקות את כל האינדקס (type=index) – הרי שהאינדקס גורם לפי 2 נתונים להיטען מהדיסק, מאשר לו היינו פשוט סורקים את הטבלה.
      • כשאינדקס הוא כ”כ גדול (3000 בתים!), ובמידה ונעשה שימוש תדיר באינדקס – שווה לחשוב על הוספת עמודה נוספת, רזה יותר, המכילה subset של תוכן העמודה המקורית (למשל: 50 תווים ראשונים) – ואת העמודה הזו נאנדקס. הפתרון הספציפי מאוד תלוי בסוג הנתונים והגישה אליהם.
    • תובנה חשובה נוספת, שעמודת ה key_len יכולה לספק לי היא בכמה עמודות מתוך אינדקס-מרובה-עמודות נעשה שימוש. אם יש לי אינדקס של שני שדות מטיפוס INT (כלומר: ביחד 8 בתים), אך העמודה key_len מחזירה ערך 4 – סימן שנעשה שימוש רק בעמודה הראשונה שבאינדקס (שימוש באינדקס יכול להיעשות רק ע”פ סדר האינדקסים “שמאל לימין”).
      • לא קל להבחין במקרים הללו (צריך לחשב גדלים של שדות) – אך הם יכולים להעיד על בעיה בלתי-צפויה. למשל: תנאי שעוטף את ערך המספר במרכאות – וכך נמנע שימוש בשדה המשני של האינדקס. לכאורה: היה שימוש באינדקס – אבל שיפור שכזה עשוי לשפר את זמן הריצה פי כמה.
      • נ.ב. שדה Int תמיד יהיה 4 בתים. ה “length” משפיע על מספר הספרות בתצוגה.
      • אם אתם לא בטוחים מה מבנה הטבלה, תוכלו להציג אותו בזריזות בעזרת
          SHOW CREATE TABLE tbl_name 
    • ref – איזה סוג של ערכים מושווים כנגד האינדקס. לא כזה חשוב.
      • const הוא הערך הנפוץ, המתאר שההשוואה היא מול ערך “קבוע”, למשל: ערך מתוך טבלה אחרת.
      • NULL הכוונה שלא נעשתה השוואה. זה מתרחש כאשר יש Join ומדובר בטבלה המובילה את ה join.
      • func משמע שנעשה שימוש בפונקציה. 
 
אם קיבלתם ערך ref=func, ואתם רוצים לדעת איזה פונקציה הופעלה, הפעילו את הפקודה SHOW WARNINGS מיד לאחר ה Explain. היא תספק לכם מידע נוסף (מה שנקרא בעבר “extended explain“).
 
זוכרים שאמרתי לכם שאם יש שאילתה מורכבת מאוד, חבל לנסות ולשבור את הראש איזו שורה ב Explain מתאימה לאיזה חלק בשאילה? 
כאשר אתם קוראים ל Show Warnings אתם גם מקבלים את הגרסה ה “expanded” של השאילתה.
 
/* select#1 */ SELECT `quote_job_execution_internals`.`value` AS `value` 
FROM  `quote_job_execution_internals` 
WHERE  ( ( `quote_job_execution_internals`.`quote_job_id` 
           = ( /* select#2 */ SELECT            `quote_job_execution_internals`.`quote_job_id` 
           FROM   `quote_job_execution_internals` 
           WHERE  ( (            `quote_job_execution_internals`.`key` = ‘nimiGlPolicyId’ ) 
           AND (`quote_job_execution_internals`.`value` = ‘1290268’ ) )) ) 
           AND ( `quote_job_execution_internals`.`key` = ‘storageId’ ) ) 
 

הסימון בהערות (“select#1” ו “select#2“) הוא הדרך הקלה לזהות אלו חלקים בשאילתה מתייחסים לאלו שורות ב Explain. 

 
 
 
קבוצה #3: כמות הרשומות

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

  • עמודת ה rows מספקת הערכה כמה נתונים ייסרקו. השאילתה עדיין לא רצה – אז לא ניתן לדעת.
    • במקרה שלנו, כאשר ה subquery עתיד לסרוק 2 שורות, וה primary select עתיד לסרוק 6 שורות – אנו מצפים לסריקה של 6 * 2 = 12 שורות, וזה מספר קטן. 
    • אם יש לנו 3 שאילתות מקוננות, וכל אחת סורקת 50 שורות – אזי נגיע סה”כ לסריקה של עד 125,000 שורות – וזה כבר הרבה!
  • עמודת ה filtered מספקת הערכה (לא מדויקת) באיזה אחוז מהרשומות שנסרקו באינדקס – ייעשה שימוש. 
    • בדוגמה למעלה קיבלנו הערכה שנטען 6 או 2 רשומות, וב “10%” מהן יעשה שימוש, כלומר: באחת.
    • כאשר הערך הוא נמוך מאוד (פחות מאחוזים בודדים, או שבריר האחוז), ובמיוחד כאשר מספר הרשומות הנסרק (rows) הוא גבוה – זהו סימן שהשימוש באינדקס הוא לא יעיל. ייתכן ואינדקס אחר יכול להתאים יותר?
    • השאיפה שלנו היא להגיע ל rows = 1 ו filtered = 100% – זהו אינדקס המנוצל בצורה מיטבית!
 
לצורך האופטימייזר, בסיס הנתונים שומר לעצמו נתונים סטטיסטיים על התפלגות הנתונים בטבלאות השונות. ב MySQL המידע נשמר ב Information_schema.statistics – והוא מתעדכן עם הזמן. 
 
אם הרגע הוספתם אינדקס, ו/או הכנסתם / עדכנתם חלקים גדולים מהטבלה – יש סיכוי טוב שייקח זמן עד שיאספו נתונים חדשים, שיעזרו לאופטימייזר להשתמש נכון באינדקסים במצב החדש.
 
הפקודה ANALYZE TABLE your_table גורמת ל MySQL לאוסף את הנתונים מחדש. זה עשוי לארוך קצת זמן.

 

הפקודה OPTIMIZE TABLE your_table גורמת ל MySQL לבצע דחיסה (סוג של defrag) על הקבצים של הטבלה – ואז להריץ Analyze Table. זה ייקח יותר זמן – ולכן מומלץ להריץ את הפקודה הזו רק “בשעות המתות”.

 

 

 

קבוצה #4: Extra


עמודת האקסטרא בד”כ תאמר לכם “Using Where” (דאא?), אבל יש כמה ערכים שהיא יכולה לקבל שדווקא מעניינים:

  • Using Index – ציינו את המקרה הזה למעלה. נעשה שימוש באינדקס בלבד על מנת לספק את הערכים (מצוין!)
  • Using filesort – מכיוון שלא הצליח לבצע מיון (ORDER BY) על בסיס אינדקס ו/או כמות הנתונים גדולה מדי – בסיס הנתונים משתמש באלגוריתם בשם filesort בכדי לבצע את המיון. בסיס הנתונים ינסה להקצות שטח גדול בזיכרון ולבצע אותו שם – לפני שהוא באמת משתמש בקבצים. 
    • פעמים רבות אפשר להימנע מ filesort ע״י אינדקס על העמודה לפיה עושים מיון. 
    • [עודכן] כמובן שבאינדקס הכולל כמה שדות – רק השדה הראשון (ה״שמאלי״) שימושי למיון, או לחלופין אם סיננו ע”פ האינדקס (WHERE) – השדה השמאלי לשדה/שדות על פיהם נעשה הסינון (תודה לאנונימי על ההערה).
    • אם יש ORDER BY על יותר מעמודה אחת – שימוש באינדקס יהיה יעיל רק אם האינדקס מכיל את השדות לפיהם ממיינים בסדר הנכון.
  • Using temporary – מקרה דומה: יש פעולה גדולה (בד״כ GROUP BY) שלא ניתן לבצע בזיכרון – ולכן משתמשים בטבלה זמנית (בזיכרון). גם זה מצב שכדאי לנסות להימנע ממנו.
    • בד”כ אין פתרונות קלים למצב הזה: לנסות ולהסתדר ללא GROUP BY? לבצע את פעולת הקיבוץ אפליקטיבית בקוד? (כמעט תמיד custom code שנכתב בחכמה ינצח את בסיס הנתונים בביצועים – אבל יהיה יקר יותר לפיתוח ותחזוקה)

 

 

אחרית דבר

לאחר הפוסט הזה אתם אמורים להבין את תוצאות הפקודה EXPLAIN בצורה דיי טובה!

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

שווה להזכיר את ה Slow Log וה Performance Schema שעוזרים לאתר בכלל את השאילתות הבעייתיות.
את Profile ו Trace (+ מידע שניתן לשלוף מה Performance Schema) – שבעזרתם ניתן לבחון כיצד השאילתה רצה בפועל.

הפרמטר  format=json (כלומר EXPLAIN format=json SELECT something) גורם ל Explain לספק פירוט עשיר יותר (ובפורמט json).

יש גם עוד הנחיות שונות שניתן להוסיף בשאילתה על מנת להנחות את האופטימייזר לפעול באופן מסוים (למשל SQL_BIG_RESULT או STRAIGHT_JOIN), או אפילו הנחיות הנובעות מהחומרה שבשימוש (להלן טבלת ה mysql.server_cost , וה optimizer_switch)
אבל אני חושב שאת תחום זה מוטב להשאיר ל DBAs…

שיהיה בהצלחה!