Sketch

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

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

Inoltre, il calcolo delle cardinalità, ad esempio il numero di utenti distinti, o dei quantili, ad esempio la durata mediana della visita, senza sketch è in genere 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é la tabella non mostra quanti utenti hanno utilizzato entrambi i prodotti. Allo stesso modo, il calcolo della durata mediana della visita non è possibile perché la distribuzione delle durate delle visite è andata persa.

Una soluzione consiste nell'archiviare gli sketch nella tabella. Ogni sketch è 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 distinti per il Prodotto A e il Prodotto B creando e unendo (riaggregando) gli sketch per ogni prodotto. Puoi anche stimare la durata mediana della visita con gli sketch di quantili che puoi unire ed eseguire query.

Ad esempio, la seguente query utilizza gli sketch HLL++ e KLL per stimare gli utenti distinti 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 sketch ha una compressione con perdita dei dati originali, introduce un errore statistico rappresentato da un limite di errore o da un intervallo di affidabilità (CI). Per la maggior parte delle applicazioni, questa incertezza è piccola. Ad esempio, uno sketch tipico di conteggio della cardinalità ha un errore relativo di circa l'1% nel 95% di tutti i casi. Uno sketch scambia una certa accuratezza, o precisione, con calcoli più veloci ed economici e meno spazio di archiviazione.

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

• Rappresenta un'aggregazione approssimativa per una metrica specifica
• È compatto
• È una forma serializzata di una struttura di dati in memoria, sublineare
• In genere è di dimensioni fisse e asintoticamente più piccolo dell'input
• Può introdurre un errore statistico che determini con un livello di precisione
• Può essere unito ad altri sketch per riepilogare l'unione dei set di dati sottostanti

Riaggregazione con unione di sketch

Gli sketch consentono di archiviare e unire i dati per una riaggregazione efficiente. Ciò rende gli sketch particolarmente utili per archiviare riepiloghi precalcolati dei set di dati, noti come visualizzazioni materializzate. Puoi unire gli sketch per creare un riepilogo di più flussi di dati in base agli sketch parziali creati per ogni flusso.

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

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

Quale tipo di sketch 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, come il livello di precisione.

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

Stimare la 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 sketch 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 coda prima di essere gestiti, utilizza uno sketch KLL.

Sketch HLL++

HyperLogLog++ (HLL++) è un algoritmo di sketching per la stima della cardinalità. HLL++ si basa sul documento HyperLogLog in Practice, in cui ++ indica gli aumenti apportati all'algoritmo HyperLogLog.

La cardinalità è il numero di elementi distinti nell' input per uno sketch. 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à ridotte e una correzione empirica della distorsione per le stime di cardinalità ridotte.

Precisione

Gli sketch HLL++ supportano la precisione personalizzata. La tabella seguente mostra i valori di precisione supportati, la dimensione massima di archiviazione e l'intervallo di affidabilità (CI) dei livelli di precisione tipici:

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

Eliminazione

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

Dettagli aggiuntivi

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 sketch 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.

Sketch KLL

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

Precisione

Gli sketch 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ò essere al massimo ±1/1000 * n off 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ò essere al massimo ±1/precision * n rispetto al 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 ranghi esatti e approssimativi. La differenza numerica tra il valore esatto e quello approssimativo 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. In questo caso, 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 nello sketch sono presenti 1.000.000 di elementi, 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 nello sketch sono presenti 1.000.000 di elementi, il rango della mediana restituita è quasi sempre compreso tra 490.000 e 510.000.

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

Dimensioni

Le dimensioni dello sketch KLL dipendono dal parametro di precisione e dal tipo di input. Se il tipo di input è INT64, gli sketch 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 sketch per gli elementi di un universo limitato di dimensioni 1B, mentre una seconda colonna fornisce un limite superiore per i valori di input arbitrari.

Phi

Phi (Φ) rappresenta il quantile da produrre come frazione del numero totale di righe nell'input dello sketch, 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.

Dettagli aggiuntivi

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

L'algoritmo KLL è definito nel documento Optimal Quantile Approximation in Streams e prende il nome dai suoi autori, Karnin, Lang e Liberty, che hanno pubblicato il documento nel 2016. L'algoritmo KLL migliora il precedente algoritmo MP80 utilizzando buffer di dimensioni variabili per ridurre l'utilizzo della memoria per i set di dati di grandi dimensioni, riducendo le dimensioni dello sketch da O(log n) a O(1). A causa della natura non deterministica dell'algoritmo, gli sketch creati sullo stesso set 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 o che dividono le osservazioni in un campione nello stesso modo. Uno sketch che supporta i quantili consente di stimare i quantili riepilogando questi intervalli e probabilità in risultati di quantili quasi esatti.

I quantili sono in genere definiti in due modi:

• Per un numero intero positivo q, i q-quantili sono un insieme di valori che partizionano un set 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 esegui una query per i 2-quantili, vengono restituiti tre valori.

• In alternativa, i quantili potrebbero 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 sketch 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 alle funzioni di approssimazione specifiche basate su sketch, GoogleSQL fornisce funzioni di aggregazione approssimativa predefinite. Queste funzioni di aggregazione approssimativa supportano gli sketch per le stime comuni, come conteggio distinto, quantili e conteggio principale, ma non consentono la precisione personalizzata. Inoltre, non espongono e archiviano lo sketch per la riaggregazione come altri tipi di sketch. Le funzioni di aggregazione approssimativa sono progettate per eseguire query rapide basate su sketch senza una configurazione dettagliata.

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