Schizzi

GoogleSQL per BigQuery supporta gli schizzi di dati. Uno schizzo dei dati è un riepilogo compatto di un'aggregazione di dati. Acquisisce tutte le informazioni necessarie per estrarre un risultato di aggregazione, continuare un'aggregazione dei dati o unirlo a un altro schizzo, consentendo la riaggregazione.

Il calcolo di una metrica utilizzando uno schizzo è notevolmente meno costoso del calcolo di un valore esatto. Se il calcolo è troppo lento o richiede troppo spazio di archiviazione temporaneo, utilizza gli schizzi per ridurre il tempo di esecuzione delle query e le risorse.

Inoltre, il calcolo delle cardinalità, ad esempio il numero di utenti unici, o dei quantili, ad esempio la durata mediana della visita, senza schizzi è solitamente possibile solo eseguendo job sui dati non elaborati perché i dati già aggregati non possono più essere combinati.

Considera una tabella con i seguenti dati:

Il calcolo del numero totale di utenti per entrambi i prodotti non è possibile perché non sappiamo quanti utenti hanno utilizzato entrambi i prodotti nella tabella. Allo stesso modo, non è possibile calcolare la durata mediana della visita perché la distribuzione delle durate delle visite è andata persa.

Una soluzione è archiviare gli schizzi nella tabella. Ogni schizzo è una rappresentazione approssimativa e compatta di una determinata proprietà di input, ad esempio la cardinalità, che puoi archiviare, unire (o riaggregare) ed eseguire query per ottenere risultati quasi esatti. Nell'esempio precedente, puoi stimare il numero di utenti unici per il prodotto A e il prodotto B creando e unendo (riaggregando) gli schizzi per ciascun prodotto. Puoi anche stimare la durata mediana della visita con gli schizzi dei quantili, che puoi unire ed eseguire query.

Ad esempio, la seguente query utilizza gli schizzi HLL++ e KLL per stimare gli utenti unici e la durata mediana della visita per YouTube (Prodotto A) e Google Maps (Prodotto B):

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

Poiché uno schizzo ha una compressione con perdita dei dati originali, introduce un errore statistico rappresentato da un limite di errore o intervallo di confidenza (CI). Per la maggior parte delle applicazioni, questa incertezza è minima. Ad esempio, uno schizzo tipico di conteggio della cardinalità ha un errore relativo di circa l'1% nel 95% dei casi. Uno schizzo sacrifica un po' di accuratezza, o precisione, per calcoli più rapidi ed economici e meno spazio di archiviazione.

In sintesi, uno schizzo ha le seguenti proprietà principali:

• Rappresenta un aggregato approssimativo per una metrica specifica
• È compatto
• È una forma serializzata di una struttura di dati in memoria sublineare
• In genere ha una dimensione fissa e asintoticamente inferiore rispetto all'input
• Può introdurre un errore statistico che determini con un livello di precisione
• Può essere unito ad altri schizzi per riassumere l'unione dei set di dati sottostanti

Aggregazione con unione degli schizzi

Gli schizzi consentono di archiviare e unire i dati per una riaggregazione efficiente. Ciò rende gli schizzi particolarmente utili per le viste materializzate dei set di dati. Puoi unire gli schizzi per creare un riepilogo di più stream di dati in base agli schizzi parziali creati per ogni stream.

Ad esempio, se crei uno schizzo per il numero stimato di utenti unici ogni giorno, puoi ottenere il numero di utenti unici negli ultimi sette giorni unendo gli schizzi giornalieri. La riaggregazione degli sketch giornalieri uniti ti aiuta a evitare di leggere l'intero input del set di dati.

La riaggregazione degli schizzi è utile anche nell'elaborazione analitica online (OLAP). Puoi unire gli schizzi per creare un riepilogo di un cubo OLAP, in cui lo schizzo riepiloga i dati lungo una o più dimensioni specifiche del cubo. I roll-up OLAP non sono possibili con i conteggi univoci effettivi.

Quale tipo di schizzo devo utilizzare?

Diversi algoritmi di sketching sono progettati per diversi tipi di metriche, ad esempio HLL++ per i conteggi distinti e KLL per i quantili. GoogleSQL fornisce anche funzioni di aggregazione approssimativa che puoi utilizzare per eseguire query su questi tipi di dati senza dover specificare i dettagli della query, ad esempio il livello di precisione.

