Практическая реализация идеальной БД

Что же вы совсем языки пооткусывали, господа?

Идеальную СУБД рассматриваю отнюдь не как тему для трепа, а как прообраз... нет, не СУБД, конечно, но реального, работоспособного макета такой СУБД. И я хочу создать такой макет, насколько это в моих силах. К сожалению, никакой помощи со стороны всезнающего All я до сих пор так и не получил - в лучшем случае, были слабые намеки на возможность конструктивного разговора. Зашел я со стороны ядра - пофлудили, замолчали. Зашел со стороны клиента - пофлудили, замолчали. Зайдем с третьей стороны - со стороны ДАННЫХ.

Как я уже говорил, меня интересуют не реляционные погремушки, а СЛОЖНО организованные данные - реальные данные из жизни, а не кастрированной "нормальности". Примеров таких данных может быть множество - скажем, каталог DMOZ, или Википедия, но лучший набор для тестирования макета, на мой взгляд - так называемая OpenStreetMap, которая лежит на downloads.cloudmade.com. Мотивирую:

1. Данные открыты, доступ свободный, версия вроде как стабильная - Last maps update: 26 August 2011 - ее я и скачал на днях к себе, как прообраз будущей идеальной БД.
2. Данные формально слабоструктурированные, представлены в виде XML (хотя он там зовется OSM), однако по характеру своему структурированность их (потенциальная) чрезвычайно высока.
3. Объем данных достаточно серьезный (по моим оценкам, около миллиарда объектов), так что ни о какой ручной подгонке результатов под ответ не может быть и речи. Мало того, все умозрительные построения доморощенных теоретиков здесь рассыпаются в пыль, из-за многочисленных, и часто весьма неожиданных нюансов. Добро пожаловать в Реальность, господа!
4. На логическом уровне там представлена не база, а именно свалка данных, что доказывает фактическое использование так называемой EAV-модели, представленной с помощью тега с замечательным названием "tag", разборка которого даже на уровне метаданных повергает в ужас даже видавшего виды меня, любимого. :) Тем не менее, ее можно считать и базой, поскольку имеется мощнейшая привязка (пространственная), которая очень неплохо выполняет структурирующую роль.
5. Там имеется гигантское количество ошибок в данных - по моим оценкам, десятки миллионов. При этом выявить их не так-то просто: данные, хоть и текстовые, но мультиязычные - по моим оценкам, на 40-50 языках.
6. Там имеется гигантское количество дублей - по моим оценкам, намного больше, чем ошибок. Кроме того, там невероятное количество просто мусора - по моим оценкам, 70-90%, если не больше.
7. Несмотря на все вышеперечисленное, в этой базе сосредоточено огромное количество весьма интересной информации - именно потому, что используется "свалочная" EAV-модель, позволяющая эту информацию хотя бы сохранить. Причем о весьма значительной части этой информации наверняка не подозревают даже создатели БД.

Аргументацию можно продолжать, но вряд ли это нужно. Еще раз приглашаю к разговору а) программистов-системщиков (для обсуждения концепций ядра СУБД), б) программистов-прикладников (для обсуждения концепций ПО клиента, т.е. браузера), в) просто пользователей (для обсуждения концепций построения интерфейса), г) специалистов в области баз данных (для обсуждения концепций и базы метаданных)... и все, пожалуй. Разумеется, приглашаю не только в эту ветку, но и во все три моих - это взгляд на одно и то же, но с разных сторон.

Forums: 

Технология подготовки идеальной БД

Итак, исходный массив данных скачан с CloudMade - 6 файлов архивов bz2 общим весом 20 323 389 127 байт. Чтобы превратить его в базу данных, потребуется достаточно сложная и кропотливая обработка. Заодно определимся и с набором необходимых утилит. Первым делом разархивируем, и нарежем на куски размером не более 4Г (по ряду причин, я предпочитаю не работать с очень уж большими файлами). Разрежем так, чтобы границы файлов совпадали с границами объектов, которые там представлены. Разрезку выполняем с помощью Total Commander - там имеется такая утилита, и она вряд ли потребуется идеальной СУБД. В результате получится 76 файлов общим весом 290 674 587 932 байт. Теперь предположим, что мы каким-то образом импортировали эти данные в нашу идеальную БД, которая теперь содержит эти самые 76 элементов данных, представленных в виде BLOB. Кроме того (для отладки алгоритмов и утилит работы с базой) создадим еще одну, небольшую БД из тех же данных. Например, "остров Мэн" - всего-то 26 791 567 байт исходных данных.

В самом общем виде задача стоит такая: получить из этого гадюшника НОРМАЛЬНУЮ БД по планете Земля (пряник для пользователей - уметь рисовать картинки по данным этой базы), и выковырять из нее всю информацию, которая там вообще есть. Для этого нам нужно предварительно отрезать наиболее очевидный мусор, максимально облегчить исходный объем данных для последующей обработки. К счастью, исходные данные более-менее структурированы, поэтому алгоритм первичной обрезки может быть достаточно простым и быстрым.

Очевидный разделитель элементов данных в исходном массиве - символ перевода строки. Разделитель объектов - закрывающий тег (в синтаксисе XML). Объектов, представленных тегами первого уровня вложенности, всего 3 типа: node, way и relation. Все они содержат практически один и тот же набор аргументов, и даже в одной и той же последовательности: id, version, timestamp, uid, user, changeset. Очевидно, что кроме id, ни эти атрибуты, ни их значения никому на фиг не нужны. В самом деле, кого из пользователей интересует, какой ник был у того, кто забросил в базу какой-нить узел, какой ID был у тамошней сессии, сколько часов и минут в это время показывал тамошний будильник, и т.д.? Иными словами, мы имеем возможность "легким движением руки" уполовинить объем данных, сохранив, по сути, всю информацию.

Какие же утилиты нам для этого потребуются? Предлагаю читателям самостоятельно подумать на эту тему. Мне удалось обойтись двумя, вполне универсальными, разработанными задолго до этого случая. До обработки всей базы еще далеко (к тому же, я собираюсь внимательно посмотреть, и причесать коды всех утилит), сейчас идет разрезка "Европы" на блоки по 4Г, но для isle_of_man.osm объем упал с 26 791 567 до 13 420 028 байт - почти идеально вдвое.

Вопросы, замечания, предложения?

Текущее состояние с тестовой БД

Итак, на автономные куски весом до 4Г гигов исходный массив нарезан, теперь полученные 76 элементов данных новоиспеченной БД отправлены на первичную обработку. Пару утилит (о которых я говорил выше) я поправил. Или испортил, если угодно: ранее они у меня имели вид жутко универсальной, мощной, гибкой, единой утилиты обработки всего и вся. Сейчас я постарел, на такие подвиги меня уже не хватает, поэтому перевел эти две утилиты пока что в специализированный вид, исправил попутно одну застарелую ошибочку (она не особо раздражала, так что править было лень), но самое главной - ускорился раз в 50.

Полученные утилиты уже отмолотили Америку, Африку, Азию и Океанию (не говоря уже об Антарктике), сейчас обрабатывается Европа - последние 120Г. Как я и говорил, первичная обрезка сбрасывает около 50% объема (позднее скажу точно), при этом, как говорил классик "до жира мы еще не добрались - спустили только воду". Пора подумать и о втором этапе. Он, по предварительным прикидкам, должен сбросить объем еще примерно вдвое, но... халява заканчивается, дальнейшее падение объема будет даваться все труднее с каждым шагом. Впрочем, это и не самоцель. Отметим, что хотя исходный массив и разрезан на 76 элементов, на логическом уровне он все равно пока представляет собой один элемент - как, скажем, файл, который состоит из множества секторов на диске.

Второй этап построим так, чтобы данные из самоописываемого формата (XML) постепенно перетекали в более структурированные конструкции - те, которые для них наиболее удобны. Как я уже говорил, типов данных, представленных тегами 1-го уровня вложенности, всего 3 штуки, и данные нужно потихоньку сводить в эти 3 группы, попутно очищая наиболее очевидный мусор (вроде created_by или source), и переводя теги в разделители формируемых структур данных. Для этого нам потребуется... все та же пара утилит!

Вопросы, замечания, предложения?

Первоначальная обрезка завершена!

Заодно данные сгруппированы по типам (тегам 1-го уровня), благо это совсем просто. Таким образом, один исходный элемент данных (разрезанный на 76 блоков) после начальной обработки разделен на 3 элемента различных типов:
node: 25 блоков, 83 024 738 967 байт. Точки на карте мира. Иногда с описанием.
way: 19 блоков, 64 546 518 949 байт. Траектории. Описания имеются гораздо чаще, чем у узлов. Состоят из узлов, и ТОЛЬКО из них, причем порядок их следования в исходных файлах ВАЖЕН! Еще один привет реляционщикам! :)
relation: нет деления на блоки, 944 276 758 байт. Тоже траектория, но состоит не только (и не столько) из узлов, сколько из дочерних траекторий. Описание имеется ВСЕГДА! Порядок не следования дочерних траекторий не соблюдается, хотя очень часто совпадает с истинным.
Итого: 45 блоков, 148 515 534 674 байт, или 51.09% от первоначального объема.

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

Вопросы, замечания, предложения?

Второй этап обрезки завершен

Итоги:
node: 13 блоков, 48 056 348 209 байт (57.88% от предыдущего состояния).
way: 8 блоков, 29 708 760 474 байт (46.03% от предыдущего состояния).
relation: нет деления на блоки, 329 455 984 байт (34.89% от предыдущего состояния).
Итого: 22 блока, 78 094 564 667 байт, 52.58% от предыдущего состояния или 26.87% от первоначального объема.

Следуюший этап будет заключаться в отсеивании почти структурированных данных. Это, разумеется, "геометрия": координаты узлов (lat/lon), и последовательность их следования в траекториях. Это вовсе не означает, что для этих данных работа по структуризации заканчивается - наоборот, она только начинается! Но вначале нужно отделить мух от котлет, геометрию от описаний, и вот в описаниях начнется уже НАСТОЯЩИЙ кошмар!

Но я все-таки не понимаю: народ окончательно попрятался в норы? Вы же читаете, я же вижу! Пусть не особо активно, но все-таки. Неужели никому совершенно нечего сказать?!

Ну вот и все: халява закончилась.

Хорошо структурированные данные отделены от плохо структурированных. По сути, их формат уже близок к идеальному: для узлов это координаты (lat/lon), а для траекторий... модно называть эту штуку контейнерами: для каждой траектории (типа way) имеется список айдишек входящих в нее узлов, причем порядок следования ВАЖЕН. Это (в отличие от структур типа node) не может в таком виде храниться в РБД, но ведь у нас идеальная база данных! Иными словами, 41 711 357 841 байт данных в узлах, и 18 605 231 070 байт траекторий полностью "готовы к употреблению". Сюда же можно отнести и 205 741 914 байт данных траекторий типа relation - там дополнительно имеются некоторые метаданные: тип дочерней траектории, и еще какая-то хрень - не вникал. В общем, здесь все, что нужно для прорисовки карт, и даже больше.

Готовы-то они готовы, да не совсем (это мягко говоря). Перед нами стоит очень нетривиальная задача верификации этих данных, а также масштабирования - карта мира все-таки! Но этими делами мы займемся позже, когда появится настроение - надоело мне в этом дерьме копаться. Да и утилиты новые понадобятся.

Слабо структурированные данные занимают на настоящий момент 5 214 924 664 байта в узлах, 10 101 006 863 в траекториях типа way и 126 299 874 типа relation. Это, главным образом, какие-то описания имеющихся в БД объектов, представленные (пока что) в модели данных EAV. Здесь по-прежнему ОЧЕНЬ много мусора, чисткой которого мы сейчас и займемся.

Вопросы, замечания, предложения?

Работаем с EAV

Господи, как же мне раскрутить народ на разговор? Ничего их не берет! В "Политике" нашел за это время троих, интересующихся именно ЭТОЙ темой, а здесь, казалось бы, сам Бог велел... ладно, хватит плакаться.

Как я уже говорил, формат "геометрических" данных уже близок к идеалу, и мы их пока не трогаем. А вот "настоящая" БД (в тыщу раз более интересная, чем все остальное - подумаешь, "веселые картинки" не нарисуем!) спряталась под видом EAV. Точнее, это создатели так думают - на самом деле там гадюшник куда более ужасный!

Наша задача - отрезать наиболее раздражающий мусор, и структурировать то, что может хоть как-то структурироваться. Написал, кстати, еще одну маленькую, и достаточно специализированную утилитку, уплотняющую БД после обработки. Параллельно обрабатываем, разумеется, "остров Мэн", как тестовую БД. Обработку ведем, ориентируясь на типы данных, хотя общий принцип одинаковый: выдергиваем из общей кучи данные под самыми популярными тегами, и отправляем их либо на свалку, либо в какое-то подобие структур.

Меньше всего данных у типа relation: отрезаем префиксы tiger, naptan, TMC, NHD, выводим теги type, name, ref,
addr, building, boundary, natural... впрочем, и префиксы выводим, как группы - это хоть и мусор, но все же как-то группирует данные - авось, легче структуры будет выявить. Получаем 12 групп (это текущее состояние - количество групп может прыгать очень сильно, подробности в нашей с Ромкой работе "Оптимизация структуры БД") общим весом 125 447 917 байт (9 466 байт для isle_of_man).

Данные типа node: выводим теги addr, note (как тег, и как префикс), kms, osak, gnis, KSJ2, name, attribution... сразу выбрасываем source, filename, identifier, revision... или ничего пока не выбрасывать? Ладно, сложим пока в группу "мусор", а потом посмотрим.

Презабавная вещь: под тегами (префикс KSJ2) спрятались и кординаты тоже: как обе сразу (coordinate), так и по отдельности, причем количество lat и long различное! В большинстве случаев они дублируются для одного и того же узла, и я сильно подозреваю, что они совпадают также и с "официальными" координатами, давно уже собранные в структурированную группу. Впрочем, проверим на досуге.

Данные типа way - аналогично: tiger, upload, highway, building, name... короче, "процесс пошел". Результаты буду сообщать по мере получения.

Вопросы, замечания, предложения? Или хоть слово скажите - вы вообще живы, нет?

Изображение пользователя Serguei_Tarassov.

Согласно определению

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

Если такое определение существует

то оно неверно по определению. :) Автор определения явно путает понятие "данные" и "информация". Кроме того, база данных вполне может содержать слабоструктурированные, и даже вовсе не структурированные данные. Если определение этого не допускает - значит, опять-таки, неверное (на хорошо: устаревшее) определение. Наконец, я нигде не нашел выражения "структурировать информацию".

Идеальная БД

То, что "языки пооткусывали" - я не думаю, что много людей понимает те проблемы о которых Вы говорите. Опять же - для того, чтобы говорить, нужно знать правильное решение. Кто его знает? :)

С Вашими тезисами по "идеальной БД" в основном согласен.

В каком состоянии сейчас Ваша работа с OpenStreetMap?
Если она продолжается, то с какой целью и какие проблемы на данный момент?

Ого! Я уж давно и надеяться перестал... :)

А зачем "много людей"? Да и понимать проблемы можно на разном уровне. Я, например, тоже в этом ни хрена не понимаю, и не знаю "правильного решения". Но ведь искать же можно! :)

Что "в основном согласны" - это может быть приятно, но бесполезно. Куда важнее, с чем Вы НЕ согласны.

С OpenStreetMap? Да забросил я ее - кому охота работать при полном вакууме? Правда, где-то с месяц назад я туда заглянул - они там объем данных чуть не утроили, как-то структурировали дерево объектов, и... изменения закончились 13 декабря прошлого года. А я как раз решил написать пару-тройку статей по модели данных. Ну и закачал снова базу, как демонстрашку и тест для работы со сложно организованными данными. Цель та же: выкопать оттуда всю информацию, которая там вообще есть.

На данный момент проблем никаких. Первая итерация закончилась - отрезал основной мусор, перевел в данные информацию о траекториях (дабы обеспечить независимость элементов данных), чуток структурировал. В общем, с 1.1Т уменьшил объем где-то до 300-400Г (точнее не скажу - почти все в аривах, раскрывать лень). Сейчас перевожу в данные имена и расширения файлов, дерево каталогов и убираю дубли. По моим оценкам, объем должен еще где-то втрое упасть. Ну, а дальше - отделение "геометрии" от собственно данных, и работа с последними. Там уже совсем интересно - насколько я помню, одних только языков более полусотни. Но это еще довольно нескоро - других дел хватает.