MongoDB: слишком много полей для индексации? Используйте общий индекс

http://edgystuff.tumblr.com/post/47178201123/mongodb-indexing-tip-3-too-many-fields-to-index-use
  • Перевод

Суть проблемы


Бывают ситуации когда документы имеют много различных полей и необходимо иметь эффективные запросы по ним. Например есть документ описывающий человека:

{
    _id: 123,
    firstName: "John",
    lastName: "Smith",
    age: 25,
    height: 6.0,
    dob: Date,
    eyes: "blue",
    sign: "Capricorn",
    ...
}


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

Решение #1: Составной индекс по именам и значениям полей


Спроектируем схему документа воспользовавшись возможностью хранения полей документа в виде списка объектов:

{
    _id: 123,
    props: [
    { n: "firstName", v: "John"},
    { n: "lastName", v: "Smith"},
    { n: "age", v: 25},
    ...
    ]
}


Для решения проблемы создается составной индекс по имени и значению объектов внутри списка. Для наглядности создадим 5 миллионов документов состоящих из фиктивных свойств от prop0 до prop9 которые имеют случайное значение от 0 до 1000.

> for (var i = 0; i < 5000000; ++i) { var arr = []; for (var j = 0; j < 10; ++j) { arr.push({n: "prop" + j, v: Math.floor(Math.random() * 1000) }) }; db.generic.insert({props: arr}) }
> db.generic.findOne()
{
  "_id": ObjectId("515dd3b4f0bd676b816aa9b0"),
  "props": [
    {
      "n": "prop0",
      "v": 40
    },
    {
      "n": "prop1",
      "v": 198
    },
...
    {
      "n": "prop9",
      "v": 652
    }
  ]
}
> db.generic.ensureIndex({"props.n": 1, "props.v": 1})
> db.generic.stats()
{
  "ns": "test.generic",
  "count": 5020473,
  "size": 1847534064,
  "avgObjSize": 368,
  "storageSize": 2600636416,
  "numExtents": 19,
  "nindexes": 2,
  "lastExtentSize": 680280064,
  "paddingFactor": 1,
  "systemFlags": 1,
  "userFlags": 0,
  "totalIndexSize": 1785352240,
  "indexSizes": {
    "_id_": 162898624,
    "props.n_1_props.v_1": 1622453616
  },
  "ok": 1
}


В таком случае размер индекса равен 1.6 Гб т.к в индексе хранится как имя свойства, так и его значение. Теперь попробуем найти документы в которых prop1 равен 0:

> db.generic.findOne({"props.n": "prop1", "props.v": 0})
{
  "_id": ObjectId("515dd4298bff7c34610f6ae8"),
  "props": [
    {
      "n": "prop0",
      "v": 788
    },
    {
      "n": "prop1",
      "v": 0
    },
...
    {
      "n": "prop9",
      "v": 788
    }
  ]
}
> db.generic.find({"props.n": "prop1", "props.v": 0}).explain()
{
  "cursor": "BtreeCursor props.n_1_props.v_1",
  "isMultiKey": true,
  "n": 49822,
  "nscannedObjects": 5020473,
  "nscanned": 5020473,
  "nscannedObjectsAllPlans": 5020473,
  "nscannedAllPlans": 5020473,
  "scanAndOrder": false,
  "indexOnly": false,
  "nYields": 0,
  "nChunkSkips": 0,
  "millis": 252028,
  "indexBounds": {
    "props.n": [
      [
        "prop1",
        "prop1"
      ]
    ],
    "props.v": [
      [
        {
          "$minElement": 1
        },
        {
          "$maxElement": 1
        }
      ]
    ]
  },
  "server": "agmac.local:27017"
}


Такое решение не дало ожидаемого результата: найдено ~50,000 документов за 252 секунды. Это происходит потому что каждый запрос n=prop1 и v=0 не требует выполнения обоих условий одновременно для вложенных документов, поэтому в итоговый результат попадают документы удовлетворяющие как требованию n=prop1, так и v=0 по раздельности, а это совсем не то что ожидалось. Можно уточнить запрос воспользовавшись $elemMatch:

> db.generic.findOne({"props": { $elemMatch: {n: "prop1", v: 0} }})


Теперь проверим как используется индекс и как долго выполняется запрос в MongoDB v2.2:

> db.generic.find({"props": { $elemMatch: {n: "prop1", v: 0} }}).explain()
{
  "cursor": "BtreeCursor props.n_1_props.v_1",
  "isMultiKey": true,
  "n": 5024,
  "nscannedObjects": 5020473,
  "nscanned": 5020473,
  "nscannedObjectsAllPlans": 5020473,
  "nscannedAllPlans": 5020473,
  "scanAndOrder": false,
  "indexOnly": false,
  "nYields": 0,
  "nChunkSkips": 0,
  "millis": 278784,
  "indexBounds": {
    "props.n": [
      [
        "prop1",
        "prop1"
      ]
    ],
    "props.v": [
      [
        {
          "$minElement": 1
        },
        {
          "$maxElement": 1
        }
      ]
    ]
  },
  "server": "agmac.local:27017"
}


Запрос выполнился правильно и вернул 5024 документа, но всё еще медленно! Из информации команды explain можно увидеть что причина в том что для поля v всё еще используется диапазон. Для того что бы понять почему так происходит, разберем пример подробнее. Если не использовать $elemMatch то все комбинации полей удовлетворяющие хотя бы одному из условий запроса по отдельности, могут попасть в итоговую выборку. В таком случае это было бы невозможно использовать для поддержания индекса, т.к это приводило бы к огромному количеству возможных комбинаций. Поэтому при запросе MongoDB сделала выбор в пользу построения B-Tree из значений вложенных документов и игнорированию возможных комбинаций (основное поведение для $elemMatch). Но почему запрос с $elemMatch выполняется так медленно? Виной этому был баг который был исправлен SERVER-3104 в MongoDB v2.4. Проверим этот же запрос в исправленной версии:

> db.generic.find({"props": { $elemMatch: {n: "prop1", v: 0} }}).explain()
{
  "cursor": "BtreeCursor props.n_1_props.v_1",
  "isMultiKey": true,
  "n": 5024,
  "nscannedObjects": 5024,
  "nscanned": 5024,
  "nscannedObjectsAllPlans": 5024,
  "nscannedAllPlans": 5024,
  "scanAndOrder": false,
  "indexOnly": false,
  "nYields": 0,
  "nChunkSkips": 0,
  "millis": 21,
  "indexBounds": {
    "props.n": [
      [
        "prop1",
        "prop1"
      ]
    ],
    "props.v": [
      [
        0,
        0
      ]
    ]
  },
  "server": "agmac.local:27017"
}


Запрос выполнился за 21 миллисекунду!

Решение #2: Один общий индекс


Другой способ решения проблемы это хранить поля в списке в виде объектов property: value. Это решение работает в MongoDB версии v2.2 и v2.4. Создадим документы вида:

> for (var i = 0; i < 5000000; ++i) { var arr = []; for (var j = 0; j < 10; ++j) { var doc = {}; doc["prop" + j] =  Math.floor(Math.random() * 1000); arr.push(doc) }) }; db.generic2.insert({props: arr}) }
> db.generic2.findOne()
{
  "_id": ObjectId("515e5e6a71b0722678929760"),
  "props": [
    {
      "prop0": 881
    },
    {
      "prop1": 47
    },
...
    {
      "prop9": 717
    }
  ]
}


Построим индекс:

> db.generic2.ensureIndex({props: 1})
> db.generic2.stats()
{
  "ns": "test.generic2",
  "count": 5000000,
  "size": 1360000032,
  "avgObjSize": 272.0000064,
  "storageSize": 1499676672,
  "numExtents": 19,
  "nindexes": 2,
  "lastExtentSize": 393670656,
  "paddingFactor": 1,
  "systemFlags": 1,
  "userFlags": 0,
  "totalIndexSize": 2384023488,
  "indexSizes": {
    "_id_": 162269072,
    "props_1": 2221754416
  },
  "ok": 1
}


Размер индекса получился размером в ~2.2 Гб что на 40% больше чем в решение #1 потому что BSON вложенных документов хранит себя в индексе как BLOB'ы. Теперь выполним запрос:

> db.generic2.find({"props": {"prop1": 0} }).explain()
{
  "cursor": "BtreeCursor props_1",
  "isMultiKey": true,
  "n": 4958,
  "nscannedObjects": 4958,
  "nscanned": 4958,
  "nscannedObjectsAllPlans": 4958,
  "nscannedAllPlans": 4958,
  "scanAndOrder": false,
  "indexOnly": false,
  "nYields": 0,
  "nChunkSkips": 0,
  "millis": 15,
  "indexBounds": {
    "props": [
      [
        {
          "prop1": 0
        },
        {
          "prop1": 0
        }
      ]
    ]
  },
  "server": "agmac.local:27017"
}


