perkenalan
Saya memberikan laporan ini dalam bahasa Inggris pada konferensi GopherCon Russia 2019 di Moskow dan dalam bahasa Rusia pada pertemuan di Nizhny Novgorod. Kita berbicara tentang indeks bitmap - kurang umum dibandingkan B-tree, tetapi tidak kalah menariknya. Membagikan pidato di konferensi dalam bahasa Inggris dan transkrip teks dalam bahasa Rusia.
Kita akan melihat cara kerja indeks bitmap, kapan lebih baik, kapan lebih buruk dibandingkan indeks lain, dan dalam kasus apa indeks ini jauh lebih cepat daripada indeks lainnya; Mari kita lihat DBMS populer mana yang sudah memiliki indeks bitmap; Mari kita coba menulis sendiri di Go. Dan “untuk hidangan penutup” kami akan menggunakan perpustakaan yang sudah jadi untuk membuat database khusus super cepat kami sendiri.
Saya sangat berharap karya saya bermanfaat dan menarik bagi Anda. Pergi!
pengenalan
Halo semua! Sekarang jam enam sore dan kami semua sangat lelah. Saat yang tepat untuk membicarakan teori indeks basis data yang membosankan, bukan? Jangan khawatir, saya akan punya beberapa baris kode sumber di sana-sini. 🙂
Terlepas dari semua leluconnya, laporan ini penuh dengan informasi, dan kami tidak punya banyak waktu. Jadi mari kita mulai.
Hari ini saya akan berbicara tentang hal berikut:
- apa itu indeks;
- apa itu indeks bitmap;
- dimana digunakan dan dimana TIDAK digunakan dan mengapa;
- implementasi sederhana di Go dan sedikit kesulitan dengan kompiler;
- implementasi yang sedikit kurang sederhana, namun jauh lebih produktif di Go assembler;
- “masalah” indeks bitmap;
- implementasi yang ada.
Jadi apa itu indeks?
Indeks adalah struktur data terpisah yang kami pelihara dan perbarui selain data utama. Ini digunakan untuk mempercepat pencarian. Tanpa indeks, pencarian memerlukan penelusuran data secara lengkap (proses yang disebut pemindaian penuh), dan proses ini memiliki kompleksitas algoritmik linier. Namun database biasanya berisi data dalam jumlah besar dan kompleksitas liniernya terlalu lambat. Idealnya, kita mendapatkan logaritma atau konstanta.
Ini adalah topik yang sangat kompleks, penuh dengan seluk-beluk dan trade-off, namun setelah melihat pengembangan dan penelitian database selama beberapa dekade, saya ingin mengatakan bahwa hanya ada beberapa pendekatan yang banyak digunakan untuk membuat indeks database.
Pendekatan pertama adalah dengan mengurangi ruang pencarian secara hierarki, membagi ruang pencarian menjadi bagian-bagian yang lebih kecil.
Kami biasanya melakukan ini dengan menggunakan berbagai jenis pohon. Contohnya adalah sekotak besar bahan di lemari Anda yang berisi kotak-kotak kecil berisi bahan yang dibagi ke dalam berbagai topik. Jika Anda membutuhkan bahan, Anda mungkin akan mencarinya di kotak yang bertuliskan "Bahan" dan bukan di kotak yang bertuliskan "Kue", bukan?
Pendekatan kedua adalah dengan segera memilih elemen atau kelompok elemen yang diinginkan. Kami melakukan ini di peta hash atau indeks terbalik. Menggunakan peta hash sangat mirip dengan contoh sebelumnya, tetapi alih-alih menggunakan sekotak kotak, Anda memiliki sekumpulan kotak kecil berisi barang-barang akhir di lemari Anda.
Pendekatan ketiga adalah menghilangkan kebutuhan akan pencarian. Kami melakukan ini menggunakan filter Bloom atau filter kukuk. Yang pertama memberikan jawaban secara instan, sehingga Anda tidak perlu mencari lagi.
Pendekatan terakhir adalah memanfaatkan sepenuhnya semua kekuatan yang diberikan perangkat keras modern kepada kita. Inilah yang kami lakukan pada indeks bitmap. Ya, saat menggunakannya terkadang kami perlu menelusuri seluruh indeks, namun kami melakukannya dengan sangat efisien.
Seperti yang saya katakan, topik indeks database sangat luas dan penuh dengan kompromi. Artinya terkadang kita dapat menggunakan beberapa pendekatan secara bersamaan: jika kita perlu lebih mempercepat pencarian, atau jika kita perlu mencakup semua kemungkinan jenis pencarian.
Hari ini saya akan berbicara tentang pendekatan yang paling tidak dikenal - indeks bitmap.
Siapakah saya untuk berbicara mengenai topik ini?
Saya bekerja sebagai pemimpin tim di Badoo (mungkin Anda lebih familiar dengan produk kami yang lain, Bumble). Kami telah memiliki lebih dari 400 juta pengguna di seluruh dunia dan banyak fitur yang memilihkan yang paling cocok untuk mereka. Kami melakukan ini menggunakan layanan khusus, termasuk indeks bitmap.
Jadi apa itu indeks bitmap?
Indeks bitmap, seperti namanya, menggunakan bitmap atau bitset untuk mengimplementasikan indeks pencarian. Dari sudut pandang luas, indeks ini terdiri dari satu atau lebih bitmap yang mewakili entitas apa pun (seperti orang) dan properti atau parameternya (usia, warna mata, dll.), dan algoritma yang menggunakan operasi bit (AND, OR, NOT ) untuk menjawab permintaan pencarian.
Kami diberitahu bahwa indeks bitmap paling cocok dan sangat berkinerja untuk kasus-kasus di mana terdapat penelusuran yang menggabungkan kueri di banyak kolom berkardinalitas rendah (pikirkan "warna mata" atau "status perkawinan" versus sesuatu seperti "jarak dari pusat kota" ). Tapi nanti saya akan tunjukkan bahwa mereka juga berfungsi dengan baik untuk kolom berkardinalitas tinggi.
Mari kita lihat contoh paling sederhana dari indeks bitmap.
Bayangkan kita memiliki daftar restoran Moskow dengan properti biner seperti ini:
- dekat metro;
- ada parkir pribadi;
- ada beranda (memiliki teras);
- Anda dapat memesan meja (menerima reservasi);
- cocok untuk vegetarian (ramah vegan);
- mahal (mahal).
Mari kita beri setiap restoran nomor urut mulai dari 0 dan alokasikan memori untuk 6 bitmap (satu untuk setiap karakteristik). Kami kemudian akan mengisi bitmap ini tergantung pada apakah restoran memiliki properti ini atau tidak. Jika restoran 4 memiliki beranda, maka bit No. 4 pada bitmap “memiliki beranda” akan disetel ke 1 (jika tidak ada beranda, maka ke 0).
Sekarang kita memiliki indeks bitmap yang paling sederhana, dan kita dapat menggunakannya untuk menjawab pertanyaan seperti:
- “Tunjukkan pada saya restoran ramah vegetarian”;
- “Tunjukkan padaku restoran murah dengan beranda tempat Anda bisa memesan meja.”
Bagaimana? Mari kita lihat. Permintaan pertama sangat sederhana. Yang perlu kita lakukan hanyalah mengambil bitmap “ramah vegetarian” dan mengubahnya menjadi daftar restoran yang bagiannya diekspos.
Permintaan kedua sedikit lebih rumit. Kita perlu menggunakan bitmap BUKAN pada bitmap “mahal” untuk mendapatkan daftar restoran murah, lalu DAN dengan bitmap “bolehkah saya memesan meja” dan DAN hasilnya dengan bitmap “ada beranda”. Bitmap yang dihasilkan akan berisi daftar perusahaan yang memenuhi semua kriteria kami. Dalam contoh ini, ini hanya restoran Yunost.
Ada banyak teori yang terlibat, tapi jangan khawatir, kita akan segera melihat kodenya.
Di mana indeks bitmap digunakan?
Jika Anda mengindeks bitmap Google, 90% jawabannya akan terkait dengan Oracle DB dalam satu atau lain cara. Tapi DBMS lain mungkin juga mendukung hal keren seperti itu, bukan? Tidak terlalu.
Mari kita lihat daftar tersangka utama.
MySQL belum mendukung indeks bitmap, tetapi ada Proposal yang menyarankan untuk menambahkan opsi ini ().
PostgreSQL tidak mendukung indeks bitmap, tetapi menggunakan bitmap dan operasi bit sederhana untuk menggabungkan hasil pencarian di beberapa indeks lainnya.
Tarantool memiliki indeks bitset dan mendukung pencarian sederhana pada indeks tersebut.
Redis memiliki bitfield sederhana) tanpa kemampuan untuk mencarinya.
MongoDB belum mendukung indeks bitmap, tetapi ada juga Proposal yang menyarankan agar opsi ini ditambahkan
Elasticsearch menggunakan bitmap secara internal).
- Tapi tetangga baru telah muncul di rumah kami: Pilosa. Ini adalah database non-relasional baru yang ditulis dalam Go. Ini hanya berisi indeks bitmap dan mendasarkan semuanya pada indeks tersebut. Kita akan membicarakannya nanti.
Implementasi di Go
Namun mengapa indeks bitmap sangat jarang digunakan? Sebelum menjawab pertanyaan ini, saya ingin menunjukkan kepada Anda bagaimana menerapkan indeks bitmap yang sangat sederhana di Go.
Bitmap pada dasarnya hanyalah potongan data. Di Go, mari gunakan irisan byte untuk ini.
Kami memiliki satu bitmap untuk satu karakteristik restoran, dan setiap bit dalam bitmap menunjukkan apakah restoran tertentu memiliki properti ini atau tidak.
Kita membutuhkan dua fungsi pembantu. Satu akan digunakan untuk mengisi bitmap kita dengan data acak. Acak, tetapi dengan probabilitas tertentu bahwa restoran tersebut memiliki properti masing-masing. Misalnya, saya yakin hanya ada sedikit restoran di Moskow yang tidak dapat memesan meja, dan menurut saya sekitar 20% restoran tersebut cocok untuk vegetarian.
Fungsi kedua akan mengubah bitmap menjadi daftar restoran.
Untuk menjawab pertanyaan “Tunjukkan restoran murah yang memiliki teras dan dapat melakukan reservasi,” kita memerlukan dua operasi bit: NOT dan AND.
Kita dapat menyederhanakan kode kita sedikit dengan menggunakan operator AND NOT yang lebih kompleks.
Kami memiliki fungsi untuk setiap operasi ini. Keduanya menelusuri irisan, mengambil elemen yang sesuai dari masing-masing irisan, menggabungkannya dengan operasi bit, dan memasukkan hasilnya ke dalam irisan yang dihasilkan.
Dan sekarang kita dapat menggunakan bitmap dan fungsinya untuk menjawab permintaan pencarian.
Performanya tidak terlalu tinggi, meskipun fungsinya sangat sederhana dan kami menghemat banyak uang dengan tidak mengembalikan potongan baru setiap kali fungsi tersebut dipanggil.
Setelah melakukan sedikit pembuatan profil dengan pprof, saya perhatikan bahwa kompiler Go kehilangan satu optimasi yang sangat sederhana namun sangat penting: fungsi inlining.
Faktanya adalah kompiler Go sangat takut dengan loop yang melewati irisan, dan dengan tegas menolak fungsi inline yang berisi loop tersebut.
Tapi saya tidak takut dan saya bisa menipu kompiler dengan menggunakan goto alih-alih loop, seperti dulu.
Dan, seperti yang Anda lihat, sekarang kompiler akan dengan senang hati menyejajarkan fungsi kita! Hasilnya, kami berhasil menghemat sekitar 2 mikrodetik. Tidak buruk!
Kemacetan kedua mudah dilihat jika Anda melihat lebih dekat pada keluaran perakitan. Kompiler menambahkan pemeriksaan batas irisan tepat di dalam loop terpanas kami. Faktanya adalah Go adalah bahasa yang aman, kompiler takut ketiga argumen saya (tiga irisan) memiliki ukuran yang berbeda. Lagi pula, secara teoritis akan ada kemungkinan terjadinya apa yang disebut buffer overflow.
Mari kita yakinkan kompiler dengan menunjukkan bahwa semua irisan memiliki ukuran yang sama. Kita dapat melakukan ini dengan menambahkan tanda centang sederhana di awal fungsi kita.
Melihat ini, kompiler dengan senang hati melewatkan pemeriksaan, dan kami akhirnya menghemat 500 nanodetik lagi.
Butches besar
Baiklah, kami berhasil meningkatkan kinerja dari implementasi sederhana kami, namun hasil ini sebenarnya jauh lebih buruk dibandingkan dengan perangkat keras saat ini.
Yang kami lakukan hanyalah operasi bit dasar, dan prosesor kami menjalankannya dengan sangat efisien. Namun sayangnya, kami “memberi makan” prosesor kami dengan pekerjaan yang sangat kecil. Fungsi kami menjalankan operasi berdasarkan byte demi byte. Kita dapat dengan mudah mengubah kode kita agar berfungsi dengan potongan 8-byte menggunakan irisan UInt64.
Seperti yang Anda lihat, perubahan kecil ini mempercepat program kami sebanyak delapan kali lipat dengan meningkatkan ukuran batch sebanyak delapan kali lipat. Keuntungannya bisa dikatakan linier.
Implementasi di assembler
Tapi ini bukanlah akhir. Prosesor kami dapat bekerja dengan potongan berukuran 16, 32, dan bahkan 64 byte. Operasi “luas” seperti itu disebut instruksi tunggal beberapa data (SIMD; satu instruksi, banyak data), dan proses mengubah kode sehingga menggunakan operasi tersebut disebut vektorisasi.
Sayangnya, compiler Go masih jauh dari sempurna dalam hal vektorisasi. Saat ini, satu-satunya cara untuk membuat vektor kode Go adalah dengan melakukan dan melakukan operasi ini secara manual menggunakan assembler Go.
Go assembler adalah binatang yang aneh. Anda mungkin tahu bahwa bahasa assembly adalah sesuatu yang sangat terkait dengan arsitektur komputer yang Anda gunakan untuk menulis, tapi tidak demikian halnya di Go. Assembler Go lebih seperti IRL (bahasa representasi perantara) atau bahasa perantara: ia praktis tidak bergantung pada platform. Rob Pike memberikan performa yang sangat baik tentang topik ini beberapa tahun lalu di GopherCon di Denver.
Selain itu, Go menggunakan format Plan 9 yang tidak biasa, yang berbeda dari format AT&T dan Intel yang diterima secara umum.
Dapat dikatakan bahwa menulis Go assembler dengan tangan bukanlah hal yang paling menyenangkan.
Namun untungnya, sudah ada dua alat tingkat tinggi yang membantu kita menulis assembler Go: PeachPy dan avo. Kedua utilitas menghasilkan assembler Go dari kode tingkat tinggi yang masing-masing ditulis dengan Python dan Go.
Utilitas ini menyederhanakan hal-hal seperti alokasi register, penulisan loop, dan secara umum menyederhanakan proses memasuki dunia pemrograman perakitan di Go.
Kita akan menggunakan avo, jadi program kita akan menjadi program Go biasa.
Seperti inilah contoh program avo yang paling sederhana. Kami memiliki fungsi main(), yang mendefinisikan fungsi Add() di dalamnya, yang artinya menjumlahkan dua angka. Ada fungsi pembantu di sini untuk mendapatkan parameter berdasarkan nama dan mendapatkan salah satu register prosesor yang gratis dan sesuai. Setiap operasi prosesor memiliki fungsi yang sesuai pada avo, seperti terlihat pada ADDQ. Terakhir, kita melihat fungsi pembantu untuk menyimpan nilai yang dihasilkan.
Dengan memanggil go generate, kita akan menjalankan program di avo dan sebagai hasilnya, dua file akan dihasilkan:
- add.s dengan kode yang dihasilkan di Go assembler;
- stub.go dengan header fungsi untuk menghubungkan dua dunia: Go dan assembler.
Sekarang kita sudah melihat apa yang dilakukan avo dan bagaimana caranya, mari kita lihat fungsi kita. Saya mengimplementasikan fungsi versi skalar dan vektor (SIMD).
Mari kita lihat versi skalarnya terlebih dahulu.
Seperti pada contoh sebelumnya, kita meminta register tujuan umum yang gratis dan valid, kita tidak perlu menghitung offset dan ukuran untuk argumennya. avo melakukan semua ini untuk kita.
Kami dulu menggunakan label dan goto (atau jumps) untuk meningkatkan kinerja dan mengelabui kompiler Go, tapi sekarang kami melakukannya dari awal. Intinya adalah bahwa siklus adalah konsep tingkat yang lebih tinggi. Di assembler, kami hanya memiliki label dan lompatan.
Kode selebihnya seharusnya sudah familier dan dapat dimengerti. Kami meniru loop dengan label dan lompatan, mengambil sepotong kecil data dari dua irisan kami, menggabungkannya dengan operasi bit (DAN BUKAN dalam kasus ini) dan kemudian memasukkan hasilnya ke dalam irisan yang dihasilkan. Semua.
Seperti inilah tampilan kode assembler terakhir. Kami tidak perlu menghitung offset dan ukuran (disorot dengan warna hijau) atau melacak register yang digunakan (disorot dengan warna merah).
Jika kita membandingkan performa implementasi bahasa assembly dengan performa implementasi terbaik di Go, kita akan melihat bahwa kinerjanya sama. Dan ini diharapkan. Lagi pula, kami tidak melakukan sesuatu yang istimewa - kami hanya mereproduksi apa yang akan dilakukan oleh kompiler Go.
Sayangnya, kami tidak dapat memaksa kompiler untuk memasukkan fungsi kami yang ditulis dalam bahasa assembly. Kompiler Go saat ini tidak memiliki fitur seperti itu, meskipun sudah ada permintaan untuk menambahkannya cukup lama.
Inilah sebabnya mengapa tidak mungkin mendapatkan manfaat apa pun dari fungsi kecil dalam bahasa assembly. Kita perlu menulis fungsi yang besar, atau menggunakan paket math/bits yang baru, atau melewati bahasa assembler.
Sekarang mari kita lihat versi vektor dari fungsi kita.
Untuk contoh ini, saya memutuskan untuk menggunakan AVX2, jadi kami akan menggunakan operasi yang beroperasi pada potongan 32-byte. Struktur kodenya sangat mirip dengan versi skalar: memuat parameter, meminta register bersama gratis, dll.
Salah satu inovasinya adalah operasi vektor yang lebih luas menggunakan register lebar khusus. Dalam kasus potongan 32-byte, ini adalah register yang diawali dengan Y. Inilah sebabnya Anda melihat fungsi YMM() dalam kode. Jika saya menggunakan AVX-512 dengan potongan 64-bit, awalannya adalah Z.
Inovasi kedua adalah saya memutuskan untuk menggunakan optimasi yang disebut loop unrolling, yang berarti melakukan delapan operasi loop secara manual sebelum melompat ke awal loop. Pengoptimalan ini mengurangi jumlah cabang dalam kode, dan dibatasi oleh jumlah register gratis yang tersedia.
Nah, bagaimana dengan performanya? Dia cantik! Kami mencapai kecepatan sekitar tujuh kali lipat dibandingkan dengan solusi Go terbaik. Mengesankan, bukan?
Namun implementasi ini pun berpotensi dipercepat dengan menggunakan AVX-512, prefetching, atau JIT (kompiler just-in-time) untuk penjadwal kueri. Namun hal ini tentu saja merupakan topik untuk laporan terpisah.
Masalah dengan indeks bitmap
Sekarang kita telah melihat implementasi sederhana dari indeks bitmap di Go dan implementasi yang jauh lebih produktif dalam bahasa assembly, akhirnya mari kita bahas mengapa indeks bitmap sangat jarang digunakan.
Makalah lama menyebutkan tiga masalah dengan indeks bitmap, tetapi makalah yang lebih baru dan saya berpendapat bahwa masalah tersebut tidak lagi relevan. Kami tidak akan mendalami masing-masing masalah ini secara mendalam, namun akan melihatnya secara dangkal.
Masalah kardinalitas tinggi
Jadi, kita diberitahu bahwa indeks bitmap hanya cocok untuk bidang dengan kardinalitas rendah, yaitu bidang yang memiliki sedikit nilai (misalnya jenis kelamin atau warna mata), dan alasannya adalah representasi biasa dari bidang tersebut (satu bit per nilai) dalam kasus kardinalitas tinggi, ini akan memakan terlalu banyak ruang dan, terlebih lagi, indeks bitmap ini akan terisi dengan buruk (jarang).
Terkadang kita mungkin menggunakan representasi yang berbeda, seperti representasi standar yang kita gunakan untuk mewakili angka. Namun munculnya algoritma kompresilah yang mengubah segalanya. Selama beberapa dekade terakhir, para ilmuwan dan peneliti telah menemukan sejumlah besar algoritma kompresi untuk bitmap. Keuntungan utamanya adalah tidak perlu mendekompresi bitmap untuk melakukan operasi bit - kita dapat melakukan operasi bit secara langsung pada bitmap terkompresi.
Baru-baru ini, pendekatan hybrid mulai bermunculan, seperti bitmap yang menderu. Mereka secara bersamaan menggunakan tiga representasi berbeda untuk bitmap - bitmap itu sendiri, array, dan apa yang disebut bit run - dan menyeimbangkan keduanya untuk memaksimalkan kinerja dan meminimalkan konsumsi memori.
Anda dapat menemukan bitmap menderu di aplikasi paling populer. Sudah ada banyak sekali implementasi untuk berbagai bahasa pemrograman, termasuk lebih dari tiga implementasi untuk Go.
Pendekatan lain yang dapat membantu kita menangani kardinalitas tinggi disebut binning. Bayangkan Anda memiliki bidang yang mewakili tinggi badan seseorang. Tinggi badan adalah angka floating point, tapi kita manusia tidak berpikir seperti itu. Bagi kami tidak ada perbedaan antara tinggi badan 185,2 cm dan 185,3 cm.
Ternyata kita dapat mengelompokkan nilai-nilai yang serupa ke dalam kelompok-kelompok dalam jarak 1 cm.
Dan jika kita juga mengetahui bahwa sangat sedikit orang yang tingginya kurang dari 50 cm dan tinggi dari 250 cm, maka pada dasarnya kita dapat mengubah bidang dengan kardinalitas tak terhingga menjadi bidang dengan kardinalitas sekitar 200 nilai.
Tentu saja, jika perlu, kita bisa melakukan pemfilteran tambahan setelahnya.
Masalah Bandwidth Tinggi
Masalah berikutnya dengan indeks bitmap adalah memperbaruinya bisa sangat mahal.
Basis data harus dapat memperbarui data sementara ratusan kueri lain mungkin sedang mencari data. Kita memerlukan kunci untuk menghindari masalah dengan akses data secara bersamaan atau masalah berbagi lainnya. Dan di mana ada satu kunci besar, di situ ada masalah - pertikaian kunci, ketika kunci ini menjadi hambatan.
Masalah ini dapat diselesaikan atau diatasi dengan menggunakan sharding atau menggunakan indeks berversi.
Sharding adalah hal yang sederhana dan terkenal. Anda dapat membagi indeks bitmap seperti yang Anda lakukan pada data lainnya. Alih-alih satu kunci besar, Anda akan mendapatkan banyak kunci kecil dan dengan demikian menghilangkan pertikaian kunci.
Cara kedua untuk menyelesaikan masalah ini adalah dengan menggunakan indeks berversi. Anda dapat memiliki satu salinan indeks yang Anda gunakan untuk mencari atau membaca, dan satu lagi yang Anda gunakan untuk menulis atau memperbarui. Dan sekali dalam jangka waktu tertentu (misalnya, setiap 100 ms atau 500 ms) Anda menggandakannya dan menukarnya. Tentu saja, pendekatan ini hanya berlaku jika aplikasi Anda dapat menangani indeks pencarian yang sedikit tertinggal.
Kedua pendekatan ini dapat digunakan secara bersamaan: Anda dapat memiliki indeks berversi shard.
Kueri yang lebih kompleks
Masalah terakhir dengan indeks bitmap adalah kita diberitahu bahwa indeks tersebut tidak cocok untuk jenis kueri yang lebih kompleks, seperti kueri rentang.
Memang, jika dipikir-pikir, operasi bit seperti AND, OR, dll. sangat tidak cocok untuk pertanyaan ala “Tunjukkan hotel dengan tarif kamar dari 200 hingga 300 dolar per malam.”
Solusi yang naif dan sangat tidak bijaksana adalah dengan mengambil hasil untuk setiap nilai dolar dan menggabungkannya dengan operasi OR bitwise.
Solusi yang sedikit lebih baik adalah dengan menggunakan pengelompokan. Misalnya dalam kelompok 50 dolar. Ini akan mempercepat proses kami sebanyak 50 kali lipat.
Namun masalahnya juga mudah diselesaikan dengan menggunakan tampilan yang dibuat khusus untuk jenis permintaan ini. Dalam makalah ilmiah ini disebut bitmap yang disandikan rentang.
Dalam representasi ini, kami tidak hanya menetapkan satu bit untuk beberapa nilai (misalnya, 200), tetapi menetapkan nilai ini dan semuanya lebih tinggi. 200 ke atas. Sama untuk 300: 300 ke atas. Dan seterusnya.
Dengan menggunakan representasi ini, kita dapat menjawab permintaan pencarian semacam ini dengan melintasi indeks dua kali saja. Pertama, kita akan mendapatkan daftar hotel yang harga kamarnya lebih murah atau $300, lalu kita akan menghapus daftar hotel yang harga kamarnya lebih murah atau $199. Siap.
Anda akan terkejut, tetapi geoquery pun dimungkinkan menggunakan indeks bitmap. Caranya adalah dengan menggunakan representasi geometris yang mengelilingi koordinat Anda dengan bangun geometris. Misalnya S2 dari Google. Gambar tersebut harus dapat direpresentasikan dalam bentuk tiga atau lebih garis berpotongan yang dapat diberi nomor. Dengan cara ini kita dapat mengubah geoquery kita menjadi beberapa query “sepanjang celah” (sepanjang garis bernomor ini).
Solusi Siap
Saya harap saya sedikit menarik minat Anda dan sekarang Anda memiliki alat lain yang berguna di gudang senjata Anda. Jika Anda perlu melakukan hal seperti ini, Anda akan tahu ke arah mana harus mencarinya.
Namun, tidak semua orang memiliki waktu, kesabaran, atau sumber daya untuk membuat indeks bitmap dari awal. Apalagi yang lebih advanced, pakai SIMD misalnya.
Untungnya, ada beberapa solusi siap pakai untuk membantu Anda.
Bitmap menderu
Pertama, ada perpustakaan bitmap yang sama yang telah saya bicarakan. Ini berisi semua wadah yang diperlukan dan operasi bit yang Anda perlukan untuk membuat indeks bitmap lengkap.
Sayangnya, saat ini, tidak ada implementasi Go yang menggunakan SIMD, yang berarti implementasi Go memiliki performa yang lebih rendah dibandingkan implementasi C, misalnya.
Pilosa
Produk lain yang dapat membantu Anda adalah Pilosa DBMS, yang sebenarnya hanya memiliki indeks bitmap. Ini adalah solusi yang relatif baru, namun berhasil memenangkan hati dengan sangat cepat.
Pilosa menggunakan bitmap menderu secara internal dan memberi Anda kemampuan untuk menggunakannya, menyederhanakan dan menjelaskan semua hal yang saya bicarakan di atas: pengelompokan, bitmap yang dikodekan rentang, konsep bidang, dll.
Mari kita lihat sekilas contoh penggunaan Pilosa untuk menjawab pertanyaan yang sudah Anda kenal.
Contohnya sangat mirip dengan yang Anda lihat sebelumnya. Kami membuat klien ke server Pilosa, membuat indeks dan bidang yang diperlukan, lalu mengisi bidang kami dengan data acak dengan probabilitas dan, akhirnya, menjalankan kueri yang sudah dikenal.
Setelah itu, kita gunakan NOT pada kolom "mahal", lalu potong hasilnya (atau AND) dengan kolom "teras" dan dengan kolom "reservasi". Dan akhirnya, kami mendapatkan hasil akhir.
Saya sangat berharap di masa mendatang indeks jenis baru ini juga akan muncul di DBMS seperti MySQL dan PostgreSQL - indeks bitmap.
Kesimpulan
Jika Anda belum tertidur, terima kasih. Saya sempat menyinggung banyak topik secara singkat karena keterbatasan waktu, namun saya harap pembicaraan tersebut bermanfaat dan bahkan mungkin memotivasi.
Indeks bitmap baik untuk diketahui, meskipun Anda tidak membutuhkannya saat ini. Biarkan mereka menjadi alat lain di kotak peralatan Anda.
Kita telah melihat berbagai trik kinerja untuk Go dan hal-hal yang belum dapat ditangani dengan baik oleh kompiler Go. Namun hal ini sangat berguna untuk diketahui oleh setiap programmer Go.
Hanya itu yang ingin saya sampaikan kepada Anda. Terima kasih!
Sumber: www.habr.com