Заметки Дмитрия Пилюгина о Microsoft SQL Server 

Twitter RSS
Home SQL Server (все заметки) Оконные функции и row goal
formats

Оконные функции и row goal

blogpost_min

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

 

 

Тестовые данные

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

01

create database ImplicitTop;
go
use ImplicitTop;
alter database ImplicitTop modify file (name = ImplicitTop, size = 1GB);
alter database ImplicitTop modify file (name = ImplicitTop_log, FILEGROWTH = 500MB);
go
set nocount on;
create table Customers(CustomerID int not null, RegionID int not null);
create table Orders(OrderID int identity not null, CustomerID int not null, SomeData char(100) not null default '');
create unique clustered index cix_OrderID on Orders(OrderID);
create unique clustered index cix_CustomerID on Customers(CustomerID);
create nonclustered index ix_CustomerID on Orders(CustomerID) include(SomeData);
go
with nums as (select top(2000) rn = row_number() over (order by(select null)) from master..spt_values v1,master..spt_values v2,master..spt_values v3)
insert Customers(CustomerID,RegionID) select rn, rn/50+1 from nums;
go
begin tran;
declare @i int = 1;
while @i <= 2000 begin	
	insert Orders with(tablock)(CustomerID) select @i from Customers;
	set @i+=1;
end;
commit tran;
go
alter table Orders add constraint FK_Customer foreign key (CustomerID) references Customers(CustomerID);
go

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

Теперь, представим, что у нас есть задача:
найти заказы клиентов из определенного региона, и вывести определённый диапазон из найденных строк, например для постраничного вывода (или с какими-то другими целями).

Проблема

Выполним запрос и посмотрим на время его выполнения:

declare @RegionID int = 1;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics time on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn
--option(recompile)
set statistics time off;

У меня он выполнился мгновенно:

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.

Теперь, выполним тот же самый запрос, для региона 5

declare @RegionID int = 5;

Время увеличилось на полсекунды:

SQL Server Execution Times:
CPU time = 422 ms, elapsed time = 428 ms.

Для региона 20:

declare @RegionID int = 20;

Время:

SQL Server Execution Times:
CPU time = 2047 ms, elapsed time = 3096 ms.

И, наконец, для региона 40:

declare @RegionID int = 40;

Время:

SQL Server Execution Times:
CPU time = 4375 ms, elapsed time = 8536 ms.

Время катастрофически неприемлемо, особенно сравнивая со временем выполнения для региона 1. Вы можете включить option(recompile), чтобы убедиться, что дело не в локальных переменных, или поменять номер страницы на 1 или даже оставить одну запись на странице – ничего из этого не поможет.

Анализ

Анализ начнем с плана выполнения. Для этого получим действительный план, выполнив запрос в режиме set statistics xml on.

-- Get The Plan
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn;
set statistics xml off;
go

Посмотрим внимательно на план и на число строк в оценках.

02

Возникает несколько вопросов: почему оценка соединения и нескольких других операторов – 100 строк, ведь число 100 нигде не фигурирует в запросе, и откуда взялся оператор Top, нигде в запросе не было конструкции select top(…).

Оценка 100 строк

Такая оценка получается в результате работы механизма Row Goal. Оптимизатор использует этот механизм, когда ему заранее известно, сколько строк необходимо получить, например, если в плане есть оператор Top.

В данном случае, он присутствует, хотя пока и непонятно почему. В если желаемое число строк заранее известно, оптимизатор может ограничивать этим значением предполагаемое количество строк сверху. Таким образом, если оператор, расположенный под оператором Top (или справа, в графическом представлении), в данном случае Sequence Project должен вернуть больше чем 100 строк, то механизм Row Goal ограничит его сверху оценкой в 100 строк. В свою очередь оператор Sequence Project распространит это ограничение далее ниже по дереву.

Как оценка кардинальности претерпевает изменения, по мере продвижения от нижних операторов плана к верхним – так и row goal, претерпевает изменения, в процессе переходя от верхних операторов к нижним.

03

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

Для этого, ему нужно знать селективность соединения, кардинальность таблицы и row goal. Поскольку, вычисление селективности соединения само по себе претендует на отдельный разговор, допустим, что мы уже знаем, сколько строк предполагается в соединении без Top.

04

Предполагаемое количество строк в соединении 108 764, всего в таблице 4 000 000 строк. Таким образом, предполагая равномерное распределение данных, чтобы получить одну строку необходимо просканировать: 4 000 000 / 108 764 = 36.776 строк. Поскольку необходимо получить сто строк, то умножим на сто: 36.776 * 100 = 3677,6 = [3678]. Именно эту цифру мы видим в плане с Top.

Row Goal и неравномерное распределение

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

05_1

По этому, реальное число строк в плане около 4 млн.:

08

Вспомним, что у нас есть индекс по полю CustomerID и у оптимизатора есть вариант воспользоваться индексом и выполнить поиск, а не сканировать всю таблицу.

05_2

Однако, при этом, он должен будет отсортировать полученные данные по OrderID, т.к. в запросе строки нумеруются в порядке OrderID: row_number() over (order by o.OrderID)

Выбор оптимизатора зависит от стоимости вариантов:

1) сканировать первые 3678 строк в порядке OrderID

2) выполнить 100 раз поиск по индексу с последующей сортировкой.

Дешевле оказывается вариант номер 1 и оптимизатор выбирает именно его, поскольку не догадывается о неравномерном распределении.

Попробуйте снять требования к сортировке, тем самым удешевив вариант номер 2, и выполнить запрос, вы увидите, что будет использоваться поиск по индексу:

 

