Как ускорить поиск несуществующих элементов в двусвязном списке?

Есть коллекция документов в Монге, представляющая собой простой двусвязный список, примерно такого вида:
Item {
  _id: number,
  _prev: number | null,
  _next: number | null,
   // все остальные поля
}

Поля _next и _prev, соответственно, содержат _id cвязанных записей, или null для первой и последней записи.
Коллекция, по мере надобности, заполняется кусками из внешнего источника, поэтому документа на _id которого ссылается _prev или _next может не быть в коллекции.
Задача: найти такие документы для их дозагрузки в коллекцию, то есть те на которые есть указание в _prev или _next у одного из документов, но их самих нет в базе.
Коллекция уже довольно большая (500к+ документов) и будет расти, а решение полным перебором - для каждой записи _prev/_next проверить наличие документа, работает десятки секунд уже сейчас, что неприемлемо долго.

Как это можно ускорить? Индексы давно созданы, шардов базы нет и не будет.

Пытался решить проблему используя агрегатор
db.items.aggregate([
  { $lookup: {
      from:         "items",
      localField:   "_prev",
      foreignField: "id",
      as:           "prev"
  }},
  { $match: {
      "prev": {$size: 0}
  }}
],{
  allowDiskUse: true
});

Со своей задачей он справляется, но опять же - долго.

По идее, как я понимаю, задача сводится к простому поиску пересечения между массивом со всеми _prev/_next и массивом со всеми _id.
Но кроме как использовать db.collection.distinct() чтобы достать из базы одним массивом значения конкретного поля из всех документов, я не нашёл.
А с ним проблема в том что работает он не быстрее решения полным перебором или решения с агрегатором.
  • Вопрос задан
  • 133 просмотра
Пригласить эксперта
Ответы на вопрос 1
@ComodoHacker
Могу предложить два решения.

  1. После записи документа проверять наличие в коллекции _prev и _next, и отсутствующие записывать в отдельную коллекцию. Тогда потом искать их не придется, они будут уже собраны в отдельной коллекции.

  2. В _id документа не класть внешний идентификатор, как вы делаете сейчас, а генерировать внутренний. А внешний сохранять в отдельном поле, по которому построить индекс. Так же поступать и с _prev и _next. При записи документа нужно искать его _prev и _next по внешним идетнификаторам, и если найдены, проставлять внутренние.

    Для поиска отсутствующих документов нужно будет проскаинровать всю коллекцию и выбрать те внешние id из _prev и _next, для которых не заполнены внутренние _id.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы