Имеет ли смысл & # 8220; fake & # 8221; растровые индексы?

Question

Я планирую программное обеспечение, которое в своей основе является приложением OLAP (оно помогает анализировать данные измерений) и будет иметь какую-то звездообразную схему для своей базы данных, потому что сохраненные значения будут рассматриваться под разными углами (время, источник, тип и т. д.) и запросы будут запрашивать агрегированные данные по этим измерениям. Как правило, запросы доставляют много строк (до 100 000).

Мои исследования по этой теме (см. также мой вопрос здесь ), кажется, указывает на то, что индексы растрового изображения - это хороший способ поиска данных так, как я планирую. Тем не менее, я хочу поддерживать несколько механизмов БД, некоторые из которых не предлагают растровые индексы в своих таблицах (в частности, MySQL).

Теперь я, безусловно, могу построить и поддерживать свой собственный индекс растрового изображения и использовать его для поиска идентификаторов строк, указывающих на таблицу фактов. Тем не менее, я подозреваю, что это разрушит всю цель индекса, потому что база данных все еще будет искать идентификаторы строк в B-дереве. Может ли кто-нибудь с более глубоким теоретическим опытом или большим опытом рассказать мне, если я все еще что-то получу, например, не нужно делать медленные соединения в таблицах измерений?

Я также был бы признателен за подсказки о том, что я должен оценить, если ответ не является простым.

Answer 1

Некоторые механизмы БД, которые непосредственно не поддерживают индексы растровых изображений, все еще имеют оптимизацию звездой, которая может выполнять этот тип запроса, не обращаясь к таблице фактов. Например, SQL Server имеет функцию, называемую пересечением индексов, которая делает нечто похожее, создавая растровые изображения на лету для выполнения разрешения. Microsoft утверждает , что производительность этого сопоставима с растровыми индексами. См. это сообщение чтобы немного развлечься по этой теме.

Я не уверен, что MySQL делает это, но Postgresql, безусловно, делает это. Некоторые варианты IIRC (я думаю, Greenplum) также напрямую поддерживают растровые индексы, и некоторые говорили о его включении в основной механизм БД. Я не помню, было ли это сделано.

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

Answer 2

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

В общем, поскольку вы все равно будете искать по индексу B-Tree, вы ничего не получите, если судите по моему опыту.

Итак, нет.

Если ваше приложение по своей природе является OLAP по своей природе, и у вас есть небольшое количество измерений, которые естественным образом группируются в упорядоченные диапазоны, и вам действительно нужно изменить асимптотику вашей задачи, вы можете рассмотреть создание структуры, подобной «таблице сумм», тогда Вы можете запросить его для любого иерархического ответа с помощью 2 ^ d операций, и вы можете амортизировать его, если выполняете несколько связанных запросов.

Пример в 2d с координатами x и y, где вас интересует сумма в диапазоне от (x1, y1) до (x2, y2).

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

Используя сумму, для каждой позиции (x, y) не сохраняйте значение этой позиции, а вместо этого сохраняйте сумму в области от (0,0) до (x, y).

Затем вы можете ответить на любой запрос диапазона:

sum (x2, y2) - сумма (x1, y2) - сумма (x2, y1) + сумма (x1, y1)

постоянная сумма накладных расходов (ну, логарифмическая по размеру набора данных, при условии, что у вас есть индекс по x и y и вы храните его в SQL)

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