MongoDB nested array query: цікава задача і нюанси фільтрації

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Цю статтю варто розглядати як розважально-пізнавальну і рекомендовану для читання людям, котрі використовують або планують використовувати mongoDB і з ностальгією згадують курси дискретної математики і теорії множин.

Note: в статті будуть використовуватися певні позначення з теорії множин (⊂,⊄,∩,≠,∅,∈).

Пару тижнів тому в телеграм-каналі MongoDB мені на очі потрапило запитання. Суть його полягає в наступному.

Припустимо, у нас є колекція документів (структура і розмір для наглядності спрощені):

[
  {
    "_id": "uid1",
    "units": [{ "id": 1 }, { "id": 2 }, { "id": 3 }]
  },
  {
    "_id": "uid2",
    "units": [{ "id": 3 }, { "id": 4 }, { "id": 5 }]
  }
]

Потрібно знайти список всіх документів, в яких всі значення полів id з об’єктів вкладеного масиву «units» містяться в заданому (вхідному) масиві.

Наприклад, якщо вхідний масив [1, 3], маємо отримати порожній список, оскільки [1,2,3]⊄[1,3] і [3,4,5]⊄[1,3].

Якщо вхідний масив [2,3,4,5,6,7,10,20], маємо отримати:

[  
  {
    "_id": "uid2",    
    "units": [{ "id": 3 }, { "id": 4 }, { "id": 5 }]  
  }
]

оскільки [1,2,3] ⊄ [2,3,4,5,6,7,10,20], але [3,4,5] ⊂ [2,3,4,5,6,7,10,20].

Якщо вхідний масив, наприклад [1,15,17,2,3,70,4,5,200], маємо отримати всю колекцію з двох елементів, оскільки [1,2,3] ⊂ [1,15,17,2,3,70,4,5,200] і [3,4,5] ⊂ [1,15,17,2,3,70,4,5,200].

Додатковою умовою була необхідність не використовувати агрегацію, оскільки вибірка потрібна була для фільтрації документів в updateMany, де агрегацію застосовувати не можна.

Задача мене зацікавила, я мав час та натхнення, тому вирішив повозитися.

До речі, в кого буде таке бажання, той може перейти mongoplayground.net і спробувати самостійно написати запит.

Розв’язок 1

Спочатку я вирішив написати запит за допомогою агрегації (це виглядало неважко), а потім спробувати його спростити до рівня одного $match.

Отже, визначимо вхідний масив як inputArray і маємо наступне рішення:

  
db.collection.aggregate([
  {
    $project: {
      units: 1, 
      ids: { $map: { input: '$units', as: 'caller', in: '$$caller.id' } }
    }
  },
  {
    $project: {
      units: 1, 
      isSubset: { $setIsSubset: ['$ids', inputArray] }
    }
  },
  {
    $match: { isSubset: true }
  },
  {
    $project: { isSubset: 0 }
  }
])

Тобто робимо наступне:

  1. в кожному документі мапимо масив об’єктів units, перетворюючи його на новий масив чисел «ids»;
  2. перевіряємо, чи є масив ids підмножиною вхідного масиву (inputArray) і зберігаємо результат перевірки в нове бульове поле «isSubset»;
  3. вибираємо тільки ті документи, де isSubset рівне true;
  4. викидаємо з проекції поле isSubset, створене в ході агрегації.

Другий крок: спрощуємо до одного $match:

  
db.collection.aggregate([
  {
    $match: {
      $expr: {
        $eq: [
          {
            $setIsSubset: [
              { $map: { input: '$units', as: 'caller', in: '$$caller.id' } },
              inputArray
            ]
          },
          true
        ]
      }
    }
  }
])

Останній крок: перетворюємо запит на звичайний find:

db.collection.find({
  $expr: {
    $eq: [
      {
        $setIsSubset: [
          { $map: { input: '$units', as: 'caller', in: '$$caller.id' } },
          inputArray
        ]
      },
      true
    ]
  }
})

Розв’язок задачі начебто є, але мені він здавався занадто пямолінийним і недостатньо вишуканим. А оскільки, як я вже згадував, в мене був час та натхнення, я вирішив знайти ще один розв’язок, використовуючи інший шлях.

Розв’язок 2

Для спрощення пояснення зробимо наступні визначення:

  • Визначимо А як масив (множину) значеннь всіх полів id об’єктів вкладеного масиву units невизначеного документу колекції.
  • Визначимо А1 як масив (множину) значеннь всіх полів id об’єктів вкладеного масиву units першого документу колекції. Тобто А1 = [1,2,3]
  • Визначимо А2 масив (множину) значеннь всіх полів id об’єктів вкладеного масиву units другого документу колекції. Тобто А2 = [3,4,5]
  • Визначимо М як вхідний масив (множину) і для наглядності надамо йому значення [1,2,3,4] в прикладах запитів (тобто матимемо А1⊂М, А2⊄М, але А2∩М≠∅).

Тепер до суті.