-- No Sort Demand
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
with Paged as 
(
	select
		rn = row_number() over (order by (select null)),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn;
set statistics xml, time off;
go

Результат:

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 97 ms.

d

06

Либо можно увеличить стоимость сканирования, увеличив число строк в Top и тем самым также склонить оптимизатор к поиску.

-- Scan
set statistics xml, time on;
select top(100) * 
from 
	Orders o 
	join Customers c on o.CustomerID = c.CustomerID
where 
	c.RegionID = 40
order by o.OrderID
option(maxdop 1);
-- Increase Scan Cost => Seek
select top(10000) * 
from 
	Orders o 
	join Customers c on o.CustomerID = c.CustomerID
where 
	c.RegionID = 40
order by o.OrderID
option(maxdop 1);
set statistics xml, time off;

Обратите внимание на планы:

07

В первом плане у нас сканирование индекса, сканируется почти 4 млн. строк, хотя ожидалось всего около 3.5 тысяч, во втором случае используется поиск по индексу и оценки более или менее совпадают с реальностью. Отдельное внимание обратите на оценочную стоимость: 2% первого плана, против 98% второго.

А теперь посмотрим на время выполнения:

SQL Server Execution Times:
CPU time = 4438 ms, elapsed time = 8108 ms.
SQL Server Execution Times:
CPU time = 31 ms, elapsed time = 237 ms.

Второй выполнился в 30 раз быстрее, хотя мы выбираем в 100 раз больше строк! Лишнее напоминание о том, что оценочная стоимость может совершенно не отражать реальное время и о том, насколько важно выбрать правильную стратегию доступа.

Остается вопрос, откуда взялся оператор Top с оценкой в 100 строк?

Оператор Top

При построении плана запроса оптимизатор исследует различные варианты, рассматривает разные альтернативы возможного выполнения. Он получает эти альтернативы в результате применения правил преобразования к дереву операторов. Одним из таких правил является SelSeqPrjToTop — Select On Sequence Project To Top. Т.е. фильтр над вычислением последовательности в проекции в Top. Последовательность в проекции, оператор Sequence Project в плане – это то, как оптимизатор реализует генерацию последовательности чисел в функции row_number(). Далее мы фильтруем по значениям row_number() и оптимизатор дополнительно ограничивает результат при помощи Top. Наличие и успешное применение данного правила говорит о том, что в оптимизатор заложена логика по распознаванию «паттерна» часто применяемого в постраничном выводе (paging).

Действительно, наверняка кому-то показалось странным то, как я написал условие для paging-а, обычно его пишут через Top. Но что интересно, оптимизатор сделал это за меня! Он сам подставил оператор Top, однако, желаемое число строк (row goal) в таком автоматически сгенерированном операторе всегда 100, даже если я запрашиваю 300 строк!

09

Убедиться в том, что это правило действительно отвечает за генерацию Top, можно отключив его, и взглянув на план (я так же добавил подсказку maxdop, чтобы получить последовательный план):

-- Rule off SelSeqPrjToTop
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn
option(queryruleoff SelSeqPrjToTop, maxdop 1);
go

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

10

На основании всего вышесказанного подведем итоги и сформулируем проблему.

Формулировка проблемы

В процессе оптимизации, применяется правило SelSeqPrjToTop, которое добавляет перед фильтрацией по функции row_number оператор Top. В автоматически добавляемом операторе Top установлено жестко определенное число желаемых строк – 100 строк. Посредством механизма row goal оператор Top влияет на оценку нижних операторов плана, осуществляющих доступ к таблицам, уменьшая предполагаемое число строк соразмерно требованию в 100 строк. Поскольку предполагается малое число строк для просмотра, а в запросе присутствует требование к сортировке – сервер решает выполнить упорядоченный просмотр кластерного индекса. В реальности, необходимые данные оказываются в конце индекса, что приводит к сканированию почти всей таблицы. Это сильно влияет на производительность в худшую сторону.

Пробные решения

2012

2012 сервер предусматривает специальную конструкцию offeset … fetch… , но к сожалению на , все сказанное выше применимо и тут. Выполним:

-- 2012
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
select *
from 
	Orders o
	join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
order by o.OrderID
    offset @PageNumber*@PageSize - @PageSize rows
    fetch next @PageSize rows only;
set statistics xml, time off;
go

Время:

SQL Server Execution Times:
CPU time = 8253 ms, elapsed time = 8287 ms.

Переписать запрос

Попробуем переписать запрос в традиционном стиле paging, который рассматривается в статье Paul White «Optimising Server-Side Paging — Part I»

-- Rewrite
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
)
select top(@PageSize) * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize
order by rn;
set statistics xml off;
go

Время, как и план, остаются такими же как и в самом начальном запросе.

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

-- Rewrite Key Seek
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
with Keys as (
	select top(@PageNumber * @PageSize)
		rn = row_number() over (order by o.OrderID),
		o.OrderID
	from
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
	order by
		o.OrderID
),
SelectedKeys as
(
select top(@PageSize)
	rn,
	OrderID
from
	Keys
where
	rn > ((@PageNumber-1)*@PageSize)
)
select
	*
from
	SelectedKeys sk
	join Orders o on sk.OrderID = o.OrderID
order by
	sk.rn
set statistics xml, time off;
go

Время:

SQL Server Execution Times:
CPU time = 8488 ms, elapsed time = 8541 ms.

Не помогло, если посмотреть на план, то видно что по прежнему используется сканирование.

Хинты force seek, with(index())

Попробуем форсировать поиск по индексу.

-- Hints
declare @RegionID int = 40;
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o with(forceseek)
		join Customers c on o.CustomerID = c.CustomerID
	where 
		c.RegionID = @RegionID
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn;
set statistics xml, time off;
go

Время:

SQL Server Execution Times:
CPU time = 63 ms, elapsed time = 66 ms.

Попробуйте менять идентификатор региона и замерять время. Я не буду приводить тут результаты, т.к. заметка и так получается очень длинной. Вы можете сами убедиться, что время примерно всегда одно и то же и довольно приемлемое!
Решение?

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

Но реальность подкидывает другие задачи. В частности, в моем случае, список регионов задавался динамически.
Вот так:

-- Dynamic List of Regions
create table #filter(id int primary key);
insert #filter values (40);
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o with(forceseek)
		join Customers c on o.CustomerID = c.CustomerID
	where 
		exists (select * from #filter f where f.id = c.RegionID)
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn;
set statistics xml, time off;
drop table #filter;
go

Если это один регион, время по прежнему приемлемо.
Но что если будет задано несколько регионов.

-- Dynamic List of Regions - Several Regions
create table #filter(id int primary key);
insert #filter values (1),(2),(3),(4),(5);
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o with(forceseek)
		join Customers c on o.CustomerID = c.CustomerID
	where 
		exists (select * from #filter f where f.id = c.RegionID)
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn;
set statistics xml, time off;
drop table #filter;
go

Время:

SQL Server Execution Times:
CPU time = 575 ms, elapsed time = 1787 ms.

Теперь, тот же запрос, то уберем подсказку forceseek.

-- Dynamic List of Regions - Several Regions -- No force seek
create table #filter(id int primary key);
insert #filter values (1),(2),(3),(4),(5);
declare @PageNumber int = 5, @PageSize int = 20;
set statistics xml, time on;
with Paged as 
(
	select
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o --with(forceseek)
		join Customers c on o.CustomerID = c.CustomerID
	where 
		exists (select * from #filter f where f.id = c.RegionID)
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn;
set statistics xml, time off;
drop table #filter;
go

Время:

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 168 ms.

Итого, без подсказки forceseek, время в 10 (!) раз меньше в случае нескольких регионов. Хотя для одного региона подсказка работает отлично!

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

Решение

Если задуматься, разве это не задача оптимизатора, выбирать поиск или сканирование в зависимости от числа предполагаемых строк? Да. И все что ему мешает — это оценка Top. По этому, вот что предлагается сделать. Ввести дополнительную переменную, которая не меньше чем предполагаемое число строк на странице умноженное на количество страниц. Но при помощи подсказки optimize for задать такое значение, которое в вашем случае не будет делать сканирование слишком дешевым, в рассматриваемом случае это 10 000 (вспомните примеры с TOP выше).
Выполним два запроса, точечный и для диапазона.

-- Range
create table #filter(id int primary key);
insert #filter values (1),(2),(3),(4),(5);
declare @PageNumber int = 5, @PageSize int = 20;
declare @n int = @PageNumber * @PageSize;
set statistics time, xml on;
with Paged as 
(
	select top(@n)
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		exists (select * from #filter f where f.id = c.RegionID)
	order by
		rn
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn
option(optimize for (@n = 10000), maxdop 1);
set statistics time, xml off;
drop table #filter;
go

-- Point
create table #filter(id int primary key);
insert #filter values (40);
declare @PageNumber int = 5, @PageSize int = 20;
declare @n int = @PageNumber * @PageSize;
set statistics time, xml on;
with Paged as 
(
	select top(@n)
		rn = row_number() over (order by o.OrderID),
		o.*
	from 
		Orders o
		join Customers c on o.CustomerID = c.CustomerID
	where 
		exists (select * from #filter f where f.id = c.RegionID)
	order by
		rn
)
select * from Paged p where p.rn > @PageNumber*@PageSize - @PageSize and p.rn <= @PageNumber*@PageSize
order by rn
option(optimize for (@n = 10000), maxdop 1);
set statistics time, xml off;
drop table #filter;
go

Время

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 207 ms.
SQL Server Execution Times:
CPU time = 62 ms, elapsed time = 170 ms.

Планы:

11

Как видно из планов, в случае диапазона, выбирается сканирование, а в случае точечного поиска — поиск по индексу. Время в обоих случаях сравнимое.
Если выбранный диапазон сам по себе тоже довольно большой и зависит от выбираемой страницы, я бы рекомендовал скомбинировать этот способ с методом Key Seek, описанным ранее.

На этом все. Спасибо за чтение.

 
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
Комментарии к записи Оконные функции и row goal отключены  comments