Как сортировка с индексом работает в MongoDB?

Question

Мне интересно, как сортировка с индексом действительно работает в MongoDB. В документации MongoDB есть couplearticles, но они фактически не описывают, как происходит сортировка или временная сложность. Поиски SO и interweb в целом до сих пор не принесли ничего важного.

Давайте предположим, что есть а документов в коллекции, находка() пункт соответствует б документов, есть предел с документов возвращаются, >>б >>с , и c - это некоторое количество, достаточно большое, чтобы возвращаемый набор не мог поместиться в память - скажем, 1M документов, например.

В начале операции, существуют б документы, которые должны быть отсортированы и отсортированный индекс дерева размера для функции документы будут отсортированы по.

Я могу себе представить:

A) траверс индекс для того, и для каждого ObjectId траверс список б документов. Возвратные совпадения до c. Это будет O (ab).

B) как A), но сначала создайте хэш-код идентификаторов объекта в b документов. Это O (a), но принимает O (b) память.

Я пытался рассмотреть виды, основанные на обходе набор б документов, но не могу придумать ничего быстрее, чем O (б журнала б), который не лучше, чем сортировка без индекса.

Я предполагаю (но, может быть, я ошибаюсь), что для каждого вида не требуется сканирование индекса, так как работает этот вид?

Update:

ответ Кевина и предоставил ссылку сужать вопрос много, но я хотел бы, чтобы подтвердить/уточнить несколько моментов:

1. Как я понимаю, вы не можете используйте разные индексы для запроса и сортировки, если вы хотите избежать сортировки в памяти. Когда я прочитал this page, казалось, что вы можете (или, по крайней мере, не указывать, так или иначе), но это кажется неправильным. По сути, документы сортируются, потому что они просматриваются в порядке индекса во время запроса и поэтому возвращаются в порядке индекса. Правильно?
2. При запросе на составной индекс индекс сортировки должен быть первым индексом в составном индексе, за исключением индексов, где запрос является равенством. Если нет, сортировка выполняется в памяти. Правильно?

3. Как работает сортировка с $in или $or запросов?Например, предположим, что запрос

   {a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

... и есть составной индекс на a и b в таком порядке. Как сортировка будет работать в случаях сортировки на a или b? $or еще сложнее, поскольку, как я понимаю, запросы $or по существу разделены на несколько отдельных запросов. Есть $or запросы всегда в памяти, по крайней мере, для слияния результатов отдельных запросов?

Answer 1

Индексы в MongoDB хранятся в структуре B-дерева, где каждая запись индекса указывает на конкретное местоположение на диске. Использование структуры B-дерева также означает, что индекс MongoDB хранится в отсортированном порядке, всегда перемещается в порядке и дешево для MongoDB для извлечения серии документов в отсортированном порядке через индексы.

этап SORT этап (т. Е. Сортировка в памяти) в запросе ограничен 32 МБ использования памяти. Запрос завершится неудачно, если этап SORT превысит этот предел. Этот предел можно обойти стороной, используя отсортированную природу индексов, чтобы MongoDB мог возвращать запрос с параметром sort() без выполнения сортировки в памяти.

Предположим, что запрос имеет форму:

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

с коллекцией a, имеющей индекс:

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

Есть два возможных сценария, когда sort() стадия задается в запрос:

1. MongoDB не может использовать отсортированный характер индекса и должен выполнять оперативную память SORT этап.

Это результат, если запрос не может использовать «префикс индекса». Например:

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

В приведенном выше запросе, индекс {b:1,c:1} может быть использован для:

• документов, имеющих b Match больше 100 для {b:{$gt:100}} части запроса.
• Однако не гарантирует, что возвращенные документы будут отсортированы с точки зрения c.

Поэтому у MongoDB нет выбора, кроме как выполнить сортировку в памяти. Результат этого запроса будет иметь этап SORT. Эта стадия SORT будет ограничена 32 МБ использования памяти.

2. MongoDB может использовать отсортированный характер индекса.

Это результат, если запрос использует:

• Сортировать ключи, соответствует порядку индекса и
• Задает один и тот же порядок, что и индекс (т.е. индекс {b:1,c:1} может быть использован для sort({b:1,c:1}) или sort({b:-1,c:-1}), но не sort({b:1,c:-1}))

Например:

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

В приведенном выше запросе, индекс {b:1,c:1} может быть использован для:

• документов, имеющих b Match больше 100 для {b:{$gt:100}} части запроса.
• В этом случае MongoDB может гарантировать, что возвращенные документы отсортированы с точки зрения b.

explain() выхода запроса выше будет не имеет SORT стадии. Кроме того, explain() вывод запроса с sort() и без него идентичны. По сути, мы получаем sort() бесплатно.

Полезный ресурс, чтобы понять эту тему: Optimizing MongoDB Compound Indexes. Обратите внимание, что это сообщение в блоге было написано еще в 2012 году. Хотя некоторые термины могут быть устаревшими, техничность сообщения все еще актуальна.

Update на последующие вопросы

1. MongoDB использует only one index for most queries. Так, например, чтобы избежать SORT этапа в памяти в запросе

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

   индекс должен охватывать как a и b поля в то же время; например требуется индекс соединения, такой как {a:1,b:1}. У вас не может быть двух отдельных индексов {a:1} и {b:1} и ожидать индекс {a:1}, который будет использоваться для части равенства, и индекс {b:1}, который будет использоваться для сортировки. В этом случае MongoDB выберет один из двух индексов.

   Поэтому правильно, что результаты сортируются, потому что они выглядят и возвращаются в порядке индекса.

2. Для того, чтобы избежать необходимости в оперативной памяти сортировки, используя индекс соединения, первая часть индекса должно удовлетворять части равенства запроса, а вторая часть должна удовлетворять сортировки части из запрос (как показано в пояснении к (1) выше).

   Если у вас есть запрос, как это:

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

   индекс {a:1,b:1} может быть использован для сортировки части (так как вы в основном возвращаются всю коллекцию). И если ваш запрос выглядит следующим образом:

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

   тот же индекс {a:1,b:1} может также использоваться для обеих частей запроса. Также:

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

   также может использовать один и тот же индекс {a:1,b:1}

   Обратите внимание на рисунок здесь: find() следуют sort() параметры следуют порядку индекса {a:1,b:1}. Поэтому индекс соединения должен быть упорядочен по формуле равенство -> сортировать.