Власне, чому ми в першому розв’язку йшли через агрегацію, чому не можна було просто взяти й використати find?

Тому що в find при використанні умови фільтрації щодо елементів вкладеного масиву, з колекції вибираються документи, де хоча б один елемент з вкладеного масиву відповідає умові. Тобто, якщо ми, наприклад, напишемо такий запит:

db.collection.find({
  'units.id': { $in: [1, 2, 3, 4] }
})

у нас вибереться не тільки тільки перший документ, але й другий, оскільки А2∩М≠∅. А нам потрібно вибрати тільки ті документи, де А⊂М, тобто тільки перший документ.

Що одразу спадає на думку — застосувати $elemMatch. Але ні, при виконанні запиту:


 db.collection.find({
  units: { $elemMatch: { id: { $in: [1, 2, 3, 4] } } }
})

маємо той самий результат, обидва документа.

Ок, що ще можна придумати? Друге що спадає на думку, застосувати «заперечення щодо протилежної операції». Що мається на увазі?

Візьмемо цю саму колекцію:

[
    {
        "_id": "uid1",
        "units": [{ "id": 1 }, { "id": 2 }, { "id": 3 }]
    },
    {
        "_id": "uid2",
        "units": [{ "id": 3 }, { "id": 4 }, { "id": 5 }]
    }
]

і спростимо умову вибірки: нехай нам потрібно вибрати документи, в яких всі об’єкти з вкладеного масиву units мають значення id <= 3, або іншими словами, потрібно вибрати документи, де для всіх id∈А виконується умова id⩽3.

Очевидно, що правильна вибірка — перший документ. І очевидно, що запит:

db.collection.find({
  "units.id": { $lte: 3 }
}) 

поверне два документи (оскільки 3∈А2). А от запит:

db.collection.find({
  "units.id": { $not: { $gt: 3 } }
})

відпрацює так, як нам потрібно, і поверне тільки перший документ. Це і є використання «заперечення щодо протилежної операції». $gt є операцією протилежною до $lte і поверне нам ті документи, де хоча б для одного id ∈ А виконується умова id>3, а операція $not дозволить вибрати всі документи з загальної колекції, які не входять в вибірку по першій умові.

Тепер знову повернемося до розв’язку основної задачі. Яка операція є протилежною щодо $in? Начебто $nin. Пробуємо:

db.collection.find({
  "units.id": { $not: { $nin: [ 1, 2, 3, 4 ] } }
})

отримуємо обидва документи. Як так? Пробуємо без $not:

db.collection.find({
  "units.id": { $nin: [ 1, 2, 3, 4 ] }
})

Отримуємо порожній список. Читаємо документацію по $nin. Знаходимо:

If the field holds an array, then the $nin operator selects the documents whose field holds an array with no element equal to a value in the specified array.

У нашому випадку це означає, що вибираються документи, для яких А∩М=∅.

Пічалька. І крім того, якось дивно. Чому поведінка $in та $nin так відрізняється? Спробуємо копнути глибше і застосувати explain(). І виявиляється, що запит:

 db.collection.find({
  'units.id': { $nin: [1, 2, 3, 4] }
})

насправді розгортається в:

db.collection.find({
  'units.id': { $not: { $in: [1, 2, 3, 4] } }
})

а запит:

db.collection.find({
  'units.id': { $not: { $nin: [1, 2, 3, 4] } }
})

взагалі в:

db.collection.find({
  $nor: [{ 'units.id': { $not: { $in: [1, 2, 3, 4] } } }]
})

Тобто операція «$nin» не є атомарною, на відміну від «$in» або тієї ж «$gt» і розгортається в «$not»: { «$in»: ...}. А при застосуванні {«$not»: { «$nin»: ...}} ми фактично отримуємо звичайний $in бо $nor і $not анулюють одне одного.

Але все ж залишився варіант з комбінуванням $nin і $elemMatch.

Пробуємо запит:


db.collection.find({
  units: { $not: { $elemMatch: { id: { $nin: [1, 2, 3, 4] } } } }
})

або він же в розгорнутому вигляді:


db.collection.find({
  units: { $not: { $elemMatch: { id: { $not: { $in: [1, 2, 3, 4] } } } } }
})

і цей запит відпрацьовує саме як нам потрібно і повертає перший документ.

Але ми пам’ятаємо, що запит:


db.collection.find({
  units: { $elemMatch: { id: { $in: [1, 2, 3, 4] } } }
})

повертає обидва документа. Тоді чому $not + $not у випадку $elemMatch відпрацьовує правильно?

Як виявляється, тому що $not знаходиться всередині $elemMatch і застосовується не до документів колекції, а до елементів вкладеного масиву.

І хоча запит:


db.collection.find({
  units: { $elemMatch: { id: { $in: [1,2,3,4] } } }
})  

повертає обидва документа з колекції , оскільки і А1∩[1,2,3]≠∅ і А2∩[1,2,3]≠∅, запит:


