Mengapa arah indeks penting di MongoDB?

114

Mengutip dokumen :

Saat membuat indeks, angka yang terkait dengan kunci menentukan arah indeks, jadi harus selalu 1 (naik) atau -1 (turun). Arah tidak masalah untuk indeks kunci tunggal atau untuk pengambilan akses acak tetapi penting jika Anda melakukan kueri pengurutan atau rentang pada indeks gabungan.

Namun, saya tidak melihat alasan mengapa arah indeks harus menjadi masalah pada indeks gabungan. Bisakah seseorang memberikan penjelasan lebih lanjut (atau contoh)?

johndodo
sumber

Jawaban:

113

MongoDB menggabungkan kunci gabungan dalam beberapa cara dan menggunakannya sebagai kunci dalam BTree.

Saat menemukan item tunggal - Urutan node di pohon tidak relevan.

Jika Anda mengembalikan berbagai node - Elemen yang berdekatan akan berada di bawah cabang pohon yang sama. Semakin dekat node dalam jangkauan, semakin cepat node tersebut dapat diambil.

Dengan indeks bidang tunggal - Urutan tidak masalah. Jika mereka berdekatan dalam urutan menaik, mereka juga akan berdekatan dalam urutan menurun.

Bila Anda memiliki kunci majemuk - Urutan mulai penting.

Misalnya, jika kuncinya adalah A ascending B ascending index mungkin terlihat seperti ini:

Baris AB
1 1 1
2 2 6
3 2 7 
4 3 4
5 3 5
6 3 6
7 5 1

Query untuk A ascending B descending perlu melewati indeks agar dapat mengembalikan baris dan akan menjadi lebih lambat. Misalnya akan mengembalikan Row1, 3, 2, 6, 5, 4, 7

Kueri berkisar dalam urutan yang sama seperti indeks hanya akan mengembalikan baris secara berurutan dalam urutan yang benar.

Menemukan record dalam BTree membutuhkan waktu O (Log (n)). Menemukan rentang rekaman secara berurutan hanya OLog (n) + k di mana k adalah jumlah rekaman yang akan dikembalikan.

Jika catatan rusak, biayanya bisa setinggi OLog (n) * k

Jared Kells
sumber
1
Baris yang dihasilkan mungkin 1, 3, 2, 6, 5, 4, 7?
johndodo
Saya masih tidak melihat alasan untuk lebih lambat. Hanya algoritme yang harus berbeda (untuk setiap grup nilai di A, algoritme harus melompat ke akhir grup dan memprosesnya dalam urutan terbalik), tetapi karena indeks MongoDB ada di memori, yang seharusnya tidak memiliki efek nyata pada kecepatan. Juga, RDBMS tidak tahu apa-apa tentang arah dengan indeks dan situasinya cukup mirip, afaik?
johndodo
8
Alasan ini menjadi hit kinerja adalah karena ini bukan hanya daftar berurutan dalam memori seperti contoh yang disederhanakan. Ini sebenarnya adalah pohon berbobot. Melompat keluar dari urutan akan melibatkan melintasi pohon lagi. RDMS secara definitif memiliki urutan ke indeks.
Jared Kells
1
Mengambil node dari BTree secara berurutan semudah bergerak di sepanjang setiap daun sampai Anda habis dan kemudian naik satu tingkat dan turun ke cabang berikutnya. Ini O (n) Rusak itu jauh lebih intensif CPU.
Jared Kells
Terima kasih untuk klarifikasi lebih lanjut. Saya memeriksa dokumen untuk indeks MySQL - sangat mungkin untuk menentukan arah indeks, tetapi pengaturannya diabaikan.
johndodo
45

The jawaban sederhana yang Anda cari adalah bahwa arah hanya penting ketika Anda menyortir pada dua atau lebih bidang .

Jika Anda menyortir {a : 1, b : -1}:

Indeks {a : 1, b : 1}akan lebih lambat dari indeks{a : 1, b : -1}

Zaid Masud
sumber
1
@MarkPieszak karena seluruh pengurutan harus dilakukan dalam memori membuat indeks tidak berguna
Sammaye
@Sammaye Saya pikir itu ide yang tepat, meskipun saya tidak yakin itu keseluruhannya . Saya harus melihat implementasinya untuk mengetahui bagaimana itu benar-benar bekerja, tetapi saya akan berpikir bahwa hasilnya dapat ditarik kembali diurutkan dengan a saja, dan kemudian b sort tambahan perlu dilakukan dalam memori.
Zaid Masud
1
hmm, aneh terakhir kali saya memeriksa kode itu jatuh sebagian karena cara penyortirannya tapi meh, mungkin itu berubah
Sammaye
Bagaimana jika saya menyortir {a: -1, b: -1}, haruskah saya memiliki {a: -1, b: -1}indeks atau akan {a: 1, b: 1}cukup.
Hussain
@Hussain dalam contoh Anda, {a: 1, b: 1}indeks harus cukup karena membalikkan indeks sepenuhnya baik-baik saja. mis. Indeks pada {a: 1}dapat digunakan untuk penyortiran{a: -1}
Zaid Masud
12

