Обработка запросов в NonStop SQL

Альберт Чен, Юнг-Фенг Као, Майк Понг, Диана Шак, Сунил Шарма, Джей Вайшнав, Хансйорг Зеллер
ПереводПеревод— деятельность по интерпретации смысла текста на одном языке (исходном языке [ИЯ]) и созданию нового, эквивалентного текста на другом языке (переводящем языке [ПЯ]).: Сергей Кузнецов

Оригинал: Albert Chen, Yung-Feng Kao, Mike Pong, Diana Shak, Sunil Sharma, Jay Vaishnav, Hansjorg Zeller. Query Processing in NonStop SQL. IEEE Bulletin of the Technical Committee on Data Engineering, Vol. 16, # 4, December 1993. Текст доступен здесь.

Содержание

1. Введение

1.1 Компоненты обработки запросов NonStop SQL

2. Query Optimization

2.1 Оценка селективности

2.2 Генерация планов

2.3 Выбор наилучшего плана

3. Возможности обработки запросов

3.1 Операции, ориентированные на множества, в дисковом процессе

3.2 Горизонтальное разделение

3.3 Комбинация и устранение сортировок

3.4 Соединения на основе хэширования

3.5 Параллельное выполнение

4. Группировка и агрегация

5. Влияние пользователей

6. Производительность

7. Заключение и перспективы

Литература

1. Введение

NonStop SQL – это отказоустойчивая, распределенная реализация языка запросов SQL для вычислительных систем Tandem NonStop [Tand87, Tand89].

Вычислительные системы Tandem NonStop являеются слабосвязанными (т.е. без общей памяти, non-shared-memory) мультипроцессорными системами. Система состоит из кластеров процессоров, и каждый кластерКластер (англ.cluster— скопление)— объединение нескольких однородных элементов, которое может рассматриваться как самостоятельная единица, обладающая определёнными свойствами. содержит до 224 процессоров. Система может инкрементно наращиваться по мере роста вычислительных требований. Процессоры взаимосвязаны через дуплексную оптоволоконную шину. Большинство устройств ввода-вывода, включая диски, являются дуплексными и могут подсоединяться к двум процессорам, чтобы обеспечить резервный путь доступа к устройству. Большая часть критичных системных процессов поддерживается в виде пар процессов, в которых один процесс действует как основной, а второй – как горячий резерв (hot standby). Таким образом, система может сохранить работоспособность при любом одиночном отказе без потери доступа к какому-либо программному или аппаратному ресурсу.

Операционная система Tandem NonStop KernelLinux (/lnks/)— ядро операционной системы, соответствующее стандартам POSIX. Разработка была начата финским студентом Линусом Торвальдсом в 1991 году. основана на передаче сообщений. Доступ к устройствам ввода-вывода, включая диски, достигается путем посылки сообщений серверным процессам, управляющим конкретным устройством. Любой процесс в системе может получить доступ к любому устройству ввода-вывода в системе, послав сообщение соответствующему серверному процессу.

Приложения обычно разрабатываются с использованием модели «клиент-сервер». Обеспечивается монитор транзакций (PATHWAY) для управления серверами и коммуникациями между клиентами и серверами. Серверы приложений могут быть написаны на разнообразных языках (C, COBOL, Pascal, TAL) с использованием встроенного SQL для доступа к данным.

NonStop SQL строится над основанной на сообщениях, отказоустойчивой архитектурой вычислительных систем Tandem. В системе обеспечивается глобальное пространство имен, и программа может получить доступ к любой таблице во всей системе (при наличии требуемых прав доступа). Транзакции могут быть распределенными и могут иметь доступ к любой таблице во всей системе. Для координации фиксации транзакций используется двухфазный протокол фиксации. В NonStop SQL используется принципПринцип или начало (лат.principium, греч. )— в теоретической философии то, чем объединяются в мысли и в действительности известная совокупность фактов. автономности узлов: при выполнении запроса к горизонтально разделенной таблице допускается недоступность некоторых разделов, если данные из этих разделов не требуются. Автономность узлов обеспечивает то, что у пользователя всегда имеется доступ к локальным данным, независимо от того, доступны или нет удаленные разделы таблицы. Полная поддержка версионности позволяет сосуществовать в распределенной системе различным версиям программ, таблиц, каталогов и системного программного обеспечения.

1.1 Компоненты обработки запросов NonStop SQL

Система обработки запросов в NonStop SQL состоит из компилятора SQL, исполнителя SQL, файловой системы SQL, дисковых процессов и словаря SQL. Компилятор SQL компилирует статические и динамические операторы SQL. Он обращается к словарю SQL для выполнения связывания имен и выборки статистической информации о содержимом таблиц для сборки плана выполнения (называемого также планом доступа) для каждого оператора. В отличие от других реализаций РСУБД, планы выполнения для статических операторов SQL сохраняются в тех же файлах, что и объектный код, производимый компиляторами основных языков (3GL).

ИсполнительИсполнитель (автор исполнения) – физическое лицо, творческим трудом которого создано исполнение: артист-исполнитель (актер, певец, музыкант, танцор или другое лицо, которое играет роль, читает, декламирует, поет, играет на музыкальном инструменте или иным образом участвует в исполнении произведения литературы, искусства или народного творчества, в том числе эстрадного, циркового или кукольного номера), а также режиссер-постановщик спектакля (лицо, осуществившее постановку театрального, циркового, кукольного, эстрадного или иного театрально-зрелищного представления) и дирижер. представляет собой набор системных библиотечных процедур, вызываемых приложением для выполнения оператора SQL. Для статического SQL исполнитель выбирает план выполнения из объектного файла, который содержит не только машинный код, произведенный компилятором основного языка, но также и план выполнения, произведенный компилятором SQL. Для динамических операторов SQL исполнитель собирает план выполнения путем вызова компилятора SQL во время выполнения. Исполнитель интерпретирует каждый план выполнения и использует файловую систему для доступа к конкретной таблице через конкретный путь доступа. Файловая система посылает сообщение соответствующему дисковому процессу для выборки данных. Каждый дисковый процесс обеспечивает доступ к объектам на конкретном диске. На рис. 1 проиллюстрирована процессная архитектура NonStop SQL.

Рис. 1: Процессная архитектура NonStop SQL

2. Оптимизация запросов

В NonStop SQL имеется основанный на оценке стоимости оптимизатор [Seli79], выполняющий как оптимизацию запросов над одним отношением, так и оптимизацию соединений. Оптимизатор генерирует план выполнения с использованием стоимости, выражаемой в терминах эквивалентного числа операций ввода-вывода, выполняемых на некоторой аппаратной конфигурации, что составляет меру системных ресурсов, потребляемых каждой операцией [Pong88]. Потребляемыми ресурсами являются инструкции ЦП, операции ввода-вывода и сообщения. Целью представления стоимости в терминах эквивалентного числа операций ввода-вывода является сведение несравнимых единиц измерения в единое целое. Оптимизатор выбирает план выполнения с наименьшей стоимостью относительно других планов выполнения, генерируемых для данного запроса. В стоимости плана выполнения учитываются доступ к удаленным данным и стоимость выполнения сортировок.

2.1 Оценка селективности

Оптимизатор оценивает селективность предикатов, используя статистику уровня столбцов, сохраняемую в словаре данных. Важными статистическими данными являются SECONDLOWVALUE, SECONDHIGHVALUE и UNIQUEENTRYCOUNT. Они собираются и хранятся в словаре данных при выполнении пользователем команды UPDATE STATISTICS. Разность между вторым наибольшим значением и вторым наименьшим значением определяет диапазон значений столбца. В оптимизаторе предполагается, что значения равномерно распределены в этом диапазоне. Селективностью предиката сравнения по равенству является обратная величина числа вхождений данного значения. Селективность предиката проверки вхождения в диапазон оценивается с использованием интерполяции. Для предиката со сравнением на неравенство, содержащего параметрПараметр (от др.-греч. «соразмеряю») — величина, значения которой служат для различения элементов некоторого множества между собой. или переменную основной программы, назначается селективность 1/3.

Для оценки селективности соединения оптимизатор рассматривает транзитивные связи между предикатами эквисоединения. Например, если заданы предикаты A = B и B = C, то оптимизатор выводит A = C. В оптимизаторе поддерживается эквивалентность классов столбцов, принадлежащих предикатам эквисоединения, и они используются для оценки селективности соединений. После того, как таблица, которой принадлежит данный столбец, добавляется к композиции соединения, для столбца соединения синтезируется число вхождений уникальных значений. МощностьМощность— физическая величина, равная отношению работы, выполняемой за некоторый промежуток времени, к этому промежутку времени. результирующей композиции используется как верхняя оценка числа вхождений уникального значения. Селективностью предиката эквисоединения считается обратная величина синтезированного числа вхождений уникального значения.

