Nama saya Marko dan saya memberi ceramah di
Gophercon Rusia tahun ini tentang jenis indeks yang sangat menarik yang disebut "indeks bitmap". Saya ingin membaginya dengan komunitas, tidak hanya dalam format video, tetapi juga sebagai artikel. Ini versi bahasa Inggris dan Anda bisa membaca bahasa Rusia di
sini . Selamat menikmati!
Materi tambahan, slide dan semua kode sumber dapat ditemukan di sini:
http://bit.ly/bitmapindexeshttps://github.com/mkevac/gopherconrussia2019Rekaman video asli:
Mari kita mulai!
Pendahuluan
Hari ini saya akan berbicara tentang
- Apa itu indeks.
- Apa itu indeks bitmap;
- Di mana itu digunakan. Mengapa itu tidak digunakan di tempat yang tidak digunakan.
- Kita akan melihat implementasi sederhana di Go dan kemudian pergi di kompiler.
- Kemudian kita akan melihat implementasi yang sedikit kurang sederhana, tetapi terasa lebih cepat, dalam perakitan Go.
- Dan setelah itu, saya akan membahas "masalah" indeks bitmap satu per satu.
- Dan akhirnya, kita akan melihat solusi apa yang ada.
Jadi apa itu indeks?
Indeks adalah struktur data berbeda yang terus diperbarui selain data utama, yang digunakan untuk mempercepat permintaan pencarian. Tanpa indeks, pencarian akan melibatkan semua data (dalam proses yang juga dikenal sebagai "pemindaian penuh") dan proses itu memiliki kompleksitas algoritme linear. Tetapi database biasanya mengandung data dalam jumlah besar, sehingga kompleksitas linier terlalu lambat. Idealnya, kami ingin mencapai kecepatan kompleksitas logaritmik atau bahkan konstan.
Ini adalah topik yang sangat besar dan kompleks yang melibatkan banyak pengorbanan, tetapi melihat ke belakang selama beberapa dekade implementasi database dan penelitian, saya berpendapat bahwa hanya ada beberapa pendekatan yang umum digunakan:
Pertama, mengurangi area pencarian dengan memotong seluruh area menjadi bagian-bagian yang lebih kecil, secara hierarkis.
Secara umum, ini dicapai dengan menggunakan pohon. Ini mirip dengan memiliki kotak-kotak kotak di lemari pakaian Anda. Setiap kotak berisi bahan yang selanjutnya disortir ke dalam kotak yang lebih kecil, masing-masing untuk penggunaan tertentu. Jika kami membutuhkan materi, kami akan lebih baik mencari kotak berlabel "materi" daripada kotak berlabel "cookie".
Yang kedua adalah untuk menunjukkan secara tepat elemen tertentu atau grup elemen seperti pada peta hash atau indeks terbalik. Menggunakan peta hash mirip dengan contoh sebelumnya, tetapi Anda menggunakan banyak kotak kecil yang tidak berisi kotak itu sendiri, melainkan item akhir.
Pendekatan ketiga adalah menghilangkan kebutuhan untuk mencari sama sekali seperti pada filter bloom atau filter cuckoo. Filter Bloom dapat langsung memberikan jawaban dan menghemat waktu untuk pencarian.
Yang terakhir adalah mempercepat pencarian dengan memanfaatkan lebih baik kemampuan perangkat keras kami seperti dalam indeks bitmap. Indeks Bitmap terkadang melibatkan seluruh indeks, ya, tetapi dilakukan dengan cara yang sangat efisien.
Seperti yang sudah saya katakan, pencarian memiliki banyak pengorbanan, jadi seringkali kita akan menggunakan beberapa pendekatan untuk meningkatkan kecepatan lebih banyak atau untuk mencakup semua jenis pencarian potensial kita.
Hari ini saya ingin berbicara tentang salah satu pendekatan yang kurang dikenal: indeks bitmap.
Tetapi siapakah saya untuk membicarakan hal ini?
Saya seorang pemimpin tim di Badoo (mungkin Anda tahu merek kami yang lain: Bumble). Kami memiliki lebih dari 400 juta pengguna di seluruh dunia dan banyak fitur yang kami gunakan untuk mencari yang paling cocok untuk Anda! Untuk tugas-tugas ini, kami menggunakan layanan yang dibuat khusus yang menggunakan indeks bitmap, antara lain.
Sekarang, apa itu indeks bitmap?
Seperti namanya, indeks Bitmap menggunakan bitmap alias bitet untuk mengimplementasikan indeks pencarian. Dari sudut pandang mata burung, indeks ini terdiri dari satu atau beberapa bitmap yang mewakili entitas (misalnya orang) dan parameternya (misalnya usia, atau warna mata) dan algoritma untuk menjawab pertanyaan pencarian menggunakan operasi bitwise seperti AND, ATAU, TIDAK, dll. .
Indeks Bitmap dianggap sangat berguna dan berkinerja tinggi jika Anda memiliki pencarian yang harus menggabungkan pertanyaan dengan beberapa kolom dengan kardinalitas rendah (mungkin, warna mata atau status perkawinan) versus sesuatu seperti jarak ke pusat kota yang memiliki kardinalitas tak terbatas.
Tetapi nanti dalam artikel saya akan menunjukkan bahwa indeks bitmap bahkan bekerja dengan kolom kardinalitas tinggi.
Mari kita lihat contoh paling sederhana dari indeks bitmap ...
Bayangkan kita memiliki daftar restoran Moskow dengan karakteristik biner:
- dekat metro
- memiliki parkir pribadi
- memiliki teras
- menerima pemesanan
- ramah vegan
- mahal
Mari beri setiap restoran indeks mulai dari 0 dan alokasikan 6 bitmap (satu untuk setiap karakteristik). Kemudian kami akan mengisi bitmap ini sesuai dengan apakah restoran tersebut memiliki karakteristik tertentu atau tidak. Jika restoran nomor 4 memiliki teras, maka bit nomor 4 di bitmap "teras" akan ditetapkan ke 1 (0 jika tidak).
Kami sekarang memiliki indeks bitmap sesederhana mungkin yang dapat kami gunakan untuk menjawab pertanyaan seperti
- Beri saya restoran yang ramah vegan
- Beri saya restoran dengan teras yang menerima pemesanan, tetapi tidak mahal
Bagaimana? Ayo lihat. Pertanyaan pertama adalah yang sederhana. Kami hanya mengambil bitmap "ramah vegan" dan mengembalikan semua indeks yang telah ditetapkan bit.
Pertanyaan kedua sedikit lebih rumit. Kami akan menggunakan operasi bitwise BUKAN pada bitmap "mahal" untuk mendapatkan restoran yang tidak mahal, DAN itu dengan bitmap "terima reservasi" dan DAN dengan "memiliki bitmap teras". Bitmap yang dihasilkan akan terdiri dari restoran yang memiliki semua karakteristik ini yang kami inginkan. Di sini kita melihat bahwa hanya Yunost yang memiliki semua karakteristik ini.
Ini mungkin terlihat sedikit teoretis tetapi jangan khawatir, kami akan segera mendapatkan kode.
Di mana indeks bitmap digunakan
Jika Anda google "indeks bitmap", 90% dari hasilnya akan menunjuk ke Oracle DB yang memiliki indeks bitmap dasar. Tapi, tentu saja, DBMS lain menggunakan indeks bitmap juga, bukan? Tidak, sebenarnya tidak. Mari kita pergi melalui tersangka biasa satu per satu.
- Tetapi ada anak laki-laki baru di blok: Pilosa. Pilosa adalah DBMS baru yang ditulis dalam Go (perhatikan tidak ada R, itu tidak berhubungan) yang mendasarkan semuanya pada indeks bitmap. Dan kita akan membicarakan Pilosa nanti.
Implementasi berjalan
Tapi mengapa? Mengapa indeks bitmap sangat jarang digunakan? Sebelum menjawab pertanyaan itu, saya ingin memandu Anda melalui implementasi indeks bitmap dasar di Go.
Bitmap direpresentasikan sebagai sepotong memori. Dalam Go, mari kita gunakan irisan byte untuk itu.
Kami memiliki satu bitmap per karakteristik restoran. Setiap bit dalam bitmap mewakili apakah restoran tertentu memiliki karakteristik ini atau tidak.
Kita membutuhkan dua fungsi pembantu. Satu digunakan untuk mengisi bitmap secara acak, tetapi dengan probabilitas yang ditentukan untuk memiliki karakteristik. Sebagai contoh, saya pikir ada sangat sedikit restoran yang tidak menerima reservasi dan sekitar 20% ramah vegan.
Fungsi lain akan memberi kita daftar restoran dari bitmap.
Untuk menjawab pertanyaan "berikan saya restoran dengan teras yang menerima reservasi tetapi tidak mahal" kami akan membutuhkan dua operasi: BUKAN dan DAN.
Kami dapat sedikit menyederhanakan kode dengan memperkenalkan operasi yang kompleks DAN TIDAK.
Kami memiliki fungsi untuk masing-masingnya. Kedua fungsi melewati irisan kami mengambil elemen yang sesuai dari masing-masing, melakukan operasi dan menulis hasilnya ke irisan yang dihasilkan.
Dan sekarang kita dapat menggunakan bitmap kita dan fungsi kita untuk mendapatkan jawabannya.
Performa tidak begitu hebat di sini meskipun fungsi kami sangat sederhana dan kami menghemat banyak alokasi dengan tidak mengembalikan irisan baru pada setiap pemanggilan fungsi.
Setelah beberapa profil dengan pprof, saya perhatikan bahwa kompiler go melewatkan salah satu optimasi yang sangat mendasar: fungsi inlining.
Anda lihat, Go compiler secara patologis takut loop melalui irisan dan menolak untuk sebaris fungsi yang memiliki mereka.
Tapi saya tidak takut pada mereka dan bisa menipu kompiler dengan menggunakan goto untuk loop saya.
Seperti yang Anda lihat, inlining menyelamatkan kami sekitar 2 mikrodetik. Tidak buruk!
Kemacetan lain mudah dikenali ketika Anda melihat lebih dekat pada output perakitan. Kompilator Go menyertakan pemeriksaan rentang di loop kami. Go adalah bahasa yang aman dan kompiler takut bahwa tiga bitmap saya mungkin memiliki panjang yang berbeda dan mungkin ada buffer overflow.
Mari kita tenangkan kompiler dan tunjukkan bahwa semua bitmap saya memiliki panjang yang sama. Untuk melakukan itu, kita dapat menambahkan pemeriksaan sederhana di awal fungsi.
Dengan pemeriksaan ini, kompilator go dengan senang hati akan melewati pemeriksaan rentang dan kami akan menghemat beberapa nanodetik.
Implementasi dalam perakitan
Baiklah, jadi kami berhasil memeras sedikit lebih banyak kinerja dengan implementasi sederhana kami, tetapi hasil ini jauh lebih buruk daripada apa yang mungkin terjadi dengan perangkat keras saat ini.
Anda tahu, apa yang kami lakukan adalah operasi bitwise yang sangat mendasar dan CPU kami sangat efektif.
Sayangnya, kami memberi makan CPU kami dengan potongan kerja yang sangat kecil. Fungsi kami melakukan operasi byte demi byte. Kita dapat dengan mudah mengubah implementasi kita agar bekerja dengan potongan 8-byte dengan menggunakan irisan uint64.
Seperti yang Anda lihat di sini, kami memperoleh kinerja sekitar 8x untuk ukuran batch 8x, sehingga peningkatan kinerja cukup linier.
Tapi ini bukan akhir dari segalanya. CPU kami memiliki kemampuan untuk bekerja dengan chunks 16-byte, 32-byte, dan bahkan dengan chunks 64-byte. Operasi ini disebut SIMD (Single Instruction Multiple Data) dan proses penggunaan operasi CPU seperti itu disebut vektorisasi.
Sayangnya, kompiler Go tidak terlalu baik dengan vektorisasi. Dan satu-satunya hal yang dapat kita lakukan saat ini untuk membuat vektor kode kita adalah dengan menggunakan Go assembly dan menambahkan sendiri instruksi SIMD ini.
Pergi perakitan adalah binatang aneh. Anda akan berpikir bahwa perakitan adalah sesuatu yang terkait dengan arsitektur yang Anda tulis, tetapi perakitan Go lebih seperti IRL (bahasa representasi perantara): itu adalah platform-independen. Rob Pike memberikan ceramah yang luar biasa tentang ini beberapa tahun yang lalu.
Selain itu, Go menggunakan format plan9 yang tidak biasa yang tidak seperti format AT&T dan Intel.
Aman untuk mengatakan bahwa menulis kode assembly tidak menyenangkan.
Beruntung bagi kami, sudah ada dua alat tingkat tinggi untuk membantu penulisan perakitan Go: PeachPy dan avo. Kedua ini menghasilkan perakitan pergi dari kode tingkat yang lebih tinggi yang ditulis dalam Python dan Go masing-masing.
Alat-alat ini menyederhanakan hal-hal seperti alokasi register dan loop dan semuanya mengurangi kompleksitas memasuki ranah pemrograman perakitan untuk Go.
Kami akan menggunakan menghindari untuk posting ini sehingga program kami terlihat hampir seperti kode Go biasa.
Ini adalah contoh paling sederhana dari program avo. Kami memiliki fungsi utama () yang mendefinisikan fungsi yang disebut Tambah () yang menambahkan dua angka. Ada fungsi pembantu untuk mendapatkan parameter berdasarkan nama dan untuk mendapatkan salah satu register umum yang tersedia. Ada fungsi untuk setiap operasi perakitan seperti ADDQ di sini, dan ada fungsi pembantu untuk menyimpan hasil dari register ke nilai yang dihasilkan.
Call go go akan menjalankan program avo ini dan dua file akan dibuat
- add.s dengan kode perakitan yang dihasilkan
- stub.go dengan tajuk fungsi yang diperlukan untuk menghubungkan kode perakitan dan pergi kami
Sekarang kita telah melihat apa yang dilakukan avo, mari kita lihat fungsi kita. Saya telah mengimplementasikan versi skalar dan SIMD (vektor) dari fungsi kami.
Mari kita lihat seperti apa versi skalar dulu.
Seperti dalam contoh sebelumnya, kita dapat meminta daftar umum dan menghindari memberi kita yang benar yang tersedia. Kami tidak perlu melacak offset dalam byte untuk argumen kami, menghindari ini untuk kami.
Sebelumnya kami beralih dari loop ke menggunakan goto untuk alasan kinerja dan menipu kompilator. Di sini, kami menggunakan goto (lompatan) dan label sejak awal karena loop adalah konstruksi tingkat yang lebih tinggi. Dalam perakitan kami hanya memiliki lompatan.
Kode lain harus cukup jelas. Kami meniru loop dengan lompatan dan label, mengambil sebagian kecil data kami dari dua bitmap kami, menggabungkannya menggunakan salah satu operasi bitwise dan memasukkan hasilnya ke dalam bitmap yang dihasilkan.
Ini adalah kode asm yang dihasilkan yang kami dapatkan. Kami tidak harus menghitung offset dan ukuran (berwarna hijau), kami tidak harus berurusan dengan register tertentu (berwarna merah).
Jika kita membandingkan implementasi ini dalam perakitan dengan yang terbaik sebelumnya yang ditulis dalam go kita akan melihat bahwa kinerjanya sama seperti yang diharapkan. Kami tidak melakukan sesuatu yang berbeda.
Sayangnya, kami tidak dapat memaksa Go compiler untuk menampilkan fungsi kami yang ditulis dalam asm. Ini benar-benar tidak memiliki dukungan untuk itu dan permintaan untuk fitur ini telah ada selama beberapa waktu sekarang. Itu sebabnya fungsi asm kecil di mana saja tidak memberikan manfaat. Anda juga perlu menulis fungsi yang lebih besar, menggunakan paket matematika / bit baru atau melewatkan sama sekali.
Mari kita tulis versi vektor dari fungsi kita sekarang.
Saya memilih untuk menggunakan AVX2, jadi kita akan menggunakan potongan 32-byte. Ini sangat mirip dengan skalar dalam struktur. Kami memuat parameter, meminta register umum, dll.
Salah satu perubahan berkaitan dengan fakta bahwa operasi vektor menggunakan register lebar spesifik. Untuk 32 byte mereka memiliki awalan Y, inilah mengapa Anda melihat YMM () di sana. Untuk 64-byte mereka akan memiliki awalan Z.
Perbedaan lain berkaitan dengan optimasi yang saya lakukan disebut unrolling atau loop unrolling. Saya memilih untuk membuka sebagian loop kami dan melakukan 8 operasi loop secara berurutan sebelum kembali. Teknik ini mempercepat kode dengan mengurangi cabang-cabang yang kami miliki dan itu sangat dibatasi oleh jumlah register yang kami miliki.
Adapun kinerja ... itu luar biasa. Kami mendapat peningkatan 7x dibandingkan dengan yang terbaik sebelumnya. Cukup mengesankan, bukan?
Seharusnya dimungkinkan untuk meningkatkan hasil ini lebih banyak lagi dengan menggunakan AVX512, prefetching dan mungkin bahkan dengan menggunakan kompilasi JIT (tepat pada waktunya) alih-alih pembuat rencana kueri "manual", tetapi itu akan menjadi subjek untuk posting yang sama sekali berbeda.
Masalah indeks bitmap
Sekarang kita telah melihat implementasi dasar dan kecepatan implementasi asm yang mengesankan, mari kita bicara tentang fakta bahwa indeks bitmap tidak banyak digunakan. Kenapa begitu?
Publikasi lama memberi kita tiga alasan ini. Tetapi yang baru-baru ini dan saya berpendapat bahwa ini telah "diperbaiki" atau ditangani sekarang. Saya tidak akan membahas banyak detail tentang hal ini di sini karena kami tidak punya banyak waktu, tetapi tentu saja layak untuk dilihat sekilas.
Masalah kardinalitas tinggi
Jadi, kami telah diberitahu bahwa indeks bitmap hanya layak untuk bidang kardinalitas rendah. yaitu bidang yang memiliki beberapa nilai berbeda, seperti jenis kelamin atau warna mata. Alasannya adalah bahwa representasi umum (satu bit per nilai berbeda) dapat menjadi cukup besar untuk nilai kardinalitas tinggi. Dan, akibatnya, bitmap bisa menjadi besar bahkan jika jarang penduduknya.
Kadang-kadang representasi yang berbeda dapat digunakan untuk bidang-bidang ini seperti representasi angka biner seperti yang ditunjukkan di sini, tetapi pengubah permainan terbesar adalah kompresi. Para ilmuwan telah datang dengan algoritma kompresi yang luar biasa. Hampir semua didasarkan pada algoritma run-length yang tersebar luas, tetapi yang lebih menakjubkan adalah kita tidak perlu mendekompres bitmap untuk melakukan operasi bitwise. Operasi bitwise normal bekerja pada bitmap terkompresi.
Baru-baru ini, kami telah melihat pendekatan hibrid tampak seperti "bitmap menderu". Roaring bitmap menggunakan tiga representasi terpisah untuk bitmap: bitmap, array, dan "bit run" dan keduanya menyeimbangkan penggunaan ketiga representasi ini untuk memaksimalkan kecepatan dan meminimalkan penggunaan memori.
Bitmap yang menderu dapat ditemukan di beberapa aplikasi yang paling banyak digunakan di luar sana dan ada implementasi untuk banyak bahasa, termasuk beberapa implementasi untuk Go.
Pendekatan lain yang dapat membantu bidang kardinalitas tinggi disebut binning. Bayangkan kita memiliki bidang yang mewakili tinggi badan seseorang. Tinggi adalah pelampung, tetapi kita tidak berpikir seperti itu. Tidak ada yang peduli jika tinggi badan Anda 185,2 atau 185,3 cm. Jadi kita bisa menggunakan "tempat sampah virtual" untuk memeras ketinggian yang sama ke tempat sampah yang sama: tempat sampah 1 cm, dalam hal ini. Dan jika Anda berasumsi bahwa ada sangat sedikit orang dengan ketinggian kurang dari 50 cm, atau lebih dari 250 cm, kita dapat mengubah tinggi kita menjadi bidang dengan kira-kira 200 kardinalitas elemen, alih-alih kardinalitas yang hampir tak terbatas. Jika perlu, kami bisa melakukan pemfilteran tambahan pada hasil nanti.
Masalah throughput tinggi
Alasan lain mengapa indeks bitmap buruk adalah karena mahal untuk memperbarui bitmap.
Basis data melakukan pembaruan dan pencarian secara paralel, sehingga Anda harus dapat memperbarui data sementara mungkin ada ratusan utas melalui bitmap melakukan pencarian. Kunci akan diperlukan kunci untuk mencegah ras data atau masalah konsistensi data. Dan di mana ada satu kunci besar, ada pertikaian kunci.
Masalah ini, jika Anda memilikinya, dapat diperbaiki dengan sharding indeks Anda atau dengan memiliki versi indeks, jika sesuai.
Sharding sangat mudah. Anda beling mereka seperti Anda akan beling pengguna dalam database dan sekarang, bukan satu kunci, Anda memiliki beberapa kunci yang sangat mengurangi pertengkaran kunci Anda.
Pendekatan lain yang kadang-kadang layak adalah memiliki indeks berversi. Anda memiliki indeks yang Anda gunakan untuk pencarian dan Anda memiliki indeks yang Anda gunakan untuk menulis, untuk pembaruan. Dan Anda menyalin dan mengalihkannya pada frekuensi rendah, misalnya 100 atau 500 ms.
Tetapi pendekatan ini hanya layak jika aplikasi Anda dapat mentolerir indeks pencarian basi yang sedikit basi.
Tentu saja, kedua pendekatan ini juga dapat digunakan bersama. Anda dapat memiliki indeks versi yang diarding.
Kueri yang tidak sepele
Masalah indeks bitmap lain berkaitan dengan menggunakan indeks bitmap dengan kueri rentang. Dan pada pandangan sekilas operasi bitwise seperti DAN dan ATAU tampaknya tidak sangat berguna untuk berbagai pertanyaan seperti "beri saya kamar hotel yang harganya 200 hingga 300 dolar semalam".
Solusi naif dan sangat tidak efisien adalah mendapatkan hasil untuk setiap titik harga dari 200 hingga 300 dan ke ATAU hasilnya.
Pendekatan yang sedikit lebih baik adalah menggunakan binning dan menempatkan hotel kami ke dalam kisaran harga dengan kisaran lebar, katakanlah, 50 dolar. Pendekatan ini akan mengurangi biaya pencarian kami sekitar 50x.
Tetapi masalah ini juga dapat diselesaikan dengan sangat mudah dengan menggunakan pengkodean khusus yang memungkinkan berbagai pertanyaan dan cepat. Dalam literatur, bitmap semacam ini disebut bitmap rentang-disandikan.
Dalam bitmap yang dikodekan rentang, kami tidak hanya menetapkan bit tertentu untuk, katakanlah, nilai 200, tetapi atur semua bit pada 200 dan lebih tinggi. Sama untuk 300.
Jadi, dengan menggunakan bitmap representasi rentang-kode ini, kueri rentang dapat dijawab dengan hanya dua melewati bitmap. Kami mendapatkan semua hotel yang harganya kurang dari, atau sama dengan, 300 dolar dan menghapus dari hasilnya semua hotel yang harganya kurang dari, atau sama dengan, 199 dolar. Selesai
Anda akan kagum tetapi bahkan permintaan geo dimungkinkan menggunakan bitmap. Caranya adalah dengan menggunakan representasi seperti Google S2 atau serupa yang melingkupi koordinat dalam angka geometris yang dapat direpresentasikan sebagai tiga atau lebih garis yang diindeks. Jika Anda menggunakan representasi seperti itu, Anda dapat mewakili kueri geo sebagai beberapa kueri rentang pada indeks garis ini.
Solusi siap
Yah, saya harap saya sedikit menggelitik minat Anda. Anda sekarang memiliki satu alat lagi di bawah ikat pinggang Anda dan jika Anda perlu menerapkan sesuatu seperti ini di layanan Anda, Anda akan tahu ke mana harus mencari.
Itu semua baik dan bagus, tetapi tidak semua orang memiliki waktu, kesabaran dan sumber daya untuk mengimplementasikan indeks bitmap sendiri terutama ketika datang ke hal-hal yang lebih maju seperti instruksi SIMD.
Jangan takut, ada dua produk open source yang dapat membantu Anda dalam usaha Anda.
Mengaum
Pertama, ada perpustakaan yang sudah saya sebutkan disebut "roaring bitmap". Pustaka ini menerapkan "wadah" menderu dan semua operasi bitwise yang Anda perlukan jika Anda ingin menerapkan indeks bitmap penuh.
Sayangnya, implementasi go tidak menggunakan SIMD, sehingga mereka memberikan kinerja yang agak lebih rendah daripada, katakanlah, implementasi C.
Pilosa
Produk lain adalah DBMS yang disebut Pilosa yang hanya memiliki indeks bitmap. Ini adalah proyek baru-baru ini, tetapi belakangan ini mendapatkan banyak daya tarik.
E-d3BCvTn1CSSDr5Vj6W_9e5_GC1syQ9qSrwdS0 ">
Pilosa menggunakan bitmap menderu di bawahnya dan memberi, menyederhanakan, atau menjelaskan hampir semua hal yang telah saya sampaikan kepada Anda hari ini: binning, bitmap yang dikodekan-range, gagasan bidang, dll.
Mari kita lihat secara singkat contoh Pilosa yang digunakan ...
Contoh yang Anda lihat sangat mirip dengan apa yang kita lihat sebelumnya. Kami membuat klien ke server pilosa, membuat indeks dan bidang untuk karakteristik kami. Kami mengisi bidang dengan data acak dengan beberapa probabilitas seperti yang kami lakukan sebelumnya dan kemudian kami menjalankan permintaan pencarian kami.
Anda melihat pola dasar yang sama di sini. TIDAK mahal berpotongan atau AND-ed dengan teras dan berpotongan dengan pemesanan.
Hasilnya seperti yang diharapkan.
Dan terakhir, saya berharap suatu saat nanti, basis data seperti mysql dan postgresql akan mendapatkan jenis indeks baru: indeks bitmap.
Kata penutup
Dan jika Anda masih terjaga, saya berterima kasih untuk itu. Kekurangan waktu berarti saya harus membaca banyak hal di postingan ini, tapi saya harap ini berguna dan bahkan mungkin menginspirasi.
Indeks Bitmap adalah hal yang berguna untuk diketahui dan dipahami bahkan jika Anda tidak membutuhkannya sekarang. Simpan sebagai alat lain dalam portofolio Anda.
Selama pembicaraan saya, kami telah melihat berbagai trik kinerja yang dapat kami gunakan dan hal-hal yang sulit untuk diatasi saat ini. Ini jelas hal-hal yang perlu diketahui oleh setiap programmer Go.
Dan ini semua yang saya miliki untuk Anda saat ini. Terima kasih banyak