Обработка запросов в DEC Rdb: основные аспекты и нерешенные проблемы

Геннадий Антошенков
Перевод: Сергей Кузнецов

Оригинал: Gennady Antoshenkov. Query Processing in DEC Rdb: Major Issues and Future Challenges. IEEE Bulletin of the Technical Committee on Data Engineering, Vol. 16, # 4, December 1993. Текст доступен здесь.

Назад Содержание

6. Архитектурные аспекты

Неопределенность преобразований распределений оценок, являющаяся неоъемлемой частью основных булевских/реляционных операций, является не единственной разновидностью неопределенностей, с которыми мы имеем дело. Значения пользовательских переменных, атрибуты уже разрешенных частей запросов, размер доступной памяти и т.д. становятся доступными на разных стадиях выполнения, и потому с ними нужно работать динамически. Этот тип неопределенности может быть, большей частью, разрешен путем привязки значения в тот момент, когда оно становится доступным, часто при старте вычисления операции.

Метод динамического выбора подплана запроса во время привязки значения предлагается в [GrWa89]. Динамические планы обеспечивают механизм переключения традиционным образом генерируемых альтернативных подпланов, применяемый во время старта подплана в зависимости от доступных значений переменных. Основанная на конкуренции динамическая оптимизация, с другой стороны, включает все те же переменные в свою модель стоимости и обеспечивает переключение стратегии во время начала и в любой другой точке выполнения подзапроса.

Однако очевидно, что статистически некоторые решения о переключении, принимаемые во время старта с небольшими вычислительными накладными расходами, помогают избежать больших накладных расходов на конкуренцию, не жертвуя оптимальностью. Это делает время старта подзапроса идеальным моментом для отделения неопределенности (обсуждавшегося в разд. 4) и начальной организации одиночного или параллельных потоков управления.

На уровне доступа к одиночной таблице механизм переключения стратегий описан в [MoHa90]. Он выполняет переключения в течение индексных сканирований по достижению некоторых порогов с целью скорректировать периодические направления неоптимального выполнения, выбранные во время компиляции. При этом подходе пороговые значения также вычисляются во время компиляции (что делает их похожими на динамические планы). В Rdb пороги, частично вычисленные во время компиляции, окончательно оформляются во время начала выборки и подгоняются под изменяющуюся «лучшую в текущий момент» стратегию в течение выборки.

В Rdb выборки из таблиц и индексов контроллируются динамическим оптимизатором на трех фазах:

1. Начальная фаза – производятся недорогие вычисления и оценки индекса, следущие из начальной конкуренции, или организуется однопотоковое выполнение.
2. Фаза сканирования индекса – сложный механизм, включающий несколько совместных и конкурирующих стратегий, поставляющий запрошенные записи и/или список ID записей или принимающий решение о последовательной выборке из таблицы.
3. Завершающая фаза – производятся непереключаемые чтения записей либо по списку ID записей, либо последовательно.

Подробное описание этой архитектуры можно найти в [Ant91] и [Ant93]. Динамическая архитектура как часть продукта представлена в [HoEn91]. На фазе сканирования индекса одновременно имеют место несколько разновидностей конкуренции, в которую вовлекается до трех индексов. Намерение быстрой доставки записей может конкурировать с построением списка ID записей. Последовательность обработки индекса может изменяться в ходе прямой конкуренции. Сканирование некоторых индексов может быть прекращено при двухфазной конкуренции за наиболее дешевую завершающую фазу. Сканирование индекса может конкурировать с уже обнаруженной полной стратегией выборки.

Несмотря на новизну и исключительную изощренность динамической концепции, в сообществе пользователей Rdb приняли ее очень быстро и предложили много соображений по ее дальнейшему совершествованию. Например, многие пользователи просили обеспечить новый вид конкуренции между индексной выборкой с обеспечением желаемого порядка сортировки и выборки через список ID записей с последующей сортировкой. Но больше всего поддержки получило то, что, анализируя ситуации многих заказчиков, мы обнаружили почти все возможные комбинации динамических переключений, ведущие к улучшению производительности. Поскольку все реализованные виды конкуренции настраивались на гиперболическое распределение стоимости, согласованное наличие и многообразие перключателей явно показывает преобладание гиперболического распределения.

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

Когда мы впервые включили динамическую оптимизацию в версию продукта, нас тревожили непредвиденные проблемы, вызываемые переключениями во время выполнения. Новое поведение переключений не беспокоит никого – случались неточные переключения, и мы производили подгонку, но обычно требовались более искуссные схемы переключения. Одним из исключений было то, что переключение на последовательную выборку на таблице с высокой активностью обновлений заставляло выбирающую транзакцию ждать и аварийно завершаться в середине выполнения. Из этого мы извлекли тот урок, что для интенсивных обновлений при всех обстоятельствах должны делаться последовательные блокировки.

