NonStop SQL

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 12:47, 26 ноября 2017.
NonStop SQL
Nonstop-sql-beyond.jpg
Создатели: Tandem Computers до 1997
Разработчики: Hewlett-Packard
Выпущена: 1987
Состояние разработки: Активно
Написана на: C и C++
Операционная система: NonStop OS
Веб-сайт www.hpe.com/ru/ru/servers/nonstop.html

NonStop SQL - это коммерческая система управления реляционными базами данных, предназначенная для отказоустойчивости и масштабируемости, которая в настоящее время продается Hewlett Packard. Последней версией продукта является SQL / MX 3.4.

Первоначально продукт был разработан Tandem Computers. Tandem был приобретен Compaq в 1997 году. Compaq позднее был приобретен Hewlett Packard в 2002 году.

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

История

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

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

Вторая версия добавила / MP к имени, для Massively Parallel. Третья версия NonStop SQL / MX была попыткой Tandem Computers создать продукт, который был более совместим с SQL ANSI, чем его предшественник, чтобы участвовать в конкурсе с другими поставщиками, такими как Oracle. Система была разработана в середине 1990-х годов для операционной системы Microsoft Windows NT, но продукт никогда не появлялся на NT, и основное внимание было перенаправлено на разработку на платформе NonStop. NonStop SQL / MX поставляется с платформой NonStop с 2002 года и может обращаться к таблицам, которые были созданы NonStop SQL / MP, хотя только «Native SQL / MX tables» предлагают соответствие ANSI и многие «похожие на Oracle» усовершенствования. Платформа бизнес-аналитики HP Neoview была построена с использованием NonStop SQL в качестве источника. NonStop SQL / MX по-прежнему процветает сегодня и является единственным продуктом базы данных OLTP, которым владеет HP.

Часть кодовой базы Neoview была открыта в 2014 году под названием Trafodion, которая сейчас находится в инкубации в качестве проекта Apache.

Принцип работы

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

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

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

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

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

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

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

Структура SQL приложения

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

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

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

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

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

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

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

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

  1. Рассматриваются только праволинейные деревья соединений. Это означает, что соединение четырех таблиц (ABCD) может быть реализовано как (((AB) C)D) или (((AC) B)D), но не как ((AB)(CD)).
  2. Рассматриваются три метода соединения, а именно, вложенные циклы, хэширование и сортировка со слиянием.
  3. Новая таблица может быть соединена с существующей композитной (соединенной) таблицей, если либо существует предикат эквисоединения, связывающий композитную и новую таблицы, либо ни для одной из оставшихся таблиц нет предиката эквисоединения, связывающего их с композитом.
  4. На каждом шаге к дереву поиска добавляется только один план, производящий декартово произведение. К дереву поиска добавляется наименьшая таблица, которая еще не принадлежит композиту, и для которой отсутствует предикат эквисоединения, связывающий ее с композитом. Этот план позволяет оптимизировать некоторые запросы (звездообразные запросы), которые выполняются наилучшим образом, если декартово произведение наименьших таблиц формируется раньше соединения результата с более крупными таблицами.

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

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

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

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

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

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

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

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

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

Дисковый процесс

Дисковый процесс обеспечивает однотабличный, ориентированный на множества доступ к таблицам.[Источник 5] Множество определяется путем задания выражения ограничения и списка атрибутов для проецирования. В запросе (сообщении) от файловой системы данные, подлежащие выборке, описываются в терминах множества (т.е. начальный и конечный ключи, выражение ограничения и атрибуты для проецирования). В ответ дисковый процесс может выдать один или более буферов с данными, соответствующими спецификации множества.

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

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

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

Таблица или индекс могут быть горизонтально разделены путем указания диапазонов ключа каждого раздела. Разделенная таблица выглядит как одна таблица, файловая система перенаправляет любые SQL-запросы SELECT, INSERT, DELETE и UPDATE в нужный раздел в зависимости от диапазона ключа, указанного в операторе.

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

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

Сортировка может выполняться либо для устранения дублирующих значений, либо для упорядочивания данных. Оптимизатор рассматривает SELECT DISTINCT, агрегатную функцию, содержащую DISTINCT, раздел GROUP BY и раздел ORDER BY как запросы сортировки данных. Поскольку сортировка является одной из наиболее трудоемких операций при выполнении запроса, оптимизатор комбинирует сортировки при возникновении следующих условий:

  1. список выборки оператора SELECT DISTINCT является подмножеством списка столбцов упорядочивания раздела ORDER BY или списка столбцов группировки раздела GROUP BY;
  2. столбцы группировки раздела GROUP BY образуют подмножество столбцов упорядочивания раздела ORDER BY; столбцы группировки образуют префикс столбцов упорядочивания;
  3. столбцы упорядочивания раздела ORDER BY образуют подмножество списка выборки оператора SELECT DISTINCT или столбцов группировки раздела GROUP BY.

Кроме того, оптимизатор устраняет сортировку, когда можно использовать индекс, в следующих случаях:

  • Индекс обеспечивает порядок данных, требуемый разделами GROUP BY или ORDER BY.
  • Столбцы группировки или весь список выборки SELECT DISTINCT образуют префикс ключа уникального индекса.

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

Во множестве прототипных реализаций и академических статей было показано, что алгоритмы соединений на основе хэширования[Источник 6][Источник 7] являются предпочтительными при наличии достаточного объема основной памяти и отсутствии индекса, органичивающего число проб на внутренней таблице. Обычно достаточным размером памяти считается квадрат размера внутренней таблицы (в блоках).

