Revolusi Estimasi Kardinalitas pada Sistem Basis Data Graf
Estimasi kardinalitas memainkan peran penting dalam kinerja sistem basis data modern, khususnya yang berhubungan dengan graf. Artikel karya Pan Hu dari Shanghai Jiao Tong University dan Boris Motik dari Oxford University yang berjudul Accurate Sampling-Based Cardinality Estimation for Complex Graph Queries menyoroti masalah utama dalam estimasi kardinalitas query yang kompleks. Dengan volume data yang terus meningkat dan kompleksitas hubungan yang berkembang pesat, seperti dalam basis data graf, solusi tradisional sering kali kewalahan. Pada tahun 2024, artikel ini diterbitkan dalam ACM Transactions on Database Systems (Vol. 49, Isu 3) dan menawarkan pendekatan baru yang tidak hanya akurat tetapi juga efisien dalam menangani query graf kompleks.
Melalui metode sampling berbasis WanderJoin yang dimodifikasi, penulis berhasil mengatasi keterbatasan yang ada dalam pendekatan sebelumnya, seperti ketidakmampuan menangani operator bersarang. Dataset besar seperti LUBM-01K-mat dengan lebih dari 132 juta fakta biner dan WatDiv dengan distribusi data nonuniform menjadi arena pengujian yang menantang. Penelitian ini menemukan bahwa algoritma baru ini mampu menghasilkan estimasi yang lebih konsisten dibandingkan metode lainnya, seperti Bounded Sketch (bs) atau Correlated Sampling (cs), bahkan pada query yang kompleks.
Artikel ini memberikan kontribusi nyata dengan mengintegrasikan metode estimasi dalam perencana query berbasis pemrograman dinamis, menghasilkan pengurangan waktu evaluasi query hingga beberapa kali lipat dibandingkan algoritma sebelumnya. Dengan efisiensi yang ditunjukkan---seperti waktu evaluasi kurang dari 1,7 detik untuk query LUBM yang kompleks---artikel ini membuktikan bahwa inovasi masih sangat diperlukan di era data besar.
***
Pendekatan yang ditawarkan Pan Hu dan Boris Motik dalam artikel ini memberikan solusi konkret terhadap permasalahan estimasi kardinalitas pada basis data graf, khususnya dengan memperkenalkan metode sampling berbasis loop. Keunggulan metode ini terletak pada kemampuannya menangani query graf kompleks dengan operator bersarang seperti union, projection, dan duplicate elimination, yang sebelumnya menjadi tantangan besar. Pada dataset LUBM-01K-mat, algoritma ini berhasil mencatat waktu evaluasi maksimal 1,7 detik dibandingkan metode WanderJoin asli yang memakan waktu rata-rata 6,2 detik untuk dataset serupa.
Eksperimen menunjukkan bahwa metode ini menghasilkan q-error yang jauh lebih rendah dibandingkan algoritma lain dalam G-CARE Framework. Sebagai contoh, pada dataset WatDiv, metode ini memberikan q-error < pada 96 dari 104 query, dibandingkan dengan hanya 75 query oleh metode Correlated Sampling (cs). Hal ini menandakan bahwa algoritma baru ini tidak hanya cepat tetapi juga konsisten dalam menghasilkan estimasi akurat bahkan pada dataset dengan distribusi data tidak merata.
Selain itu, integrasi metode ini dalam perencana query berbasis pemrograman dinamis juga memberikan dampak signifikan pada kinerja keseluruhan sistem basis data. Penulis melaporkan bahwa estimasi kardinalitas yang lebih akurat mampu mempercepat evaluasi query hingga beberapa kali lipat dibandingkan dengan pendekatan tradisional yang mengandalkan heuristik atau model statistik berbasis asumsi independensi atribut.
Dataset besar seperti WatDiv, dengan lebih dari 107 juta fakta biner, dan DBLP, yang terdiri dari 50 juta fakta biner, menjadi ujian nyata bagi efisiensi algoritma ini. Hasilnya, estimasi akurat dapat dicapai hanya dalam waktu 55 milidetik hingga 405 milidetik untuk query kompleks pada dataset ini. Kecepatan ini membuka peluang besar untuk mengaplikasikan algoritma dalam berbagai skenario seperti analisis jaringan sosial atau manajemen data besar berbasis graf.
Namun, tantangan tetap ada. Metode ini masih memerlukan pengujian lebih lanjut untuk mendukung fitur seperti path queries atau grouping pada tingkat kompleksitas yang lebih tinggi. Selain itu, dalam skala industri, integrasi algoritma dengan sistem basis data berbasis AI seperti NeuroCard dapat membuka babak baru dalam efisiensi sistem basis data.
***
