Sebagai contoh yang disederhanakan, misalkan saya memiliki tabel seperti ini:
seq | value
----+------
102 | 11954
211 | 43292
278 | 19222
499 | 3843
Tabel mungkin berisi ratusan juta catatan, dan saya harus sering melakukan kueri seperti ini:
SELECT sum(value) WHERE seq > $a and seq < $b
Bahkan jika seq
diindeks, implementasi basis data yang khas akan berulang melalui setiap baris untuk menghitung jumlah dalam kasus terbaik O(n)
, di mana n
ukuran rentang.
Apakah ada database yang dapat melakukan ini secara efisien, seperti dalam O(log(n))
per permintaan?
Saya telah menemukan struktur data yang disebut Pohon Segmen seperti yang dijelaskan di sini . Juga kadang-kadang disebut sebagai pohon rentang atau pohon interval, meskipun semua nama ini sering digambarkan sebagai variasi struktur data yang sedikit berbeda.
Namun, saya belum menemukan database yang mengimplementasikan struktur data seperti itu. Menerapkannya dari awal mudah untuk struktur dalam memori, tetapi menjadi rumit jika harus bertahan atau terlalu besar untuk masuk ke dalam memori. Jika ada pola yang efisien untuk mengimplementasikan ini di atas database yang ada, itu juga bisa membantu.
Catatan: Ini bukan tabel tambahan saja, jadi solusi seperti menjaga jumlah kumulatif tidak akan berfungsi dalam kasus ini.
Jawaban:
Menggunakan indeks SQL Server ColumnStore
Yah, oke, hanya satu - indeks CS yang terkelompok.
Jika Anda ingin membaca tentang perangkat keras tempat saya melakukan ini, silakan ke sini . Pengungkapan penuh, saya menulis posting blog itu di situs web perusahaan tempat saya bekerja.
Aktif untuk ujian!
Berikut ini beberapa kode umum untuk membangun tabel yang cukup besar. Peringatan yang sama seperti Evan, ini bisa memakan waktu cukup lama untuk membangun dan mengindeks.
Yah, Evan menang untuk kesederhanaan, tetapi saya sudah membicarakan hal itu sebelumnya.
Inilah definisi indeks. La dan dee dan dah.
Melihat hitungan, setiap Id memiliki distribusi yang cukup merata:
Hasil:
...
Dengan setiap Id yang memiliki ~ 5.005.005 baris, kita dapat melihat rentang ID yang cukup kecil untuk memberi Anda jumlah 10 juta baris.
Hasil:
Profil permintaan:
Untuk bersenang-senang, agregasi yang lebih besar:
Hasil:
Profil permintaan:
Semoga ini membantu!
sumber
PostgreSQL dengan indeks BRIN
Itu tidak benar. Setidaknya, tidak ada database yang layak yang akan melakukan itu. PostgreSQL mendukung pembuatan indeks BRIN pada tabel-tabel semacam ini. Indeks BRIN super kecil dan dapat memuat ram bahkan di meja sebesar ini. Ratusan juta baris bukan apa-apa.
Di sini, 300 juta baris didefinisikan seperti yang Anda pesan. Peringatan mungkin membutuhkan waktu lama untuk membuatnya (Waktu: 336057.807 ms + 95121.809 ms untuk indeks).
Dan sekarang...
1,4 detik untuk mengumpulkan / menjumlahkan 5.889.135 baris dalam kisaran yang diberikan.
Meskipun tabelnya 10 GB, indeks BRIN adalah 304 kB.
Bahkan lebih cepat
Jika ini masih belum cukup cepat, Anda dapat melakukan cache agregat sebanyak 100 ribu baris.
Sekarang Anda hanya perlu menggunakan baris brin dan agregat
2(1e5-1)
daripada 300 juta atau apa pun.Perangkat keras
Lenovo x230, i5-3230M, RAM 16GB, 1tb Samsung 840 SSD.
sumber
O(n)
, mungkinO(sqrt(n))
. Tergantung pada bagaimana Anda akan menentukan interval yang akan digunakan dalam materialisasi.