Поиск отсутствующих индексов таблиц в базе на MS SQL Server. Ms sql индексы

Отсутствующие индексы в MS-SQL или оптимизация «по-быстрому»

При выполнении запроса, как мы знаем, оптимизатор SQL Server исходя из существующих индексов и имеющейся свежей статистики пытается за разумное время найти лучший план запроса, конечно если этот план уже не «сидит» в кэше сервера, и запрос выполняется по этому плану и план сохраняется в кэш сервера. Если план уже построен для этого запроса ранее, то запрос выполняется по существующему плану.

Нам в этой теме интересен следующий момент: Во время компиляции плана запроса, при переборе возможных индексов, если лучшего индекса не нашлось (по мнению сервера), то в плане запроса помечается этот не найденный индекс, и сервер ведет статистику по таким индексам – сколько раз сервер бы воспользовался этим индексом и сколько стоил этот запрос. Эти отсутствующие индексы – missing indexes мы сейчас и разберем, что с ними делать и как с ними работать.

Предлагаю на примере разобраться с отсутствующими индексами. Создадим пару таблиц в нашей, БД на локальном или тестовом сервере:

if object_id ('orders_detail') is not null drop table orders_detail;

if object_id('orders') is not null drop table orders;

create table orders

(

id int identity primary key,

dt datetime,

seller nvarchar(50)

)

create table orders_detail

(

id int identity primary key,

order_id int foreign key references orders(id),

product nvarchar(30),

qty int,

price money,

cost as qty * price

)

with cte as

(

select 1 id union all

select id+1 from cte where id < 20000

)

insert orders

select

dt,

seller

from

(

select

dateadd(day,abs(convert(int,convert(binary(4),newid()))%365),'2016-01-01') dt,

abs(convert(int,convert(binary(4),newid()))%5)+1 seller_id

from cte

) c

left join

(

values

(1,'Vasa'),

(2,'Peta'),

(3,'Anna'),

(4,'Ira'),

(5,'Igor')

) t (id,seller) on t.id = c.seller_id

option(maxrecursion 0)

insert orders_detail

select

order_id,

product,

qty,

price

from

(

select

o.id as order_id,

abs(convert(int,convert(binary(4),newid()))%5)+1 product_id,

abs(convert(int,convert(binary(4),newid()))%20)+1 qty

from orders o cross join

(

select top(abs(convert(int,convert(binary(4),newid()))%5)+1) *

from

(

values (1),(2),(3),(4),(5),(6),(7),(8)

) n(num)

) n

) c

left join

(

values

(1,'Сахар', 50),

(2,'Молоко', 80),

(3,'Хлеб', 20),

(4,'Макароны', 40),

(5,'Пиво', 100)

) t (id,product, price) on t.id = c.product_id

Структура простая из 2х табличек: продажи где поля идентификатор, дата продажи и продавец и другая таблица – детализация этих продаж, где какие-то товары в этой продаже указаны с ценой и количеством.

Предлагаю посмотреть простой запрос и его план:

select count(*) from orders o join orders_detail d on o.id = d.order_id

where d.cost > 1800

На графическом отображении плана запроса видна подсказка зеленым цветом об отсутствующем индексе, если кликнуть по ней правой кнопкой мыши и выделить «Missing Index Details..» то получим текст предлагаемого индекса, в тексте только лишь убрать комментарии и дать какое-нибудь имя индексу и скрипт готов к выполнению.

Мы не будем строить этот индекс, который дала подсказка в SSMS, а посмотрим будет ли рекомендован индекс этот динамическими представлениями, связанными с отсутствующими индексами. Эти представления:

select * from sys.dm_db_missing_index_group_stats

select * from sys.dm_db_missing_index_details

select * from sys.dm_db_missing_index_groups

Мы из этого видим, что в 1м представлении у нас есть статистика по отсутствующих индексах, а именно:

Сколько бы раз произвелся поиск если бы предложенный индекс существовал?
Сколько раз использовалось бы сканирование если бы предложенный индекс существовал.
Дата время последней потребности в этом индексе
Текущая реальная стоимость плана запроса без предлагаемого индекса.

