Данные OSM в MongoDB

После замеров скорости работы скриптов на питоновском профайлере cProfile оказалось, что самая затратная операция - count(). Вызвать .count у запроса - в 4 раза дороже, чем .next().

Оказалось, что вызовы count занимают в моём скрипте больше половины времени, 160 секунд из 290.

Переделал скрипт. Было:

for node in db.nodes.find(...):
    bad_neighbors = db.nodes.find({'_id': {'$in': node['neighbors']}})
    while bad_neighbors.count() > 0:
        for neighbor in bad_neighbors:
            ...
        bad_neighbors.rewind()

Заменил на счётчик в виде переменной, который запускается в цикле.

for node in db.nodes.find(...):
    bad_neighbors = db.nodes.find({'_id': {'$in': node['neighbors']}})
    bad_neighbors_count = 0
    while True:
        for neighbor in bad_neighbors:
            bad_neighbors_count += 1
            ...
        if bad_neighbors_count == 0:
            break
        bad_neighbors.rewind()

Суммарное время сократилось до 134 секунд, из них 107 - на cursor.next, в которых один и тот же объект достаётся минимум дважды. Есть куда оптимизировать.

siberiano, стесняюсь спросить, с монгой никогда не работал - а while bad_neighbors: не работает, или не подходит по контексту?

Я написал плагин к Osmosis. После некоторого размышления я изменил структуру базы, убрав оттуда обратные ссылки (node → way, way → relation, relation → relation). Слишком большой оверхед при импорте получался.

Пока получается такая статистика:
Импорт Новосибирской области (с gis-lab.info) занимает 84 секунды из которых 10 уходит на создание нужных индексов. Машина – одноядерный Athlon 3200.


> db.stats()
{
    "db" : "osm",
    "collections" : 6,
    "objects" : 967076,
    "avgObjSize" : 62.81341693930984,
    "dataSize" : 60745348,
    "storageSize" : 109661952,
    "numExtents" : 21,
    "indexes" : 6,
    "indexSize" : 67698688,
    "fileSize" : 469762048,
    "ok" : 1
}

Места действительно жрет как слон веники. Как это можно оптимизировать, не представляю.

Я пошагово удаляю соседей, которые не на перекрёстках и на ходу меняю список соседей. Поэтому когда ближайших обработал, надо запросить ещё раз, и так пока по всем направлениям не дойду до перекрёстков.

А my_cursor всегда переводится в True, даже если в нём пусто:
In [21]: x = db.routes.find({‘_id’: -1})
In [22]: 1 if x else 0
Out[22]: 1

Он оставляет место под расширения документов, чтобы если начнёшь писать в них новые свойства, не пришлось раскидывать кластерами по файлу.

Если ты что-то удалил из базы, чтобы сжать, нужно $ mongod --repair --dbpath=…

А какие индексы делаешь? Я для того чтобы сделать дорожный граф, создал единственный индекс - tags.highway.

Сейчас после небольшой работы с монго я пришёл к такой схеме:

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

  2. никаких рабочих вычислений на этой базе делать нельзя. Для предметной области нужно делать отдельную БД, и туда экспортировать объекты уже в том виде, в котором нужно.

  3. Лучше держать немного больших документов, чем много мелких. Будет оптимальнее использоваться диск (больше реальных данных, меньше доля “заделов”). То есть нужно всё денормализовывать, чтобы не делать "join"ов. Чем меньше раз запрашиваешь курсор, тем лучше. Напротив, атомарная запись или запись одного документа в mongo очень быстрая, ею можно пользоваться часто.

  4. потоковая конвертация с mongo - тормозная. Если есть возможность, лучше всё сразу считать в память, потом формировать объекты, какие нужно, и записывать. У меня размер коллекции в базе - 87 МБ, в памяти Питона те же объекты занимают 9 МБ.

Примерно к тем же выводам я и пришел. У меня две базы. Одна под минутную репликацию, вторая под геометрию. В основной базе три коллекции примерно такой структуры:


Nodes:
{ 
    "_id" : NumberLong(32521222), 
    "lat" : 54.7724042, 
    "lon" : 83.1009863, 
    "tags": {"amenity": "parking"} 
}

Ways:
{ 
    "_id" : NumberLong(17237995), 
    "nodes" : [NumberLong(178727045), NumberLong(269537100)], 
    "tags" : { "highway" : "primary"}, 
}

Relations:
{ 
    "_id" : NumberLong(129298), 
    "members" : [{
        "ref" : NumberLong(23363997),
        "type" : "way",
        "role" : "to"
    }, {
        "ref" : NumberLong(35133693),
        "type" : "way",
        "role" : "from"
    }, {
        "ref" : NumberLong(248503088),
        "type" : "node",
        "role" : "via"
    }], 
    "tags" : { "restriction" : "no_left_turn", "type" : "restriction" } 
}

Индексы на полях ways.nodes и (relations.members.type, relations.members.ref). Без индексов не получится отслеживать изменения геометрии при изменении объекта. Что отсюда можно выкинуть, не представляю.

