Sketsa

GoogleSQL untuk BigQuery mendukung sketsa data. Sketsa data adalah ringkasan singkat dari penggabungan data. Fungsi ini menangkap semua informasi yang diperlukan untuk mengekstrak hasil penggabungan, melanjutkan penggabungan data, atau menggabungkannya dengan sketsa lain, sehingga memungkinkan penggabungan ulang.

Menghitung metrik menggunakan sketsa jauh lebih murah daripada menghitung nilai pasti. Jika komputasi Anda terlalu lambat atau memerlukan terlalu banyak penyimpanan sementara, gunakan sketsa untuk mengurangi waktu dan resource kueri.

Selain itu, menghitung kardinalitas, seperti jumlah pengguna yang berbeda, atau kuantil, seperti durasi kunjungan median, tanpa sketsa biasanya hanya dapat dilakukan dengan menjalankan tugas pada data mentah karena data yang sudah digabungkan tidak dapat digabungkan lagi.

Pertimbangkan tabel dengan data berikut:

Produk Jumlah pengguna Durasi kunjungan median
Produk A 500 juta 10 menit
Produk B 20 juta 2 menit

Menghitung jumlah total pengguna untuk kedua produk tidak memungkinkan karena kami tidak tahu jumlah pengguna yang menggunakan kedua produk tersebut di tabel. Demikian pula, penghitungan median durasi kunjungan tidak dapat dilakukan karena distribusi durasi kunjungan telah hilang.

Solusinya adalah menyimpan sketsa dalam tabel. Setiap sketsa adalah representasi perkiraan dan ringkas dari properti input tertentu, seperti kardinalitas, yang dapat Anda simpan, gabungkan (atau digabungkan ulang), dan kueri untuk hasil yang hampir sama persis. Pada contoh sebelumnya, Anda dapat memperkirakan jumlah pengguna yang berbeda untuk Produk A dan Produk B dengan membuat dan menggabungkan (menggabungkan ulang) sketsa untuk setiap produk. Anda juga dapat memperkirakan durasi kunjungan median dengan sketsa kuantil yang juga dapat Anda gabungkan dan di-kueri.

Misalnya, kueri berikut menggunakan sketsa HLL++ dan KLL untuk memperkirakan pengguna unik dan durasi kunjungan median untuk YouTube (Produk A) dan Google Maps (Produk 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
  );

Karena memiliki kompresi lossy terhadap data asli, sketsa menyebabkan error statistik yang dinyatakan oleh batas error atau interval keyakinan (CI). Untuk sebagian besar aplikasi, ketidakpastian ini cukup kecil. Misalnya, sketsa penghitungan kardinalitas umum memiliki error relatif sekitar 1% dalam 95% dari semua kasus. Sketsa mengorbankan sejumlah akurasi, atau presisi, untuk komputasi yang lebih cepat dan lebih murah, serta lebih sedikit menggunakan penyimpanan.

Singkatnya, sketsa memiliki sifat-sifat utama berikut:

  • Merepresentasikan perkiraan gabungan untuk metrik tertentu
  • Bentuknya ringkas
  • Adalah bentuk serial dari struktur data sublinear dalam memori
  • Biasanya berukuran tetap dan secara asimetris lebih kecil daripada input
  • Dapat menyebabkan error statistik yang Anda tentukan dengan tingkat presisi
  • Dapat digabungkan dengan sketsa lain untuk meringkas penyatuan set data yang mendasarinya

Penggabungan ulang dengan penggabungan sketsa

Sketsa memungkinkan Anda menyimpan dan menggabungkan data untuk penggabungan ulang secara efisien. Hal ini membuat sketsa sangat berguna untuk tampilan terwujud set data. Anda dapat menggabungkan sketsa untuk membuat ringkasan beberapa aliran data berdasarkan sebagian sketsa yang dibuat untuk setiap aliran.

Misalnya, jika Anda membuat sketsa untuk estimasi jumlah pengguna yang berbeda setiap hari, Anda bisa mendapatkan jumlah pengguna unik selama tujuh hari terakhir dengan menggabungkan sketsa harian. Menggabungkan ulang sketsa harian yang digabungkan membantu Anda menghindari membaca input penuh dari set data.

Penggabungan ulang sketsa juga berguna dalam pemrosesan analisis online (OLAP). Anda dapat menggabungkan sketsa untuk membuat tampilan gabungan dari Kubus OLAP, dengan sketsa tersebut merangkum data bersama satu atau beberapa dimensi kubus yang spesifik. Tampilan gabungan OLAP tidak mungkin dilakukan dengan jumlah berbeda yang sebenarnya.

Jenis sketsa mana yang harus saya gunakan?

