Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

VPS в России, Европе и США

Бесплатная поддержка и администрирование

Оплата российскими и международными картами

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

1999 г

Обзор методов оптимизации запросов в реляционных системах

Сураджит Чаудхари

Перевод: Сергей Кузнецов

Предыдущий раздел - Содержание - Следующий раздел

2. Введение

Реляционные языки запросов обеспечивают высокоуровневый "декларативный" интерфейс для доступа к данным, хранимым в реляционных базах данных. Со временем появился язык SQL [41] как стандарт реляционных языков запросов. Двумя ключевыми подкомпонентами компонента вычисления запросов в SQL-ориентированной системе баз данных являются оптимизатор запросов и подсистема выполнения запросов.

Подсистема выполнения запросов реализует набор физических операций. На вход каждой операции поступают один или несколько потоков данных, и на выходе формируется поток данных. Примерами физических операций являются сортировка (внешняя), последовательное сканирование, индексное сканирование, соединение методом вложенных циклов и соединение сортировкой и слиянием. Я называю эти операции физическими, поскольку они не обязательно связаны один к одному с реляционными операциями. Проще всего представлять физические операции как куски кода, которые используются в качестве строительных блоков для обеспечения возможности выполнения SQL-запросов. Абстрактным представлением такого выполнения является дерево физических операций, пример которого показан на рис. 1. Дуги в дереве операций представляют потоки данных между операциями. Мы используем термины "дерево физических операций" и "план выполнения" (или просто план) в одном и том же смысле. Подсистема выполнения отвечает за выполнение плана, что приводит к формированию ответов на запросы. Следовательно, возможности подсистемы выполнения запросов определяют структуру допустимых деревьев операций. В [21] читатель может найти обзор методов вычисления запросов.

Дерево операций
Рис. 1. Дерево операций

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

  • Алгебраическое представление данного запроса может быть преобразовано во многие другие логически эквивалентные алгебраические представления; например,
    Join (Join (A,B),C) = Join (Join (B,C),A)
  • Для данного алгебраического представления может существовать много деревьев операций, реализующих алгебраическое выражение; например, в системе баз данных обычно поддерживается несколько алгоритмов соединения.

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

  • Пространство планов (пространство поиска).
  • Метод оценки стоимости, чтобы можно было оценить каждый план в каждом пространстве поиска. Интуитивно, это оценка ресурсов, требуемых для выполнения плана.
  • Алгоритм перебора, который может осуществлять поиск в пространстве планов выполнения.

Желаемым оптимизатором является такой, в котором

(1) пространство поиска включает планы с низкой стоимостью;
(2) метод оценок является точным;
(3) алгоритм перебора эффективен.

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

Мы начинаем с обсуждения подхода к оптимизации в System R, поскольку это был необыкновенно элегантный подход, который питал многие последующие работы в области оптимизации. В разделе 4 мы обсудим, что представляет собой пространство поиска, анализируемое оптимизатором. В этом разделе представлены алгебраические преобразования, включаемые в пространство поиска. Раздел 5 посвящается проблеме оценки стоимости. В разделе 6 мы обсуждаем тему перебора пространства поиска. Это завершает обсуждение базовых основ оптимизации. В разделе 7 мы обсудим некоторые современные разработки в области оптимизации запросов.

Предыдущий раздел - Содержание - Следующий раздел

 

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...