Наиболее замечательные отзывы, поступившие от заказчиков, заключались в том, что (a) были установлены и востребованы почти все общие механизмы обработки запросов, применимые для динамической оптимизации и еще не включенные в нее, и (b) внутри динамического оптимизатора была обнаружена и доложена нам в качестве запроса на совершенствование применимость новых принципов к областям, в которых они ранее не применялись. В большинстве случаеы такие запросы на распространение технологии базировались на конкретных сценариях приложений.

7. Распространение технологии

Для обнаружения преимуществ распространения технологических средств и принципов в различные производственные области обычно требуется умственное напряжение. Но в требовательной среде баз данных неиспользование таких преимуществ может приводить к неожиданной деградации производительности, вызывающей большое неудовлетворение заказчиков. В приложениях баз данных обычно содержится набор запросов, для выполнения которых требуется множество вариаций нескольких конкретных возможностей, что оказывает давление на механизмы обработки запросов. Когда в некоторую область, находящуюся под давлением, вводится новое средство, стратегии запросов меняются для обеспечения возможности использования этого средства. Если распространение средства является неполным, непокрытые случаи могут не сочетаться с новыми стратегиями выполнения, что вызывает деградацию производительности.

Распространение технологии требуется в ходе интеграции каждого нового средства. Оно также является выгодным в проектной и исследовательской деятельности. Например, в [Gra94] представлен подробный баланс распространения нескольких свойств (дуализм) между методами соединения хэшированием и сортировкой со слиянием. Если обе стратегии соединения сосуществуют, дуализм может быть полезен не только на концептуальном уровне, но также и в реализации.

В течение цикла разработки Rdb мы использовали многочисленные преимущества распространения понятий. Путем введения «убывающих» индексов мы допустили возможность любых комбинаций возрастания/убывания составных атрибутов ключа. Однако в некоторых важных приложениях заказчиков имеются многочисленные запросы вида «выдать из последовательности записей X десять записей ниже C и десять записей выше C», которые могут быть эффективно разрешены с помощью двух (возрастающего и убывающего) индексов на X. Несмотря на эту возможность, цена двойного объема памяти и дополнительных обновлений индексов для подхода с двумя индексами была чрезмерной. Это вынудило нас реализовать обратное индексное сканирование и, таким образом, обеспечить решение отмеченной проблемы с помощью одного индекса.

В 1987 г. мы ввели эффективное соединение слиянием отношений A и B по атрибуту X с использованием индекса на B.X. Если для некоторого разрыва между двумя соседними значениями A.X имеется несколько значений B.X, которые нужно пропустить, эти значения B.X пропускаются в манере зигзаг путем испытания всех ключей в текущей индексной странице, а затем (для больших разрывов) спуска от корня B-дерева к концу разрыва.

Затем мы обратили внимание, что прохождение значения конца разрыва от A к B можно также осуществить через агрегат, определенный на B.X, и реализовали зигзагообразный пропуск разрыва над одним или несколькими агрегатами. Далее, при оптимизации выборки с несколькими диапазонами мы применили зигзагообразный пропуск к разрывам в упорядоченном списке диапазонов. Наконец, оптимизации соединения слиянием и списка диапазонов были интегрированы в динамическую стратегию выборки, называемую «Leaf». Если для поддержки дополнительных ограничений были доступны индексы, отличные от B.X (скажем, B.Y), то на начальной стадии применялась тактика организации конкуренции «Sorted», при которой:

1. B.X и B.Y сканирутся в параллель;
2. на стороне X читаются и выдаются записи в желаемом порядке сортировки;
3. на стороне Y строится фильтр ID записей для дополнительного ограничения Y;
4. после заполнения фильтра начинается пропуск записей на стороне X, не входящих в фильтр Y.

Рис. 2. SQL-запрос и план выполнения с использованием технологии пропусков

На рис. 2 показан SQL-запрос, в котором все методы пропуска, описанные выше, объединяются в единый план выполнения, напечатанный утилитой Rdb выдачи дампа стратегии. Концевые значения разрывов передаются из цикла Outer в цикл Inner через Aggregate к Leaf#01 для пропуска через FgrNdx BX (индекс переднего плана). Одновременно к индексу BX для пропуска передаются концы разрыва в списке диапазонов [2:2], [4:4], [8:8], [16:16], [32:32]. В то же самое время, сканируется BgrNdx1 BY (индекс заднего плана), и его список ID записей, ограничиваемый B.Y < 1, используется для конструирования фильтра «B.Y < 1». Если фоновое сканирование BY завершается раньше BX, полный фильтр, произведенный BY, используется для избежания чтения записей в сканировании BX. В противном случае BX быстрее достигает цели без фильтрации, и выборка из B завершается.

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