db.collection.find({
  units: { $elemMatch: { id: { $not: { $in: [1,2,3,4] } } } }
})  

повертає тільки другий документ, оскільки (А1 — А1∩[1,2,3,4])=∅, а (А2 — А2∩[1,2,3,4])≠∅. І відповідно, якщо ми додамо $not перед $elemMatch, то отримаємо як результат лише перший документ. Отже, другий розв’язок:


db.collection.find({
  units: { $not: { $elemMatch: { id: { $nin: inputArray } } } }
})

і для наочності перший розв’язок:


db.collection.find({
  $expr: {
    $eq: [
      {
        $setIsSubset: [
          { $map: { input: '$units', as: 'caller', in: '$$caller.id' } },
          inputArray
        ]
      },
      true
    ]
  }
})

де inputArray — заданий (вхідний) масив, який використовуємо для фільтрації.

Висновок

Використовуйте mongoDB, якщо вона вам подобається, і отримаєте задоволення від знаходження цікавих рішень, і не використовуйте, якщо вона вам не подобається, бо задовбетесь :).

👍НравитсяПонравилось2
В избранноеВ избранном1
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Дякую, паее Ярославе! Було цікаво і корисно :)

Прошу.
Якщо будуть побажання стосовного того, що варто освітити в роботі mongoDB — пишіть. Постараюся відповісти або в коментарях або, якщо тема об’ємна, в окремій статті.

Зачем это все. Код на одной мало известной субд

Модель документа

class Document
        {
            public Unit[] Units;
        }

        class Unit
        {
            public int Id { get; set; }
        }

Тестовый входящий запрос

            var testArray = new Unit[] { new Unit { Id = 1 }, new Unit { Id = 2 } };

Сам запрос на LINQ

     var docs =_dniproDbClient.GetWhere<Document>(x => x.Units.Length == testArray.Length)
                           .Where(x => x.Units.All(y => testArray.Contains(y)));

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

Зачем это все.

Затем что тред не о

одной мало известной субд

Ну и монга тоже linq поддерживает, хоть и с нюансами

Ну и монга тоже linq поддерживает, хоть и с нюансами

Так используйте линкью, а не эту боль и страдания под названием find в Монго.
А если нужно быстродействие, то добавьте отдельное поле UnitsHash в документе и храните там хеш от всех элементов в массиве. И искать будете все документы на первой космической.

Зачем это все.

Тим хто використовує Монгу може бути корисно. Ну і задача сама по собі цікава з точки зору вирішення в mongoDB.

var docs =_dniproDbClient.GetWhere(x => x.Units.Length == testArray.Length)
.Where(x => x.Units.All(y => testArray.Contains(y)));

Ну і чим це краще ніж:

db.collection.find({
units: { $not: { $elemMatch: { id: { $nin: inputArray } } } }
})
Ну і чим це краще ніж:

1. Тем что у меня есть условие

GetWhere(x => x.Units.Length == testArray.Length)

Которое сразу отметает все массивы, размер которых не равен тому что мы ищем.

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

А ваше

db.collection.find({
units: { $not: { $elemMatch: { id: { $nin: inputArray } } } }
})

Это полные дрова. Это фулскан умноженный на количество элементов в inputArray.

На самом деле, как я написал выше, правильное решение вообще через

UnitsHash

И тогда запрос будет еще проще и будет выполнятся фактически за О(1), тоесть моментально почти при любом размере коллекции.

1) З чого Ви взяли, що вхідний масив і масив units повинні мати однаковий розмір для проходження умови вибірки?
2) В першому реченні сказано, що це стання пізнавально-розважальна, для того щоб краще зрозуміти як працюють вибірки в mongoDB. І це для тих, хто використовує монгу.
Щодо практичного застовування — людина яка ставила питання на каналі дякувала, і казала що в них все працює чудово, документи швидко оновлюються по умові фільтрації. Мабуть той об’єм даних і структура документів для яких це рішення застосовується не призводить до проблем зі швидкістю. І звичайно для кожного випадку потрібно індивідуально підбирати схему, при необхідності доповнювати структуру документу і будувати відповідний запит.
І я взагалі не розумію, чому Ви наводите приклади коду на .NET, якщо рішення запропоноване мною може бути цікавим для зовсім іншого стеку технологій.

Да, моя ошибка. Не дочитал условие задачи. Тогда оптимизация не такая тривиальная, через хеш не получится.

Но сам линкью упращается в два раза.

db.Where(x => x.Units.All(y => testArray.Contains(y)));

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

Можливо я помиляюся, але мабуть замість

Contains(y)

повинно бути

Contains(y.id)

Але ок, тепер Linq запит виглядає лаконічним, хоча навряд чи значно ефективнішим ніж мій.
І все ж питання, чому Ви наводите приклад .NET, якщо стеком може бути наприклад Ruby+MongoDB ?
Щодо методу монте карло і пробації — дякую за інфу, ознайомлюся.

Подписаться на комментарии