מערכונים

‫GoogleSQL for BigQuery תומך בסקיצות נתונים. סקיצת נתונים היא סיכום קומפקטי של צבירת נתונים. הוא כולל את כל המידע שנדרש כדי לחלץ תוצאת צבירה, להמשיך צבירת נתונים או למזג אותה עם סקיצה אחרת, וכך מאפשר צבירה מחדש.

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

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

נניח שיש לכם טבלה עם הנתונים הבאים:

מוצר מספר המשתמשים משך ביקור חציוני
מוצר א' ‫500 מיליון 10 דקות
מוצר ב' 20 מיליון ‫2 דקות

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

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

לדוגמה, השאילתה הבאה משתמשת בסקיצות של HLL++‎ ו-KLL כדי להעריך את מספר המשתמשים הייחודיים ואת משך הביקור החציוני ב-YouTube (מוצר א') ובמפות Google (מוצר ב'):

-- Build sketches for YouTube stats.
CREATE TABLE user.YOUTUBE_ACCESS_STATS
AS
SELECT
  HLL_COUNT.INIT(user_id) AS distinct_users_sketch,
  KLL_QUANTILES.INIT_INT64(visit_duration_ms) AS visit_duration_ms_sketch,
  hour_of_day
FROM YOUTUBE_ACCESS_LOG()
GROUP BY hour_of_day;

-- Build sketches for Maps stats.
CREATE TABLE user.MAPS_ACCESS_STATS
AS
SELECT
  HLL_COUNT.INIT(user_id) AS distinct_users_sketch,
  KLL_QUANTILES.INIT_INT64(visit_duration_ms) AS visit_duration_ms_sketch,
  hour_of_day
FROM MAPS_ACCESS_LOG()
GROUP BY hour_of_day;

-- Query YouTube hourly stats.
SELECT
  HLL_COUNT.EXTRACT(distinct_users_sketch) AS distinct_users,
  KLL_QUANTILES.EXTRACT_POINT_INT64(visit_duration_ms_sketch, 0.5)
  AS median_visit_duration, hour_of_day
FROM user.YOUTUBE_ACCESS_STATS;

-- Query YouTube daily stats.
SELECT
  HLL_COUNT.MERGE(distinct_users_sketch),
  KLL_QUANTILES.MERGE_POINT_INT64(visit_duration_ms_sketch, 0.5)
  AS median_visit_duration, date
FROM user.YOUTUBE_ACCESS_STATS
GROUP BY date;

-- Query total stats across YouTube and Maps.
SELECT
  HLL_COUNT.MERGE(distinct_users_sketch) AS unique_users_all_services,
  KLL_QUANTILES.MERGE_POINT_INT64(visit_duration_ms_sketch, 0.5)
    AS median_visit_duration_all_services,
FROM
  (
    SELECT * FROM user.YOUTUBE_ACCESS_STATS
    UNION ALL
    SELECT * FROM user.MAPS_ACCESS_STATS
  );

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

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

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

צבירה מחדש באמצעות מיזוג סקיצות

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

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

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

באיזה סוג של סקיצה כדאי להשתמש?

אלגוריתמים שונים של סקיצות מיועדים לסוגים שונים של מדדים, כמו HLL++‎ לספירות נפרדות ו-KLL למדדי כמות. ב-GoogleSQL יש גם פונקציות נצברות משוערות שבהן אפשר להשתמש כדי לשלוח שאילתות לגבי סוגי הנתונים האלה בלי לציין פרטים של השאילתה, כמו רמת הדיוק.

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

הערכת עוצמה (cardinality)

אם אתם צריכים להעריך את העוצמה, אתם יכולים להשתמש ב-HLL++ sketch.

לדוגמה, כדי לקבל את מספר המשתמשים הייחודיים שהשתמשו באופן פעיל במוצר בחודש מסוים (מדדי MAU או 28DAU), צריך להשתמש ב-HLL++ sketch.

חישוב אחוזון

אם אתם צריכים לקבל קוונטיל של קבוצת נתונים, אתם יכולים להשתמש בסקיצה של KLL.

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

HLL++ sketches

‫HyperLogLog++‎ ‏ (HLL++‎) הוא אלגוריתם ליצירת סקיצות להערכת עוצמה. האלגוריתם HLL++‎ מבוסס על המאמר HyperLogLog in Practice, שבו הסימון ++‎ מציין את השיפורים שבוצעו באלגוריתם HyperLogLog.

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