Основная проблема у меня в том, что для того чтобы построить геометрию, скажем, для вея, нужны координаты его точек, а это довольно тяжелая выборка. Выгрузить все ноды в память тоже не вариант. Для РФ они занимают 1Гб только в бинарном виде.

Кстати, а ты можешь расшарить в битторренте базу России? (mongodubp => bz2) Именно эти три коллекции.

Вот пример документа у меня в базе. При работе с ними никаких дополнительных запросов не нужно. Теги путей я уберу скоро, они не нужны. Из файла области таких документов получается ~36 000.

{
    "_id" : 130763674,
    "changeset" : 6422529,
    "id" : 130763674,
    "lat" : 55.0410469,
    "lon" : 82.3909092,
    "timestamp" : "2010-11-21T13:30:55Z",
    "uid" : 183878,
    "user" : "whalerich",
    "version" : "9",
    "routes" : [
        {
            "way" : [
                {
                    "ref" : "M-51",
                    "highway" : "trunk"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk"
                }
            ],
            "via" : [
                130763195,
                659857287
            ],
            "id" : 210244290,
            "len" : 721.3430402945971
        },
        {
            "way" : [
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                },
                {
                    "ref" : "M-51",
                    "highway" : "trunk",
                    "oneway" : "yes"
                }
            ],
            "via" : [
                997755222,
                130763193,
                997754917,
                130763192,
                997754958,
                410845442,
                410845443
            ],
            "id" : 210244284,
            "len" : 913.9816212646475
        },
        {
            "way" : [
                {
                    "name" : "Северный обход Новосибирска",
                    "highway" : "trunk"
                },
                {
                    "name" : "Северный обход Новосибирска",
                    "highway" : "trunk"
                }
            ],
            "via" : [
                707377151
            ],
            "id" : 389013040,
            "len" : 335.20540758147973
        }
    ],
    "neighbors" : [
        210244290,
        210244284,
        389013040
    ]
}

Дело мое движется время от времени…
Хочу описать некоторый алгоритм, чтобы стало себе понятнее)

Для быстрого отображения или редактирования карты хотелось бы иметь возможность быстро определить какие веи и “свободные” ноды входят целиком, “задевают” этот тайл или накрывают его.
(Если тайл лежит целиком внутри вея, то этот вей задает его цвет полностью и этот признак тоже хотелось бы иметь в базе.)

Алгоритм, который собирает эту инфу я и накодил. Наверняка есть баги какие-нибудь и пока нет поддержки дырок, но ее ввести достаточно легко вроде бы.
Работает эта штука следующим образом.
Алгоритм пробегает по всем веям в базе и делает с ними следующее:
Сперва находится тайл максимального уровня, который содержит в себе целиком данный вей.
Для этого берем любую точку вея и смотрю в каком тайле максимального уровня (например 15 или 17) она лежит. Смотрим лежат ли все остальные точки вея (ну или bbox вея) в этом же тайле. Если нет, то берем предка этого тайла и делаем аналогичную проверку для него. Когда мы получили тайл в котором лежат все точки вея, то этот тай будет для нас скажем “корневым”… тайлом с которого мы запустим итерационный процесс.

После этого составляется список тайлов для проверки. Пока в него добавляется только корневой тайл.
Проверка заключается в том что ищется пересечение тайла с веем… и тайлу ставится признак того полностью внутри ли он, полностью снаружи или на него попадает граница вея.
Если тайл полностью снаружи, то мы благополучно о нем забываем и выкидываем из списка.
Если тайл полностью внутри вея, то мы добавляем в базе этому тайлу признак того что вей такой-то накрывает тайл полностью, после чего тоже удаляем из списка.
Если тайл попал на границу вея, то мы оставляем его в списке, а в базу ничего не добавляем. (Хотя возможно и нужно добавить инфу о том что в базе будут его потомки. Чтобы потом было удобнее по всему дереву пробегать.)
После проверки всех тайлов и добавления информации в базу мы делим все оставшиеся в списке тайлы на 4 новых, уровень которых выше соответственно на единицу. Список конечно чистим от старых тайлов прошлого уровня. После чего запускаем тест снова. И так продолжается до какого-то максимального уровня…
Когда дошли до этого уровня, то сохраняем в базу инфу для каждого тайла. О том что он содержит вей такой-то…

Проиллюстрирую работу алгоритма на простом примере:

Но есть пример интереснее:

Думаю наверняка где-то это уже реализовано, но пока свой велосипед удобнее)
Думаю если держать такую информацию о тайлах в каком-то, ориентированном на быстрое чтение, виде, то можно сделать быстрый поиск необходимых веев и нодов для рендера карты.
Статистику не собирал, но много тайлов максимального уровня будет там где есть мелкие веи, населенные пункты и т.д. для лесов, морей, рек такой информации должно быть мало…
Рендер может определить цвет каких тайлов ему нужен исходя из то куда направлена камера.
Затем посмотреть есть ли эти тайлы в базе, вычислить их цвет исходя из информации о их предках, если их нет… или найти потомков и составить “представление” для данного тайла.
Получив id всех необходимых объектов для отрисовки выкидываем дубликаты и подгружаем того что нет в кэше… рисуем. На мой взгляд вроде бы идея имеет право на жизнь)
Правда тут у меня возникают некоторые вопросы, которые я еще не продумал) Например как лучше добавить разную геометрию для разных уровней… или отрезать вообще часть “глобальных” уровней сделав пререндер и т.д. Как удобнее и оптимальнее бегать по дереву тайлов и быстро использовать имеющуюся инфу, но надеюсь я на правильном пути.

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

Интересно. Кстати, попробовал на pypy 1.7, экспорт из .osm.bz2 в .json.bz2 получился чуть-чуть быстрее.

Товарищи, посмотрите пожалуйста отношение №934119… там в участниках несколько outer-веев, причем они не замкнуты!
Корректно ли вообще такое отношение?
Я так понимаю в мультиполигоне должен быть только один outer и несколько inner’ов могут быть… причем и те и другие должны быть закрытыми веями.
Также все эти веи должны быть с непересекающимися контурами и несамопересекающимися.

Если есть несколько outer-веев, то такой мультиполигон может быть разбит на несколько отношений… и тут как бы отношение уже несет другой смысл, оно описывает теги для отдельных outer’ов… не знаю правильно ли так делать… отношение multipolygon должно указывать где дырки у конкретного вея

Вот тут всё написано.

Корректно. И outer и inner может быть несколько замкнутых полигонов, составленных из отдельных веев. Вот пересечения и самопересечения недопустимы.

Спасибо! Самое фиговое что можно из нескольких незамкнутых веев полигон собрать замкнутый…
Как-то эту хрень надо в один нормальный полик превращать…

Препроцессить, не?

для простых поликов научился кое-как создавать списки веев и отдельных нодов входящие в конкретный тайл…
теперь нужно учитывая отношения сделать также только с мультиполигонами и береговыми линиями вода/суша
Я рассчитывал что с мультиполигонами ситуация несколько проще чем оказалось)
т.е. они хотя бы должны были состоять из замкнутых веев) А их еще и собрать нужно… точка к точке, надеюсь в базе нету перепутанных местами незакрытых outer’ов, но почти уверен что есть) В таком случае придется еще и высчитывать можно ли корректно собрать один или несколько замкнутых полигонов из списка outer’ов незакрытых…

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

В итоге должна быть информация для любого тайла который хочется нарисовать:

  1. какие веи целиком “накрывают” тайл, т.е. заливают его монотонным цветом
  2. какие веи рисуются в нем целиком или наезжают на него частью т.е. видна граница этих веев на тайле
  3. отдельно стоящие точки, которые попадают в тайл
    для быстрого рендера потом можно получить список всего что обязательно нужно рисовать (2 и 3 пункты) и список того что нужно не рисовать, но учитывать при заливке (2 пункт).

Демку такой штуки я делал на небольших примерах… не так уж и много объектов получается, гугл и MapsWithMe же как-то рендерят на лету
Объем не очень большой т.к. информация хранится только для крупных тайлов в основном, для мелких она хранится в том случае если мы в густо зарисованных районах типа крупных городов…

Встречайте! Страшный и ужасный мультиполигон
Достаточно сложный… состоит из нескольких перемешанных местами незакрытых и закрытых внешних веев, а также внутренних)

Как-то удалось собрать его в кучу… связкой Boost Graph и Boost Geometry)
На других страшных мультиполигонах не тестил, но уже что-то!

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

  1. из всех незакрытых веев, которые записаны в релейшн нужно посмотреть первые и последние id нодов… они будут вершинами графа
  2. в граф добавить ребра соответствующие этим нодам. Далее найти циклы в графе. Соответственно должны получится полигоны из вершин графа.
  3. для каждого цикла проверить последовательности нодов в веях и “развернуть” некоторые веи т.к. направление их не учитывается.
  4. для каждого цикла сложить ноды всех веев (с учетом разворота) в отдельный вектор , в итоге получаем вектор векторов нодов, т.е. массив полигонов!
    Попутно можно ловить ошибки, сохранять их в бд.

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

Вроде очень неэффективно.
Берешь обычный std::map, например, или любой другой ассоциативный массив.
В нём у тебя будет храниться инфа о незамкнутых контурах.
Берешь очередной вей из отношения, смотришь, если есть какая-нибудь из конечных точек в мапе - пристегиваешь к сегменту, может быть склеиваешь два.
Если нет - добавляешь новым сегментом.
Как то так.

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

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

Реализовал без графов, достаточно просто, примеры которые есть работают…
попроще получилось и шустрее должно быть, буду гонять на planet.pbf или дампе России может и вылезет что нехорошее, но пока все ок!

UPD: вот на таком полигоне все поломалось)
UPD2: полигон поправил… там реально ошибка, на такой релейшн еррор нужно вешать!