מערכונים

‫GoogleSQL ל-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
  );

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

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

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

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

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

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

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

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

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

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

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

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

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

חישוב אחוזון

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

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

‫HLL++ sketches

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

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

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

דיוק

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

דיוק נפח האחסון המקסימלי ‫65% רווח סמך רווח בר-סמך של 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 ‫4KiB + 28B ±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,024KiB + 30B ±0.10% ±0.20% ±0.30%
21 ‫2,048KiB‏ + 32B ±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 ‫‎16,384KiB + 32B ±0.03% ±0.05% ±0.08%

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

מחיקה

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

פרטים נוספים

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

שילוב עם Sketch

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

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

שרטוטי KLL

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

דיוק

שרטוטי KLL תומכים ברמת דיוק בהתאמה אישית. הדיוק מגדיר את רמת הדיוק של האחוזון המשוער 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 פריטים ב-sketch, הדירוג של החציון שיוחזר יהיה כמעט תמיד בין 499,000 ל-501,000.

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

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

גודל

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

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

Phi

‫Phi (Φ) מייצג את האחוזון שצריך להפיק כחלק מהמספר הכולל של השורות בקלט של ה-sketch, מנורמל בין 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). בגלל האופי הלא דטרמיניסטי של האלגוריתם, יכול להיות ששרטוטים שנוצרו באותה קבוצת נתונים עם אותה רמת דיוק לא יהיו זהים.

אחוזונים

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

בדרך כלל מגדירים קוונטילים בשתי דרכים:

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

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

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

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

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

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