Константин Селезнев
Как известно, задача разработки СУБД в ИТ-индустрии изначально не стояла, но были актуальны прикладные задачи, требующие обработки массивов структурированной информации. Постепенно выяснилось, что во многих случаях алгоритмы накопления, поиска и анализа данных одинаковы, а следовательно, их можно сделать универсальными и выделить в виде отдельных инструментальных средств — систем управления базами данных. К прикладному ПО обработки больших объемов информации всегда предъявляются одни и те же требования — скорость работы и стоимость разработки, которые трансформируются в требования к используемой СУБД. Чем гибче и богаче возможности СУБД, тем проще разработчику прикладной системы приспосабливать их для своих нужд, а значит, тем меньше оказывается стоимость создаваемого ПО.
Таким образом, можно сформулировать наиболее общие требования к СУБД — гибкость и скорость работы. Другие часто предъявляемые и не менее важные требования, такие как поддержка широко распространенных языков запросов или возможность параллельной обработки данных, изначально не были ключевыми. Изменение требований к прикладному ПО влечет за собой изменение требований к СУБД, откуда следует, что развитие технологий СУБД определяется потребностями разработчиков прикладного ПО. Именно поэтому всевозможные экспериментальные СУБД часто остаются невостребованными даже в том случае, если превосходят свои аналоги по каким-либо характеристикам.
За многолетнюю историю развития СУБД было выработано несколько моделей представления структурированной информации: иерархическая, сетевая, реляционная, объектно-реляционная и т. д. Наибольшее распространение получила реляционная модель, предложенная Эдгаром Коддом в 1970 году, которая надолго стала стандартом представления структурированной информации. Причины этого вытекают из сформулированных требований к СУБД. Во-первых, реляционная модель оказалась достаточно простой, с точки зрения прикладного программиста. Во-вторых, она обладает достаточной гибкостью и позволяет представлять информацию из самых разных предметных областей. В-третьих, в рамках этой модели используется мощный и удобный подход к манипулированию данными (реляционная алгебра), впоследствии оформленный в виде языка SQL. В-четвертых, простота и естественность реляционной алгебры позволили создать высокопроизводительные и универсальные алгоритмы выполнения запросов, удовлетворяющие большую часть потребностей разработчиков прикладных систем. Наконец, к сегодняшнему дню создано множество инструментальных средств, ориентированных на обработку реляционных данных, что дает еще одно преимущество реляционных СУБД.
Итак, при разработке прикладного ПО из исходных требований следует выбор модели представления информации, а уже из нее следует выбор конкретной СУБД. Эта схема может показаться абстрактной в силу того, что на текущий момент доминирующей является реляционная модель, а выбор СУБД производится из достаточно ограниченного списка, который заранее продиктован другими факторами, такими как интеграция, простота поддержки, стоимость и т. д.
Реляционная модель предполагает оперирование только атомарными данными и исключает обработку какой-либо неструктурированной информации, а это приводит к тому, что хранение графических, аудио- или видеоданных становится невозможным. Более того, невозможно даже хранение текстовых документов произвольной длины. Поэтому, первым отступлением от классической реляционной модели в сторону удобства разработки прикладного ПО можно считать введение типа BLOB (Binary Large Object — «бинарные данные большого объема»), который сегодня поддерживается большинством современных СУБД и закреплен в стандартах языка SQL. Каждая СУБД, помимо BLOB, может иметь свои собственные «дополнительные» типы данных, которые обычно требуют введения дополнительных поисковых операций (например, полнотекстовый поиск по BLOB). Это еще дальше уводит от классической реляционной модели.
По мере роста объемов хранимой информации и сложности ее внутренних взаимосвязей стали возникать новые проблемы. Увеличение сложности SQL-запросов привело к тому, что СУБД уже далеко не всегда способны выработать оптимальный план выполнения поступившего запроса. На практике это производится двумя способами. Первый — в тексте SQL указываются «подсказки», помогающие оптимизатору запросов выработать наиболее эффективный план. Второй — вместо запроса используется хранимая процедура. Причина хорошей применимости обоих способов кроется в том, что встроенные в СУБД оптимизаторы запросов располагают только статистической информацией о содержимом базы и строят планы выполнения запросов только на ее основе, а разработчик прикладного ПО всегда обладает гораздо большими сведениями.
Оба отступления от базовых принципов реляционной модели (введение неатомарных типов данных и тонкое управление алгоритмами обработки) напрямую следуют из особенностей самой модели, провозглашающей универсальность способов хранения информации и алгоритмов ее обработки. За этой универсальностью скрывается невозможность учета специфики данных, позволяющей существенно оптимизировать работу алгоритмов.
Допустим, требуется организовать хранение большого множества чисел и быстро выполнять операции поиска, добавления и удаления числа. Для этого в реляционной базе создается таблица с одним числовым полем, а по этому полю формируется поисковый индекс на основе B-дерева. Такое решение работает быстро, но предполагает дублирование информации (числа хранятся и в самой таблице, и в поисковом индексе). Более эффективным было бы использование только B-дерева, но реляционные СУБД не всегда способны это определить.
Данный пример может показаться слишком простым, но похожая ситуация реализована в Triple Storages (хранение графов семантических сетей в семантическом Web), отвечающих за хранение и обработку графов семантических связей. Каждая дуга графа представляет собой три числа (два кода вершин и один код окраски). Множество всех дуг можно было бы хранить в виде реляционной таблицы с необходимыми поисковыми индексами, но вместо этого хранят только поисковые индексы, поскольку каждый из них содержит всю информацию о каждой дуге.
Третий пример — полнотекстовые поисковые системы Интернета. Их база данных должна содержать поисковые слова и коды документов, в которых эти слова являются ключевыми. Это несложно сделать с помощью реляционной таблицы, состоящей из двух полей — поисковое слово и код документа. Если слово встречается в нескольких документах или документ имеет несколько ключевых слов, то таблица содержит несколько записей.
Возможна существенная оптимизация рассмотренного примера: скажем, вместо текстового представления слова можно хранить его целочисленный код, а вместо кода документа хранить BLOB, где будут содержаться коды всех документов, имеющих отношение к данному слову. Дальнейшая оптимизация в рамках реляционного подхода невозможна, но ее можно провести посредством так называемого инвертированного индекса. Коды документов сортируются по возрастанию, и в полученном списке вычисляются разницы между кодами соседних документов. Получается последовательность, состоящая из кода первого документа и множества чисел небольшой величины. Она хорошо сжимается алгоритмами энтропийной компрессии (например, алгоритмом Лемпеля — Зива-Велча), в результате чего значительно сокращается объем ввода/вывода, ускоряется загрузка информации с диска и в конечном счете растет скорость полнотекстового поиска.
Задача не для реляционной СУБД
Имеется набор из 10 тыс. датчиков, один раз в секунду отправляющих показатели (вещественные числа). Показатели датчиков стабильны и изменяются плавно. Необходимо в интерактивном режиме анализировать месячные данные и определять, приводит ли резкое изменение одного показателя больше чем на фиксированную пороговую величину к изменению другого показателя больше чем на другую пороговую величину. Желательно использовать обычный ПК, не привлекая специальные решения (RAID-массивы и т. п.).
Если каждый датчик генерирует значение раз в секунду, то за месяц объем данных составит 96 Гбайт, и если использовать РСУБД, то потребуется примерно такой же объем дискового пространства плюс расход на хранение индексов «время -> показания датчиков», количество которых зависит от логической структуры базы. Если потребуется хранить данные за несколько месяцев, то реляционная СУБД уже не подходит.
Показания датчиков можно представить в виде матрицы: строки соответствуют моментам времени, а столбцы — номерам датчиков. Проектирование реляционной базы сводится к представлению этой матрицы в виде реляционных таблиц. Самым простым и логичным с точки зрения реляционного подхода способом организации является использование таблицы с полями «время – код датчика – значение», но это решение неприменимо на практике из-за огромного размера таблицы (2 592 000 секунд x 10 тыс. значений).
Указанную матрицу можно «разворачивать» в реляционные таблицы по горизонтали или по вертикали. В первом случае записи реляционных таблиц будут соответствовать моментам времени, а поля реляционных таблиц — номерам датчиков. Для оценки изменения значения датчика нужно взять запись, соответствующую данному моменту времени, получить запись для следующего момента и вычислить разницу значений в одном и том же поле. Поскольку первичным ключом таблицы является значение времени, то первые два шага будут выполняться достаточно медленно, и даже поиск моментов, когда датчик изменил свои показания больше чем на пороговую величину, на практике работать не будет. Это объясняется тем, что для каждой из 2 592 000 записей нужно будет найти «следующую» из тех же 2 592 000 записей. Если в целях оптимизации таблицы разбить по дням, то каждая из них будет содержать 24 x 60 x 60 = 86 400 записей, и, соответственно, нужно будет делать 30 (количество дней) поисков, каждый из которых будет анализировать 86 400 записей и для каждой искать «следующую» из 86 400 записей.