מערכונים

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

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

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

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

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

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

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

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

דיוק

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

דיוק נפח האחסון המקסימלי 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 ‫‎1024 KiB + 30 B ±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++‎ עם Java.

שרטוטי KLL

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

Precision

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

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

Phi

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

פרטים נוספים

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

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

אחוזונים

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

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

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

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

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

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

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

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