Hapus duplikat dengan menggunakan fitur HLL di ApsaraDB for SelectDB - ApsaraDB for SelectDB

HyperLogLog (HLL) adalah algoritma deduplikasi perkiraan yang tertanam dalam ApsaraDB for SelectDB. Ketika nilai unik eksak tidak diperlukan, HLL berjalan lebih cepat dan menggunakan jauh lebih sedikit memori dibandingkan COUNT DISTINCT — sehingga cocok untuk beban kerja analitik skala besar seperti penghitungan pengunjung unik harian (UV) dan statistik tayangan halaman.

HLL mencapai kompleksitas ruang sebesar O(log(logn)) dan kompleksitas waktu sebesar O(n). Laju kesalahan tipikal berkisar antara 1%–2%, tergantung pada ukuran set data dan fungsi hash yang digunakan.

Kapan menggunakan HLL

Gunakan HLL ketika kedua kondisi berikut terpenuhi:

Set data berukuran besar dan volumenya telah mencapai skala di mana biaya deduplikasi akurat menjadi tinggi.
Hasil perkiraan dapat diterima — misalnya, penghitungan UV harian atau statistik tayangan halaman.

Untuk deduplikasi eksak, gunakan COUNT DISTINCT sebagai gantinya.

Cara kerja HLL

HLL merupakan versi peningkatan dari algoritma LogLog. Dasar matematisnya adalah percobaan Bernoulli.

Dasar matematis

Percobaan Bernoulli adalah eksperimen melempar koin: lempar koin berulang kali hingga sisi depan muncul, lalu catat jumlah lemparan sebagai k. Ulangi eksperimen ini sebanyak n kali. Jumlah maksimum lemparan di seluruh percobaan adalah k_max.

Menggunakan estimasi kemungkinan maksimum (maximum likelihood estimation/ MLE), kardinalitas yang diestimasi (jumlah total nilai unik) adalah:

n = 2^k_max

Mencatat hanya k_max sudah cukup untuk mengestimasi kardinalitas — Anda tidak perlu menyimpan nilai mentahnya.

Kesalahan estimasi

Satu putaran estimasi memiliki laju kesalahan tinggi ketika n kecil. Misalnya, setelah tiga percobaan dengan k_max = 6, rumus menghasilkan 2^6 = 64, yang jauh dari nilai aktual n = 3. Kesalahan berkurang seiring bertambahnya jumlah percobaan.

Implementasi HLL di SelectDB

Fitur HLL di SelectDB merupakan implementasi rekayasa dari algoritma HLL. Kolom HLL menyimpan status komputasi antara, bukan nilai mentah. SelectDB secara terus-menerus mengagregasi status ini untuk mengurangi volume data dan mempercepat kueri. Laju kesalahan hasil estimasi yang diperoleh dengan menggunakan fitur HLL sekitar 1%.

HLL hanya dapat digunakan sebagai kolom nilai (bukan kolom kunci), dengan tipe agregasi HLL_UNION. Sistem menentukan panjang kolom secara otomatis berdasarkan tingkat agregasi; Anda tidak perlu menentukan panjang atau nilai default.

HLL umumnya digunakan untuk menggantikan COUNT DISTINCT dan bekerja bersama fitur ROLLUP untuk menghitung jumlah UV secara efisien dalam rentang waktu tertentu.

Fungsi HLL

Function	Description
`HLL_UNION_AGG(hll)`	Fungsi agregasi. Menghitung kardinalitas perkiraan di seluruh baris yang sesuai dengan kondisi kueri.
`HLL_CARDINALITY(hll)`	Menghitung kardinalitas perkiraan untuk satu nilai kolom HLL.
`hll_hash(column_name)`	Menghasilkan nilai kolom HLL dari kolom sumber yang ditentukan. Gunakan fungsi ini saat memasukkan atau mengimpor data.

Catatan

Untuk mengkueri kolom HLL, gunakan HLL_UNION_AGG. Pemilihan langsung nilai mentah kolom HLL tidak didukung.

Hitung pengunjung unik berdasarkan tanggal

Contoh ini membuat tabel agregat, memuat data sampel, dan mengkueri jumlah UV menggunakan HLL.

Langkah 1: Buat tabel dengan kolom HLL

CREATE TABLE test_hll(
    dt date,
    id int,
    name char(10),
    province char(10),
    os char(10),
    pv hll hll_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
    "replication_num" = "1",
    "in_memory"="false"
);

Penting

Saat mendefinisikan kolom HLL:

Tetapkan tipe kolom sebagai hll dan tipe agregasi sebagai hll_union.
Jangan tetapkan kolom HLL sebagai kolom kunci.
Jangan tentukan panjang atau nilai default — sistem akan mengatur panjang secara otomatis.

Langkah 2: Impor data

Siapkan file CSV (test_hll.csv) dengan konten berikut:

2022-05-05,10001,Test 01,Beijing,windows
2022-05-05,10002,Test 01,Beijing,linux
2022-05-05,10003,Test 01,Beijing,macos
2022-05-05,10004,Test 01,Hebei,windows
2022-05-06,10001,Test 01,Shanghai,windows
2022-05-06,10002,Test 01,Shanghai,linux
2022-05-06,10003,Test 01,Jiangsu,macos
2022-05-06,10004,Test 01,Shaanxi,windows

Semua metode impor menggunakan hll_hash(id) untuk mengisi kolom HLL pv dari kolom id.

Stream Load

curl --location-trusted -u root: \
  -H "label:label_test_hll_load" \
  -H "column_separator:," \
  -H "columns:dt,id,name,province,os,pv=hll_hash(id)" \
  -T test_hll.csv \
  http://127.0.0.1:8030/api/demo/test_hll/_stream_load

Pemuatan yang berhasil mengembalikan:

{
    "TxnId": 693,
    "Label": "label_test_hll_load",
    "TwoPhaseCommit": "false",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 8,
    "NumberLoadedRows": 8,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 320,
    "LoadTimeMs": 23,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 9,
    "CommitAndPublishTimeMs": 11
}

Broker Load

LOAD LABEL demo.test_hlllabel
(
    DATA INFILE("hdfs://hdfs_host:hdfs_port/user/doris_test_hll/data/input/file")
    INTO TABLE `test_hll`
    COLUMNS TERMINATED BY ","
    (dt,id,name,province,os)
    SET (
        pv = HLL_HASH(id)
    )
);

Langkah 3: Kueri jumlah UV

Total UV di semua tanggal

SELECT HLL_UNION_AGG(pv) FROM test_hll;

+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

Hasil ini setara dengan COUNT(DISTINCT pv):

SELECT COUNT(DISTINCT pv) FROM test_hll;

+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

UV berdasarkan tanggal

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;

+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)