מערכונים

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

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

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

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

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

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

לדוגמה, בשאילתה הבאה נעשה שימוש בסקיצות של 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) של רמות דיוק אופייניות:

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

מחיקה

אי אפשר למחוק ערכים מסקיצה של HLL++.

פרטים נוספים

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

שילוב עם Sketch

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

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

סקיצות של KLL

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

דיוק

סקיצות KLL תומכות בדיוק מותאם אישית. הפרמטר Precision מגדיר את רמת הדיוק של הכמות החלקית המשוערת 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 שונה מהדירוג האמיתי ב-n/100 לכל היותר ב-99.999% מהמקרים. במילים אחרות, הערך שמוחזר הוא כמעט תמיד בין האחוזון ה-49 ל-51. אם יש לכם מיליון פריטים בסקיצה, הדירוג של החציון שמוחזר הוא כמעט תמיד בין 490,000 ל-510,000.

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

גודל

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

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. הערך Φ-quantile x הוא ��כיב של הקלט כך שחלק של Φ מהקלט קטן מ-x או שווה לו, וחלק של (1-Φ) גדול מ-x או שווה לו. בסימון הזה, החציון הוא הכמותון 0.5, והאחוזון ה-95 הוא הכמותון 0.95.

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

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

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

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