Индексы в MySQL
Вы здесь: Главная — MySQL — MySQL Основы — Индексы в MySQL
В предыдущих статьях я часто упоминал про индексы в MySQL. и я обещал, что скоро о них расскажу. Так вот, это время пришло, и сегодня Вы узнаете об индексах MySQL, об их назначении и о том, как их создавать.
Индексы используются для ускорения выборки данных из таблиц базы данных. По сути дела, индекс в MySQL — это сортировка определённого поля в таблице. То есть если поле сделать индексом, то вся таблица будет отсортирована по этому полю. Почему это выгодно?
Допустим, в нашей таблице находится 1000000 записей. У каждой записи есть уникальный идентификатор ID. И, допустим, нам надо вытащить записть с ID = 530124. Если нет индекса, то MySQL будет поочерёдно перебирать все записи в таблице, пока не найдёт нужную. В худшем случае, он будет вынужден перебрать
Однако, индексы обладают одним существенным изъяном, который не позволяет делать индексом каждое поле таблицы. Фактически, индекс — это ещё одна таблица, но просто с отсортированным соответствующим полем. То есть, делая индекс одного поля, Вы создаёте ещё одну точно такую же таблицу, которая будет занимать дополнительное место на диске.
Ещё один небольшой минус индексов в MySQL заключается в том, что запросы на вставку новых записей заставляют проводить сортировку таблицы заново. В результате, вставка новых записей будет происходить несколько дольше обычного. Но не забывайте, что в большиинстве случаев делать это приходится гораздо реже, чем делать выборку, поэтому данный минус не существенен.
Как сделать индекс в MySQL?
Для первичных ключей (PRIMARY KEY) индекс создаётся автоматически, а вот для других полей последовательность действий в PHPMyAdmin следующая:
- Зайти на главную страницу PHPMyAdmin.
- Выбрать из выпадающего списка имя базы данных, где находится требуемая таблица.
- Кликнуть по имени таблицы, в которую Вы хотите создать индекс.
- Щёлкнуть на значок «Молнии» напротив того поля, для которого Вы хотите создать индекс.
И, напоследок, хочется сделать небольшое резюме, чтобы Вы поняли: «Когда надо создавать индексы MySQL«:
- Если по полю очень часто идёт выборка, то его надо делать индексом.
- Если в таблицу очень часто добавляются записи, и при этом выборка происходит редко (такое иногда бывает), то индексы делать не надо.
И ещё кое-что. Если вдруг Вы видите, что Ваши запросы на выборку очень сильно тормозят, то проанализируйте причину этого. Скорее всего, надо просто добавить индекс. В общем, тестируйте, и всё станет понятно.
-
-
Михаил Русаков
Михаил РусаковКопирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!
Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.
Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления
Если у Вас остались какие-либо вопросы, либо у Вас есть желание высказаться по поводу этой статьи, то Вы можете оставить свой комментарий внизу страницы.
Порекомендуйте эту статью друзьям:
Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):
-
Кнопка:
<a href=»https://myrusakov.ru» target=»_blank»><img src=»https://myrusakov.ru/images/button.gif» alt=»Как создать свой сайт» /></a>Она выглядит вот так:
-
Текстовая ссылка:
<a href=»https://myrusakov.ru» target=»_blank»>Как создать свой сайт</a>Она выглядит вот так: Как создать свой сайт
- BB-код ссылки для форумов (например, можете поставить её в подписи):
[URL=»https://myrusakov.ru»]Как создать свой сайт[/URL]
myrusakov.ru
Кластерные и «обычные» индексы MySQL (InnoDB) / Habr
Все мы помним хрестоматийное объяснение «что такое индексы в БД и как они облегчают задачи поиска нужных строк». Уверен, у большинства из вас перед глазами встаёт нечто подобное:И сразу становится очевидно, насколько меньше данных нужно перелопатить для поиска двух-трёх нужных строк. Гениально. Просто. Понятно.
И лично мне всегда казалось, что улучшать эту схему некуда… Пока я не познакомился с кластерными индексами. Оказалось, что всё не так уж радужно с «обычными» индексами.
Итак, что же такое кластерный индекс, чем он лучше некластерного, и как с ним обстоит дело у MySQL.
Некластерные индексы
Чтобы не запутаться, до поры до времени будем рассматривать простой индекс по одному полю. Упрощённо некластерный индекс можно представить как отдельную таблицу, каждая строка в которой ссылается на одну или несколько строк в таблице с данными. Строки в индексной таблице упорядочены и сгруппированы по значениям ключевых полей. Представим элементарный запрос:
SELECT * FROM `t1` WHERE `fld1` = 12;Совсем без индексации будет прочитана и проверена каждая строка, и неудовлетворяющие условию строки просто не попадут в результат. Но прочитаны они будут.
При использовании «обычного», некластерного индекса, задача поиска сильно ускоряется. Во-первых, индексная таблица весит много меньше таблицы с данными, а значит элементарно может быть прочитана быстрее. Во-вторых, СУБД чаще всего стараются кешировать индексы в оперативную память, которая сама по себе много шустрее жёсткого диска*. В-третьих, в индексах отсутствуют дублирующиеся строки. А значит, как только мы нашли первое значение, поиск можно прекращать — оно же и последнее. В-четвёртых, данные в индексе отсортированы. А в-третьих и в-четвёртых вместе позволяют использовать алгоритм бинарного поиска (он же метод деления пополам), эффективность которого многократно превосходит простой перебор.
* Если ресурсы позволяют, таблицу данных тоже можно (и нужно) кешировать в оперативную память. Однако индексам и месту для них в оперативной памяти, по понятным причинам, принято уделять больше внимания.
Индексация — великая сила. Но если представить все указатели индексной таблицы на строки в таблице данных ОДНОВРЕМЕННО, получится достаточно сложная «паутина»:
И эта паутина, со множеством пересекающихся стрелок, подводит нас к проблеме (просто таки наглядно её демонстрирует), которую создаёт некластерный индекс.
Фрагментация
Оптимизатор MySQL может принять решение вообще не использовать индексы для поиска по небольшим таблицам (до пары десятков записей — зависит от конкретной структуры данных и индекса). Почему? Потому что поиск простым перебором читает данные последовательно. А указатель в индексе ссылается на разрозненные участки данных. И прыжки по ссылкам из индекса в конечном итоге могут стоить дороже полного перебора.
Итак, что мы имеем на данном этапе эволюции индексирования. Представьте большую, фрагментированную с точки зрения индексации, таблицу. Как данные приходили хаотичными и неотсортированными, так они и сохранялись. Теперь представьте индексную таблицу к ней. И наш старый добрый запрос:
SELECT * FROM `t1` WHERE `fld1` = 12;Что происходит? Находится значение в индексе — это быстро и просто — и из таблицы данных читаются строки, на которые этот индекс ссылается. Естественно, при большой фрагментированности таблицы накладные расходы на чтение из разных её частей становятся ощутимыми.
И вот тут-то нам и пригодятся…
Кластерные индексы
Кластерные индексы отличаются от некластерных точно так же, как оглавление книги отличается от алфавитного указателя. Алфавитный указатель (некластерный индекс) для точного слова (значения) даёт точные номера страниц (строки в БД). Оглавление же указывает диапазон страниц, соответствующих определённой главе, в которой уже найдётся искомое слово. Причём каждая глава, если она достаточно велика, может содержать собственное оглавление.
Кластерный индекс — это древовидная структура данных, при которой значения индекса хранятся вместе с данными, им соответствующими. И индексы, и данные при такой организации упорядочены. При добавлении новой строки в таблицу, она дописывается не в конец файла*, не в конец плоского списка, а в нужную ветку древовидной структуры, соответствующую ей по сортировке.
* В разных движках и при разных настройках это может быть вовсе и не конец, и вовсе и не файла. Слово файл здесь означает «некую единицу измерения данных, соответствующую одной таблице», а «конец файла» употребляется как символ последовательной, линейной записи.
Один из самых мощных и производительных движков для MySQL — InnoDB. Тому много причин, и одна из них — кластерные индексы. Проще всего понять как устроены кластерные индексы, если представить их в динамике: как они разрастаются по мере добавления данных, и как начинает ветвиться таблица.
Первый этап: плоский список
Данные в InnoDB хранятся страницами по 16 Кб. Размер одной страницы — это предельный размер узла нашей древовидной структуры, от которого зависит в какой момент начнётся ветвление. Если вся таблица помещается в одну страницу, то она хранится в виде плоского списка, отсортированного по ключевому полю, без отдельной индексной таблицы.
Точно такими же маленькими табличками в будущем будут представлены все наши данные, а соединять их в дерево будут цепочки индексных страниц.
Второй этап: дерево
Когда данные перестают помещаться в одну страницу, список превращается в дерево. Страница с данными разделяется на две, причём в том узле (на той странице), где раньше были данные, теперь располагается индекс, охватывающий обе новые страницы. Конкретный узел такого дерева обязан включать в себя индексы всех дочерних узлов или конечные данные, если узел последний. Узлы могут ссылаться друг на друга только в одном направлении: от родителя к потомку.
По мере добавления всё новых и новых данных, дерево будет усложняться и углубляться. И чем больше оно будет и ветвистее, тем больший выйгрышь даст такая схема хранения данны.
Серые страницы идентичны странице первого этапа — это просто отсортированные данные, листья (конечные узлы) нашего дерева. Голубые страницы — это промежуточные узлы дерева, содержащие только индекс и не содержащие данных. Стрелками помечены пути поиска определённых значений ключа.
Вспомним наш запрос (зелёная стрелка):
SELECT * FROM `t1` WHERE `fld1` = 12;Обращаясь к таблице, запрос попадает на первую страницу и получает индекс, тут же отправляющий его на конечную страницу с данными, где находятся строки, удовлетворяющие критериям поиска. Страница уже прочитана на этапе поиска, все данные собраны, БД может вернуть ответ.
Однако индекс, указывающий на другую страницу, не обязательно ведёт сразу на страницу с данными. Индекс может указывать на страницу с промежуточным индексом. Возможно, при больших объёмах таблицы, БД придётся провести больше итераций поиска, но каждая такая итерация включает минимальный объём данных, а потому в целом всё равно поиск проходит быстрее.
Здесь действует простое правило, актуальное для любого типа индекса: чем разнообразнее данные, тем эффективнее использовать индекс для поиска конкретных значений.
Поскольку данные являются частью индекса, отсортированы и целенаправленно фрагментированы, очевидно что для одной таблицы может использоваться только один кластерный ключ. Из такой, достаточно сложной логики хранения индексов и данных, есть ещё одно важное следствие: операции записи, а особенно изменение имеющихся данных ключевых полей — крайне ресурсоёмкий процесс. Старайтесь использовать для кластерных индексов редко изменяемые поля.
Что касается сложных (составных) кластерных ключей, для них действует абсолютно такая же схема, только сортировка данных осуществляется по двум полям. Сам же индекс мало отличается от некластерного составного ключа.
Кластерные ключи в InnoDB
Здесь всё просто. Каждая таблица InnoDB имеет кластерный ключ. Каждая. Без исключения.
Гораздо интереснее, какие поля для этого выбираются.
- Если в таблице задан PRIMARY KEY — это он
- Иначе, если в таблице есть UNIQUE (уникальные) индексы — это первый из них
- Иначе InnoDB самостоятельно создаёт скрытое поле с суррогатным ID размером в 6 байт
До третьего пункта лучше не доводить свой многострадальный сервер, и добавить таки ID самостоятельно.
И не забывайте, что InnoDB во вторичных ключах хранит полный набор значений полей кластерного ключа в качестве ссылки на конечную строку в таблице. Чем больше первичный ключ, тем больше вторичные ключи.
habr.com
Выбор и использование индексов MySQL
Первичный индекс
При построении первичного индекса необходимо учитывать несколько факторов:
INT+AUTO_INCREMENT— лучший выбориспользовать строки — плохо, много места и долгая обработка
MyISAMпакует индексы — еще медленнее для строк (до 6 раз)InnoDBвключает первичный индекс во вторичные — дополнительное местов
InnoDBпервичный ключ — кластерный индекс по умолчаниюСлучайные строки (
MD5,SHA1) — медленные выборки и вставка (соседние записи не являются соседними в индексе)Хранение
UUID— удалить тире, еще лучше преобразовать вUNHEX()
Виды индексов
Поиск элемента в хорошей хэш-таблице занимает О(1).
В хорошо сбалансированном дереве — O(log(n)).
В массиве — O(n).
Наилучшие алгоритмы сортировки имеют сложность O(n*log(n)).
Плохие алгоритмы сортировки — O(n2).
https://habrahabr.ru/company/mailru/blog/266811/
B-TREE
Возможности
B-TREE — основной используемый типа индекса. Поиск может выполняться:
по полному значению
по левостороннему префиксу, по первой колонке индекса
по интервалу значений (range), только для первой колонки
по фиксированному значению первой колонки (или нескольких) и интервалу на последующую
Также эти индексы используются при сортировке, а также работаю как покрывающие индексы (то есть из них можно получиться значение, не обращаясь к таблице).
Ограничения
Для B-TREE индексов существуют и ограничения:
нельзя искать по суффиксу (имена, оканчивающиеся на определенную букву)
нельзя пропустить колонку в индексе
не учитываются колонки справа от сравнения с интервалом (
date_of_birth):
WHERE last_name="Smith" AND
first_name LIKE 'J%' AND
date_of_birth = '1976-12-23'IN (v1,v2,v3)тоже считается интервалом (range), но после него учитываются.
HASH
Особенности
Основное преимущество — очень быстрый поиск по полному значению индекса, но масса ограничений:
нельзя использовать для покрывающих индексов
нельзя использовать для поиска по префиксу
нельзя использовать для сортировки
не может использовать в выражениях
<,>, только в=,IN,<>не эффективен при частых коллизиях
Эмуляция через B-TREE
Предположим, у нас есть большой и медленный индекс по url:
SELECT id FROM url WHERE url="http://www.mysql.com";
Можно построить быстрый индекс по url_crc, индекса по url нет:
SELECT id FROM url WHERE url='http://www.mysql.com'
AND url_crc=CRC32('http://www.mysql.com'); Выборка ведется по url для разрешения коллизий.
Заполнение url_crc — триггер или слой модели. Внимательно выбираем хэш-функцию, SHA1, MD5 — слишком сложные и длинные.
- crc32-trigger.sql
DELIMITER $$ CREATE TRIGGER `url_crc_fill` BEFORE INSERT ON `url` FOR EACH ROW BEGIN SET NEW.url_crc = CRC32(NEW.url); END $$ DELIMITER ;
Еще один пример для точного поиска по адресу:
DROP TRIGGET IF EXISTS `address_crc_fill_insert`;
DROP TRIGGET IF EXISTS `address_crc_fill_update`;
DELIMITER $$
CREATE TRIGGER `address_crc_fill_insert` BEFORE INSERT ON `MarketNavigator`
FOR EACH ROW BEGIN
SET NEW.FullAddressCRC = CRC32(NEW.FullAddress);
END $$
CREATE TRIGGER `address_crc_fill_update` BEFORE UPDATE ON `MarketNavigator`
FOR EACH ROW BEGIN
IF NEW.FullAddress <> OLD.FullAddress THEN
SET NEW.FullAddressCRC = CRC32(NEW.FullAddress);
END IF;
END $$
DELIMITER ;Использование индексов
Принцип изолирования колонок
Индекс не используется, если колонка внутри выражения или вызова функции:
SELECT actor_id FROM actor WHERE actor_id + 1 = 5; SELECT ... WHERE TO_DAYS(CURRENT_DATE) * TO_DAYS(date_col) <= 10;
Часто можно переписать запрос с учетом принципа изолирования колонок, тогда индексы используются:
SELECT actor_id FROM actor WHERE actor_id = 4; SELECT ... WHERE date_col >= DATE_SUB(CURRENT_DATE, INTERVAL 10 DAY);
Префиксные индексы и селективность
Для длинных строк часто имеет смысл строить индекс по префиксу строки (а не по полному значению), уменьшая место и ускоряя обработку.
При этом важно не забывать о селективности:
selectivity = cardinality / общее количество значений cardinality - количество различных значений
Длина префикса — компромисс между хорошей селективностью и занимаемым местом.
По реальным данным считаем селективность для различных длин префиксов, выбираем оптимальную.
Кластеризованный индекс
Определяет физический порядок записей. В случае InnoDB это единая структура для хранения и индекса, и данных. В качестве кластеризованного индекса выбираются:
1. первичный ключ 2. первый уникальный ключ, если нет первичного 3. суррогатный первичный ключ в порядке добавления записей, если нет уникальных ключей
Все прочие созданные индексы ссылаются не на записи, а на значения кластеризованного индекса, это важная особенность InnoDB.
Преимущества
очень быстрая выборка по первичному ключу
эффективный поиск по интервалу первичного ключа
быстрая сортировка по первичному ключу
покрывающие индексы автоматически используют первичный ключ
быстрая вставка в порядке сортировки первичного ключа
Недостатки
вторичные индексы занимают больше места
при поиске по вторичному ключу выполняется дополнительный просмотр по первичному
при обновлении первичного ключа — перемещение строки
медленная вставка, если порядок не совпадает с сортировкой первичного ключа
Как правило, достоинства перевешивают недостатки.
Покрывающие (covering) индексы
MySQL может брать данные из индекса, не обращаясь к записи, в результате получаем значительное увеличение производительности:
меньше обрабатываемых данных
быстрее навигация по записям
лучшее кеширование
для InnoDB — нет дополнительного поиска по первичному ключу
CREATE INDEX store_film ON inventory(store_id, film_id, name); SELECT store_id, film_id FROM inventory WHERE store_id = 1; SELECT store_id, film_id FROM inventory WHERE store_id = 1 AND name LIKE 'Secret%';
Существуют ограничения:
работает только для
B-TREEиндексоввсе запрашиваемые колонки должны быть в индексе
условие
LIKE— только по префиксу (pattern%)
Например, в приведенном ниже запросе покрывающий индекс не используется: поле price не в индексе, LIKE не по префиксу:
SELECT store_id, film_id, price
FROM store_film
WHERE store_id = 1 AND
name LIKE '%mission%';Дублирующиеся и избыточные индексы
Дублирующиеся (dublicate) индексы — индексы по одним и тем же колонкам в том же порядке, всегда нужно оставлять только один.
Избыточные (redundant) индексы — если один индекс содержит другой: (A,B) и (A,B,C).
Прежде чем добавить новый индекс — смотрим, нельзя ли расширить старый, но возможны варианты:
(A INT, B INT) и (A INT, B INT, C VARCHAR)
Второй индекс может быть существенно медленнее первого, в том числе для покрывающих индексов.
Многокритериальные индексы
Если необходим поиск по форме, содержащей много полей:
CREATE INDEX search ON people(gender,eye_color,hair_color,city,age);
Работает с запросами gender, gender+country, gender+country+region. Но что делать с поиском по region+age?
Можно построить еще один индекс, однако большое количество индексов (по одному на каждую комбинацию) - плохо.
Иногда можно извернуться, указав отсутствующее в запросе поле со всеми возможными значениями
... WHERE eye_color IN('brown','blue','hazel')
AND hair_color IN('black','red','blonde','brown')
AND gender IN('M','F');Сортировка по индексам
Для того, чтобы индексы использовались при сортировке, необходимо выполнение следующих требований:
порядок колонок в индексе должен точно совпадать с
ORDER BYне работает для разнонаправленной сортировки (
ASC/DESC) при нескольких колонках вORDER BYдля
JOIN— еслиORDER BYсодержит только колонки первой таблицылевосторонняя префиксность, кроме случаев ограничения в
WHEREпо константе
Пример:
CREATE INDEX rental_date (rental_date,inventory_id,customer_id); SELECT rental_id, staff_id FROM rental WHERE rental_date = '2005-05-25' ORDER BY inventory_id, customer_id;
Сортировка по индексу не работает в следующих случаях:
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id, staff_id;
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC, customer_id ASC;
... WHERE rental_date = '2005-05-25' ORDER BY customer_id;
... WHERE rental_date > '2005-05-25' ORDER BY inventory_id, customer_id;
AND hair_color IN('black','red','blonde','brown')
AND gender IN('M','F');Порядок следования полей в индексе
При построении индекса в большинстве случаев можно придерживаться следующего принципа:
сначала колонки, по которым делается выборка по значению, в порядке убывания селективности
потом колонка, по которой делается выборка по интервалу
CREATE INDEX ON employees(department_id, education_type, gender, age);
^ ^ ^ ^
SELECTIVITY: 10 3 2 20 В тексте WHERE порядок следования условий как правило не играет роли, оптимизатор запросов достаточно умный.
В SORT — еще как влияет, поэтому нужно еще и учитывать наиболее частые сортировки.
pushorigin.ru
Оптимизация MySQL-индексов
Как индексы могут влиять на производительность MySQL запросов
Если говорить простым языком, то запросы к MySQL условно можно разделить на 2 типа — операции выборки и операции обновления. К первым относятся операции SELECT, ко вторым — UPDATE, INSERT, DELETE. Довольно много информации по этому поводу есть в официальной документации, а так же в российском комьюнити. Но если в официальной документации обычно описывается как правильно использовать индексы и составлять правильные запросы, то в рамках этой статьи мне бы хотелось рассказать о личном опыте того, как можно оптимизировать «всё и разом» если более логично подойти к организации хранения своих данных и выборе типов данных.
Любой разработчик в курсе, что основным слабым звеном в доступе к данным являются дисковые операции. Именно количество дисковых операций, необходимых для выполнения запроса, в основном и влияет на скорость выполнения этого запроса. И если на непосредственные операции чтения/записи к самим данным мы повлиять не можем, то мы можем легко повлиять на операции предшествующие им — а именно операции с индексами. Именно индексы позволяют движку MySQL почти напрямую получать ячейку где хранятся требуемые данные, а не искать их используя fullscan по всему файлу с данными. Именно поэтому любой опытный программист и администратор работающий с базами данных скажет что индекс должен помещаться целиком в память, чтоб исключить лишние дисковые операции. В MySQL за размер буффера для хранения индекса отвечает системная переменная key_buffer_size. Но бесконечно его увеличивать не получится — в железе есть ограничение по максимальному количеству ОЗУ, а вот ограничения по максимальному размеру таблиц в базе данных довольно далеко выходят за рамки обычных жестких дисков, поэтому для нас они почти бесконечны. И рано или поздно возникает проблема выхода размеров индекса за рамки key_buffer_size что приводит к резкому снижению скорости выполнения запросов.
Как уменьшить размер индексов в базе данных
Уменьшить размер индексов можно по нескольким направлениям:
- Удалить неиспользуемые индексы
- Уменьшить размер целочисленных индексов
- Оптимизировать хранение строковых индексов
Какие индексы можно удалить
Прежде всего стоит понимать что в одной операции сравнения на одной таблице может максимально использоваться лишь только один индекс. Например в запросе
SELECT id, message FROM ticket WHERE manager_id = 3 AND title like «a%»;
при наличии двух проиндексированных столбцов manager_id и title MySQL сможет использовать лишь один из них. Т.е. по этому индексу будут сразу найдены строки удовлетворяющие одному из условий и уже потом для каждой из них будет проверяться удовлетворяет ли строка второму условию. Поэтому нет смысла плодить индексы по всем столбцам, надеясь что MySQL будет их использовать. Часто это может привести к тому что оптимизатор будет выбирать неоптимальный путь для выполнения запроса.
Рассмотрим еще один частовстречающуюся неверную конфигурацию:
SELECT id, email FROM user WHERE is_active = 1
В том что в случае если по индексу is_active MySQL увидит несколько тысяч строк, а таблица большая, — оптимизатор будет делать fullscan, т.к. в этом случае выигрыш от последовательного чтения всей таблицы будет больше, чем необходимость делать несколько тысяч отдельных операций случайного доступа к диску. Таким образом индексы всех тех столбцов, которые содержат в себе лишь несколько различных значений (имеют высокую «повторяемость значений»), можно смело удалять. К таковым, например, относятся различные столбцы хранящие флаги (булевы значения), или значения типа enum. Как вариант — эти столбцы можно добавить к другому составному индексу, если они часто используются как дополнительный фильтр при выборке с другими столбцами.
Переходим к составным индексам. Иногда невнимательные разработчики добавляют несколько индексов и покрывают один индекс другим. Например, если изначально для таблицы user была выставлена индексация столбца added_time, а в дальнейшем из-за частого использования запроса
SELECT id, email FROM user WHERE added_time > now() — INTERVAL 1 DAY AND is_approved = 1
был добавлен составной индекс (added_time, is_approved), то новый полностью покрывает старый — MySQL сможет комфортно использовать этот новый индекс индекс по первому столбцу. В данном случае старый можно смело удалить. Подробнее о том как работают составные индексы можно почитать на сайте документации MySQL
Как уменьшить размер целочисленных индексов
Не стоит забывать что уменьшая тип данных Primary Key небольшой таблицы, мы так же будем уменьшать и тип данных всех внешних ключей к ней. Например если в таблице status 10 строк, а столбец id имеет тип int то, казалось бы, сменив его на тип tinyint мы выиграем всего 30 байт индекса. Но ведь мы сменим и все столбцы status_id в связанных таблицах, а если в тех таблицах суммарно несколько десятков миллионов строк, то можно выиграть десятки и сотни мегабайт в объеме индексного хранилища.
Как правильно выбрать тип для индексного столбца
Для того чтоб верно выбрать тип столбца — нужно понимать сколько уникальных значений в нем будет за время полное время жизни проекта. Потенциальное количество уникальных значений должно целиком покрываться максимальным значением unsigned-варианта типа. Разумеется, если мы говорим об экономии индексного пространства, то значение auto_increment_increment не должно быть более 1.
Пространство которое можно покрыть целочисленными unsigned-типами:
Type Capacity TINYINT 255 SMALLINT 65535 MEDIUMINT 16777215 INT 4294967295 BIGINT 18446744073709551615
Tinyint идеально подойдет под небольшие списки статусов и типов каких-либо сущностей. Smallint будет хорош для списков пользователей внутренней биллинговой системы. Mediumint должно хватить для списков пользователей под проект среднего размера со свободной регистрацией. Int будет достаточным для идентификации почти любых вручную генерируемых объектов. И, наконец, bigint подойдет для идентификации самых массовых сущностей или массово генерируемых событий. Так же bigint подойдет как замена строковых индексов.
Как оптимизировать хранение строковых индексов
Когда необходимо сделать индекс по строке, например по столбцу с типом varchar, то, для сокращения размера индекса, часто индексируют дополнительный столбец char(32) содержащий md5-преобразование от строки. Тем не менее, результат md5-преобразования занимает 32 байта на каждую строку, что тоже весьма затратно. md5 — это набор из 32-х 16-ричных цифр, позволяющий нам охватить пространство в 2^256 или больше чем 10^38. Но для большинства задач хватает намного меньшего диапазона значений. Например, можно сократить char(32) до char(16) и получить экономию в два раза в размере ключа. Но в 16 байтах мы будем хранить 16 символов или 16 16-ричных цифр, которые
my2i.ru
Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL / Habr
В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБДB-Tree
Семейство B-Tree индексов — это наиболее часто используемый тип индексов, организованных как сбалансированное дерево, упорядоченных ключей. Они поддерживаются практически всеми СУБД как реляционными, так нереляционными, и практически для всех типов данных.
Так как большинство, наверное, их хорошо знает(или могут прочесть о них например, здесь), то единственное, что, пожалуй, следует здесь отметить, это то, что данный тип индекса оптимален для множества с хорошим распределением значений и высокой мощностью(cardinality-количество уникальных значений).
Пространственные индексы
В данный момент все данные СУБД имеют пространственные типы данных и функции для работы с ними, для Oracle — это множество типов и функций в схеме MDSYS, для PostgreSQL — point, line, lseg, polygon, box, path, polygon, circle, в MySQL — geometry, point, linestring, polygon, multipoint, multilinestring, multipolygon, geometrycollection, MS SQL — Point, MultiPoint, LineString, MultiLineString, Polygon, MultiPolygon, GeometryCollection.
В схеме работы пространственных запросов обычно выделяют две стадии или две ступени фильтрации. СУБД, обладающие слабой пространственной поддержкой, отрабатывают только первую ступень (грубая фильтрация, MySQL). Как правило, на этой стадии используется приближенное, аппроксимированное представление объектов. Самый распространенный тип аппроксимации – минимальный ограничивающий прямоугольник (MBR – Minimum Bounding Rectangle) [100].
Для пространственных типов данных существуют особые методы индексирования на основе R-деревьев(R-Tree index) и сеток(Grid-based Spatial index).
Spatial grid
Spatial grid(пространственная сетка) index – это древовидная структура, подобная B-дереву, но используется для организации доступа к пространственным(Spatial) данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами(широтой и долготой). В этой структуре узлами дерева выступают ячейки пространства. Например, для двухмерного пространства: сначала вся родительская площадь будет разбита на сетку строго определенного разрешения, затем каждая ячейка сетки, в которой количество объектов превышает установленный максимум объектов в ячейке, будет разбита на подсетку следующего уровня. Этот процесс будет продолжаться до тех пор, пока не будет достигнут максимум вложенности (если установлен), или пока все не будет разделено до ячеек, не превышающих максимум объектов.
В случае трехмерного или многомерного пространства это будут прямоугольные параллелепипеды (кубоиды) или параллелотопы.
Quadtree
Quadtree – это подвид Grid-based Spatial index, в котором в родительской ячейке всегда 4 потомка и разрешение сетки варьируется в зависимости от характера или сложности данных.
R-Tree
R-Tree (Regions Tree) – это тоже древовидная структура данных подобная Spatial Grid, предложенная в 1984 году Антонином Гуттманом. Эта структура данных тоже разбивает пространство на множество иерархически вложенных ячеек, но которые, в отличие от Spatial Grid, не обязаны полностью покрывать родительскую ячейку и могут пересекаться.
Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: с квадратичной и линейной сложностью(Гуттман, конечно, описал и с экспоненциальной сложностью — Exhaustive Search, но он, естественно, нигде не используется).
Квадратичный подтип заключается в разбиении на два прямоугольника с минимальной площадью, покрывающие все объекты. Линейный – в разбиении по максимальной удаленности.
HASH
Hash-индексы были предложены Артуром Фуллером, и предполагают хранение не самих значений, а их хэшей, благодаря чему уменьшается размер(а, соответственно, и увеличивается скорость их обработки) индексов из больших полей. Таким образом, при запросах с использованием HASH-индексов, сравниваться будут не искомое со значения поля, а хэш от искомого значения с хэшами полей.
Из-за нелинейнойсти хэш-функций данный индекс нельзя сортировать по значению, что приводит к невозможности использования в сравнениях больше/меньше и «is null». Кроме того, так как хэши не уникальны, то для совпадающих хэшей применяются методы разрешения коллизий.
Bitmap
Bitmap index – метод битовых индексов заключается в создании отдельных битовых карт (последовательность 0 и 1) для каждого возможного значения столбца, где каждому биту соответствует строка с индексируемым значением, а его значение равное 1 означает, что запись, соответствующая позиции бита содержит индексируемое значение для данного столбца или свойства.
| EmpID | Пол |
|---|---|
| 1 | Мужской |
| 2 | Женский |
| 3 | Женский |
| 4 | Мужской |
| 5 | Женский |
Битовые карты
| Значение | Начало | Конец | Битовая маска |
|---|---|---|---|
| Мужской | Адрес первой строки | Адрес последней строки | 10010 |
| Женский | Адрес первой строки | Адрес последней строки | 01101 |
Основное преимущество битовых индексов в том, что на больших множествах с низкой мощностью и хорошей кластеризацией по их значениям индекс будет меньше чем B*-tree. (Подробнее стоит прочесть здесь или здесь)
Reverse index
Reverse index – это тоже B-tree индекс но с реверсированным ключом, используемый в основном для монотонно возрастающих значений(например, автоинкрементный идентификатор) в OLTP системах с целью снятия конкуренции за последний листовой блок индекса, т.к. благодаря переворачиванию значения две соседние записи индекса попадают в разные блоки индекса. Он не может использоваться для диапазонного поиска.
Пример:
| Поле в таблице(bin) | Ключ reverse-индекса(bin) |
|---|---|
| 00000001 | 10000000 |
| … | … |
| 00001001 | 10010000 |
| 00001010 | 01010000 |
| 00001011 | 11010000 |
Inverted index
Инвертированный индекс – это полнотекстовый индекс, хранящий для каждого лексемы ключей отсортированный список адресов записей таблицы, которые содержат данный ключ.
| 1 | Мама мыла раму |
| 2 | Папа мыл раму |
| 3 | Папа мыл машину |
| 4 | Мама отполировала машину |
В упрощенном виде это будет выглядеть так:
| Мама | 1,4 |
| Мыла | 1 |
| Раму | 1,2 |
| Папа | 2,3 |
| Отполировала | 4 |
| Машину | 3,4 |
Partial index
Partial index — это индекс, построенный на части таблицы, удовлетворяющей определенному условию самого индекса. Данный индекс создан для уменьшения размера индекса.
Function-based index
Самим же гибким типом индексов являются функциональные индексы, то есть индексы, ключи которых хранят результат пользовательских функций. Функциональные индексы часто строятся для полей, значения которых проходят предварительную обработку перед сравнением в команде SQL. Например, при сравнении строковых данных без учета регистра символов часто используется функция UPPER. Создание функционального индекса с функцией UPPER улучшает эффективность таких сравнений.
Кроме того, функциональный индекс может помочь реализовать любой другой отсутствующий тип индексов данной СУБД(кроме, пожалуй, битового индекса, например, Hash для Oracle)
Сводная таблица типов индексов
| MySQL | PostgreSQL | MS SQL | Oracle | |
| B-Tree index | Есть | Есть | Есть | Есть |
| Поддерживаемые пространственные индексы(Spatial indexes) | R-Tree с квадратичным разбиением | Rtree_GiST(используется линейное разбиение) | 4-х уровневый Grid-based spatial index (отдельные для географических и геодезических данных) | R-Tree c квадратичным разбиением; Quadtree |
| Hash index | Только в таблицах типа Memory | Есть | Нет | Нет |
| Bitmap index | Нет | Есть | Нет | Есть |
| Reverse index | Нет | Нет | Нет | Есть |
| Inverted index | Есть | Есть | Есть | Есть |
| Partial index | Нет | Есть | Есть | Нет |
| Function based index | Нет | Есть | Есть | Есть |
Стоит упомянуть, что в PostgreSQL GiST позволяет создать для любого собственного типа данных индекс основанный на R-Tree. Для этого нужно реализовать все 7 функций механизма R-Tree.
Дополнительно можно прочитать здесь:
Oracle Spatial User’s Guide and Reference
Пространственные данные в MS SQL
MS SQL: Spatial Indexing Overview
Hilbert R-tree
Пространственные типы PostgreSQL
Пространственные функции PostgreSQL
Индексирование пространственных данных в СУБД Microsoft SQL Server 2000
Papadias D., Theodoridis T. Spatial Relations, Minimum Bounding Rectangles and Spatial Data Structures // Technical Report KDB-SLAB-TR-94-04,
Faloutsos C., Kamel I. Hilbert R-Tree: An Improved R-Tree UsingFractals // Department of CS, University of Maryland, TechnicalResearch Report TR-93-19,
Wikipedia: Hilbert R-tree
Методы поиска во внешней памяти
Артур Фуллер. Intelligent database design using hash keys
PS. Возможно я что-либо забыл упомянуть, пишите на личку или в комментарии — добавлю.
habr.com
Когда MySQL не использует индексы
Stack Overflow на русскомLoading…
- 0
- +0
- Тур Начните с этой страницы, чтобы быстро ознакомиться с сайтом
- Справка Подробные ответы на любые возможные вопросы
- Мета Обсудить принципы работы и политику сайта
- О нас Узнать больше о компании Stack Overflow
- Бизнес Узнать больше о поиске разработчиков или рекламе на сайте
- Войти Регистрация
-
текущее сообщество
ru.stackoverflow.com
дата — INDEX по полю datetime MySQL (производительность)
Stack Overflow на русскомLoading…
- 0
- +0
- Тур Начните с этой страницы, чтобы быстро ознакомиться с сайтом
- Справка Подробные ответы на любые возможные вопросы
- Мета Обсудить принципы работы и политику сайта
- О нас Узнать больше о компании Stack Overflow
- Бизнес Узнать больше о поиске разработчиков или рекламе на сайте
- Войти Регистрация
-
текущее сообщество
- Stack Overflow на русском справка чат
- Stack Overflow на
ru.stackoverflow.com