C.1 Поисковые таблицы
Как описывалось в подразделе 4.2, поисковые таблицы оказываются полезными в тех случаях, когда в данных имеется некоторая локальность, не очевидная по схеме базы данных. Чтобы получить наилучшее разделение для данных этого типа, необходимо поддерживать информацию о разделении для каждого отдельного кортежа. На логическом уровне это представляет собой отображение между кортежами и идентификаторами разделов. Поддерживать это отображение для всех атрибутов кортежей невозможно. Однако во многих приложениях доступ к данным, в основном, производится по первичному ключу, значения которого обычно образуют плотное множество целых чисел, генерируемых системой. Для приложений такого типа хранение и поддержка поисковых таблиц могут быть очень эффективными. К этой информации можно относиться как к "мягкому состоянию" ("soft state"), потому что в случае отказа системы ее легко можно восстановить путем сканирования базы данных.
На физическом уровне мы экспериментировали с тремя разными реализациями поисковых таблиц: традиционные индексы, битовые массивы и фильтры Блюма. Наиболее общим решением являются традиционные индексы, которые можно использоваться для любого(ых) типа(ов) данных столбца(ов) разделения. Кроме того, эти структуры данных эффективны и хорошо изучены. Однако для поддержки индексов требуется больше всего ресурсов. Битовые массивы пригодны для поддержки (почти) плотного множества целочисленных ключей, если каждому ключу сопоставить смещение в массиве идентификаторов разделов. Это очень компактный и быстрый способ хранения поисковых таблиц, естественным образом пригодный для многих приложений, в которых используются автоинкрементные целые первичные ключи. При наличии нескольких гигабайт основной памяти, в массиве можно сохранять идентификаторы разделов для миллиардов кортежей.
Наконец, мы произвели прадварительное тестирование с использованием фильтров Блюма, которые обеспечивают более компактное представление, но иногда срабатывают ложным образом (false positive). Эти ложные срабатывания приводят к снижению производительности, но не влияют на корректность. При маршрутизации запросов ложное срабатывание означает, что некоторый раздел вовлекается в выполнение некоторого оператора, хотя это не требуется. Реальная экономия памяти зависит от многих параметров, таких как число кортежей, число разделов и интенсивность ложных срабатываний.
В настоящее время мы изучаем возможности (i) наилучшей реализации поисковых таблиц для распределенных баз данных, (ii) определения того, когда лучше использовать поисковые таблицы, а не традиционные хэш-разделение и разделение по диапозонам значений, а также (iii) выбора наилучшей реализации для каждого сценария.