Lo schizzo che utilizzi dipende dal tipo di dati che devi stimare.

Stima della cardinalità

Se devi stimare la cardinalità, utilizza uno sketch HLL++.

Ad esempio, per ottenere il numero di utenti unici che hanno utilizzato attivamente un prodotto in un determinato mese (metriche MAU o 28DAU), utilizza uno sketch HLL++.

Calcolare un quantile

Se devi ottenere un quantile di un set di dati, utilizza uno schizzo KLL.

Ad esempio, per ottenere la durata mediana della visita dei clienti in un negozio o per monitorare la latenza del 95° percentile dei ticket in una coda prima di essere gestiti, utilizza uno schizzo KLL.

Sketch HLL++

HyperLogLog++ (HLL++) è un algoritmo di sketching per la stima della cardinalità. HLL++ si basa sull'articolo HyperLogLog in Practice, in cui ++ indica i miglioramenti apportati all'algoritmo HyperLogLog.

Cardinalità è il numero di elementi distinti nell'input per uno schizzo. Ad esempio, puoi utilizzare uno sketch HLL++ per ottenere il numero di utenti unici che hanno aperto un'applicazione.

HLL++ stima cardinalità molto piccole e molto grandi. HLL++ include una funzione hash a 64 bit, una rappresentazione sparsa per ridurre i requisiti di memoria per le stime di cardinalità ridotta e una correzione empirica della distorsione per le stime di cardinalità ridotta.

Precisione

Gli sketch HLL++ supportano la precisione personalizzata. La tabella seguente mostra i valori di precisione supportati, le dimensioni massime dello spazio di archiviazione e l'intervallo di confidenza (CI) dei livelli di precisione tipici:

Puoi definire la precisione per uno schizzo HLL++ quando lo inizializzi con la funzione HLL_COUNT.INIT.

Eliminazione

Non puoi eliminare i valori da uno sketch HLL++.

Ulteriori dettagli

Per un elenco delle funzioni che puoi utilizzare con gli sketch HLL++, consulta Funzioni HLL++.

Integrazione di Sketch

Puoi integrare gli sketch HLL++ con altri sistemi. Ad esempio, puoi creare schizzi in applicazioni esterne, come Dataflow, Apache Spark e ZetaSketch, e poi utilizzarli in GoogleSQL o viceversa.

Oltre a GoogleSQL, puoi utilizzare gli sketch HLL++ con Java.

KLL sketches

KLL (abbreviazione di Karnin-Lang-Liberty) è un algoritmo di streaming per calcolare gli schizzi per i quantili approssimativi. Calcola quantili arbitrari in modo molto più efficiente rispetto ai calcoli esatti al prezzo di un piccolo errore di approssimazione.

Precisione

Gli schizzi KLL supportano la precisione personalizzata. La precisione definisce l'esattezza di un quantile approssimativo q restituito.

Per impostazione predefinita, il rango di un quantile approssimativo può differire al massimo di ±1/1000 * n da ⌈Φ * n⌉, dove n è il numero di righe nell'input e ⌈Φ * n⌉ è il rango del quantile esatto.

Se fornisci una precisione personalizzata, il rango del quantile approssimativo può differire al massimo di ±1/precision * n dal rango del quantile esatto. L'errore rientra in questo limite di errore nel 99,999% dei casi. Questa garanzia di errore si applica solo alla differenza tra i ranking esatti e approssimativi. La differenza numerica tra il valore esatto e quello approssimato per un quantile può essere arbitrariamente grande.

Ad esempio, supponiamo di voler trovare il valore mediano, Φ = 0.5, e di utilizzare la precisione predefinita di 1000. Il rango del valore restituito dalla funzione KLL_QUANTILES.EXTRACT_POINT differisce dal rango effettivo al massimo di n/1000 nel 99,999% dei casi. In altre parole, il valore restituito è quasi sempre compreso tra il 49,9° e il 50,1° percentile. Se hai 1.000.000 di elementi nello schizzo, il rango della mediana restituita è quasi sempre compreso tra 499.000 e 501.000.