8. Заключение

При обработке запросов проявляется тенденция к преобразованию промежуточных потоков данных таким образом, что неопределенность оценок мощности потоков быстро и радикально возрастает. Это ограничивает применимость традиционной модели стоимости на основе средней точки и приводит к потребности методов динамической оптимизации, напрямую имеющих дело с неопределенностью. Мы обнаружили, что преобладающей формой неопределенностей, порождаемых вложенными запросами, является гипербола, и разработали настроенную на гиперболу конкурентную стоимостную модель для использования в динамическом оптимизаторе DEC Rdb.

В течение динамической оптимизации во время старта операции организуется выполнение одной стратегии или конкуренция нескольких альтернативных стратегий. Параллельный прогон альтернативных стратегий сокращает неопределенность и облегчает надежный выбор наилучшего способа продолжения. На основе отзывов заказчиков мы установили адекватность динамического подхода и потребность в дальнейшем усовершенствовании конкуренции. Мы видим значительный потенциал той же самой динамической структуры для ускорения процесса сокращения неопределенности путем динамического взятия образцов и рандомизации обработки запросов.

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

Параллельная обработка запросов является очевидным способом использования быстро возрастающей мощности компьютеров для работы со сверхбольшими объемами данных. Мы ожидаем, что создание динамического оптимизатора Rdb с его параллельной архитектурой будет способствовать решению проблем параллельной обработки, связанных с высоким уровнем неопределенности, скошенностью и неизвестными корреляциями.

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

Литература

[Ant91] G.Antoshenkov, “Dynamic Optimization of a Single TableAccess,” Technical Report DBS-TR-5, DECTR-765, DEC Data Base Systems Group, (June 1991).

[Ant92] G. Antoshenkov, “Random Sampling from Pseudo-Ranked B+ Trees,” Proceedings of the 18th VLDB conference), (August 1992).

[Ant93] G. Antoshenkov, “Dynamic Query Optimization in Rdb/VMS,” Proceedings of Ninth Int. Conference on Data Engineering, (April 1993).

[Babb79] E. Babb, “Implementing a Relational Database by Means of Specialized Hardware,” ACM Transactions on Database Systems, Vol. 4, No. 1, (March 1979).

[HaSw92] P. Haas and A. Swami, “Sequential Sampling Procedures for Query Size Estimation,” Proceedings of the ACM SIGMOD Conference, (June 1992).

[HoEn91] L. Hobbs and K. England, “Rdb/VMS: A Comprehensive Guide,” Digital Equipment Corporation, Chapter 6 (1991).

[Gra94] G. Graefe, “Sort-Merge-Join: An Idea Whose Time Has(h) Passed?” to appear in Proceedings of Int. Conference on Data Engineering, (1994).

[GrWa89] G.Graefe and K.Ward, “Dynamic Query Execution Plans,” Proceedings of the ACM SIGMODConference, (May 1989).

[IoCh91] Y. Ioannidis and S. Christodoulakis, “On the Propagation of Errors in the Size of Join Results,” Proceedings of the ACM SIGMOD Conference, (June 1991).

[LiNS90] R. Lipton, J. Naughton, D. Schneider, “Practical Selectivity Estimation through Adaptive Sampling,” Proceedings of the ACM SIGMOD Conference, (June 1990).

[MoHa90] C.Mohan, D. Haderle, Y.Wang, J. Cheng, “Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques,” Advances in Database Technology - EDBT’90, (March 1990).

[OlRo89] F. Olken and D. Rotem, “Random Sampling from B+ Trees,” Proceedings of the 15th VLDB conference, (1989).

[OlRo90] F. Olken and D. Rotem, “Random Sampling from Hash Files,” Proceedings of the ACM SIGMOD Conference, (June 1990).

[OlRo93] F. Olken and D. Rotem, “Sampling from Spatial Databases,” Proceedings of Ninth Int. Conference on Data Engineering, (April 1993).

[Roy91] S. Roy, “Adaptive Methods in Parallel Databases,” PhD Dissertation, Dept. of Computer Science, Stanford University, (August 1991).

[SACL79] P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, T. Price, “Access Path Selection in a Relational Database Management System,” Proceedings of the ACM SIGMOD Conference, Boston, (June 1979). Есть перевод на русский язык: П. Селинджер, М. Астрахан, Д. Чемберлин, Р. Лури, Т. Прайс. Выбор пути доступа в реляционной системе управления базами данных.

[Zipf49] G.K. Zipf, Human Behavior and the Principle of Least Effort, Addison-Wesley, Reading, MA, (1949).

Назад Содержание