Bagaimana cara kerja pengurutan dengan indeks di MongoDB?

Indeks di MongoDB disimpan dalam struktur B-tree, di mana setiap entri indeks menunjuk ke lokasi tertentu di disk. Menggunakan struktur B-tree juga berarti bahwa indeks MongoDB disimpan dalam urutan yang diurutkan, selalu dilalui dalam urutan, dan murah bagi MongoDB untuk mengambil serangkaian dokumen dalam urutan yang diurutkan melalui indeks.

Pembaruan :Struktur B-tree benar untuk mesin penyimpanan MMAPv1, tetapi diimplementasikan sedikit berbeda oleh mesin penyimpanan WiredTiger (default sejak MongoDB 3.2). Ide dasarnya tetap sama, di mana murah untuk melintasi indeks dalam urutan yang diurutkan.

Sebuah SORT stage (yaitu pengurutan dalam memori) dalam kueri dibatasi hingga 32MB penggunaan memori. Kueri akan gagal jika SORT tahap melebihi batas ini. Batas ini dapat diabaikan dengan memanfaatkan sifat indeks yang diurutkan, sehingga MongoDB dapat mengembalikan kueri dengan sort() parameter tanpa melakukan pengurutan dalam memori.

Mari kita asumsikan bahwa kueri berbentuk:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort(...)

dengan koleksi a memiliki indeks:

    db.a.createIndex({b:1,c:1})

Ada dua kemungkinan skenario ketika sort() tahap ditentukan dalam kueri:

1. MongoDB tidak dapat menggunakan sifat indeks yang diurutkan dan harus melakukan SORT di dalam memori panggung .

Ini adalah hasil jika kueri tidak dapat menggunakan "awalan indeks". Misalnya:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({c:1})

Dalam kueri di atas, indeks {b:1,c:1} dapat digunakan untuk:

• Mencocokkan dokumen yang memiliki b lebih besar dari 100 untuk {b:{$gt:100}} bagian dari kueri.
• Namun, tidak ada jaminan bahwa dokumen yang dikembalikan diurutkan berdasarkan c .

Oleh karena itu, MongoDB tidak punya pilihan selain melakukan pengurutan di dalam memori. explain() output dari kueri ini akan memiliki SORT panggung. SORT . ini stage akan dibatasi hingga 32MB penggunaan memori.

2. MongoDB dapat menggunakan sifat indeks yang diurutkan .

Ini adalah hasil jika query menggunakan:

• Urutkan kunci yang sesuai dengan urutan indeks, dan
• Menentukan urutan yang sama dengan indeks (yaitu indeks {b:1,c:1} dapat digunakan untuk sort({b:1,c:1}) atau sort({b:-1,c:-1}) tapi bukan sort({b:1,c:-1}) )

Misalnya:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({b:1})

Dalam kueri di atas, indeks {b:1,c:1} dapat digunakan untuk:

• Mencocokkan dokumen yang memiliki b lebih besar dari 100 untuk {b:{$gt:100}} bagian dari kueri.
• Dalam hal ini, MongoDB dapat menjamin bahwa dokumen yang dikembalikan diurutkan berdasarkan b .

explain() keluaran kueri di atas tidak memiliki SORT panggung. Juga, explain() keluaran kueri dengan dan tanpa sort() identik . Intinya, kita mendapatkan sort() gratis.

Sumber daya yang berharga untuk memahami subjek ini adalah Mengoptimalkan Indeks Senyawa MongoDB. Harap diperhatikan bahwa entri blog ini ditulis pada tahun 2012. Meskipun beberapa istilah mungkin sudah usang, teknis postingan masih relevan.

Pembaruan tentang pertanyaan tindak lanjut

1. MongoDB hanya menggunakan satu indeks untuk sebagian besar kueri. Jadi misalnya, untuk menghindari SORT dalam memori tahap dalam kueri

   db.a.find({a:1}).sort({b:1})
   

   indeks harus mencakup keduanya a dan b bidang pada saat yang sama; misalnya indeks gabungan seperti {a:1,b:1} Dibutuhkan. Anda tidak dapat memiliki dua indeks terpisah {a:1} dan {b:1} , dan mengharapkan {a:1} indeks yang akan digunakan untuk bagian kesetaraan, dan {b:1} indeks yang akan digunakan untuk bagian sortir. Dalam hal ini, MongoDB akan memilih salah satu dari dua indeks.

   Oleh karena itu, benar bahwa hasil diurutkan karena dicari dan dikembalikan dalam urutan indeks.

2. Untuk menghindari pengurutan dalam memori menggunakan indeks gabungan, bagian pertama indeks harus memenuhi bagian kesetaraan kueri, dan bagian kedua harus memenuhi bagian pengurutan dari kueri (seperti yang ditunjukkan dalam penjelasan untuk (1) di atas).

   Jika Anda memiliki pertanyaan seperti ini:

   db.a.find({}).sort({a:1})
   

   indeks {a:1,b:1} dapat digunakan untuk bagian sortir (karena pada dasarnya Anda mengembalikan seluruh koleksi). Dan jika kueri Anda terlihat seperti ini:

   db.a.find({a:1}).sort({b:1})
   

   indeks yang sama {a:1,b:1} juga dapat digunakan untuk kedua bagian kueri. Juga:

   db.a.find({a:1,b:1})
   

   juga dapat menggunakan indeks yang sama {a:1,b:1}

   Perhatikan polanya di sini:find() diikuti oleh sort() parameter mengikuti urutan indeks {a:1,b:1} . Oleh karena itu, indeks majemuk harus diurutkan berdasarkan equality -> sort .

Pembaruan tentang penyortiran berbagai jenis

Jika bidang memiliki jenis yang berbeda antar dokumen (misalnya jika a apakah string dalam satu dokumen, nomor di dokumen lain, boolean di dokumen lain), bagaimana proses pengurutan?

Jawabannya adalah urutan perbandingan tipe MongoDB BSON. Untuk memparafrasekan halaman manual, urutannya adalah:

1. MinKey (tipe internal)
2. Nol
3. Angka (int, long, double, desimal)
4. Simbol, String
5. Objek
6. Array
7. BinData
8. Id Objek
9. Boolean
10. Tanggal
11. Stempel waktu
12. Ekspresi Reguler
13. MaxKey (tipe internal)

Jadi dari contoh di atas dengan menggunakan urutan menaik, dokumen yang berisi angka akan muncul terlebih dahulu, kemudian string, lalu boolean.