Berbagai algoritma pembuatan sketsa dirancang untuk berbagai jenis metrik, seperti HLL++ untuk jumlah unik dan KLL untuk kuartil. GoogleSQL juga menyediakan Fungsi agregat perkiraan yang dapat Anda gunakan untuk membuat kueri jenis data ini tanpa harus menentukan detail kueri seperti tingkat presisi.

Sketsa yang Anda gunakan bergantung pada jenis data yang perlu Anda estimasi.

Perkiraan kardinalitas

Jika Anda perlu memperkirakan kardinalitas, gunakan sketsa HLL++.

Misalnya, untuk mendapatkan jumlah pengguna unik yang secara aktif menggunakan produk dalam bulan tertentu (metrik MAU atau 28DAU), gunakan sketsa HLL++.

Menghitung kuantil

Jika Anda perlu mendapatkan kuartil set data, gunakan sket KLL.

Misalnya, untuk mendapatkan median durasi kunjungan pelanggan di toko, atau untuk melacak latensi persentil ke-95 saat tiket tetap berada dalam antrean sebelum ditangani, gunakan sketsa KLL.

Sketsa HLL++

HyperLogLog++ (HLL++) adalah algoritma pembuatan sketsa untuk memperkirakan kardinalitas. HLL++ didasarkan pada makalah HyperLogLog in Practice, dengan ++ menunjukkan augmentasi yang dilakukan pada algoritma HyperLogLog.

Kardinalitas adalah jumlah elemen berbeda dalam input untuk sketsa. Misalnya, Anda dapat menggunakan sketsa HLL++ untuk mendapatkan jumlah pengguna unik yang telah membuka aplikasi.

HLL++ memperkirakan kardinalitas yang sangat kecil dan sangat besar. HLL++ mencakup fungsi hash 64-bit, representasi renggang untuk mengurangi persyaratan memori untuk estimasi kardinalitas kecil, dan koreksi bias empiris untuk estimasi kardinalitas kecil.

Presisi

Sketsa HLL++ mendukung presisi kustom. Tabel berikut menunjukkan nilai presisi yang didukung, ukuran penyimpanan maksimum, dan interval keyakinan (CI) untuk tingkat presisi standar:

Presisi Ukuran penyimpanan maksimum 65% CI 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 (default) 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 16384 KiB + 32 B ±0.03% ±0.05% ±0.08%

Anda dapat menentukan presisi untuk sketsa HLL++ saat menginisialisasinya dengan fungsi HLL_COUNT.INIT.

Penghapusan

Anda tidak dapat menghapus nilai dari sketsa HLL++.

Detail tambahan

Untuk daftar fungsi yang dapat Anda gunakan dengan sketsa HLL++, lihat fungsi HLL++.

Integrasi sketsa

Anda dapat mengintegrasikan sketsa HLL++ dengan sistem lain. Misalnya, Anda dapat membuat sketsa di aplikasi eksternal, seperti Dataflow, Apache Spark, dan ZetaSketch, lalu menggunakannya di GoogleSQL atau sebaliknya.

Selain GoogleSQL, Anda dapat menggunakan sketsa HLL++ dengan Java.

Sketsa KLL

KLL (singkatan dari Karnin-Lang-Liberty) adalah algoritma streaming untuk menghitung sketsa untuk perkiraan kuantil. Fungsi ini menghitung kuartil arbitrer jauh lebih efisien daripada komputasi yang tepat dengan mengorbankan error perkiraan kecil.

Presisi

Sketsa KLL mendukung presisi kustom. Presisi menentukan ketepatan kuartil perkiraan q yang ditampilkan.

Secara default, peringkat kuantil perkiraan dapat menyimpang maksimum ±1/1000 * n dari ⌈Φ * n⌉, dengan n adalah jumlah baris dalam input dan ⌈Φ * n⌉ adalah peringkat kuantil yang tepat.

Jika Anda memberikan presisi kustom, peringkat kuantil perkiraan dapat maksimal ±1/precision * n dari peringkat kuantil yang tepat. Error berada dalam batas error ini dalam 99,999% kasus. Jaminan error ini hanya berlaku untuk perbedaan antara peringkat yang tepat dan perkiraan. Perbedaan numerik antara nilai persis dan nilai perkiraan untuk kuartil dapat sangat besar.

Misalnya, Anda ingin menemukan nilai median, Φ = 0.5, dan Anda menggunakan presisi default 1000. Kemudian, peringkat nilai yang ditampilkan oleh fungsi KLL_QUANTILES.EXTRACT_POINT berbeda dengan peringkat sebenarnya paling banyak n/1000 dalam 99,999% kasus. Dengan kata lain, nilai yang ditampilkan hampir selalu berada antara persentil ke-49,9 dan ke-50,1. Jika Anda memiliki 1.000.000 item dalam skets, peringkat median yang ditampilkan hampir selalu antara 499.000 dan 501.000.