Запрос выполнился за 15 мс что быстрее первого решения! Но есть одно условие, при составлении запроса необходимо описывать объект поддокумента целиком. Для того что бы выполнить выборку документов удовлетворяющие запросу где prop1 может быть равен от 0 до 9, необходимо выполнить запрос:

> db.generic2.find({"props": { $gte: {"prop1": 0}, $lte: {"prop1": 9} })


Немного неудобно, а так же если есть и другие поля во вложенном документе, то они должны участвовать при составлении запроса (т.к вложенные документы хранятся в виде BLOB'ов).
Так же есть еще одно ограничение: нельзя индексировать отдельно только значения полей, тогда как в решении #1 можно построить индекс props.v для поиска например всех документов имеющие значение 10. Решение #2 этого не позволяет.

Заключение


Можно увидеть что MongoDB v2.4 теперь предлагает простое и эффективное решение для построения общих индексов для документов имеющих большое количество полей, которым можно воспользоваться для своих «Big Data» проектов.
Поделиться публикацией
Комментарии 17
    0
    Хм. А ведь это решение можно обобщить для всех баз данных, не только MongoDB…
      +1
      уже: postgresql hstore + gis/gist
        0
        Это какая-то технология, поддерживаемая СУБД?
        Я-то говорил про модификацию схемы данных, что можно сделать независимо от используемой СУБД.
          0
          такая схема называется «слабоструктурированные данные», под них и заточен hstore с индексами gis/gist.
            0
            Ну да, можно и в реляционной БД хранить данные в формате key-value, однако сразу огребаем проблемы с типами. Также, невозможно использовать внешние ключи и каскадные операции.
              +1
              Да, с внешними ключами проблема, хотя про невозможность вы зря сказали — гибридную схему никто не отменял.
              Про недостатки схемы key-value я давно знаю, а вот тот факт, что у такого способа есть еще и достоинства, я узнал только сейчас.
              Впрочем, мне и поиск по всем полям раньше делать не доводилось.
                0
                Да, истина как всегда где-то между :) гибридная схема может иметь смысл.

                Но на счет эффективности одного индекса против нескольких в реляционной БД, я бы так сходу ответ не дал. Сложный вопрос. И от данных зависит.
        +1
        > Для наглядности создадим миллион документов состоящих из фиктивных свойств
        > for (var i = 0; i < 5000000; ++i)

        И всё же миллион или пять миллионов?
          +4
          Автор, явно не хватает зависимости времени вставки от варианта решения.
            0
            Я не автор, это лишь мой ужасный перевод =) Но я воспроизводил эти примеры и попробовал сделать замер вставки после создания индексов:

            Решение #1
            > beginTime=new Date();for(var i=0;i<1000000;++i){var arr=[];for(var j=0;j<10;++j){arr.push({n:"prop"+j,v:Math.floor(Math.random()*1000)})}db.generic.insert({props:arr})}print((new Date()).getTime()-this.beginTime.getTime());
            531189
            




            Решение #2
            > beginTime=new Date();for(var i=0;i<1000000;++i){var arr=[];for(var j=0;j<10;++j){var doc={};doc["prop"+j]=Math.floor(Math.random()*1000);arr.push(doc)}db.generic2.insert({props:arr})}print((new Date()).getTime()-this.beginTime.getTime());
            532890
            




            P.S без индексов вставка была ~16к insert/s
              0
              Т.е. оба варианта решения уменьшили скорость вставки примерно одинаково, в 8 раз.
            0
            Делал нечто похожее. Только я склеивал ключ и значение. Например: prop0-40, prop1-198. Ваше решение конечно более гибкое, т.к. даёт возможность искать в том числе и по диапазоном, а моё работает только на сравнение.
              0
              А теперь создадим в 10 раз больше документов и всё равно получаем индекс, не влазящий в оперативную память. А на FreeBSD это гарантированный крэш, даже не торможение.
                0
                Хм, а почему на FreeBSD индекс, не влазящий в оперативную память, приведет к крэшу?
                  0
                  Это вопросы к разработчикам. По-моему, они неправильно используют memory map. Там всё очень плохо становится, когда база вместе с индексами приближается по объёму к размеру оперативной памяти. На линуксе всё просто тормозить начинает (довольно логично), а на фрях — плохо дело.
                0
                Отлично! Решил после этого поста обновить mongodb и переписать поиск по таблице с пользователями
                  0
                  Правильно ли я понимаю что в первом варианте нельзя сделать сортировку, а во втором варианте возможен поиск только по одному полю?

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое