2014-12-22

Об nxQL

Вышел PostgreSQL 9.4, где фичей №1 заявлен новый тип данных jsonb, по которыму можно строить индексы и делать эффективные запросы внутренностей JSON документа. Теперь вопрос: «Зачем нужна Монга, если JSON можно хранить в Постгресе?» — будут задавать не только шепотом на кухне. Попробую на этот вопрос неответить.

Появление jsonb перечеркивает мои предыдущие тыкания в JSON в PostgreSQL. Если json — это просто строка, которая требует парсинга для каждого обращения к её внутренностям, то jsonb — это некие бинарные данные (как я понимаю, родственные типу hstore), поддерживающие прямой доступ и индексацию. В общем, jsonb — это сильно быстрее, и это гораздо ближе к BSON в Монге. Цель одинаковая — бинарный формат вместо человекочитаемого текста для повышения эффективности доступа.
Follow SQL
Зачем вообще нужно хранить JSON в реляционной базе? Ведь реляционная модель вполне прекрасно может отображать иерархические данные, как в JSON документе. У меня только один ответ — schemaless. Да, та самая бессхемность, которой гордятся NoSQL, внезапно пригодилась в SQL.
На самом деле не так уж и внезапно. Блобы были почти всегда. XMLи закидывать в БД научились давным давно. Теперь же очередь дошла до модного молодежного JSON. Если мы храним его в нереляционной БД, то говорим о документо-ориентированных NoSQL. Если мы храним его в реляционной БД, то говорим о специальном типе данных, который можно вставить в колонку таблицы.
Сложность, жесткость, вредность схемы данных, пожалуй, сильно преувеличена. Всякие Хибернейты или Активрекорды прекрасно прячут эту самую схему от разработчика. Разработчик работает с объектами. Как они сохраняются в базу, уже проблема фреймворка. (Где вы, объектные БД?) Даже проблему миграции, за что не любят схемы, фреймворк может решить.
Другой пример — Кассандра. Не думайте, что NoSQL — это обязательно schemaless. С самого начала в Кассандре была схема, нужно было указать имена и типы данных в колонках. Но это ничуть не мешало вам вставить в строку еще полтора миллиарда колонок с другими именами и произвольными данными. Просто вам самим пришлось бы определяться с типами значений при извлечении. Но в Кассандре 2.0, с появлением CQL 3 все изменилось. Теперь вы обязаны объявлять таблицы заранее. И только после этого делать к ним запросы. В синтаксисе, пугающе похожем на SQL. А динамические данные можно выразить как списки, множества или мапы в качестве значения ячейки таблицы. Как в SQL. Жду, кто сделает еще полшага и позволит сохранять и JSON документы, которые, вообще-то, почти как мапы.
Так чем лучше Монга? Масштабируемостью. Совсем чуть-чуть поплясав с бубном, можно собрать большуший, да еще и географически распределенный кластер, в котором можно хранить все ваши любимые BigData. Ну конечно, еще нужно правильно организовать данные и выбрать ключ шардинга. Такой возможности искаропки у Постгреса нет.
Но какие-то возможности для масштабирования у Постгреса есть. Во-первых, штатная репликация весьма хороша. К тому же, в Постгресе 9.4 её еще улучшили и теперь возможно делать мультимастера. Так, чтобы несколько серверов выступали мастером для разных таблиц (например, по признаку географического местонахождения пользователя), а слейвы имели бы копию таблиц с мастеров. Уже неплохо.
А еще есть Postgres-XC, который умер и родил более свежий Postgres-XL. Это полноценный кластер, построенный поверх модифицированного PostgreSQL. Это не решение искаропки. Это надстройка. Но она делает то, что делает. Решает те же проблемы, что решают многочисленные NewSQL. Пытаются сохранить реляционную модель и SQL как язык запросов, но при этом хорошо отмасштабироваться. И натыкаются на те же самые решения вроде выпиливания единой точки отказа, координации распределенных транзакций, эффективного объединения данных, раскиданных под разным узлам кластера. Последнее, как всегда, нормально работает только если мы правильно выберем ключ шардинга, и в запросе будем его указывать.
Deploy button
А еще Postgres-XL выглядит чертовски сложным в развертывании и настройке. Уж больно много в него входит разных компонент, которые должны работать вместе. Танцев с бубнами предвидится сильно больше, чем в случае Монги. Это напоминает HBase, который сам по себе является надстройкой над Hadoop. А Hadoop, в свою очередь, тоже не так прост. Поэтому теперь уже никто в здравом уме не скачивает HBase с серверов Апача, а берут сборку от Cloudera.
Базы данных становятся настолько сложны, что уже состоят не из одного, а из нескольких продуктов. К нашему счастью, в основном открытых. И координировать эти продукты становится все сложнее. Всякие облака да Докеры тут как нельзя кстати. Вангую, что вскоре все эти наши БД будут поставляться только в виде готовых настроенных образов, а не отдельных пакетов для ОС. Управление конфигурацией становится затратнее собственно разработки.
HTSQL
А вот вам еще одна тенденция. В старой Кассандре обращение к БД происходило через строгое API посредством Thrift. На каждую операцию, будь то получение всей строки по ключу или получение набора колонок по ключу и т.п., рисовался свой RPC вызов, на сервере и на клиенте. А в новой Кассандре есть CQL. Язык запросов. По внешнему виду и по назначению аналогичный SQL. И остается только один вызов в API — выполнение этого CQL. И если будет добавлена какая-то новая фича, будет расширен язык запросов, но не API или протокол, или клиентский код.
Еще более занятен пример графовых БД. Появились они вроде совсем недавно, но успели обзавестись и общим API: Blueprints, и своим специальным языком запросов: Gremlin. Полагаю, что для сохранения конкурентного преимущества, Монге нужно срочно изобрести стандартный язык запросов для документо-ориентированных данных :)
Забавно, что переводить SQL в запросы к Монге уже научились. С другой стороны, тот же LINQ давно имеет API для конструирования правильных SQL запросов. Становится почти без разницы, работать через API или через язык запросов.
451 Research — Data Platforms Landscape Map
Итак. Сочетание заранее определенной схемы и динамических данных — да. Горизонтальное масштабирование и кластеризация — да. Возникновение стандартных языков запросов в дополнение к API — да. Поставка готовых образов для развертывания в облаках — да. Это то, что происходило, происходит и будет происходить в ближайшем будущем среди систем хранения структурированных данных, будь то NoSQL, SQL или NewSQL. И я нарекаю это nxQL.

2014-12-09

О HappyDev

Новый, две тысячи четырнадцатый, HappyDev завершился. Успешно.

Участником я был на десятках конференций. Докладчиком я был несколько раз, на конференциях такого масштаба. А теперь я еще и организатором оказался. Совсем чуть-чуть. Ну попереписывался с докладчиками, ну порулил расписанием, ну подвез Макса Дорофеева из аэропорта на б.о. им. Стрельникова.
Кстати, Максиму очень понравилась хэппидевовая шапка-ушанка, снег (в Москве в последние два года со снегом напряженка, а ту неделю, что он там все же был, Максим случайно провел в Тайланде) и омское метро.
Я замечал, что когда приезжаешь на конференцию докладчиком, то другие доклады проходят мимо мозга. Буквально. Сидишь, слушаешь. А что услышал, не запоминаешь. Совсем. Потому что до своего доклада ты волнуешься, как его, свой родной, хорошо прочитать. А после своего доклада радуешься, что все уже позади. На остальные доклады наплевать.
Когда ты еще и организатор, ситуация усугубляется. Ибо тебя больше волнует, чтобы микрофоны работали, чтобы презентации (их правильная версия) были на экране, как правильно произносится фамилия докладчика, о чем там будет следующий доклад, чтобы его правильно объявить, сколько там еще времени на вопросы, как бы отобрать микрофон у того чувака в зале, который задает уже третий вопрос подряд и куча других мелких вещей. А доклады? Ну что доклады. Докладчики что-то говорят. Слушатели проявляют интерес. Аплодисменты в конце есть. Все ок.
Так что давайте все поблагодарим тех людей, которые бегали, рвали, метали и организовывали: Аню, Гришу, Сашу (он так усердно три часа жарил шашлыки на морозе, что в результате заболел), Алёну, Ксюшу, Женю (и еще одного Женю, без которого интернета не было бы вообще). А также многих сотрудников компаний 7bits и Avelix. А также тринадцать штук добровольцев-падаванов, которые взяли на себя самую тяжелую физическую работу (сильные программисты вырастут).
Спасибо группе «Моя дорогая» за душевные песни, которые отвлекли от неизбежной пьянки запланированного употребления алкоголя. Омичи, помните, что рядом с вами, в одном городе, рождается настоящее, уникальное и неповторимое Искусство, Музыка и Поэзия.
Конкурсы обошли меня стороной. Как-то некогда было искать пару для кофе, а на второй день кофе вообще не приехал (еще бы, -30 по цельсию). Кстати, в процессе подготовки этих кофейных промокодов произошло небольшое столкновение между альтруизмом, который призывал всем выдать одинаковый код, и жадностью, которая призывала всем выдать уникальный код. Победил реализм. А квест я заметил только в тот момент, когда кто-то попытался сфотографировать толпу народа перед столовой в прыжке. Беда была в том, что сфотографировать людей в прыжке на телефон оказалось почти невозможно. Можно либо зависнуть в воздухе, либо в гневе растоптать телефон за тормозную камеру.
ИП Дорофеев
Какие-то доклады я все же послушал.
Александр Чернышев четко и конкретно рассказал про Swift. К сожалению, я никогда не разрабатывать под iOS, поэтому могу только сказать, что код на Objective-C со слайдов я прочесть не могу, взгляд спотыкается о квадратные скобки, а вот код на Swift вполне читаем. И еще у меня вызывает сомнение тезис о том, что Swift является функциональным языком.
Катя Боброва объяснила про разные виды тестирования, как они друг с другом сочетаются, зачем их надо делать. Удивительно, но у меня в голове это пересеклось с системно-инженерным подходом в изложении Анатолия Левенчука позднее. Разделяй и властвуй. Раздели систему на маленькие кусочки вдоль и/или поперек, и тестируй их.
Максим Дорофеев в очередной раз показал, что его нужно, можно и весело слушать независимо от того, о чем он говорит. Доклад был хороший, мастер-класс был потрясающий. Вот ссылки на все ексельки с кривульками: http://bit.ly/ttrs-pln, http://bit.ly/prj-est-tmpl, http://bit.ly/ebdc-tmpl, http://bit.ly/Reliable-Scrum. Вангую появление всяких вероятностных графиков во всяких жирах, редмайнах и ютреках. Ребята из JetBrains, у вас есть реальный шанс вырваться вперед, если первыми запилите.
Женя Тюменцев снова отжег про математические доказательства SOLID принципов. Не вдаваясь в подробности: разработчики, помните, когда вам говорят поменьше пользоваться switch, это не потому, что старшие товарищи такие злые, а потому, что это все имеет математическое обоснование. Почему это не работает на модели акторов?
Антон Плешивцев поделился интересным опытом разбора пользовательских запросов (на пользовательском языке) с помощью Clojure.
Анатолий Левенчук попытался сдвинуть нам мышление. К сожалению, доклад был дистанционный, поэтому, может, проняло не всех. А я совершил глупость, прочитав книжку до доклада. Поэтому ничего особо нового не услышал. Ну как книжку, скорее конспект лекций. Безусловно приятно понимать, как системный подход работает в инженерии. Безусловно радостно знать, что этому теперь учат, пусть и не здесь. Не знаю, как у вас, а я от прочтения книжки получил радость узнавания. Ну и нахватался некоторых умных слов :)
На второй день я сам провел мастер-класс по NoSQL (презенташечка есть, видео не будет). И сходил на Дорофеева, где мы вынимали бусинки из носков и рисовали кривульки.


Бассейн и глинтвейн были теплыми, воздух и снег были холодными. Все было хорошо. Через год надо повторить.

2014-11-23

Об OSM

OSM — это OpenStreetMap. Это уникальный в своем роде проект, где, подобно Википедии, подробнейшая карта мира создается энтузиастами. Аж с 2004 года. Когда еще никаких народных карт да мапмейкеров даже не существовало. Ну и, в отличие от упомянутых конкурентов, данные OSM открыты под свободной лицензией, что приводит к тому, что встретить эти данные можно где угодно, где нужна карта.
OSM logo
А сами эти данные изложены в весьма интересной и не очень реляционной модели.
Есть узлы (nodes), с айдишником и парой географических координат (широтой и долготой в WGS 84). Узлы — это, собственно, единственные объекты, имеющие эти самые координаты.
Есть пути (ways), которые объединяют от двух до двух тысяч узлов в некоторую ломаную линию. Путь может представлять какую-нибудь дорогу, например. Путь может быть замкнутым, если первая и последняя точка у него совпадает. Замкнутый путь может представлять, например, здание, или ограничивать определенную площадь.
Есть отношения (relations), которые объединяют узлы, пути и другие отношения в более сложные структуры. Узлы, пути и отношения, входящие в данное отношение являются его членами (members), и как правило обозначены конкретными ролями (roles) в рамках данного отношения. Отношениями может быть выражено все что угодно.
Есть теги (tags), которые придают смысл всем другим объектам. Это наборы пар ключ-значение, навешанные на все эти узлы, пути и отношения. Какие ключи, и что означают их значение, собственно, и является основой OSM, и решается путем длительных споров и переговоров. Но это уже никак не затрагивает саму модель данных. Такой вот конвенционализм.
OSM data model
Есть еще юзеры, ченджсеты, версии и даты изменения. Но это уже контроль версионности основной модели. Это ж по сути вики. Нужно знать, кто, когда и что поменял, чтобы, если что, дать по шапке и откатить обратно.
Чаще всего эту модель представляют в виде XML файла с расширением OSM.
<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="CGImap 0.0.2">
    <bounds minlat="54.0889580" minlon="12.2487570" maxlat="54.0913900" maxlon="12.2524800"/>
        <node id="298884269" lat="54.0901746" lon="12.2482632" user="SvenHRO" uid="46882" visible="true" version="1" changeset="676636" timestamp="2008-09-21T21:37:45Z"/>
        <node id="261728686" lat="54.0906309" lon="12.2441924" user="PikoWinter" uid="36744" visible="true" version="1" changeset="323878" timestamp="2008-05-03T13:39:23Z"/>
        <node id="1831881213" version="1" changeset="12370172" lat="54.0900666" lon="12.2539381" user="lafkor" uid="75625" visible="true" timestamp="2012-07-20T09:43:19Z">
            <tag k="name" v="Neu Broderstorf"/>
            <tag k="traffic_sign" v="city_limit"/>
        </node>
        ...
        <way id="26659127" user="Masch" uid="55988" visible="true" version="5" changeset="4142606" timestamp="2010-03-16T11:47:08Z">
            <nd ref="292403538"/>
            <nd ref="298884289"/>
            ...
            <tag k="highway" v="unclassified"/>
            <tag k="name" v="Pastower Straße"/>
        </way>
        ...
        <relation id="56688" user="kmvar" uid="56190" visible="true" version="28" changeset="6947637" timestamp="2011-01-12T14:23:49Z">
            <member type="node" ref="294942404" role=""/>
            <member type="way" ref="4579143" role=""/>
            ...
            <tag k="name" v="Küstenbus Linie 123"/>
            <tag k="route" v="bus"/>
            <tag k="type" v="route"/>
            ...
        </relation>
        ...
</osm>
XML этот содержит перечисление узлов, путей и отношений с их тегами. Чаще всего этот XML содержит объекты, ограниченные некоторым обрамляющим прямоугольником интересующей нас местности. Но есть и файл с данными по всей планете Земля, так и называется, planet.osm. В несжатом виде он весит сотни гигабайт, что, очевидно, обработать почти невозможно.
Поэтому сейчас переходят на гораздо более компактный формат PBF. Это те же узлы, пути и отношения, но упакованные в бинарном виде с помощью Google Protobuf.
Конвенционализм выражается и в том, что не по всем моментам применения тегов достигнуто окончательное соглашение. И большая часть вики посвящена описанию правил использования тегов.
Помнится, на заре OSM долго спорили, на каком языке должно даваться имя по-умолчанию: на местном наречии или на международном (сиречь, английском). В результате родилась целая куча тегов для имен. И это не считая локализации, которая делается тегами с суффиксами :en:ru и т.п.


Посмотреть теги можно либо на самой карте, либо (что более интересно) перейдя в режим редактирования. Для редактирования вам понадобится какой-нибудь, например, гугловый, аккаунт, и тыкнуть кнопку Edit в браузере (главное, не жмите Save :). Раньше редактирование в основном производилось через десктопные редакторы (вроде JOSM или Merkaator). Теперь же онлайн редакторы (по дефолту запускается Potlatch) предоставляют несколько удобный интерфейс, для работы с типичным набором тегов и отношениями, чтобы создавать уже правильные объекты, соответствующие принятым соглашениям.
Гибкость модели с отношениями и тегами приводит иногда к тому, что некоторые обычные вещи выражаются в OSM как-то не очень. Например, в OSM отсутствует адресный каталог. По идее, дома должны быть связаны с улицами, улицы входить в районы города, города объединяться в области, области входить в страну и т.п. Но в OSM здание связано с улицей лишь косвенно: значение тега addr:street может совпадать с тегом name улицы где-то поблизости. А может и не совпадать. А может, такой улицы (в виде отдельного пути) и нет нигде. А то, что улица находится в таком-то городе можно узнать только по географическим координатам (путь улицы проходит где-то внутри контуров города) и больше никак. Даже совпадения тегов нет. Впрочем, для выражения связи улиц и домов уже придумали несколько "стандартов" отношений. Что, пожалуй, только добавляет путаницы.


С другой стороны, в OSM есть потрясающие своей детальностью данные об административном делении континентов, стран и т.д. и т.п. У тега admin_level, который применяется к многоугольникам, представляющим административные границы есть аж десять значений, которые определены для всех стран и обозначают границы государства, округов, субъектов федерации, районов, городов и т.п.
А вот построить маршрут по дорогам в OSM, как они есть, не получится. Ибо пути в OSM не обязаны объединяться в связный направленный граф. Направление движения и тип дороги — это теги. А перекресток — это отношение со своими тегами. Две дороги на перекрестке не обязаны иметь общий узел в месте перекрестка. А разрешенные направления поворотов задаются еще дополнительными ограничивающими отношениями. Эти навески отношений да гроздья тегов сильно сложнее просто графа. Поэтому все средства для прокладки маршрутов по OSM преобразуют исходную модель в граф, а потом осуществляют поиск уже по графу.


У OSM есть свой рендер, и даже не один. Вы наверняка видели результат его работы где-нибудь в вебе, где рисуется карта. Ибо, опять-таки, OSM — самый свободный вариант.
Все эти OSM данные доступны через API, с большой буквы A, ибо это главное API. Правда, в последнее время API сильно ограничивает как объем данных, выдаваемых по одному запросу, так и количество запросов в секунду. Теперь API позиционируется как место для внесения изменений в OSM. И это единственное место. Все редакторы коммитят сюда. Так достигается целостность данных и истории изменений. А вот для больших или сложных запросов существуют зеркала и даже другие API: например, XAPI или Overpass API.
За главным API скрывается обычный реляционный PostgreSQL, вроде даже без PostGIS. Ну разве что для тегов используется колонка со специальным типом key-value хранилища hstore. Можно запросто заполучить копию подобной базы (без полной истории изменений, только последний слепок). Нужно взять PostgreSQL и Osmosis. Создать схему данных по скриптам из Osmosis. Раздобыть osm (или лучше pbf) нужного вам города или страны (всю планету даже не пытайтесь, только если вам это действительно нужно и есть большой и быстрый сервер). Залить файлик в PostgreSQL с помощью Osmosis. Теперь можно делать запросы к базе и даже сделать своё API :) Только тут всплывают пространственные данные, рассмотренные в прошлый раз. Osmosis позволяет в таблицы с узлами или путями добавить колонки с точками или полигонами. Эту локальную базу можно держать актуальной, если брать файлы обновлений (OSC) и накатывать их.

2014-11-15

О Spatial Data

Любая приличная СУБД нынче поддерживает то, что называется Spatial Data. А юные СУБД торопятся обзавестись этой поддержкой. А как только обзаводятся, громогласно об этом заявляют. Потому что это — конкурентное преимущество.
Map of Equestria
Что же это за пространственные данные? Лучше обратиться к Википедии. К описанию стандартов со смешными именами: WKT (Well-Known Text) и WKB (Well-Known Binary).

WKT — это стандартное текстовое описание пространственных данных. WKB — это полностью аналогичное описание, но в бинарном виде. Взаимоотношение между ними примерно такое же, как между текстовым JSON и бинарным монговым BSON. Есть еще GeoJSON, тоже текстовый, но в JSON синтаксисе.
Собственно, «классические» CУБД хранят пространственные данные в виде BLOBов, являющихся некоторым расширением WKB. В отдельных колонках специального типа. А новомодные документоориентированные NoSQL БД, которые хранят документы в JSON или BSON, предпочитают GeoJSON представление.
Как видите, описать можно координаты точек, прямых, ломаных, многоугольников (интересным случаем является многоугольник с дыркой, «бублик»). А также множество точек, прямых, ломаных, многоугольников (единым объектом).
Координат у каждой точки может быть, в общем-то, сколько угодно. Но на практике используют две или три. Две — для координат на плоскости, например, для чертежей. Три — для координат в трехмерном пространстве. (Применения пространственных данных для операций в четырехмерном пространстве-времени не встречал).
Перечисленные выше стандарты не оговаривают, в каких единицах выражаются пространственные координаты. Им пофигу. Для чертежей, для станков, для планов зданий это могут быть обычные миллиметры, сантиметры, метры в обычном евклидовом пространстве. Но часто пространственные (spatial) данные используются для указания координат на планете Земля. Получаются геопространственные (geospatial) данные.
Тут с координатами все сложнее. Тут все завязано на проекцию. Тут есть свои стандарты. В пределах одного города можно привязаться к какому-нибудь меридиану и какой-нибудь параллели как к началу отсчета, и считать Землю плоской. И измерять все в тех же метрах. Но в рамках всего земного шара принято все же пользоваться широтой (в градусах к северу или югу от экватора) и долготой (в градусах к востоку или западу от Гринвича). Ну а третьей координатой может быть высота над уровнем моря, например, в метрах.
С широтой и долготой тоже есть разночтения, вызванные тем, что Земля не является идеальным шаром. Не является она и эллипсоидом. Но на практике её все же считают эллипсоидом с определенными большим и малым радиусами. И все эти наши гугло/яндексо/бинго/OSM/прочиекарты пользуются широтой и долготой по стандарту WGS 84.

В приличных СУБД, следующих стандартам OGC, все поддерживаемые системы координат аккуратно перечислены в соответствущих системных таблицах. Там, собственно, содержатся все необходимые коэффициенты для правильных операций над пространственными данными. И этих систем координат, тысячи их.
Какие операции можно делать с пространственными данными? Ну, банально, находить расстояния. Между точками, между точкой и прямой, между точкой и многоугольником. Хорошо, если у нас евклидова система координат. Применяем теорему Пифагора и вот оно — расстояние. Но вот на земном шаре не все так просто. Ибо градус долготы на разных широтах имеет совсем разное значение в метрах. А прямые — не всегда такие прямые (посмотрите на маршруты авиарейсов, а ведь это прямые). Так что за правильную реализацию подсчета расстояний (в метрах) между точками на земном шаре, заданными широтой и долготой (в градусах), уже стоит сказать разработчикам СУБД спасибо.
Еще можно находить вхождение точки (и других примитивов) в многоугольник (чтобы, например, ответить на вопрос: какие киоски находятся в этом парке), пересечение линий и многоугольников (проходит ли эта дорога через этот район) и тому подобные вещи. Список функций можно посмотреть в стандарте или реализациях.
Ну и конечно же можно индексировать пространственные данные. Тут все несколько интересно. Что индексировать-то? Допустим, нам нужно определить объекты, ближайшие к заданной точке. Т.е. выбрать те объекты, расстояние от которых до заданной точки минимально. Конечно, можно построить функциональный индекс по расстоянию и воспользоваться им для быстрого поиска. Но ведь точка, для которой мы проиндексируем расстояние, в других запросах будет другая.
R-Tree
Индексируют обрамляющие прямоугольники (или параллелепипеды для трех координат). Т.е. минимальные и максимальные значение координат объекта, прямоугольники, чьи ребра параллельны осям координат. Или же факт вхождения нескольких объектов в общий обрамляющий прямоугольник. Такие индексы не дают точного ответа о расстояниях или взаимоотношениях объектов. Но дают ответ о взаимоотношениях обрамляющих прямоугольников объектов. В результате, например, для нахождения ближайших объектов к точке, нам нужно сначала выбрать объекты, находящиеся в некоторой (прямоугольной) окрестности этой точки. А уже затем разобраться с точными значениями расстояний, подсчитав их уже для малого множества выбранных объектов.
select b.name, Distance(MakePoint(73.391631, 54.976775, 4326), b.geom)
from building b
where b.rowid in
    (select pkid from idx_building_geom where
         xmin > 73.390 and xmax < 73.393 and ymin > 54.975 and ymax < 54.978)
order by 2
limit 5;
Ну и в каких же СУБД все это хозяйство реализовано?
  • PostGIS — расширение для PostgreSQL. Самая крутая реализация, все остальные — в догоняющих.
  • SpatiaLite — расширение для SQLite. Дада, для той самой маленькой встраиваемой SQL базы есть вполне полноценное расширение для работы с (гео)пространственными данными, почти не уступающее по возможностям PostGIS.
  • В MySQL тоже есть стандартное расширение.
  • Для Oracle тоже есть Oracle Spatial and Graph. За ваши деньги.
  • В MongoDB есть нужные индексы и (относительно) небольшой набор операций.
  • У Couchbase, который недавно стал документо-ориентированным, тоже есть какие-то георасширения.
  • Тысячи их...
Хранить пространственный объект целиком в колонке таблицы или поле документа — не единственный способ представления. Возьмем, например, границу между двумя государствами. Контур каждой страны — это некий многоугольник, который хранится в каком-то одном значении в БД. И эти многоугольники соприкасаются неким множеством ребер, которые и образуют границу. Но вот беда, каждый многоугольник содержит свою копию описания ребер границы. Во-первых, тут есть дублирование данных. Во-вторых, если кто-то неудачно отредактирует многоугольник одного государства, но забудет отредактировать многоугольник другой страны, то случится межгосударственный конфликт. Потому что где-то контуры стран перестанут соприкасаться, и возникнет ничейная территория. А где-то контуры одного государства зайдут на территорию другого государства.
Можно же один раз указать точки и прямые границы между государствами. А затем сказать, что получившаяся линия входит в контуры обоих государств, и с одной стороны этой линии — одно государство, а с другой — другое. Дублирования, дырок и наложений в этом случае не возникает. Такой способ описания (гео)пространственных данных называется топологией. И реализован он в PostGIS и, если верить Википедии, в Oracle. Забавно, что от SQL там почти ничего не остается. Вся работа делается через функции.

В общем-то, топологический подход используется и в OpenStreetMap. Но структура данных OSM заслуживает отдельной истории. Как-нибудь в следующий раз.
Имея точки, линии да многоугольники в БД, мы можем рисовать карту (в векторе), делать прямой (почтового адреса в географические координаты) и обратный (географических координат в почтовый адрес) геокодинг. Но для полноценной ГИС этого мало. Часто имеет смысл иметь растровую версию карт (тайлы), чтобы эффективнее отображать карту в том же вебе. Гисовые расширения БД, соответственно, также поддерживают хранение и выдачу тайлов для нужного участка земной поверхности.
GeoHashing
Для построения маршрутов недостаточно иметь линии, отображающие дороги. Нужно иметь связный граф. А дальше уже ходить по нему, да пользоваться алгоритмом Дейкстры. Собственно, поддержка построения маршрутов в (гео)пространственных расширениях к СУБД сводится к построению графа (отдельно от базовых пространственных данных) и манипуляций с ним.
Напоследок еще чуть-чуть:

2014-11-09

Об островах

Или о сортах кофе.
Java logo
Началось все в апреле. На JavaDay в Омск приехал Филипп Торчинский и рассказывал про Kotlin. Показывал, как можно применять Kotlin для веб разработки. В сентябре я снова встретился с Филиппом и он снова рассказывал про Kotlin. Но рядом упомянул волшебное слово Android. И решил я посмотреть, что за Kotlin такой. Начал читать и возникло стойкое дежавю. И тут наткнулся на новость о выходе Ceylon версии 1.1. Вот откуда дежавю.
И Котлин, и Цейлон являются языками для JVM со строгой статической типизацией. Они оба нацелены на исправление некоторых родовых недостатков Явы, которые многие программисты хотели бы видеть исправленными. За счет потери обратной совместимости с Явой. Но они оба считают себя проще, понятнее и легче для изучения, чем Scala. Хотя Скала тоже исправляет недостатки Явы, но делает это излишне академично.
Ява — это остров в Индонезии, где выращивают кофе, видимо, полюбившийся в свое время программистам Sun Microsystems. Цейлон, он же Шри-Ланка, — это остров чуть южнее Индостана, где выращивают чай. Котлин — это остров в Финском заливе, рядышком с Санкт-Петербургом, где находится город Кронштадт и где в настоящий момент ремонтируется Аврора. Видимо, петербуржцы из JetBrains решили взять название ближайшего острова.
Kotlin logo
Из Явы специально выпилили все операции с прямыми указателями на память ради безопасности, чтобы избежать сегфолтов и прочих проблем. Однако в Яве осталось значение null как почти прямой аналог нулевого указателя. И при обращении к null возникает NullPointerException. Это, конечно, не полный крах приложения, нульпоинтер можно отловить и что-то с этим сделать. Тем не менее, этот эксепшен — самая частая проблема кода на Яве.
И Котлин, и Цейлон борются с нульпоинтерами, добавив проверку на null в систему типов. Если у вас есть переменная типа String, она не может принимать значение null. Это гарантируется компилятором, и подобная попытка вызовет ошибку компиляции. Если же переменной нужно присвоить null, придется объявить её как String? (с вопросиком). Это совсем другой тип переменной, и преобразовать String? в String можно только после явной проверки на null.
var a : String = "abc"
a = null // compilation error

var b : String? = "abc"
b = null // ok

val l = b?.length() ?: -1
variable String a = "abc";
a = null; // compilation error

variable String? b = "abc";
b = null; // ok

value l2 = b?.size else -1;
Подобные проверки возможны и в Яве, с помощью нестандартных аннотаций вроде @Nullable@NotNull и т.п. Однако в этом случае проверки выполняются IDE или статическими анализаторами, а не компилятором.
В Цейлоне тип String? на самом деле является сокращением для юнион типа String|Null. Юнион типы (например String|Integer) являются важным свойством Цейлона и лежат в основе многих фич языка. А Null — это специальный тип, у которого есть единственное валидное значение null. Соответственно, переменная типа String|Null может содержать либо строку (ни в коем случае не null), либо само значение null.
Котлин и Цейлон, вслед за Скалой, уделяют много внимания иммутабельности. Все переменные и поля классов объявляются как изменяемые или неизменные. В последнем случае им можно присвоить значение лишь раз, аналогично final в Яве. Все коллекции по умолчанию неизменяемые. А изменяемые коллекции — это совсем другие классы.
val s1 = "abc"
s1 = "def" //compilation error

var s2 = "abc"
s2 = "def"

val l = listOf(1, 2, 3)
val m = arrayListOf<Int>()
m.addAll(l)
value s1 = "abc";
s1 = "def"; //compilation error

variable value s2 = "abc";
s2 = "def";

value l = [1, 2, 3];
value m = ArrayList();
m.addAll(l);
Котлин и Цейлон, вслед за C#, добавляют проперти и атрибуты в классы, избавляя от головной боли геттеров и сеттеров. Отныне у классов вообще нет каких-либо полей, непосредственно содержащих ссылку на значение. Отныне любой доступ, который выглядит как обращение к полю, осуществляется через геттер или сеттер. А для неизменяемых "полей" и сеттера нет.
class Address(var street : String,
              var building : String) {
    public var asString : String
    get() {
        return "$street, $building"
    }
    set(value) {
        //parse value
    }
}
class Address(street, building) {
    shared variable String street;
    shared variable String building;
    shared String asString =>
        "``street``, ``building``";
    assign asString {
        //parse value
    }
}
В генериках и Котлин, и Цейлон, вслед на Скалой, радуют штукой под названием declaration-site variance. Variance — это отношение наследования генерик-типов к направлению наследования их аргументов-типов. Например,List<Number> и List<Integer> не являются наследниками друг друга, это называется инвариантностью. Но Integer является подклассом Number, а значит, вполне безопасно извлекать элементы из List<Integer> и помещать их в List<Number>. И тогда List<Number> будет суперклассом List<Integer>. В Яве можно записать List<? extends Number>, т.е. список подклассов Number. Это называется ковариантностью, и справедливо только если мы извлекаем элементы из списка. В то же время вполне нормально помещать Integer в List<Number>. Тогда уже List<Number> будет подклассом List<Integer>. Это называется контрвариантностью. и справедливо только если мы помещаем элементы в список.
Если вы ничего не поняли в предыдущем абзаце — это нормально. Я всегда так себя чувствую, когда погружаюсь в дебри генериков. Я даже думаю, что динамическая типизация придумана не зря, ибо избавляет от подобной боли. Ну а declaration-site variance в Котлине и Цейлоне лишь позволяет вместо ломания головы по поводу variance просто сказать, возвращает ли наш генерик объекты этого типа или же принимает их. Вы просто указываетеin или out, а компилятор уже сам разберется какие типы куда можно безопасно приводить.
class Box<out T>(val item : T) {
    public fun get() : T {
        return item;
    }
}