Se utilizzi una precisione personalizzata di 100 per trovare il valore mediano, il rango del valore restituito dalla funzione KLL_QUANTILES.EXTRACT_POINT differisce dal rango effettivo al massimo di n/100 nel 99,999% dei casi. In altre parole, il valore restituito è quasi sempre compreso tra il 49° e il 51° percentile. Se hai 1.000.000 di elementi nello schizzo, il rango della mediana restituita è quasi sempre compreso tra 490.000 e 510.000.

Puoi definire la precisione per uno schizzo KLL quando lo inizializzi con la funzione KLL_QUANTILES.INIT.

Dimensioni

Le dimensioni dello schizzo KLL dipendono dal parametro di precisione e dal tipo di input. Se il tipo di input è INT64, gli schizzi possono utilizzare un'ulteriore ottimizzazione particolarmente utile se i valori di input provengono da un universo ridotto. La tabella seguente contiene due colonne per INT64. Una colonna fornisce un limite superiore per le dimensioni dello schizzo per gli elementi di un universo limitato di dimensioni 1 miliardo, mentre una seconda colonna fornisce un limite superiore per valori di input arbitrari.

Phi

Phi (Φ) rappresenta il quantile da produrre come frazione del numero totale di righe nell'input dello schizzo, normalizzato tra 0 e 1. Se una funzione supporta phi, restituisce un valore v tale che circa Φ * n input siano minori o uguali a v e (1-Φ) * n input siano maggiori o uguali a v.

Ulteriori dettagli

Per un elenco delle funzioni che puoi utilizzare con gli schizzi KLL, consulta Funzioni quantile KLL.

L'algoritmo KLL è definito nell'articolo Optimal Quantile Approximation in Streams e prende il nome dai suoi autori, Karnin, Lang e Liberty, che lo hanno pubblicato nel 2016. L'algoritmo KLL migliora il precedente algoritmo MP80 utilizzando buffer di dimensioni variabili per ridurre l'utilizzo di memoria per set di dati di grandi dimensioni, riducendo le dimensioni dello schizzo da O(log n) a O(1). A causa della natura non deterministica dell'algoritmo, gli schizzi creati sullo stesso insieme di dati con la stessa precisione potrebbero non essere identici.

Quantili

I quantili sono punti di taglio che dividono l'intervallo di una distribuzione di probabilità in intervalli continui con probabilità uguali oppure dividono le osservazioni in un campione nello stesso modo. Uno schizzo che supporta i quantili consente di stimare i quantili riepilogando gli intervalli e le probabilità in risultati di quantili quasi esatti.

I quantili vengono in genere definiti in due modi:

• Per un numero intero positivo q, i q-quantili sono un insieme di valori che partizionano un insieme di input in q sottoinsiemi di dimensioni quasi uguali. Alcuni di questi hanno nomi specifici: il singolo 2-quantile è la mediana, i 4-quantili sono quartili, i 100-quantili sono percentili e così via. Le funzioni KLL restituiscono inoltre il minimo e il massimo (esatti) dell'input, quindi quando si esegue una query per i 2-quantili, vengono restituiti tre valori.

• In alternativa, i quantili possono essere considerati singoli Φ-quantili, dove Φ è un numero reale con 0 <= Φ <= 1. Il Φ-quantile x è un elemento dell'input tale che una frazione Φ dell'input sia minore o uguale a x e una frazione (1-Φ) sia maggiore o uguale a x. In questa notazione, la mediana è il quantile 0,5 e il 95° percentile è il quantile 0,95.

Ad esempio, puoi utilizzare uno schizzo che supporta i quantili per ottenere la mediana del numero di volte in cui un'applicazione viene aperta dagli utenti.

Funzioni di aggregazione approssimativa

In alternativa a funzioni di approssimazione specifiche basate su schizzi, GoogleSQL fornisce funzioni di aggregazione approssimativa predefinite. Queste funzioni aggregate approssimative supportano gli schizzi per le stime comuni come conteggio distinto, quantili e conteggio principale, ma non consentono una precisione personalizzata. Inoltre, non espongono e memorizzano lo schizzo per la riaggregazione come altri tipi di schizzi. Le funzioni di aggregazione approssimativa sono progettate per eseguire query rapide basate su schizzi senza una configurazione dettagliata.

Per un elenco delle funzioni di aggregazione approssimativa che puoi utilizzare con l'approssimazione basata sullo schizzo, consulta Funzioni di aggregazione approssimativa.