Jika Anda menggunakan presisi kustom 100 untuk menemukan nilai median, peringkat nilai yang ditampilkan oleh fungsi KLL_QUANTILES.EXTRACT_POINT akan berbeda dengan peringkat sebenarnya paling banyak n/100 dalam 99,999% kasus. Dengan kata lain, nilai yang ditampilkan hampir selalu antara persentil ke-49 dan ke-51. Jika Anda memiliki 1.000.000 item dalam sketsa, peringkat median yang ditampilkan hampir selalu antara 490.000 dan 510.000.

Anda dapat menentukan presisi untuk sketsa KLL saat menginisialisasinya dengan fungsi KLL_QUANTILES.INIT.

Ukuran

Ukuran sketsa KLL bergantung pada parameter presisi dan jenis input. Jika jenis input Anda adalah INT64, sketsa dapat menggunakan pengoptimalan tambahan yang sangat membantu jika nilai input berasal dari alam semesta kecil. Tabel berikut berisi dua kolom untuk INT64. Satu kolom memberikan batas atas ukuran sketsa untuk item dari alam semesta terbatas berukuran 1B, dan kolom kedua memberikan batas atas untuk nilai input arbitrer.

Presisi FLOAT64 INT64 (<1B) INT64 (Semua)
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 (Φ) mewakili kuartil yang akan dihasilkan sebagai fraksi dari jumlah total baris dalam input sketsa, yang dinormalisasi antara 0 dan 1. Jika fungsi mendukung phi, fungsi akan menampilkan nilai v sehingga input Φ * n kurang dari atau sama dengan v, dan input (1-Φ) * n lebih besar dari atau sama dengan v.

Detail tambahan

Untuk daftar fungsi yang dapat Anda gunakan dengan sketsa KLL, lihat fungsi kuartil KLL.

Algoritma KLL ditentukan dalam makalah Optimal Quantile Approximation in Streams, dan diberi nama setelah penulisnya, Karnin, Lang, dan Liberty, yang memublikasikan makalah tersebut pada tahun 2016. Algoritma KLL meningkatkan algoritma MP80 yang lebih lama dengan menggunakan buffer berukuran variabel untuk mengurangi penggunaan memori untuk set data besar, sehingga mengurangi ukuran sketsa dari O(log n) menjadi O(1). Karena sifat algoritma yang non-deterministik, sketsa yang dibuat pada kumpulan data yang sama dengan presisi yang sama mungkin tidak identik.

Kuantil

Kuartil adalah titik pemotongan yang membagi rentang distribusi probabilitas menjadi interval berkelanjutan dengan probabilitas yang sama, atau membagi pengamatan dalam sampel dengan cara yang sama. Sketsa pendukung kuartil memungkinkan Anda memperkirakan kuartil dengan meringkas interval dan probabilitas tersebut menjadi hasil kuartil yang hampir sama persis.

Kuartil biasanya ditentukan dengan dua cara:

  • Untuk bilangan bulat positif q, kuantil q adalah kumpulan nilai yang mempartisi kumpulan input menjadi q subset dengan ukuran yang hampir sama. Beberapa di antaranya memiliki nama tertentu: satu kuartil 2 adalah median, kuartil 4 adalah kuartil, kuartil 100 adalah persentil, dll. Fungsi KLL juga menampilkan minimum (persis) dan maksimum input, sehingga saat membuat kueri untuk kuartil 2, tiga nilai akan ditampilkan.

  • Atau, kuartil dapat dianggap sebagai kuartil Φ individual, dengan Φ adalah bilangan riil dengan 0 <= Φ <= 1. Kuantil Φ x adalah elemen input sehingga fraksi Φ input kurang dari atau sama dengan x, dan fraksi (1-Φ) lebih besar dari atau sama dengan x. Dalam notasi ini, median adalah kuartil 0,5, dan persentil ke-95 adalah kuartil 0,95.

Misalnya, Anda dapat menggunakan sketsa yang mendukung kuartil untuk mendapatkan median jumlah kali aplikasi dibuka oleh pengguna.

Fungsi perkiraan agregat

Sebagai alternatif fungsi perkiraan berbasis sketsa tertentu, GoogleSQL menyediakan fungsi agregat perkiraan yang telah ditetapkan sebelumnya. Fungsi agregat perkiraan ini mendukung sketsa untuk estimasi umum seperti jumlah, kuantil, dan jumlah teratas yang berbeda, tetapi tidak memungkinkan presisi kustom. Fungsi ini juga tidak mengekspos dan menyimpan sketsa untuk penggabungan ulang seperti jenis sketsa lainnya. Fungsi agregat perkiraan dirancang untuk menjalankan kueri cepat berbasis sketsa tanpa konfigurasi mendetail.

Untuk daftar fungsi agregat perkiraan yang dapat Anda gunakan dengan perkiraan berbasis sketsa, lihat Fungsi agregat perkiraan.