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

Question

[Ascard]

Есть коллекция документов в Монге, представляющая собой простой двусвязный список, примерно такого вида:

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() чтобы достать из базы одним массивом значения конкретного поля из всех документов, я не нашёл.
А с ним проблема в том что работает он не быстрее решения полным перебором или решения с агрегатором.

Comments

[ComodoHacker]

документа на _id которого ссылается _prev или _next может не быть в коллекции.

Тогда откуда взялся этот _id?

[Ascard]

ComodoHacker, прилетает из внешнего источника, вместе с остальным содержимым.
Я же написал - документы в базу догружатся по мере необходимости. Ленивая такая коллекция получается. То есть в списке возможны пустоты. Вот для их выявления и нужно находить такие недозагруженные документы.

Answer 1

[ComodoHacker]

Могу предложить два решения.

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

Comments

[Ascard]

Неплохо, спасибо за идеи. Буду пробовать.