מערכונים

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

דיוק

סקיצות HLL++ תומכות בדיוק בהתאמה אישית. בטבלה הבאה מוצגים ערכי הדיוק הנתמכים, גודל האחסון המקסימלי והרווח בר-הסמך (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 ‫‎2,048 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 תומכות בדיוק מותאם אישית. הדיוק מגדיר את רמת הדיוק של האחוזון המשוער q שמוחזר.

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

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

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

אם משתמשים בדיוק מותאם אישית של 100 כדי למצוא את ערך החציון, הדירוג של הערך שמוחזר על ידי הפונקציה KLL_QUANTILES.EXTRACT_POINT שונה מהדירוג האמיתי ב-99.999% מהמקרים, בהפרש של n/100 לכל היותר. במילים אחרות, הערך שמוחזר הוא כמעט תמיד בין האחוזון ה-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 ‫706B ‫1.47KB
50 ‫3.49 KB ‫1.72KB ‫3.60KB
100 ‫6.94 KB ‫3.44 KB ‫7.12 KB
200 ‫13.87 KB ‫6.33 KB ‫13.98 KB
500 35.15 KB ‫14.47 KB ‫35.30 KB
1000 ‫71.18KB ‫27.86KB ‫71.28KB
2000 ‫144.51KB ‫55.25 KB ‫144.57KB
5,000 ‫368.87KB ‫139.54KB ‫368.96KB
10000 ‫749.82KB ‫282.27KB ‫697.80KB
20000 ‫1.52MB ‫573.16 KB ‫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 מספקת פונקציות מצטברות משוערות מוגדרות מראש. הפונקציות המצטברות האלה של הערכה משוערת תומכות בסקיצות להערכות נפוצות כמו ספירה של ערכים ייחודיים, חלוקה לעשירונים וספירה של הערכים המובילים, אבל הן לא מאפשרות דיוק בהתאמה אישית. בנוסף, הם לא חושפים ולא מאחסנים את הסקיצה לצורך צבירה מחדש, כמו סוגים אחרים של סקיצות. הפונקציות המצטברות המשוערות נועדו להרצת שאילתות מהירות שמבוססות על סקיצה, בלי הגדרה מפורטת.

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