2.2 ГенерацияГенерация — поколение, которое представлено более или менее одновозрастными особями, сменяемое последующим поколением, которое при дифференциации жизненного цикла может существенно отличаться от предыдущего. К примеру: при чередовании поколении (гетерагонии, метагенезе) у тлей (Aphidoidea), галлиц (Cecidomyiidae) и некоторых других насекомых. планов

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

Оптимизатор строит дерево планов доступа, называемое деревом поиска для перечисляемых планов соединения. С логической точки зрения, рассматриваются все возможные планы. Однако пространство поиска сокращается путем использования следующих эвристик:

1. Рассматриваются только праволинейные деревьяДерево— типичная форма деревянистых растений, имеющих ствол из древесины с лиственной кроной. соединений. Это означает, что соединение четырех таблиц (ABCD) может быть реализовано как (((AB) C)D) или (((AC) B)D), но не как ((AB)(CD)).
2. Рассматриваются три метода соединения, а именно, вложенные циклы, хэширование и сортировка со слиянием.
3. Новая таблица может быть соединена с существующей композитной (соединенной) таблицей, если либо существует предикат эквисоединения, связывающий композитную и новую таблицы, либо ни для одной из оставшихся таблицБогуслав Таблиц (словацк. Bohuslav Tablic (Tablicz); 6 сентября 1769, Ческе Брезово, Словакия — 21 января 1832, Костолне Моравце, Словакия) — чешско-словацкий писатель, священник, деятель возрождения словаков-лютеран, подобно тому как Бернолак является деятелем возрождения словаков-католиков. Таблиц учредил в Пресбурге «Общество чешско-словацкой литературы и языка» с целью издавать на понятном народу чешском языке простонародные и школьные книги. Учреждение этого общества было причиной если не процветания словацкой литературы, то появления в пресбургском лицее кафедры словацкого языка, для чего общество собрало большой капитал. Занять кафедру приглашен был Юрай Палкович. Общество скоро распалось, но кафедра продолжала существовать. Молодёжь имела возможность слушать историю своего народа на родном языке. В 1812 г. Таблиц был одним из основателей нового «Литературного общества Горных Городов» (Bergstdte), задававшегося прежней целью; результатом было открытие кафедры словацкого языка и в Банской Штьявнице. Это общество также скоро распалось. Таблиц писал очень много и по различным специальностям. Первое место занимают его «Poesie» (Вацов, 1806-1812). К ним приложены биографии известных словацких деятелей. Его «Sloventi verovci» (Вацов, 1805-1809) — отрывки из произведений древних словацких писателей, в то время почти уже позабытых. Перу Таблица принадлежит также много книг для народа, изданных двумя упомянутыми обществами. нет предиката эквисоединения, связывающего их с композитом.
4. На каждом шаге к дереву поиска добавляется только один план, производящий декартово произведение. К дереву поиска добавляется наименьшая таблица, которая еще не принадлежит композиту, и для которой отсутствует предикат эквисоединения, связывающий ее с композитом. Этот план позволяет оптимизировать некоторые запросы (звездообразные запросы), которые выполняются наилучшим образом, если декартово произведение наименьших таблиц формируется раньше соединения результатРезультат— заключительное последствие последовательности действий или событий, выраженных качественно или количественно. Возможные результаты включают преимущество, неудобство, выгоду, потерю, ценность и победу.а с более крупными таблицами.

Каждый узел дерева поиска представляет путь доступа для соединенного набора таблиц. Он характеризуется следующим:

1. набором содержащихся в нем таблиц;
2. путем доступа для чтения из него строк;
3. набором вычисленных предикатов;
4. порядком сортировки;
5. мощностью.

Важным является понятие порядка. Например, при сканировании таблицы с выборкой строк через индекс строки будут выдаваться в некотором порядке. От этого порядка зависит, можно ли избежать последующей сортировки (для ORDER BY или GROUP BY), или можно ли использовать предикат на ключе индекса, или следует ли выполнить сортировку со слиянием.

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

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