אלגוריתם HLL++‎ מעריך קרדינליות קטנות מאוד וגדולות מאוד. האלגוריתם HLL++‎ כולל פונקציית גיבוב (hash) של 64 ביט, ייצוג דליל כדי לצמצם את דרישות הזיכרון לאומדנים של עוצמה קטנה, ותיקון הטיה אמפירי לאומדנים של עוצמה קטנה.

דיוק

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

Precision גודל אחסון מקסימלי ‫65% CI 95% CI רווח בר-סמך של 99%
10 ‫‎1 KiB + 28 B ‫±3.25% ‫±6.50% ‫±9.75%
11 ‫‎2 KiB + 28 B ‫±2.30% ‫±4.60% ‫±6.89%
12 ‫4 KiB + 28 B ‫±1.63% ‫±3.25% ‫±4.88%
13 ‎8 KiB + 28 B ‫±1.15% ‫±2.30% ‫±3.45%
14 ‎16 KiB + 30 B ‫±0.81% ‫±1.63% ‫±2.44%
‫15 (ברירת מחדל) ‎32 KiB + 30 B ‫±0.57% ‫±1.15% ‫±1.72%
16 ‫‎64 KiB + 30 B ‫±0.41% ‫±0.81% ‫±1.22%
17 ‫‎128 KiB + 30 B ‫±0.29% ‫±0.57% ‫±0.86%
18 ‫256 KiB + 30 B ‫±0.20% ‫±0.41% ‫±0.61%
19 ‫512 KiB + 30 B ‫±0.14% ‫±0.29% ‫±0.43%
20 ‫‎1,024 KiB + 30 B ‫±0.10% ‫±0.20% ‫±0.30%
21 ‫2048 KiB + 32 B ‫±0.07% ‫±0.14% ‫±0.22%
22 ‫‎4096 KiB + 32 B ‫±0.05% ‫±0.10% ‫±0.15%
23 ‫‎8192 KiB + 32 B ‫±0.04% ‫±0.07% ‫±0.11%
24 ‎16384 KiB + 32 B ‫±0.03% ‫±0.05% ‫±0.08%

אפשר להגדיר את רמת הדיוק של סקיצת HLL++‎ כשמאתחלים אותה באמצעות הפונקציה HLL_COUNT.INIT.

מחיקה

אי אפשר למחוק ערכים מ-HLL++ sketch.

פרטים נוספים

רשימה של פונקציות שאפשר להשתמש בהן עם HLL++ sketches‎ זמינה במאמר בנושא פונקציות HLL++‎.

שילוב עם Sketch

אפשר לשלב HLL++ sketches עם מערכות אחרות. לדוגמה, אתם יכולים ליצור סקיצות באפליקציות חיצוניות, כמו Dataflow,‏ Apache Spark ו-ZetaSketch, ואז להשתמש בהן ב-GoogleSQL או להיפך.

בנוסף ל-GoogleSQL, אפשר להשתמש ב-HLL++ sketches עם Java.

סקיצות של KLL

‫KLL (קיצור של Karnin-Lang-Liberty) הוא אלגוריתם סטרימינג לחישוב סקיצות של כמויות חלקיות משוערות. הפונקציה מחשבת אחוזונים שרירותיים בצורה יעילה בהרבה מחישובים מדויקים, במחיר של שגיאת קירוב קטנה.

דיוק

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

כברירת מחדל, הדירוג של קוונטיל משוער יכול להיות לכל היותר ±1/1000 * n פחות מ-⌈Φ * n⌉, כאשר n הוא מספר השורות בקלט ו-⌈Φ * n⌉ הוא הדירוג של הקוונטיל המדויק.

אם תספקו רמת דיוק בהתאמה אישית, הדירוג של הכמות החציונית המשוערת יכול להיות לכל היותר ±1/precision * n פחות מהדירוג של הכמות החציונית המדויקת. השגיאה נמצאת בתוך גבול השגיאה הזה ב-99.999% מהמקרים. ההתחייבות הזו לשגיאה חלה רק על ההבדל בין דירוגים מדויקים לבין דירוגים משוערים. ההבדל המספרי בין הערך המדויק לבין הערך המשוער של קוונטיל יכול להיות גדול באופן שרירותי.

לדוגמה, נניח שאתם רוצים למצוא את ערך החציון, Φ = 0.5, ואתם משתמשים בדיוק ברירת המחדל של 1000. במקרה כזה, הדירוג של הערך שמוחזר על ידי הפונקציה KLL_QUANTILES.EXTRACT_POINT שונה מהדירוג האמיתי ב-n/1000 לכל היותר ב-99.999% מהמקרים. במילים אחרות, הערך שמוחזר הוא כמעט תמיד בין האחוזון ה-49.9 לאחוזון ה-50.1. אם יש לכם 1,000,000 פריטים בסקיצה, הדירוג של החציון שמוחזר יהיה כמעט תמיד בין 499,000 ל-501,000.

