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

Topik ini menjelaskan cara menggunakan fitur HyperLogLog (HLL) yang disediakan oleh ApsaraDB for SelectDB untuk menghapus duplikat dan mempercepat kueri.

Ikhtisar

Dalam skenario bisnis nyata, tekanan pada deduplikasi data meningkat seiring dengan pertumbuhan jumlah data bisnis. Jika jumlah data mencapai skala tertentu, biaya deduplikasi akurat juga meningkat. Jika dapat diterima, Anda dapat menggunakan algoritma deduplikasi perkiraan untuk dengan cepat menghapus duplikat dan mengurangi tekanan pada perhitungan.

ApsaraDB for SelectDB menyediakan algoritma HLL untuk membantu Anda menerapkan deduplikasi perkiraan. HLL mendukung kompleksitas ruang yang sangat baik dalam format O(log(logn)) dan kompleksitas waktu dalam format O(n). Tingkat kesalahan hasil perhitungan dapat dikontrol sekitar 1% hingga 2%. Tingkat kesalahan tergantung pada ukuran set data dan fungsi hash yang digunakan.

Cara kerja HLL

Algoritma HLL adalah versi peningkatan dari algoritma LogLog dan mendukung deduplikasi perkiraan. Dasar matematikanya adalah uji Bernoulli.

Dasar matematika

Sebuah koin memiliki dua sisi. Kemungkinan sisi depan atau belakang koin muncul adalah 50% setelah koin dilempar. Terus lemparkan koin sampai sisi depan koin muncul, yang dicatat sebagai uji Bernoulli penuh. Dengan cara ini, jika n uji Bernoulli dilakukan, sisi depan koin muncul n kali.

Sebagai contoh, koin dilempar k kali dalam uji Bernoulli. Jumlah kali koin dilempar dalam uji Bernoulli pertama adalah k1. Pada uji Bernoulli ke-n, jumlah kali koin dilempar adalah kn. Nilai n meningkat dengan jumlah uji Bernoulli. Di antara uji Bernoulli, jumlah maksimum kali koin dilempar bisa k, yang menunjukkan bahwa sisi depan koin muncul setelah koin dilempar k kali. Jumlah maksimum kali koin dilempar dinamai k_max. Kesimpulan berikut dapat ditarik berdasarkan uji Bernoulli:

kn tidak lebih besar dari k_max.
kn sama dengan k_max dalam setidaknya satu uji Bernoulli.

Digabungkan dengan metode estimasi kemungkinan maksimum (MLE), korelasi estimasi berikut ada antara n dan k_max: n = 2^k_max. Jika Anda hanya mencatat k_max, Anda dapat memperkirakan jumlah total catatan data, yaitu kardinalitas.

Kesalahan estimasi

Jika hasil berikut diperoleh:

Pada tes pertama, koin dilempar tiga kali hingga sisi depan muncul. Dalam hal ini, k = 3 dan n = 1.
Pada tes kedua, koin dilempar dua kali hingga sisi depan muncul. Dalam hal ini, k = 2 dan n = 2.
Pada tes ketiga, koin dilempar enam kali hingga sisi depan muncul. Dalam hal ini, k = 6 dan n = 3.
...
Pada tes ke-n, koin dilempar 12 kali hingga sisi depan muncul. Dalam hal ini, n = 2^12.

Berdasarkan tiga tes pertama, k_max = 6 dan n = 3. Jika Anda menerapkan nilai-nilai tersebut ke rumus estimasi, nilai yang dihitung dari 2^6 tidak sama dengan 3. Ini menunjukkan bahwa jika jumlah tes kecil, tingkat kesalahan metode estimasi ini tinggi.

Tiga tes ini membentuk satu putaran estimasi. Jika hanya satu putaran estimasi yang dilakukan dan n besar, tingkat kesalahan estimasi relatif berkurang, tetapi masih belum rendah.

Fungsi HLL

Fitur HLL adalah implementasi teknik berdasarkan algoritma HLL. Fungsi HLL digunakan untuk menyimpan hasil antara selama proses perhitungan berbasis HLL. HLL hanya dapat digunakan sebagai tipe kolom nilai dalam tabel untuk terus mengurangi jumlah data dengan menggabungkan data. Ini mempercepat kueri. Tingkat kesalahan hasil estimasi yang diperoleh dengan menggunakan fitur HLL mencapai sekitar 1%. Kolom HLL dihasilkan dengan menggunakan kolom lain atau data impor. Saat data diimpor, fungsi hll_hash digunakan untuk menentukan kolom yang digunakan untuk menghasilkan kolom HLL dalam data. Fungsi HLL sering digunakan untuk menggantikan fungsi COUNT DISTINCT dan digunakan bersama dengan fungsi ROLLUP untuk dengan cepat menghitung jumlah pengunjung unik (UV).

Fungsi HLL berikut disediakan:

HLL_UNION_AGG(hll)
Fungsi ini adalah fungsi agregat dan digunakan untuk menghitung kardinalitas perkiraan untuk semua data yang memenuhi kondisi.
HLL_CARDINALITY(hll)
Fungsi ini digunakan untuk menghitung kardinalitas perkiraan untuk kolom HLL tunggal.
HLL_HASH(column_name)
Fungsi ini digunakan untuk menghasilkan kolom HLL saat data dimasukkan atau diimpor. Untuk informasi lebih lanjut tentang cara menggunakan fungsi ini, lihat bagian Contoh dari topik ini.

Contoh

Buat tabel yang berisi 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
Perhatikan item berikut saat Anda menggunakan fungsi HLL:
- Saat Anda menggunakan fungsi HLL untuk menghapus duplikat dari kolom, Anda harus menetapkan tipe kolom ke HLL dan tipe agregasi kolom ke HLL_UNION dalam pernyataan CREATE TABLE.
- Kolom HLL tidak dapat digunakan sebagai kolom kunci.
- Anda tidak perlu menentukan panjang atau nilai default untuk kolom HLL. Panjang ditentukan oleh sistem berdasarkan derajat agregasi data.

Impor data.

Impor data sampel berikut dari file test_hll.csv:

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

Impor data dengan menggunakan salah satu metode berikut:

Impor data dengan menggunakan Stream Load. Contoh kode:

# 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

{
    "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
}

Impor data dengan menggunakan Broker Load. Contoh kode:

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

Kueri data.

Anda tidak dapat langsung mengkueri nilai asli kolom HLL. Anda hanya dapat mengkueri nilai asli kolom HLL dengan menggunakan fungsi HLL_UNION_AGG.

Hitung jumlah total tampilan halaman (PV). Contoh kode:

SELECT HLL_UNION_AGG(pv) FROM test_hll;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

Hasil yang dikembalikan setara dengan yang dikembalikan oleh fungsi (DISTINCT pv).

SELECT COUNT(DISTINCT pv) FROM test_hll;
+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

Hitung PV dalam sehari. Contoh kode:

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;
+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)