2е представление это уже тело индекса по сути:

База данных
Объект/таблица
Сортированные колонки
Колонки включенные для увеличения покрытия индекса

3е представление - это связь 1го и 2х представлений.

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

with igs as

(

select *

from sys.dm_db_missing_index_group_stats

)

, igd as

(

select *,

isnull(equality_columns,'')+','+isnull(inequality_columns,'') as ix_col

from sys.dm_db_missing_index_details

)

select --top(10)

'use ['+db_name(igd.database_id)+'];

create index ['+'ix_'+replace(convert(varchar(10),getdate(),120),'-','')+'_'+convert(varchar,igs.group_handle)+'] on '+

igd.[statement]+'('+

case

when left(ix_col,1)=',' then stuff(ix_col,1,1,'')

when right(ix_col,1)=',' then reverse(stuff(reverse(ix_col),1,1,''))

else ix_col

end

+') '+isnull('include('+igd.included_columns+')','')+' with(online=on, maxdop=0)

' command

,igs.user_seeks

,igs.user_scans

,igs.avg_total_user_cost

from igs

join sys.dm_db_missing_index_groups link on link.index_group_handle = igs.group_handle

join igd on link.index_handle = igd.index_handle

where igd.database_id = db_id()

order by igs.avg_total_user_cost * igs.user_seeks desc

В порядке эффективности индексов выведены отсутствующие индексы. Идеально когда этот резалтсет ничего не возвращает, на нашем примере этот резалтсет возвратит минимум один индекс:

Когда совсем лень или некогда разбираться с тормозами у пары заказчиков я выполнял этот запрос, копировал первую колонку и выполнял на сервере. После этого тормоза уходили 😊.

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

create index ix_01 on tbl1 (a,b) include (c)

create index ix_02 on tbl1 (a,b) include (d)

create index ix_03 on tbl1 (a)

И эти индексы используются для поиска/seek, то вполне очевидно, что логичнее заменить эти индексы на один который покроет все 3 предложенных:

create index ix_1 on tbl1 (a,b) include (c,d)

Т.е. как минимум ревью предлагаемых индексов перед тем как их накатить на боевой сервер. Хотя…. Повторюсь, например на сервер TFS я накатывал потерянные индексы и общая производительность выростала, а время на такую оптимизацию затрачено минимум. Хотя, впоследствии с ТФС 2015 на ТФС 2017 я столкнулся с тем что обновление не проходило из-за новых индексов. Но их легко можно найти были по маске

select * from sys.indexes where name like 'ix[_]2017%'

kurenkov.pro

Поиск отсутствующих индексов таблиц в базе на MS SQL Server — AUsevich

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

- чтению большего количества строк данных
- увеличению времени выполнения запроса
- появлению избыточных блокировок
- и другим негативным последствиям

В данной статье мы рассмотрим как можно найти недостающие индексы с помощью динамических административных функций MS SQL Server.

Информация о динамических функциях

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

В данной статье мы воспользуемся тремя динамическими административными функциями (DMF): dm_db_missing_index_group_stats, dm_db_missing_index_groups, dm_db_missing_index_details

Запрос поиска недостающих индексов и анализ его результата

Следующий запрос выведет всю необходимую в дальнейшем информацию:

SELECT TOP 10 DB_NAME(database_id), mid.*, migs.*, avg_total_user_cost * avg_user_impact * (user_seeks + user_scans) as Perf FROM sys.dm_db_missing_index_group_stats as migs INNER JOIN sys.dm_db_missing_index_groups AS mig ON (migs.group_handle = mig.index_group_handle) INNER JOIN sys.dm_db_missing_index_details AS mid ON (mig.index_handle = mid.index_handle) ORDER BY avg_total_user_cost * avg_user_impact * (user_seeks + user_scans) DESC

SELECT TOP 10

DB_NAME(database_id),

mid.*,

migs.*,

avg_total_user_cost * avg_user_impact * (user_seeks + user_scans) as Perf

