Русские документы
Ежедневные компьютерные новости RSS rusdoc.ru  Найти :
Новости
Последние поступления
Книжный магазин
  Hardware:
Видеоустройства
Системные платы
Процессоры
Мобильные устройства
Аудиосистема
Охлаждение системы
Накопители информации
КПК и ноутбуки
Телефоны и связь
Периферия
Система
Сети
Разные устройства
 
  Programming:
Web-разработка
Языки программирования
Технологии и теория
Разработка игр
Программная инженерия
 
  Software:
Операционные системы
Windows 7
Базы данных
Обзоры программ
Графика и дизайн
   
  Life:
Компьютерная жизнь
Разные материалы
   
Партнеры
Публикация
Правовая информация
Реклама на сайте
Обратная связь
Экспорт в RSS Экспорт в RSS2.0
    Читать в Яндекс.Ленте



Производительность SELECT-запросов

Раздел: Software / SQL @ 25.06.2008 | Ключевые слова: sql select производительность версия для печати

Источник: habrahabr

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

Я подумал-подумал, и решил написать о производительности выборок. Без понимания принципов работы СУБД трудно понять, где индексы обязательны, а где нет, в каком порядке перечислять поля в индексах, и важен ли порядок возрастания/убывания. Потому и возникают приложения, где выборки работают медленно, или базы, перегруженные ненужными индексами.

Здесь опубликована (условно говоря) первая часть статьи. Если сообществу тема покажется интересной, буду писать дальше.

Введение

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

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

В этой статье мы рассмотрим производительность запросов SELECT. Здесь не раскрываются особенности конкретных реализаций СУБД, но описывается фундамент, лежащий в основе любого SQL-сервера. Я надеюсь, что статья поможет начинающим SQL-программистам в нелёгком деле становления профессионального мастерства.

Задача

Я полагаю, что читатели знакомы с основными понятиями теории реляционных баз данных: записями, полями и таблицами. Необходимо и владение SQL, хотя бы на начальном уровне. Наконец, читателям требуется знание алгоритмов линейного и бинарного поиска; а, кроме того, таких структур данных, как массив, список и бинарное дерево.

Поскольку статья носит практический характер, мы будем часто обращаться к конкретным примерам, для чего нам потребуется простая таблица, скажем, такая, которая хранит запросы к HTTP-серверу (иными словами, лог HTTP-сервера):

CREATE TABLE HttpLog

(

  id INT NOT NULL                        — уникальный идентификатор записи

  time DATETIME NOT NULL,                — дата/время запроса

  ip CHAR(15) NOT NULL,                  — IP-адрес клиента

  method CHAR(8) DEFAULT ‘GET’ NOT NULL, — метод: GET, POST, PUT и т.д.

  uri VARCHAR(2048) NOT NULL,            — адрес страницы в виде /path/filename.ext

  size INT NOT NULL,                     — ответ сервера (размер в байтах)

  status INT NOT NULL                    — статус: 200, 302, 404, 501 и т.д.

)

Содержимое таблицы может быть, например, таким:

idtimeipmethodurisizestatus
1 2007-01-03 15:59:34 192.168.10.68 GET /images/name.gif 1254 404
2 2007-01-03 15:59:34 192.168.10.68 GET /images/combo.gif 743 200
3 2007-01-03 15:59:34 192.168.10.68 GET /images/harddrive.gif 947 200
4 2007-01-03 16:00:33 192.168.10.70 POST /index.php 6723 200
5 2007-01-03 16:01:52 192.168.10.70 GET /scripts/scripts.js 11743 200

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

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

SELECT SUM(size) FROM HttpLog WHERE MONTH(time) = 1 AND YEAR(time) = 2007

Здесь СУБД просуммирует приблизительно треть нашей таблицы, но вернёт всего одно число. Для определённости мы будем считать, что объём выборки соответствует количеству обработанных записей, то есть в данном случае приблизительно равен 3 миллионам.

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

Структуры данных и алгоритмы

Чтобы упростить изложение, давайте предположим, что все записи нашей таблицы помещаются в оперативную память. Каждая запись хранится в структуре (в терминах языка C), или в классе с открытыми полями (в терминах C++, Java, C#):

public class HttpLogRecord

{

  public int id;

  public DateTime time;

  public string ip;

  public string method;

  public string uri;

  public int size;

  public int status;

}

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

public class BinaryTreeNode

{

  public HttpLogRecord record;

  public BinaryTreeNode leftChild;

  public BinaryTreeNode rightChild;

}

Бинарное дерево позволяет эффективно осуществлять все основные операции с таблицей:

ОперацияСреднее время выполнения
Поиск записи по ключу O(logn)
Получение i-той записи O(n)
Определение минимума и максимума O(logn)
Вставка O(logn)
Удаление O(logn)
Сортировка O(m), где m — размер выборки

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

  • Очень дорогой оказывается операция получения записи по её порядковому номеру. Между тем, эта операция очень важна в веб-разработке (например, при постраничном выводе позволяет получить записи, скажем, с 150-й страницы, с порядковыми номерами от 3000 до 3019).
  • Бинарное дерево поддерживает только один порядок сортировки, определяемый первичным ключом. Если нам нужна выборка, упорядоченная по дате/времени, придётся осуществлять сортировку повторно, а быстродействие такой операции гораздо ниже.
  • Наконец, бинарное дерево может оказаться вырожденным. Такое происходит, если в таблицу вставляются уже упорядоченные данные. При тривиальной реализации дерево превратится в однонаправленный список (все левые дочерние узлы пусты, дерево растёт только по крайней правой ветке; или наоборот).
    Скорость операций поиска, вставки, удаления для вырожденного дерева составляет O(n), что очень медленно для больших таблиц.

Давайте посмотрим, как можно обойти эти недостатки.

Извлечение i-той записи

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

public class BinaryTreeNode

{

  public HttpLogRecord record;

  public int leftSubTreeSize;

  public BinaryTreeNode parent;

  public BinaryTreeNode leftChild;

  public BinaryTreeNode rightChild;

}

При вставке/удалении узла, мы должны пробежаться до корня (с помощью ссылки parent), и, поднимаясь из левого поддерева, увеличивать/уменьшать поле leftSubTreeSize. Эффективность такой операции составляет O(logn). Обратите внимание, что первой записью в бинарном дереве в данном случае является самый левый лист, а последней — самый правый.

Чтобы найти запись по порядковому номеру, необходимо немного изменить алгоритм бинарного поиска. Порядковый номер корневой записи точно равен leftSubTreeSize, так что мы сразу можем определить: в левом или правом поддереве находится нужная запись, и затем действовать рекурсивно. Производительность поиска i-той записи в данном случае составляет O(logn).

Обращаю ваше внимание, что с помощью этой техники мы можем не только быстро извлекать записи по порядковому номеру, но и определять порядковый номер записей за время O(logn).

Индексация

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

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

public class BinaryTreeNode

{

  public int recordIndex;

  public int leftSubTreeSize;

  public BinaryTreeNode parent;

  public BinaryTreeNode leftChild;

  public BinaryTreeNode rightChild;

}

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

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

Несколько интересных следствий:

  • Мы в любой момент можем создать новый индекс или восстановить повреждённый, поэтому СУБД позволяют переиндексировать таблицы, если цел массив записей. Создание индекса — ресурсоёмкая операция, фактически, это сортировка массива, и её эффективность равна O(n×logn).
  • Не смотря на то, что дополнительный уровень косвенности увеличивает накладные расходы, их эффективность составляет O(1), то есть не зависит от количества записей. Чтобы добиться такой производительности, после удаления записей массив не уплотняется, и в нём остаются пустые места. СУБД позволяют уплотнять таблицы, но поскольку производительность этой операции составляет O(n), уплотнение следует производить нечасто, и только во время минимальной нагрузки на SQL-сервер.
  • Размер узла в бинарном дереве небольшой, по сравнению с размером записи. Даже для нашей 10-тимиллионой таблицы, индекс можно держать в оперативной памяти полностью, что кардинально увеличит производительность. Именно поэтому СУБД так требовательны к оперативной памяти.
  • Один из индексов таблицы (как правило, самый используемый) объявляется первичным. С точки зрения реализации это ничего не означает, поэтому в некоторых СУБД объявление первичного индекса не обязательно.

Сбалансированные деревья

Если в бинарное дерево вставляются упорядоченные записи, дерево вырождается в список, и эффективность операций поиска ухудшается до O(n).

Для решения этой проблемы, после вставки и удаления узлов бинарное дерево перестраивается так, чтобы избежать вырождения. За подробностями я отсылаю читателей в Google (искать по ключевым словам «сбалансированные деревья», «AVL деревья», «красно-чёрные деревья»). Упрощённо можно считать, что записи в сбалансированном дереве распределены более-менее равномерно, и эффективность поиска всегда составляет O(logn).

Балансировка дерева требует накладных расходов, производительность которых равна O(logn).

Эффективность операций со сбалансированным деревом и быстрым поиском i-той записи приведена ниже:

ОперацияХудшее время выполнения
Поиск записи по ключу O(logn)
Получение i-той записи O(logn)
Определение минимума и максимума O(logn)
Вставка O(logn)
Удаление O(logn)
Сортировка O(m), где m — размер выборки

B-деревья (сильноветвящиеся деревья)

Наконец, мы обсудим вопрос хранения индекса на диске. Для решения этой задачи в СУБД используются B-деревья (би-деревья), которые в русскоязычной литературе называются также сильноветвящимися.

B-деревья используют те же принципы, что и сбалансированные, но в отличие от последних, они могут храниться на диске отдельными блоками. Подробнее с B-деревьями вы можете ознакомиться в разделе 6.2.4 многотомника Д. Кнута («Искусство программирования», том III), либо через Google.

С точки зрения принципов работы СУБД, B-деревья не привносят ничего нового, однако заинтересованному читателю будет полезно разобраться с этой структурой данных.

Производительность простых выборок

Поиск записи по ключу

Рассмотрим извлечение одной записи из таблицы HttpLog по её идентификатору:

SELECT * FROM HttpLog WHERE id = @id

Если в таблице предусмотрен индекс по полю id, эффективность поиска составит O(logn), в противном случае — O(n).

Поиск записей по двум ключам:

SELECT * FROM HttpLog WHERE status = 404 and ip = @ip

Составной индекс по полями [status, ip] или [ip, status] позволит найти нужную запись за время O(logn).

Рекомендация: если вы ищете в таблице записи с конкретными значениями полей, создавайте индекс по этим полям. Порядок следования полей в индексе значения не имеет.

Выборка записей по диапазону ключей

Извлечём из лога HTTP-сервера все записи со статусом 4xx (ошибка):

SELECT * FROM HttpLog WHERE status >= 400 AND status <= 499

В данном случае, SQL-сервер, пользуясь индексом по полю status, может определить диапазон узлов в бинарном дереве, удовлетворяющих условию. Если индекс построен по возрастанию поля status, то при обходе дерева слева направо SQL-сервер извлечёт все требуемые записи из таблицы. Если же индекс построен по убыванию, SQL-сервер сможет обойти дерево справа налево.

Поиск первой и последней записи требует времени O(logn). Однако реальная эффективность запроса зависит от размера выборки, и составляет O(m), где m — количество записей, удовлетворяющих условию.

К сожалению, в нашем конкретном случае количество записей может оказаться очень большим (несколько сотен тысяч). Для того, чтобы справиться с этой проблемой, мы могли бы показывать записи постранично (в данном запросе используется синтаксис MySQL):

SELECT * FROM HttpLog WHERE status >= 400 AND status <= 499 LIMIT @startIndex, @pageSize

SQL-сервер, может найти запись с порядковым номером @startIndex за время O(logn). Размер выборки составит @pageSize (как правило, не больше ста). Таким образом, скорость выполнения запроса может вырасти в 1000 раз.

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

Количество записей

Попробуем узнать, сколько всего запросов вызвали ошибку 4xx:

SELECT COUNT(*) FROM HttpLog WHERE status >= 400 AND status <= 499

SQL-сервер может определить порядковые номера первой записи и последней записи диапазона за время O(logn). Вычтя первое число из второго, он получит количество записей в диапазоне.

Рекомендации: при наличии индекса, выполнение операции COUNT становится очень быстрым.

Сортировка

Предположим, мы хотим получить список всех запросов за день, отсортированный по возрастанию даты/времени запроса:

SELECT * FROM HttpLog WHERE DATE(time) = ‘2007-01-03’ ORDER BY time ASC

При наличии индекса время выполнения запроса составит O(logn + m), не зависимо от возрастания/убывания поля time в индексе. Границы диапазона будут найдены за время O(logn), и затем SQL-сервер, обойдя дерево слева направо (или справа налево), выберет все записи внутри диапазона. Обратите внимание, что эти записи будут упорядочены.

При отсутствии индекса, SQL-серверу потребуется O(n) операций, для того, чтобы выбрать m записей, и затем ещё O(m×logm) операций, чтобы их упорядочить. Суммарное время выполнения запроса составит O(n + m×logm). Очевидно, что если мы используем упорядоченные выборки, нам необходимо создать соответствующие индексы (не важно, по возрастанию или убыванию).

Давайте рассмотрим похожий пример: выберем все записи со статусом 404 и упорядочим их по возрастанию даты/времени:

SELECT * FROM HttpLog WHERE status = 404 ORDER BY time ASC

Индекс по полям [time, status] нас в данном случае не спасёт, поскольку сервер будет проверять все значения time, которых может оказаться много. А вот индекс [status, time] позволит сразу найти границы диапазона, где status = 404, внутри которого записи будут упорядочены по полю time. Порядок возрастания/убывания в данном случае не важен.

Точное совпадение порядка ключей в индексе и клаузе ORDER BY требуется и в таких запросах:

SELECT * FROM HttpLog ORDER BY ip ASC, status DESC

Теоретически, порядок в данном случае может оказаться некритичным, но лучше предоставить серверу возможность выбирать записи подряд, то есть создать индекс [ip ASC, status DESC]. Похожий запрос:

SELECT * FROM HttpLog WHERE size < 100 ORDER BY ip ASC, status DESC

требует индекса [ip ASC, status DESC, size], а не [size, ip ASC, status DESC], как могло бы показаться на первый взгляд. При этом порядок возрастания/убывания для поля size не важен.

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

Вопросы читателям:

  • Интересна ли статья, актуальна? Имеет ли смысл писать дальше?
  • Сложная/не сложная? Нужно ли более подробно описывать, что, как и почему?
  • Не перегружена ли деталями?
  • Всё ли нормально с подачей материала, не возникает ли ощущение, что автор скачет с темы на тему?

Ну и в целом, интересуют любые отзывы.

Это интересно:








версия для печатиРаспечатать статью


Вернуться в раздел: Software / SQL


Реклама:
Читать наc на:

Add to Google
Читать в Яндекс.Ленте






Rambler's Top100
© Copyright 1998-2012 Александр Томов. All rights reserved.