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

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

Предположим, что в коллекции есть документы, предложение find() соответствует b документам, есть ли предел c документов, возвращаемых, a → b → c, а c - некоторое количество, достаточно большое, такое, что возвращаемый набор не может поместиться в память - скажем, 1M документов, например.

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

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

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

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

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

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

Update:

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

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

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

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

Ответ 1

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

Обновление: структура B-дерева верна для механизма хранения MMAPv1, но реализована немного по-другому механизмом хранения WiredTiger (по умолчанию начиная с MongoDB 3.2). Основная идея остается той же, когда обход индекса обходится дешево в отсортированном порядке.

Стадия 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 больше 100 для части {b:{$gt:100}} запроса.
Однако нет гарантии, что возвращенные документы отсортированы в соответствии с c.

Поэтому у MongoDB нет другого выбора, кроме как выполнить сортировку в памяти. Вывод explain() этого запроса будет иметь стадию 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 больше 100 для части {b:{$gt:100}} запроса.
В этом случае MongoDB может гарантировать, что возвращенные документы отсортированы в соответствии с b.

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

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

Обновленная информация о последующих вопросах

MongoDB использует только один индекс для большинства запросов. Так, например, чтобы избежать этапа в памяти SORT в запросе
```
db.a.find({a:1}).sort({b:1})
```
индекс должен одновременно охватывать поля a и b; например требуется составной индекс, такой как {a:1,b:1}. Вы не можете иметь два отдельных индекса {a:1} и {b:1} и ожидать, что индекс {a:1} будет использоваться для части равенства, а индекс {b:1} будет использоваться для части сортировки. В этом случае MongoDB выберет один из двух индексов.

Таким образом, верно, что результаты сортируются, поскольку они ищутся и возвращаются в порядке индекса.
Чтобы избежать сортировки в памяти с использованием составного индекса, первая часть индекса должна обслуживать часть запроса на равенство, а вторая часть должна обслуживать часть запроса сортировки (как показано в пояснении к ( 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}. Поэтому составной индекс должен быть упорядочен по равенству → сортировке.

Обновление о сортировке различных типов

Если поле имеет разные типы между документами (например, если a - строка в одном документе, число в других, логическое значение в другом), как будет выполняться сортировка?

Ответ - MongoDB BSON порядок сравнения типов. Перефразируя страницу справочника, порядок:

MinKey (внутренний тип)
Null
Числа (целые, длинные, двойные, десятичные)
Символ, Строка
объектаМассив
BinData
ObjectId
Логическое
Дата
Отметка
Регулярное выражение
MaxKey (внутренний тип)

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