FROM sys.dm_db_missing_index_group_stats as migs

INNER JOIN sys.dm_db_missing_index_groups AS mig

ON (migs.group_handle = mig.index_group_handle)

INNER JOIN sys.dm_db_missing_index_details AS mid

ON (mig.index_handle = mid.index_handle)

ORDER BY avg_total_user_cost * avg_user_impact * (user_seeks + user_scans) DESC

Выражение avg_total_user_cost * avg_user_impact * (user_seeks + user_scans), использованное в запросе, соответствует оценке выигрыша при добавлении отсутствующего индекса. Файл запроса можно скачать во вложениях к статье.

Выполним запрос и проанализируем его результаты на простом примере.

Отсутствующие индексы в базе данных

Как видно, отсутствует индекс в таблице AccumRg23573, при этом запрос, для которого необходим индекс, выполняется с предикатом равенства по полю Fld23580RRef. В поле user_seeks указано что этот индекс мог бы быть использован 750 раз в целях поиска по индексу, avg_user_impact говорит о том что средний процент выигрыша равен 99,99%. Так же имеет смысл обратить внимание на поле last_user_seek, оно указывает на дату и время последнего пользовательского запроса, который мог бы использовать отсутствующий индекс для поиска. Если последний раз подходящий запрос был давно, возможно, индекс будет использовать редко и необходимости в нем нет — необходимо оценить перед добавлением индекса. Теперь воспользуемся обработкой выводящей структуру хранения базы данных в терминах 1С:Предприятия (из статьи «Получение информации о структуре хранения базы данных в терминах 1С:Предприятие и СУБД»).

Структура хранения базы данных с отсутствующим индексом

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

Добавим отсутствующий индекс

Статистика использования индекса

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

Статистика использования добавленного отсутствующего индекса

Оценив значения в колонке user_seeks можно сделать вывод что в данной системе этот индекс используется достаточно часто, а эффективность от его использования высока (была оценена первым запросом).

ausevich.ru

MSSQL – простые индикаторы нехватки индексов

Как обычно в нашей профессии, есть несколько способов решить задачу :)

Расскажу о трёх наиболее простых подходах (и одном бонусном), не углубляясь в детали. Если интересны как раз глубокие детали, рекомендую почитать документацию (начать стоит с Designing Indexes, а прочитав о проектировании продолжить Performance (Database Engine)).

Кстати, если тема плана выполнения для вас нова – неплохим стартом будет мой давний пост «SQL – execution plan».

DISCLAIMER: в этой статье я даю простые советы, которые чаще всего работают, однако в MSSQL практически невозможно дать рекомендации на все случаи жизни – данные бывают разные, запросы бывают разные…

1. Мысленный эксперимент

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

Что касается простейших советов, они следующие:

Если данных не мизерное количество – вам нужны индексы.
Если есть внешние ключи – настоящие или по смыслу (некоторые их принципиально не любят делать) – они хорошие кандидаты для индексирования.
Чаще всего стоит сделать кластерный индекс и сделать его не слишком большим (потому что другие индексы будут ссылаться на строки по кластерному индексу). Кстати, кластерный индекс отлично подходит для выборки по диапазону (например, по диапазону дат).
Помните, что индексы тоже хранятся на диске. Простейший вывод – большое количество индексов снизит скорость вставки (иногда и обновления) данных. Обычно до создания 5-7 индексов проблем не возникает.
Статистика очень важна для правильного использования индексов. Хорошая новость – чаще всего MSSQL сам достаточно неплохо за ней следит, плохая новость – это не всегда срабатывает.
Для наиболее критичных запросов, возвращающих небольшое количество столбцов, имеет смысл использовать покрытие индексом (это уже чуть более продвинутая техника, но ничего сложного в ней нет).

Поскольку я обещал не углубляться в детали – идём дальше.

Database Engine Tuning Advisor

Это сравнительно простой в использовании, но, тем не менее, мощный и результативный инструмент, который даёт рекомендации по улучшению производительности запросов. Правда, надо отметить, что он недоступен в Express-версии.