אם משתמשים בערך דיוק מותאם אישית של 100 כדי למצוא את ערך החציון, הדירוג של הערך שמוחזר על ידי הפונקציה KLL_QUANTILES.EXTRACT_POINT שונה מהדירוג האמיתי ב-n/100 לכל היותר ב-99.999% מהמקרים. במילים אחרות, הערך שמוחזר הוא כמעט תמיד בין האחוזון ה-49 ל-51. אם יש לכם מיליון פריטים בסקיצה, הדירוג של החציון שמוחזר הוא כמעט תמיד בין 490,000 ל-510,000.

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

גודל

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

Precision FLOAT64 INT64 (<1B) INT64 (כל ערך)
10 ‫761 מיליארד ‫360 B ‫717 מיליארד
20 ‫1.46KB ‫706 B ‫1.47KB
50 ‫3.49 KB ‫1.72KB ‫3.60 KB
100 ‫6.94 KB ‫3.44 KB ‫7.12 KB
200 ‫13.87 KB ‫6.33 KB ‫13.98 KB
500 ‫35.15KB ‫14.47 KB ‫35.30 KB
1000 ‫71.18KB ‫27.86KB ‫71.28KB
2000 ‫144.51KB ‫55.25 KB ‫144.57KB
5,000 ‫368.87 KB ‫139.54KB ‫368.96KB
10000 ‫749.82KB ‫282.27KB ‫697.80 KB
20000 ‫1.52MB ‫573.16KB ‫1.37MB
50000 ‫3.90MB ‫1.12MB ‫3.45MB
100000 ‫7.92MB ‫2.18MB ‫6.97MB

Phi

‫Phi (Φ) מייצג את הכמותון שיווצר כחלק היחסי מתוך המספר הכולל של השורות בקלט של הסקיצה, בנורמליזציה בין 0 ל-1. אם פונקציה תומכת ב-phi, היא מחזירה ערך v כך שערך של בערך Φ * n תשומות קטן מ-v או שווה לו, וערך של (1-Φ) * n תשומות גדול מ-v או שווה לו.

פרטים נוספים

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

אלגוריתם ה-KLL מוגדר במאמר Optimal Quantile Approximation in Streams, והוא נקרא על שם המחברים שלו, Karnin,‏ Lang ו-Liberty, שפרסמו את המאמר בשנת 2016. אלגוריתם KLL משפר את אלגוריתם MP80 הישן יותר באמצעות מאגרי נתונים זמניים בגודל משתנה כדי לצמצם את השימוש בזיכרון עבור מערכי נתונים גדולים, וכך מקטין את גודל הסקיצה מ-O(log n) ל-O(1). בגלל האופי הלא דטרמיניסטי של האלגוריתם, יכול להיות שסקיצות שנוצרו על אותו מערך נתונים עם אותה רמת דיוק לא יהיו זהות.

Quantiles

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

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

  • עבור מספר שלם חיובי q, קבוצת הערכים של q-החלקים היא קבוצה שמחלקת קבוצת קלט ל-q קבוצות משנה בגודל כמעט שווה. לחלק מהפונקציות האלה יש שמות ספציפיים: הכמותון היחיד עם 2 ערכים הוא החציון, הכמותונים עם 4 ערכים הם הרבעונים, הכמותונים עם 100 ערכים הם האחוזונים וכו'. בנוסף, פונקציות KLL מחזירות את המינימום והמקסימום (המדויקים) של הקלט, כך שכאשר מבצעים שאילתה לגבי הכמותונים עם 2 ערכים, מוחזרים שלושה ערכים.

  • אפשרות אחרת היא להתייחס לקוונטילים כאל קוונטילים בודדים מסדר Φ, כאשר Φ הוא מספר ממשי עם 0 <= Φ <= 1. הקוונטיל ה-Φ x הוא רכיב של הקלט כך שחלק של Φ מהקלט קטן מ-x או שווה לו, וחלק של (1-Φ) גדול מ-x או שווה לו. בסימון הזה, החציון הוא הכמותון 0.5, והאחוזון ה-95 הוא הכמותון 0.95.

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

פונקציות צבירה משוערות

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

רשימה של פונקציות צבירה משוערות שאפשר להשתמש בהן עם קירוב מבוסס-סקיצה מופיעה במאמר פונקציות צבירה משוערות.