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 è sostanzialmente meno costoso del calcolo di un valore esatto. Se il calcolo è troppo lento o richiede troppo spazio di archiviazione temporaneo, utilizza gli sketch per ridurre il tempo e le risorse delle query.

Inoltre, il calcolo delle cardinalità, come il numero di utenti distinti, o dei quantili, come la durata media delle visite, senza sketch è 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:

Prodotto Numero di utenti Durata mediana della visita
Prodotto A 500 milioni 10 minuti
Prodotto B 20 milioni 2 minuti

Non è possibile calcolare il numero totale di utenti per entrambi i prodotti perché la tabella non mostra quanti utenti hanno utilizzato entrambi i prodotti. Allo stesso modo, non è possibile calcolare la durata mediana delle visite perché la distribuzione delle durate delle visite è andata persa.

Una soluzione è archiviare gli sketch nella tabella. Ogni sketch è una rappresentazione approssimativa e compatta di una particolare proprietà di input, ad esempio la cardinalità, che puoi archiviare, unire (o riaggregare) e sottoporre a 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 delle visite con gli sketch dei quantili, che puoi unire ed eseguire query allo stesso modo.

Ad esempio, la seguente query utilizza gli sketch HLL++ e KLL per stimare gli utenti distinti e la durata media delle visite 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 di dati 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 è minima. Ad esempio, un tipico sketch di conteggio della cardinalità ha un errore relativo di circa l'1% nel 95% di tutti i casi. Uno sketch sacrifica un po' di accuratezza o precisione per calcoli più rapidi e meno costosi 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 sublineare in memoria
  • In genere ha una dimensione fissa ed è asintoticamente più piccolo dell'input
  • Può introdurre un errore statistico che determini con un livello di precisione
  • Può essere unito ad altri sketch per riassumere l'unione dei set di dati sottostanti

Riaggregazione con unione di sketch

Gli sketch ti consentono di archiviare e unire i dati per una riaggregazione efficiente. Questo rende gli sketch particolarmente utili per archiviare riepiloghi precalcolati di set di dati, noti come viste materializzate. Puoi unire gli sketch per creare un riepilogo di più stream di dati in base agli sketch parziali creati per ogni stream.

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'intero input 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 riassume i dati lungo una o più dimensioni specifiche del cubo. I roll-up OLAP non sono possibili con i conteggi distinti reali.

Quale tipo di sketch devo utilizzare?

Algoritmi di sketching diversi sono progettati per tipi di metriche diversi, come HLL++ per conteggi distinti e KLL per quantili. GoogleSQL fornisce anche funzioni aggregate approssimative 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.

Stima 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 DAU in 28 giorni), utilizza uno sketch HLL++.

Calcola un quantile

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

Ad esempio, per ottenere la durata media delle visite dei clienti in un negozio o per monitorare la latenza del 95° percentile dei ticket che rimangono in una 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, dove ++ indica i miglioramenti apportati all'algoritmo HyperLogLog.

La cardinalità è il numero di elementi distinti nell'input di 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 sparse per ridurre i requisiti di memoria per le stime di cardinalità ridotta e una correzione empirica del bias 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 di archiviazione e l'intervallo di affidabilità (CI) dei livelli di precisione tipici:

Precisione Dimensione massima dello spazio di archiviazione CI 65% 95% CI 99% CI
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 (valore predefinito) 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 1024 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 16.384 KiB + 32 B ±0,03% ±0,05% ±0,08%

Puoi definire la precisione di uno sketch 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 con 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 calcolare gli sketch 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 sketch KLL supportano la precisione personalizzata. La precisione definisce l'esattezza di un quantile approssimativo restituito q.

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

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

Ad esempio, supponiamo che tu voglia trovare il valore mediano, Φ = 0.5, e utilizzi la precisione predefinita di 1000. In questo caso, il ranking del valore restituito dalla funzione KLL_QUANTILES.EXTRACT_POINT differisce dal ranking reale 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 sketch, il ranking 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 ranking del valore restituito dalla funzione KLL_QUANTILES.EXTRACT_POINT differisce dal ranking reale di un 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 sketch, il ranking della mediana restituita è quasi sempre compreso tra 490.000 e 510.000.

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

Dimensioni

La dimensione dello sketch KLL dipende dal parametro di precisione e dal tipo di input. Se il tipo di input è INT64, gli sketch possono utilizzare un'ottimizzazione aggiuntiva, particolarmente utile se i valori di input provengono da un universo di piccole dimensioni. 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 pari a 1 miliardo, mentre una seconda colonna fornisce un limite superiore per i valori di input arbitrari.

Precisione FLOAT64 INT64 (<1B) INT64 (qualsiasi)
10 761 B 360 B 717 B
20 1,46 kB 706 B 1,47 KB
50 3,49 kB 1,72 kB 3,60 kB
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,18 KB 27,86 KB 71,28 KB
2000 144,51 kB 55,25 kB 144,57 KB
5000 368,87 kB 139,54 kB 368,96 kB
10000 749,82 KB 282,27 kB 697,80 kB
20000 1,52 MB 573,16 KB 1,37 MB
50000 3,90 MB 1,12 MB 3,45 MB
100000 7,92 MB 2,18 MB 6,97 MB

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.

Ulteriori dettagli

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

L'algoritmo KLL è definito nel paper Optimal Quantile Approximation in Streams e prende il nome dai suoi autori, Karnin, Lang e Liberty, che hanno pubblicato il paper nel 2016. L'algoritmo KLL migliora il precedente algoritmo MP80 utilizzando buffer di dimensioni variabili per ridurre l'utilizzo della memoria per 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 dividono le osservazioni in un campione nello stesso modo. Uno sketch che supporta i quantili ti consente di stimare i quantili riassumendo questi intervalli e probabilità in risultati dei quantili quasi esatti.

I quantili vengono in genere definiti in due modi:

  • Per un numero intero positivo q, i quantili q sono un insieme di valori che suddividono 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 i quartili, i 100-quantili sono i 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 è minore o uguale a x e una frazione (1-Φ) è 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 basate su sketch specifiche, GoogleSQL fornisce funzioni di aggregazione approssimate predefinite. Queste funzioni aggregate approssimative supportano gli sketch per stime comuni come conteggio distinto, quantili e conteggio massimo, ma non consentono la precisione personalizzata. Inoltre, non espongono e non memorizzano lo sketch per la riaggregazione come altri tipi di sketch. Le funzioni aggregate approssimative sono progettate per eseguire query rapide basate su sketch senza una configurazione dettagliata.

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