Если вкратце, на вход он принимает набор запросов (можно подготовить с помощью SQL Server Profiler) и, после их анализа (иногда довольно длительного), даёт рекомендации.

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

Missing Index Feature

Вероятно, вы уже обращали внимание, что при просмотре плана выполнения иногда встречаются рекомендации вида "Missing index...". Это как раз работает Missing Index Feature.

На это можно посмотреть, запустив на базе AdventureWorks (в моём случае была база для 2012 версии) такой запрос:

select s.ProductID from Sales.SalesOrderDetail s where s.UnitPrice = 2

Если включен просмотр плана выполнения (Ctrl+M), мы увидим вполне логичную рекомендацию для улучшения производительности этого запроса. Да, повторюсь – не стоит улучшать один, особенно не критичный запрос – мы можем замедлить другие, более важные запросы. С этой точки зрения предыдущие варианты более правильные.

И обещанный бонус, которым редко пользуются, но стоит иметь в виду его наличие – sys.dm_db_missing_index_detail и его друзья (насколько я понимаю, это источник информации, которую показывает план выполнения). Попробовать можно просто выбрав записи из этого представления после запроса, приведённого выше. По моему мнению, этот способ менее удобен для использования человеком, однако может использоваться для последующего автоматического разбора.

Если у вас есть замечания, пожелания или новые темы – пишите в комментариях или на olegaxenow.reformal.ru. Постараюсь учесть.

www.olegaxenow.com

Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL / Хабр

В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБД

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

Как видите, значение в индексе изменяется намного больше, чем само значение в таблице, и поэтому в структуре b-tree, они попадут в разные блоки.

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 SQLMS SQL: Spatial Indexing OverviewHilbert R-treeПространственные типы PostgreSQLПространственные функции PostgreSQLИндексирование пространственных данных в СУБД Microsoft SQL Server 2000Papadias 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

Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL | Базы данных | Статьи | Программирование Realcoding.Net

B-Tree

Пространственные индексы

В данный момент все данные СУБД имеют пространственные типы данных и функции для работы с ними, для 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

Quadtree

R-Tree

R-Tree (Regions Tree) – это тоже древовидная структура данных подобная Spatial Grid, предложенная в 1984 году Антонином Гуттманом. Эта структура данных тоже разбивает пространство на множество иерархически вложенных ячеек, но которые, в отличие от Spatial Grid, не обязаны полностью покрывать родительскую ячейку и могут пересекаться.Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: с квадратичной и линейной сложностью(Гуттман, конечно, описал и с экспоненциальной сложностью — Exhaustive Search, но он, естественно, нигде не используется).Квадратичный подтип заключается в разбиении на два прямоугольника с минимальной площадью, покрывающие все объекты. Линейный – в разбиении по максимальной удаленности.

HASH

Bitmap

EmpID Пол

1	Мужской
2	Женский
3	Женский
4	Мужской
5	Женский

Битовые карты

Значение Начало Конец Битовая маска

Мужской	Адрес первой строки	Адрес последней строки	10010
Женский	Адрес первой строки	Адрес последней строки	01101

Reverse index

Поле в таблице(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

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 SQLMS SQL: Spatial Indexing OverviewHilbert R-treeПространственные типы PostgreSQLПространственные функции PostgreSQLИндексирование пространственных данных в СУБД Microsoft SQL Server 2000Papadias 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. Возможно я что-либо забыл упомянуть, пишите на личку или в комментарии — добавлю.

Автор материала: курс евро

www.realcoding.net

Дефрагментация индексов со сбором статистики MS SQL 2008 R2 / Хабр

Одна из первых задач, которая возникает перед DBA после развертывания новой БД — это настройка планов по ее обслуживанию. Зачастую, в план обслуживания включается задача по дефрагментации индексов. Мне нравится, когда я знаю не только то, что дефрагментация выполнилась ночью с воскресенья на понедельник, но и то, как она прошла, сколько выполнялась, какие индексы были перестроены и в каком состоянии они остались после дефрагментации.

Для сбора такой статистики мною был написан небольшой скриптик, который собирает информацию о выполненной работе, а так же дает максимально подробное описание о состоянии индексов до и после проделанной процедуры.

Но начнем с простого, создадим таблицу для хранения этих самых данных (я создал отдельную БД, куда складываю таблицы, которыми пользуюсь во время обслуживания баз данных сервера):

Столбец Тип Комментарий

proc_id	int	Порядковый номер процедуры, для идентификации
start_time	datetime	Начало выполнения запроса ALTER INDEX
end_time	datetime	Завершение выполнения запроса ALTER INDEX
database_id	smallint	Идентификатор БД
object_id	Int	Идентификатор таблицы
table_name	varchar(50)	Имя таблицы
index_id	Int	Идентификатор индекса
index_name	varchar(50)	Имя индекса
avg_frag_percent_before	float	Процент фрагментации индекса перед выполнением ALTER INDEX
fragment_count_before	bigint	Количество фрагментов до дефрагментации
pages_count_before	bigint	Количество страниц индекса до дефргаментации
fill_factor	tinyint	Уровень заполнения страниц индекса
partition_num	int	Номер секции
avg_frag_percent_after	float	Процент фрагментации индекса после выолнения ALTER INDEX
fragment_count_after	bigint	Количество фрагментов после дефрагментации
pages_count_after	bigint	Количество страниц индекса после дефргаментации
action	varchar(10)	Выполняемое действие

Вся процедура дефрагментации, будет брать данные из этой таблицы, а значит, надо ее заполнить:DECLARE @currentProcID INT –-Порядковый номер процедуры дефрагментации –-Выбираем последний номер, и просто добавляем единичку SELECT @currentProcID = ISNULL(MAX(proc_id), 0) + 1 FROM dba_tasks.dbo.index_defrag_statistic --И заполняем таблицу данными о состоянии индексов INSERT INTO dba_tasks.dbo.index_defrag_statistic ( proc_id, database_id, [object_id], table_name, index_id, index_name, avg_frag_percent_before, fragment_count_before, pages_count_before, fill_factor, partition_num) SELECT @currentProcID, dm.database_id, dm.[object_id], tbl.name, dm.index_id, idx.name, dm.avg_fragmentation_in_percent, dm.fragment_count, dm.page_count, idx.fill_factor, dm.partition_number FROM sys.dm_db_index_physical_stats(DB_ID(), null, null, null, null) dm INNER JOIN sys.tables tbl ON dm.object_id = tbl.object_id INNER JOIN sys.indexes idx ON dm.object_id = idx.object_id AND dm.index_id = idx.index_id WHERE page_count > 8 AND avg_fragmentation_in_percent > 10 AND dm.index_id > 0 Условия выборки:page_count > 8 – я считаю, что перестраивать индексы с малым количеством страниц не имеет смысла, т.к. лучше не станет, а время, затраченное на выполнение процедуры — очень ценно, особенно если база работает круглосуточно и постоянно находится под высокой нагрузкой. (После замечания unfilled поднял планку до 8 страниц)avg_fragmentation_in_percent > 10 – Тоже очень субъективная цифра, практически во всей документации предлагают не трогать индекс, если его фрагментация составляет 10 или менее процентов, с чем я согласен, если у вас дела обстоят по другому, меняем.dm.index_id > 0 – 0 – это куча

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

--Обьявим необходимые переменные DECLARE @partitioncount INT --Количество секций DECLARE @action VARCHAR(10) --Действие, которые мы будем делать с индексом DECLARE @start_time DATETIME --Начало выполнения запроса ALTER INDEX DECLARE @end_time DATETIME --Конец выполнения запроса ALTER INDEX --см описание таблицы DECLARE @object_id INT DECLARE @index_id INT DECLARE @tableName VARCHAR(250) DECLARE @indexName VARCHAR(250) DECLARE @defrag FLOAT DECLARE @partition_num INT DECLARE @fill_factor INT --Сам запрос, который мы будем выполнять, я поставил MAX, потому как иногда меняю такие скрипты, и забываю поправить размер данной переменной, в результате получаю ошибку. DECLARE @sql NVARCHAR(MAX) --Далее объявляем курсор DECLARE defragCur CURSOR FOR SELECT [object_id], index_id, table_name, index_name, avg_frag_percent_before, fill_factor, partition_num FROM dba_tasks.dbo.index_defrag_statistic WHERE proc_id = @currentProcID ORDER BY [object_id], index_id DESC --Сначала не кластерные индексы OPEN defragCur FETCH NEXT FROM defragCur INTO @object_id, @index_id, @tableName, @indexName, @defrag, @fill_factor, @partition_num WHILE @@FETCH_STATUS=0 BEGIN SET @sql = N'ALTER INDEX ' + @indexName + ' ON ' + @tableName SELECT @partitioncount = count (*) FROM sys.partitions WHERE object_id = @object_id AND index_id = @index_id; --В моем случае, важно держать неможко пустого места на страницах, потому, что вставка в тоже таблицы имеете место, и не хочеться тратить драгоценное время пользователей на разбиение страниц IF (@fill_factor != 80) BEGIN @sql = @sql + N' REBUILD WITH (FILLFACTOR = 80)' SET @action = 'rebuild80' END ELSE BEGIN --Тут все просто, действуем по рекомендации MS IF (@defrag > 30) --Если фрагментация больше 30%, делаем REBUILD BEGIN SET @sql = @sql + N' REBUILD' SET @action = 'rebuild' END ELSE --В противном случае REORGINIZE BEGIN SET @sql = @sql + N' REORGANIZE' SET @action = 'reorginize' END END --Если есть несколько секций IF @partitioncount > 1 SET @sql = @sql + N' PARTITION=' + CAST(@partition_num AS nvarchar(5)) print @sql --Вывод выполняемого запроса --Фиксируем время старта SET @start_time = GETDATE() EXEC sp_executesql @sql --И время завершения SET @end_time = GETDATE() --Сохраняем время в таблицу UPDATE dba_tasks.dbo.index_defrag_statistic SET start_time = @start_time, end_time = @end_time, [action] = @action WHERE proc_id = @currentProcID AND [object_id] = @object_id AND index_id = @index_id FETCH NEXT FROM defragCur INTO @object_id, @index_id, @tableName, @indexName, @defrag, @fill_factor, @partition_num END CLOSE defragCur DEALLOCATE defragCur

Ну и на последок, соберем информацию о индексах после процедуры дефрагментации:

UPDATE dba SET dba.avg_frag_percent_after = dm.avg_fragmentation_in_percent, dba.fragment_count_after = dm.fragment_count, dba.pages_count_after = dm.page_count FROM sys.dm_db_index_physical_stats(DB_ID(), null, null, null, null) dm INNER JOIN dba_tasks.dbo.index_defrag_statistic dba ON dm.[object_id] = dba.[object_id] AND dm.index_id = dba.index_id WHERE dba.proc_id = @currentProcID AND dm.index_id > 0

После выполнения такого скрипта, можно получить и посчитать очень много полезной информации. Например, время обслуживания всех индексов и каждого отдельно. Понять как это связано с размером индекса, увидеть эффективность данной операции. Собрав такую информацию за несколько раз, можно немного поменять процедуру, наверняка какие-то индексы фрагментируются больше и быстрее. В таком случае их обслуживание следует выполнять чаще. Как воспользоваться полученной информацией, решайте сами. Что же касается меня, то я, после анализа каждой такой процедуры, меняю планы обслуживания, если того требует ситуация. Мои базы работают под высокой нагрузкой круглосуточно. Поэтому постоянно перестраивать все индексы и на 1-2 часа снижать производительность сервера я не могу. Если Ваша БД, тоже работает круглосуточно, для выполнения таких вещей, следует настроить Resource Governor.

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

Более подробно об используемых мною системных представлениях можно почитать в msdn:

sys.sysindexessys.tablessys.dm_db_index_physical_stats

habr.com