sware

SWARE: Pengindeksan Sadar Keterurutan

Kode sumber untuk penyerahan makalah ICDE 2023: "Pengindeksan untuk Data yang Hampir Diurutkan"

Tentang

Repositori berisi kode sumber untuk implementasi B+tree dan SWARE. Dalam versi kode saat ini, kedua implementasi bersifat generik, namun file aplikasi yang menguji struktur data indeks ini hanya mendukung tipe data integer. Selain itu, file aplikasi menggunakan nilai yang sama untuk kunci dan nilai setiap entri. Ekstensi kode di masa mendatang akan mendukung tipe data yang lebih besar.

Kedua struktur data memerlukan alokasi kumpulan buffer saat menjalankan kode, yang dapat diperluas hingga jumlah yang diperlukan jika diperlukan untuk dijalankan sepenuhnya di memori. Alokasi buffer pool diberikan dalam bentuk jumlah blok yang setiap bloknya berukuran 4KB. Misalnya, jika Anda menggunakan alokasi 1 juta blok, maka Anda mengalokasikan 1 juta*4KB = 4 GB memori untuk struktur data pohon.

Pohon SA B+ juga memerlukan jumlah entri yang dapat ditampung buffer dalam memorinya saat menjalankan program, bersama dengan faktor pengisian yang harus dipertahankan saat melakukan bulkloading. Setiap entri adalah pasangan nilai kunci.

Bagaimana cara menjalankannya

Menghasilkan beban kerja penyerapan

Gunakan generator data pengurutan dari repo ini: https://github.com/BU-DiSC/bods untuk menghasilkan kunci penyerapan (dapat menentukan payload size=0 untuk menghasilkan kunci saja). Seperti disebutkan di atas, file aplikasi menggunakan nilai yang sama untuk kunci dan nilai setiap entri (pasangan K,V). Catat jalur ke beban kerja yang dihasilkan.

B+ Pohon

1. kompilasi menggunakan perintah "make bplustree"
2. Jalankan file yang dapat dieksekusi menggunakan format berikut:

./ test_base_index < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. queries >

Misalnya, Anda akan menggunakan:

./ test_base_index createdata_1000000 - elems_100000 - K_100000 - L_1seed1632764083 . dat sample . txt 1000000 100000 100000 200000

Di sini, kami menyerap beban kerja 1 juta entri/kunci dengan K=L=100.000. Kami menggunakan cache kumpulan buffer untuk 1 juta blok dan menjalankan 200.000 kueri titik. Latensi keluaran untuk kueri penyerapan dan titik ditulis ke "sample.txt".

Pohon SA B+

1. kompilasi menggunakan perintah "make satree"
2. Jalankan file yang dapat dieksekusi menggunakan format berikut:

./ test_satree < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. entries > < swareBuffer allocation > < fill factor % >  < #. queries >

Misalnya, Anda akan menggunakan:

/ test_satree createdata_1000000 - elems_10 - K_10 - L_1seed1632764083 . dat swaresample . txt 1000000 10 10 1000000 10000 95 200000

Di sini, kami menyerap beban kerja 1 juta entri/kunci dengan K=L=100.000 (10% dari total entri). Kami menggunakan cache kumpulan buffer untuk 1 juta blok dan menjalankan 200.000 kueri titik. Latensi keluaran untuk kueri penyerapan dan titik ditulis ke "swaresample.txt". Buffer dalam memori akan menampung 10.000 entri (1% dari 1 juta) dan kami mempertahankan faktor pengisian sebesar 95%.