Mengapa indeks

Pahami dua poin kunci.

  1. Meskipun indeks lebih baik daripada tidak ada indeks, indeks yang benar jauh lebih baik daripada keduanya.
  2. MongoDB hanya akan menggunakan satu indeks per kueri, membuat indeks gabungan dengan bidang yang tepat mengurutkan apa yang mungkin ingin Anda gunakan.

Indeks tidak gratis. Mereka mengambil memori, dan memberlakukan penalti kinerja saat melakukan penyisipan, pembaruan, dan penghapusan. Biasanya pencapaian kinerja dapat diabaikan (terutama dibandingkan dengan perolehan dalam kinerja baca), tetapi itu tidak berarti bahwa kami tidak bisa pintar-pintar membuat indeks kami.

Bagaimana Indeks

Mengidentifikasi kelompok bidang apa yang harus diindeks bersama adalah tentang memahami kueri yang Anda jalankan. Urutan bidang yang digunakan untuk membuat indeks Anda sangat penting. Kabar baiknya adalah, jika Anda salah melakukan order, indeks tidak akan digunakan sama sekali, jadi akan mudah dikenali dengan penjelasan.

Mengapa Menyortir

Kueri Anda mungkin perlu Diurutkan. Namun pengurutan bisa menjadi operasi yang mahal, jadi penting untuk memperlakukan bidang yang Anda sortir seperti bidang yang Anda kueri. Jadi akan lebih cepat kalau sudah index. Namun ada satu perbedaan penting, bidang yang Anda sortir harus merupakan bidang terakhir dalam indeks Anda. Satu-satunya pengecualian untuk aturan ini adalah jika bidang juga merupakan bagian dari kueri Anda, maka aturan harus-menjadi-terakhir tidak berlaku.

Bagaimana Menyortir

Anda dapat menentukan urutan pada semua kunci indeks atau subset; namun, kunci sortir harus terdaftar dalam urutan yang sama seperti yang muncul di indeks. Misalnya, pola kunci indeks {a: 1, b: 1} dapat mendukung pengurutan di {a: 1, b: 1} tetapi tidak di {b: 1, a: 1}.

Pengurutan harus menentukan arah pengurutan yang sama (yaitu naik / turun) untuk semua kuncinya sebagai pola kunci indeks atau menentukan arah pengurutan terbalik untuk semua kuncinya sebagai pola kunci indeks. Misalnya, pola kunci indeks {a: 1, b: 1} dapat mendukung pengurutan pada {a: 1, b: 1} dan {a: -1, b: -1} tetapi tidak pada {a: -1 , b: 1}.

Misalkan ada indeks ini:

{ a: 1 }
{ a: 1, b: 1 }
{ a: 1, b: 1, c: 1 }

Example                                                    Index Used
db.data.find().sort( { a: 1 } )                            { a: 1 }
db.data.find().sort( { a: -1 } )                           { a: 1 }
db.data.find().sort( { a: 1, b: 1 } )                      { a: 1, b: 1 }
db.data.find().sort( { a: -1, b: -1 } )                    { a: 1, b: 1 }
db.data.find().sort( { a: 1, b: 1, c: 1 } )                { a: 1, b: 1, c: 1 }
db.data.find( { a: { $gt: 4 } } ).sort( { a: 1, b: 1 } )   { a: 1, b: 1 }
Somnath Muluk
sumber
Saya mengerti itu contoh tetapi jika ada indeks, { a: 1, b: 1, c: 1 }apakah Anda benar-benar membutuhkan indeks { a: 1}dan { a: 1, b: 1}atau indeks { a: 1, b: 1, c: 1 }mencakup semua kasus? Jika kueri selalu menggunakan pengurutan yang sama: 1 tidak ada pengurutan dalam kueri dengan -1
Lukas Liesis
1
Jika ada banyak query yang bekerja hanya pada properti 'a', maka lebih cepat mencari dengan indeks dengan properti 'a' untuk mesin database, daripada mencari berdasarkan indeks dengan 3 properti 'a', 'b', 'c'. Karena ukuran indeks akan bertambah dan hitungannya juga bertambah. ex. Jika ada 20 bab di buku. Jadi lebih cepat untuk pergi ke bab 3 dan kemudian halaman tertentu. @LukasLiesis
Somnath Muluk