val intBox = Box<Int>(123);
val numBox : Box<Number> = intBox;
val num : Number = numBox.get();
class Box<out Item>(Item item) {
    shared Item get() {
        return item;
    }
}

Box<Integer> intBox = Box(123);
Box<Number<Integer>> numBox = intBox;
Number<Integer> num = numBox.get();
В Котлине и Цейлоне есть множество других приятностей. Во многих случаях можно не указывать типы значений, компилятор сам догадается. В интерфейсах (трейтах) можно описывать реализации методов, что позволяет вместо делегирования, как в Яве, устроить просто множественное наследование от нужных интерфейсов. Можно перегружать операторы. В Котлине это сделано по-питоновски просто: оператору соответствует определенный метод объекта. В Цейлоне для каждого оператора нагородили интерфейсов, которые нужно реализовать, чтобы оператор заработал с вашими объектами. Есть первоклассные и высокопорядочные функции, лямбдочки, замыкания и прочие функциональные прелести. Есть возможность писать в DSL стиле.
fun <T, R> List<T>.map(transform : (T) -> R) : List<R> {
    val result = arrayListOf<R>()
    for (item in this)
        result.add(transform(item))
    return result
}

listOf(1, 2, 3).map { it -> it * 2 }
List<Result> map<Item, Result>
        (List<Item> list)(Result(Item) transform) {
    List<Result> result = ArrayList();
    for (item in list) {
        result.add(transform(item));
    }
    return result;
}

map<Integer, Integer>(Array{1, 2, 3})
    ((item) => item * 2);
Ну и оба они "компилируются" в Ява-скрипт. Хотя и там и там рантайм под Ява-скриптом сильно отличается (по использованию) от рантайма под JVM. Полной прозрачности не наблюдается.
Компилятор Котлина, как и Скалы, производит байткод, т.е. .class файлы. Дальше с этими файлами можно делать что угодно. Лишь нужна небольшая стандартная рантайм библиотечка, чтобы этот байткод корректно заработал. В результате и Котлин, и Скала легко интегрируются в существующую инфраструктуру Явы. И, например, на них без особых проблем можно писать под Андроид.
А вот компилятор Цейлона согласен работать только с модулями, которые состоят из пакетов, которые содержат классы, функции и прочие элементы языка. В результате получается .car файл — архив модуля, внутри которого прячется все тот же JVMовый байткод. Каждый модуль имеет имя, версию и зависимости. Ребята переизобрели Maven и фактически реализовали Jigsaw. Оно хорошо для редхатового же JBoss, но вряд ли удобно где-то еще.
Ceylon logo
Как вы успели заметить, Котлин указывает типы после имени переменной, через двоеточие, как в Паскале и Скале. А вот Цейлон остался верным сишному (и Явовому) стилю. Вот только, похоже, для автоматического угадывания типов, точнее для опускания типов в коде, паскалевская нотация удобнее. В Цейлоне, например, приходится добавлять глупое ключевое слово value. Еще Цейлон грешен многочисленными длинными аннотациями, а также чудовищно навороченными иерархиями стандартных интерфейсов.
Это я к чему. Если мы говорим, что наш язык такой же выразительный, как, скажем, Питон, но проще и понятнее, чем Скала, то давайте действительно делать его выразительным, простым и понятным.
Scala logo
Будущее Цейлона не ясно. Вероятно, он будет иметь хождение внутри инфрастуктуры РедХата. Но не понятно, можно ли его использовать где-то еще. Под Андроид, вроде, он не очень применим.
У Котлина будущее посветлее. Весной его продвигали под веб разработку. Осенью его стали продвигать под Андроид разработку. Хоть разработчики и честно сознаются, что если вы уже используете Скалу, то Котлин вам не нужен, но пара технических преимуществ перед Скалой у Котлина есть: он быстрее компилируется (скорость компиляции была одной из целей разработчиков), его рантайм меньше скалового (что важно для мобильной разработки).
Более подробно изыскания про Котлин и Скалу я изложил на ИТ-субботнике.