2.2.1 Последовательные планы выполнения

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

2.2.2 Планы параллельного выполнения

NonStop SQL может параллельно выполнять операторыОператор (позднелат.operator— работник, исполнитель, от operor— работаю, действую)— то же, что отображение в математике. SQL SELECT, INSERT, UPDATE, DELETE, соединения, группировку и агрегацию. Исчерпывающее обсуждениеДиалог (греч. — первоначальное значение— разговор, беседа двух людей) в обыденном смысле— литературная или театральная форма устного или письменного обмена высказываниями (репликами) в разговоре между двумя и более людьми;— в философском и научных смыслах— специфическая форма и организация общения, коммуникации. Традиционно противопоставляется монологу. планов параллельного выполнения представлено в подразд 3.5. Целью использования параллельной схемы выполнения запросов является разделение рабочей нагрузки между несколькими ЦП и сокращение времени ответа за счет потребления дополнительных ресурсов. Параллельные планы выполнения генерируются оптимизатором, когда это разрешается пользователем.

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

Сначала оптимизатор выбирает самый дешевый план из всех планов параллельного выполнения. Если стоимость двух планов различается не более чем на 5%, применяются правила разрешения конфликтов. План выбирается в соответствиеМногозначная функция — обобщение понятия функции, допускающее наличие нескольких значений функции для одного аргумента. со следующей схемой предшествования:

1. Выбор плана, соответствующего разделам, предшествует выбору любого другого параллельного плана.
2. Выбор любого параллельного плана предшествует выбору плана с повторным хэш-разделением (hash-repartitioned plan).
3. Выбор более дешевого из двух планов с повторным хэш-разделением.

Оптимизатор выбирает параллельный план выполнения, если его стоимость ниже стоимость наилучшего последовательного плана.

2.2.3 Доступ через несколько индексов

Если в запросе над одной таблицей предикаты раздела WHERE представлены в дизъюнктивной нормальной форме, и никакое дерево дизъюнкта не содержит в себе другойДругой — центральная категория современной философии. Актуализация данного понятия связана с такими событиями, как антропологический и лингвистический поворот. Другой — это не Я, тот, кто противостоит мне, находится по ту сторону меня, моих ценностей, моего мировоззрения. И вместе с тем, Другой такой же как Я: он мыслит, чувствует, ходит и т. д. дизъюнкт, то оптимизатор пытается использовать план доступа через несколько индексов. В соответствии с этим планом, один или более индексов, принадлежащих одной и той же таблице, последовательно сканируются, и выполняется логическое объединение выбранных строк. Этот план конкурирует с другими планами на основе его стоимости.

2.3 Выбор наилучшего плана

После того как оптимизатор завершает перечисление планов выполнения, для каждого плана в дереве поиска имеется ассоциированная стоимость. Оптимизатор намеревается выбрать план выполнения с наименьшей стоимостью (такой план считается наилучшим). Часто в дереве поиска содержатся два или более планов выполнения, стоимости которых очень близки. Поэтому в оптимизаторе реализуется иерархия правил разрешения конфликтов для сравнения двух правил, стоимость которых отличается не более чем на 10%. ИерархияИерархия (от др.-греч. , из «священный» и «правление»)— порядок подчинённости низших звеньев высшим, организация их в структуру типа дерево; принцип управления в централизованных структурах. Ситуативно подчиненность может возникать по горизонтальному принципу, это качество гибкости системы управления. правил выглядит следующим образом:

1. Выбор локального плана доступа, а не удаленного.
2. Выбор плана, в котором в качестве пути доступа используется индекс, если для каждого столбца ключа индекса специфицирован предикат сравнения по равенству.
3. Если имеются два плана, которые принадлежат типу, описанному в п.2, выбирается тот из них, который обеспечивает ключевой доступ к базовой таблице (таблица реализуется в ключевом-последовательном файле), а не альтернативный индексный путь доступа.
4. Выбор плана с более низкой индексной селективностью.
5. Выбор плана, в котором используется большее число предикатов на ключевых столбцах индекса.
6. Выбор плана, в котором используется индекс с UNIQUE.
7. При прочих равных условиях выбор плана, производящего прямой доступ к базовой таблице.

Содержание Вперёд