מערכונים

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

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

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

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

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

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

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

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

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

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

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

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

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

חישוב אחוזון

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

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

רישומי HLL++‎

‫HyperLogLog++‎ ‏(HLL++) הוא אלגוריתם ליצירת סקיצות להערכת עוצמה (cardinality). האלגוריתם 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 ‫‎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 תומכות בדיוק מותאם אישית. הדיוק מגדיר את רמת הדיוק של האחוזון המשוער 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 ‫706 מיליארד ‫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.87 KB ‫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, והוא נקרא על שם המחברים שלו, קרנין, לאנג וליברטי, שפרסמו את המאמר בשנת 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 מספקת פונקציות מצטברות משוערות מוגדרות מראש. הפונקציות האלה של צבירה משוערת תומכות בסקיצות להערכות נפוצות כמו ספירה של ערכים ייחודיים, אחוזונים וספירה של הערכים המובילים, אבל הן לא מאפשרות דיוק מותאם אישית. בנוסף, הם לא חושפים ולא מאחסנים את הסקיצה לצורך צבירה מחדש, כמו סוגים אחרים של סקיצות. הפונקציות המצטברות המשוערות נועדו להרצת שאילתות מהירות שמבוססות על סקיצה, בלי הגדרה מפורטת.

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