שאלות מראיונות עבודה: בעיית N+1

26/03/2015

שאלה: במערכת Ruby On Rails נתון מודל מארזים ומודל שעורים, כך שכל שעור שייך למארז. כך מוגדרות הטבלאות בבסיס הנתונים:

CREATE TABLE bundles (
  id INTEGER PRIMARY KEY, 
  name VARCHAR(255)
)

CREATE TABLE lessons (
  id INTEGER PRIMARY KEY,
  name VARCHAR(255),
  bundle_id INTEGER 
)

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

1. הפתרון הנאיבי

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

Bundle.all.each do |b|
  puts "Bundle: #{b.name}, count: #{b.lessons.count} "
end

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

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

2. בואו נדבר על SQL

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

SELECT b.id, b.name, count(*) as lessons_count
FROM bundles b
LEFT OUTER JOIN lessons l
ON b.id = l.bundle_id
GROUP BY b.id, b.name;

השימוש ב LEFT OUTER JOIN משאיר גם שורות מתוך טבלת המארזים בהן אין שעורים כלל (בניגוד ל INNER JOIN שהיה מבטל שורות אלו).

3. בחזרה ל RoR

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

Bundle.joins("LEFT OUTER JOIN lessons ON lessons.bundle_id = bundles.id").select("bundles.id, bundles.name, count(lessons.id) as lessons_count").group("bundles.id", "bundles.name")

ולכן קוד הפתרון המלא ייראה כך:

bundles_with_counts = Bundle.joins("LEFT OUTER JOIN lessons ON lessons.bundle_id = bundles.id").select("bundles.id, bundles.name, count(lessons.id) as lessons_count").group("bundles.id", "bundles.name")

bundles_with_counts.all.each do |b|
  puts "#{b.name} has #{b.lessons_count} lessons"
end

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

bundles_with_counts = Bundle.includes(:lessons).group('bundles.id').pluck('bundles.id, count(lessons.id)')

 

4. נסיון 2: פחות רובי, יותר בסיס נתונים

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

CREATE or REPLACE VIEW bundles_with_lessons_count as
  SELECT b.*,count(*) as lessons_count FROM bundles b
  LEFT OUTER JOIN lessons l
  ON b.id = l.bundle_id
  GROUP BY b.id;

שימו לב ש PostgreSQL מסוגל לנחש את שמות כל עמודות הטבלא בחלק ה GROUP BY ולכן מספיק לציין את המפתח הראשי. יש בסיסי נתונים שידרשו מכם לציין את רשימת כל העמודות המופיעות בשאילתה כדי לבצע קיבוץ.
מתכנתי RoR יכולים לשים את פקודת היצירה בתוך Migration כדי שתשמר גם בבקרת התצורה באופן הבא:

class AddBundlesLessonsView < ActiveRecord::Migration
    def up
          execute <<-SQL
               create or replace view bundles_with_lessons_count as
               SELECT b.*,count(*) AS lessons_count FROM bundles b
               LEFT OUTER JOIN lessons l
               ON b.id = l.bundle_id
               GROUP BY b.id;
          SQL
     end

def down
          execute <<-SQL
               DROP VIEW bundles_with_lessons_count
          SQL
     end
end

לאחר יצירת ה View נבנה מודל המתבסס עליו. מודל זה ישמש לשליפות בלבד. כדי לאפשר עדכון דרך Views נצטרך להוסיף טריגרים וזה נושא לפוסט נפרד. המודל החדש שלנו יירש ממודל ה Bundle הרגיל אבל יבצע את השליפות מתוך ה View. כך נראה הקוד עבור הקובץ bundle_with_lessons_count.rb:

class BundleWithLessonsCount < Bundle
     self.table_name = "bundles_with_lessons_count"
end

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

BundleWithLessonsCount.all.each do |b|
     puts "Bundle: #{b.name}, count: #{b.lessons.count} "
end

 

5. עריכה: עמודת מונים

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

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

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

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

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

6. סיכום וקריאת המשך

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

  1. אפשר לקרוא עוד על בעיית N+1 בריילס בקישור:
    http://railscasts.com/episodes/372-bullet?view=asciicast
  2. הרחבה על מודלים מגובים ב View בריילס:
    http://dan.chak.org/enterprise-rails/chapter-11-view-backed-models/
  3. אפשרות להוסיף, לעדכן ולמחוק רשומות דרך Views
    https://vibhorkumar.wordpress.com/2011/10/28/instead-of-trigger/
  4. בעיית N+1 שליפות מופיעה גם בשפות אחרות. כאן למשל תמצאו סקירה שלה בספריית Hibernate של שפת Java:
    http://architects.dzone.com/articles/how-identify-and-resilve-n1
  5. ניהול אוטומטי של עמודת מונים באמצעות counter_cache:
    http://yerb.net/blog/2014/03/13/three-easy-steps-to-using-counter-caches-in-rails/