Для использование премуществ большого объема основной памяти, распространенной в современных системах, в NonStop SQL поддерживаются алгоритмы соединения на основе хэширования вдобавок к традиционным алгоритмам вложенных циклов и сортировки со слиянием. Используемый в NonStop SQL адаптивный алгоритм соединения на основе хэширования (Adaptive Hash Join algorithm)[Источник 8] является разовидностью хорошо известного гибридного алгоритма соединения с использованием хэширования (Hybrid Hash Join), разработанного в проекте параллельной машины баз данных GAMMA в University of Wisconsin .

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

  • оценку размера входных отношений и
  • оценку объема памяти, доступной для соединения.

Эти оценки используются для определения стоимости различных алгоритмов соединения. Выбирается алоритм с наименьшей стоимостью. Соединения методами вложенных циклов и сортировки со слиянием не испытывают деградации эффективности, если реальные значения размеров входных отношений и размера памяти отличаются от оценок оптимизатора. Это связано с тем, что их планы выполнения не зависят от размера таблиц и доступной памяти. Однако для выполнения соединения хэшированием некоторые параметры, такие как число хэш-классов и объем информации, поддерживаемой в основной памяти, являются предопределенными. Изменение условий среды может вызвать деградацию производительности или даже отказ выполнения соединения. В адаптивном алгоритме соединения с хэшированием используется несколько методов, делающих его более надежным и производительным в большом диапазоне размеров основной памяти:

  1. обмены с дисками порциями переменного размера;
  2. динамический своппинг частей хэш-таблицы в дисковые файлы;
  3. алгоритм «hash loop» для случаев предельного переполнения.

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

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

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

Для внесения параллелизма в реляционные операции в систему внедрен компонент, называемый серверным процессом-исполнителем (Executor Server Process, ESP). Таким образом, между приложением (master executor) и процессами ESP имеется отношение «главный-подчиненный» («master-slave»). Каждый ESP состоит из небольшой основной программы и файловой системы. Исполнитель приложения взаимодействует с серверными исполнителями через сообщения.

В этой архитектуре допускается широкое разнообразие параллельных планов выполнения, в которых для запросов над одной таблицей параллелизм может обеспечиваться файловой системой, а для всех типов реляционных операций – исполнителем. Файловая система всегда производит доступ к разделенным таблицам последовательно. ESP используются для параллельного выполнения операторов SQL SELECT, INSERT, DELETE и UPDATE над разделенными файлами. Однако, если у таблицы имеются индексы, размещенные на разных дисках, то обновление записи базовой таблицы и соответствующих индексных данных производится параллельно файловой системой. Поскольку стоимость запуска ESP может быть значительной, эти процессы разделяются между операторами SQL и остаются существовать вне границ транзакций.

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

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

Если операнд агреатных функций MIN или MAX является столбцом, входящим в ключ индекса, и запрос содержит предикаты сравнения по равенству на других столбцах ключа, предшествующих данному, то NonStop SQL вычисляет агрегат, позиционируясь на первую или последнюю запись заданного диапазона ключа для индекса. Соответствующие строки всегда содержит минимальное и максимальное значение соответственно для этого столбца индекса. Исполнитель просто читает первую строку, возвращаемую файловой системой, и возвращает приложению MIN или MAX.

Как описывалось в разд. 3, NonStop SQL также выполняет группировку и агрегацию в параллель. Этим методом для заданного запроса могут быть вычислены любые агрегатные функции SQL. Оптимизатор автоматически выбирается эту стратегию для запросов с единственной переменной, а также в тех случаях, когда агрегатная функция ссылается на наиболее внутреннюю таблицу последовательности соединений. Эта оптимизация сокращает число сообщений, которыми обменивается файловая система SQL с дисковым процессом, а также снижает сетевой трафик. Она также используется для группировки, если строки читаемые с диска, находятся в порядке группировки, т.е. если столбцы группировки образуют префикс ключа индекса.

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

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

Источники

  1. The Tandem Database Group, NonStop SQL:A Distributed, High-performance, High-availability Implementation of SQL, 2nd Int. Workshop on High Performance Transaction Systems, Springer Lecture Notes in Computer Science No. 359.
  2. The Tandem Database Group, NonStop SQL:A Distributed, High-performance, High-availability Relational DBMS, First Annual Distributed Database Event, The Relational Institute
  3. P. Selinger et. al., Access Path Selection in a Relational Database Management System, ACM SIGMOD Conference 1979, С. 23-34.
  4. Mike Pong, NonStop SQL Optimizer: Query Optimization and User Influence, Tandem Systems Review 4,2 (1988), С. 22-38.
  5. A. Borr, F. Putzolu, High Performance SQL Through Low-level System Integration, ACM SIGMOD 1988, С. 342-349.
  6. D. DeWitt, R. Gerber, Multiprocessor Hash-based Join Algorithms, 1985 VLDB, С. 151-164.
  7. D. Schneider, D. DeWitt, A Performance Evaluation of Four Parallel Join Algorithms in a Sharednothing Multiprocessor Environment, ACM SIGMOD 1989, С. 110-121.
  8. H. Zeller, J. Gray, An Adaptive Hash Join Algorithm for Multiuser Environments, 16. VLDB, 1990, С. 186-197.

Ссылки