Имеет ли смысл «подделывать» растровые индексы?
Я планирую программное обеспечение, в основе которого лежит приложение OLAP (оно помогает анализировать данные измерений) и будет иметь некую звездную схему для своей базы данных, потому что сохраненные значения будут рассматриваться под разными углами (время, источник, тип и т. д.), и запросы будут запрашивать агрегированные данные по этим измерениям. Запросы обычно доставляют много строк (примерно до 100 000).
Мое исследование по этой теме (см. Также мой вопрос здесь), кажется, указывает на то, что индексы растровых изображений являются хорошим способом поиска данных так, как я планирую. Однако я хочу поддерживать несколько механизмов БД, некоторые из которых не предлагают индексы растровых изображений в своих таблицах (в частности, MySQL).
Теперь я могу создать и поддерживать свой собственный индекс растрового изображения и использовать его для поиска идентификаторов строк, указывающих на таблицу фактов. Однако я подозреваю, что это сведет на нет всю цель индекса, потому что база данных по-прежнему будет искать идентификаторы строк в B-дереве. Может ли кто-нибудь с более глубокими теоретическими знаниями или большим опытом сказать мне, получу ли я что-нибудь, например, отсутствие необходимости выполнять медленные соединения с таблицами измерений?
Я также был бы признателен за подсказки о том, что я должен оценить, если ответ не является однозначным.
Ответы 2
Некоторые механизмы БД, которые напрямую не поддерживают индексы растровых изображений, по-прежнему имеют звездообразную оптимизацию, которая может выполнять этот тип запроса, не обращаясь к таблице фактов. SQL Server, например, имеет функцию под названием Index Intersection, которая делает нечто подобное, создавая растровые изображения на лету для разрешения. Microsoft претензии, что производительность этого сопоставима с индексами растровых изображений. См. Эта публикация для небольшого обсуждения этой темы.
Я не уверен, что MySQL делает это, но Postgresql определенно делает. Некоторые варианты IIRC (я думаю, Greenplum) также напрямую поддерживают растровые индексы, и были разговоры о включении этого в основной движок БД. Я не помню, было ли это сделано еще.
Я думаю, вы обнаружите, что большинство современных платформ СУБД предлагают те или иные оптимизации запросов типа «звезда», так что вам, вероятно, не придется изобретать колесо заново. Вы можете найти одного или двух, которые не могут этого сделать, но у вас всегда есть возможность просто не поддерживать их.
Мне повезло с индексами растровых изображений при манипулировании большим количеством данных в памяти с помощью пользовательских структур данных, но их довольно неудобно реализовать в сторонней базе данных, у которой нет хорошего (похожего на postgresql) API для расширение их индексных структур.
В общем, поскольку вы все равно будете искать в индексе B-Tree, вы ничего не получите, если мой опыт может служить ориентиром.
Так что нет.
Если ваше приложение по своей природе является OLAP, и у вас есть небольшое количество измерений, которые естественным образом группируются в упорядоченные диапазоны, и вам действительно нужно изменить асимптотику вашей проблемы, вы можете подумать о создании структуры, подобной `` таблице сумм '', тогда вы можете запросить это для любого иерархического ответа с 2 ^ d операциями, и вы можете амортизировать это, если выполняете ряд связанных запросов.
Пример в 2d с координатами x и y, где вас интересует сумма в диапазоне от (x1, y1) до (x2, y2).
При хранении отдельно вам придется суммировать количество записей, пропорциональных площади.
Используя таблицу суммирования, для каждой позиции (x, y) не сохраняйте значение этой позиции, а вместо этого сохраняйте сумму области от (0,0) до (x, y).
Затем вы можете ответить на любой запрос диапазона, спросив:
сумма (x2, y2) - сумма (x1, y2) - сумма (x2, y1) + сумма (x1, y1)
постоянное количество накладных расходов (ну, логарифмическое по размеру набора данных, если у вас есть индекс по x и y и вы сохраняете его в SQL)
Это, конечно, не работает, если у вас есть сложные атрибуты, которые не разбиваются на диапазоны, но могут обрабатывать простые лексикографические индексы, даты и т. д.
Для баз данных, которые действительно поддерживают растровые индексы, я бы предложил использовать их, а не использовать наименьший общий знаменатель для всех баз данных.