Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Методы поиска интервала дат  [new]
Serg_77m
Member

Откуда: Донецк
Сообщений: 237
Провёл небольшое исследование по поиску наилучшего метода для поиска интервала дат.

Задача. Есть некая таблица, в которой имеется два поля, образующие интервал дат. Нужно быстро находить записи, для которых некоторая заданная дата попадает в интервал. Имена полей: начальная дата — DATN, конечная — DATK. Конечная дата в интервал не включается. DATK может быть NULL, это означает, что интервал разомкнутый, конец интервала — бесконечность.

Тестовый набор данных. Первоначально для тестирования взял реальную таблицу о перемещении сотрудников по должностям. Интервалы дат бывают о нескольких дней до десятилетий. Однако, она оказалась слишком маленькой, всего 3600 записей, поэтому построил тестовый набор на случайных данных. Начальную дату предположил распределённой равномерно в диапазоне от 01.01.1970 до 09.11.2014 (всего 16384 дней), длина интервала распределена неравномерно: чем длиннее интервал, тем реже он встречается. Функцию неравномерности постарался скопировать с реальных данных. Если конечная дата оказывалась больше 26.11.2014 – ставил NULL. Всего в тестовом наборе 40 тыс. записей, размер таблицы — 872 k.
+ Скрипт
use tempdb
go
-- Таблица с тестовым набором данных
create table dbo.intervals (
  ID int identity primary key,
  DATN smalldatetime not null,
  DATK smalldatetime,
  FLAG tinyint,
  DATK1 as isnull(DATK,convert(smalldatetime,'20790606',112))
)
go
-- Таблица чисел от 0 до 2047
create table dbo.nums1 (N int primary key)
insert into dbo.nums1 (N) values (0)
insert into dbo.nums1 (N) select N+1 from dbo.nums1
insert into dbo.nums1 (N) select N+2 from dbo.nums1
insert into dbo.nums1 (N) select N+4 from dbo.nums1
insert into dbo.nums1 (N) select N+8 from dbo.nums1
insert into dbo.nums1 (N) select N+16 from dbo.nums1
insert into dbo.nums1 (N) select N+32 from dbo.nums1
insert into dbo.nums1 (N) select N+64 from dbo.nums1
insert into dbo.nums1 (N) select N+128 from dbo.nums1
insert into dbo.nums1 (N) select N+256 from dbo.nums1
insert into dbo.nums1 (N) select N+512 from dbo.nums1
insert into dbo.nums1 (N) select N+1024 from dbo.nums1
go
-- Генерация тестовых данных
insert into intervals (DATN,DATK,FLAG)
select
  dateadd(d,INT_BEGIN,'19700101') as DATN,
  case when INT_BEGIN+INT_LEN<16400 then dateadd(d,INT_BEGIN+INT_LEN,'19700101') end as DATK,
  FLAG1
from (
  select
    cast(substring(ID1,1,2) as int) & 0x3FFF as INT_BEGIN,
    round(500*(power(1e0-cast(substring(ID1,3,2) as int)/65536e0,-0.56455)-1),0) INT_LEN,
    cast(substring(ID1,5,1) as tinyint) & 
    cast(substring(ID1,6,1) as tinyint) as FLAG1
  from (
    select cast(newid() as binary(16)) as ID1
    from NUMS1 a,NUMS1 b
    where a.N<1000 and b.N<40
  ) a
) a
go


Методы поиска. Всего протестировал 4 метода.
1. Индекс по (DATK) include (DATN). Вернее, вместо DATK подставил вычисляемое поле isnull(DATK,'20790606') для обработки разомкнутых интервалов. Размер индекса — 632 k.
+ Скрипт
-- Простой индекс для поиска
create index ix_intervals on dbo.intervals (DATK1) include (DATN)
go


2. Полное перечисление дат. Индексированное представление, в котором на каждую запись тестового набора перечислены все даты, попадающие в интервал. Здесь разомкнутые интервалы представляют проблему, т.к, плодят очень много записей. В качестве заглушки здесь подставил дату 31.12.2019. В реальной базе её можно сдвигать раз в год или ещё реже, и перестраивать представление. Всего в представлении получилось ~24 млн. записей, размер — 410 M.
+ Скрипт
-- Вторая таблица чисел от 0 до 2047
create table dbo.nums2 (N int primary key)
insert into dbo.nums2 (N) select N from dbo.nums1
go

-- Полное перечисление дат
create view dbo.view_intervals with schemabinding as
select a.ID,dateadd(d,b.N*1000+c.N,a.DATN) as DATI
from dbo.intervals a
  inner join dbo.nums1 b on b.N between 0 and
        (datediff(d,DATN,isnull(a.DATK,convert(smalldatetime,'20191231',112)))-1)/1000
  inner join dbo.nums2 c on c.N between 0 and
        case when datediff(d,DATN,isnull(a.DATK,convert(smalldatetime,'20191231',112)))-b.N*1000 >= 999
             then 999
             else datediff(d,DATN,isnull(a.DATK,convert(smalldatetime,'20191231',112)))-b.N*1000-1
        end
go
create unique clustered index ix_view_intervals on view_intervals (DATI,ID)
go


3. Многоуровневое перечисление дат.
+ Скрипт
-- Вспомогательные таблицы для построения многоуровневого представления
create table dbo.nums3 (
  LVL tinyint primary key,
  LSIZE tinyint,
  LMAX int,
  DATELIM smalldatetime
)
insert into nums3 (LVL,LSIZE,LMAX,DATELIM) values (0,1,255, '20191231')
insert into nums3 (LVL,LSIZE,LMAX,DATELIM) values (1,1,255, '20191231')
insert into nums3 (LVL,LSIZE,LMAX,DATELIM) values (2,1,5,   '20191231')
insert into nums3 (LVL,LSIZE,LMAX,DATELIM) values (3,1,255, '20191231')
go
create table dbo.nums4 (N tinyint primary key)
insert into nums4 (N) values (0)
insert into nums4 (N) values (1)
go

-- Многоуровневое представление
create view dbo.view_multilevel with schemabinding as
select a.ID,b.LVL,
  case when c.N=0 then substring(cast(DATN as binary(4)),1,b.LVL) 
                  else substring(cast(isnull(DATK,DATELIM) as binary(4)),1,b.LVL) 
  end + substring(cast(d.N as binary(2)),3-b.LSIZE,b.LSIZE) as DATB
from dbo.intervals a
  cross join dbo.nums3 b
  inner join dbo.nums4 c on c.N between 0 and
    case when substring(cast(DATN as binary(4)),1,LVL)=substring(cast(isnull(DATK,DATELIM) as binary(4)),1,LVL) 
         then 0 else 1 end
  inner join dbo.nums1 d on d.N between
    case when c.N=1 then 0
         when substring(cast(DATN as binary(4)),b.LVL+1+b.LSIZE,4)<>0x 
           then substring(cast(DATN as binary(4)),b.LVL+1,b.LSIZE)+1
         when substring(cast(DATN as binary(4)),1,LVL)<>substring(cast(isnull(DATK,DATELIM) as binary(4)),1,LVL)
             and substring(cast(DATN as binary(4)),b.LVL+1,b.LSIZE)=0x 
           then null
         else substring(cast(DATN as binary(4)),b.LVL+1,b.LSIZE)
    end
    and
    case when c.N=1 or substring(cast(DATN as binary(4)),1,b.LVL)=substring(cast(isnull(DATK,DATELIM) as binary(4)),1,b.LVL) 
         then substring(cast(isnull(DATK,DATELIM) as binary(4)),b.LVL+1,b.LSIZE)-1
         else b.LMAX
    end
where cast(DATN as binary(4))<cast(isnull(DATK,DATELIM) as binary(4))   
go
create unique clustered index ix_1 on view_multilevel (DATB,LVL,ID)
go
-- Функция поиска
create function dbo.fn_multilevel_seek(@date smalldatetime)
returns table as return
select ID
from view_multilevel with (noexpand)
where DATB=substring(cast(@date as binary(4)),1,1) and LVL=0
union all
select ID
from view_multilevel with (noexpand)
where DATB=substring(cast(@date as binary(4)),1,2) and LVL=1
/*
-- Эти ветви используются, если нужен поиск по времени
union all
select ID
from view_multilevel with (noexpand)
where DATB=substring(cast(@date as binary(4)),1,3) and LVL=2
union all
select ID
from view_multilevel with (noexpand)
where DATB=substring(cast(@date as binary(4)),1,4) and LVL=3
*/
go

Несмотря на громоздкий вид, идея простая. Начальная и конечная дата интервала переводится в binary(4), получается, к примеру, интервал: 0x7D560000 – 0x816A0000. В представлении на эту запись создаются ключи: 0x7D56, 0x7D57, 0x7D58, …, 0x7DFF, 0x7E, 0x80, 0x8100, 0x8102, …, 0x8169. Т.е, сокращённое перечисление дат в двоичном формате. У такого представления получилось ~7 млн. записей, размер — 140 M.

4. Гибрид. На каждую исходную запись создаётся несколько записей для каждого года, полностью или не полностью попадающего в интервал. Индекс строится по year(...)+DATK. Это должно несколько ускорить поиск по сравнению с простым индексом по DATK. В этом представлении получилось 106 тыс. записей, размер — 2.6 M.
+ Скрипт
-- Гибридное представление
create view dbo.view_hybrid with schemabinding as
select a.ID,b.N as YM,
  a.DATN,
  isnull(a.DATK,convert(smalldatetime,'20790606',112)) as DATK
from dbo.intervals a
  inner join dbo.nums1 b on b.N between year(a.DATN)-1900 and isnull(year(a.DATK),2019)-1900
go
create unique clustered index ix1 on view_hybrid (YM,DATK,ID)
go

-- Функция поиска
create function dbo.fn_hybrid_seek(@date smalldatetime)
returns table as return
select ID
from view_hybrid with (noexpand)
where YM=year(@date)-1900 and DATN<=@date and DATK>@date
go


Тестирование поиска. Для тестирования была создана табличная переменная, в которую было помещено 2048 случайных дат. В первом тесте распределение дат создаётся равномерным в диапазоне 01.01.1970- 09.11.2014. Однако, реально запросы к более поздним датам бывают чаще, чем к более ранним. Закон распределения мне неизвестен, было протестировано два: обратно-квадратичный и обратно-экспоненциальный.

Тестирование проводилось на старом ноутбуке Celeron M, 1,4 GHz, 2G RAM.
SQL Server 2008 R2 Express x86, лимит памяти для SQL-сервера установлен в 600 M.
Статистика по CPU и IO получена трассировкой.

Равномерное распределение
+ Скрипт
declare @test table (DAT1 smalldatetime)

-- Равномерное распределение
insert into @test (DAT1)
select dateadd(d,floor(cast(substring(cast(newid() as binary(16)),1,2) as int)/4e0),'19700101')
from nums1

-- Простой поиск по индексу
select *,
  (select count(*) from intervals z where z.DATK1>a.DAT1 and z.DATN<=a.DAT1) as C1
from @test a
order by DAT1

-- Полное перечисление дат
select *,
  (select count(*) from view_intervals z with (noexpand) where z.DATI=a.DAT1) as C1
from @test a
order by DAT1

-- Многоуровневое представление
select *,
  (select count(*) from fn_multilevel_seek(a.DAT1)) as C1
from @test a
order by DAT1

-- Гибридный индекс
select *,
  (select count(*) from fn_hybrid_seek(a.DAT1)) as C1
from @test a
order by DAT1

go

Метод поискаTime totalTime CPUIO Reads
Индекс7,7527,14189878
Полное перечисление7,7290,78113865
Многоуровневое перечисление1,0220,89120574
Гибрид1,1471,04717358


Обратно-экспоненциальное распределение
+ Скрипт
declare @test table (DAT1 smalldatetime)

-- Обратно-экспоненциальное распределение
insert into @test (DAT1)
select dateadd(d,floor(16500+1000*log(1-cast(substring(cast(newid() as binary(16)),1,2) as int)/65536e0)),'19700101')
from nums1

-- Простой поиск по индексу
select *,
  (select count(*) from intervals z where z.DATK1>a.DAT1 and z.DATN<=a.DAT1) as C1
from @test a
order by DAT1

-- Полное перечисление дат
select *,
  (select count(*) from view_intervals z with (noexpand) where z.DATI=a.DAT1) as C1
from @test a
order by DAT1

-- Многоуровненый индекс
select *,
  (select count(*) from fn_multilevel_seek(a.DAT1)) as C1
from @test a
order by DAT1

-- Гибридный индекс
select *,
  (select count(*) from fn_hybrid_seek(a.DAT1)) as C1
from @test a
order by DAT1
go

Метод поискаTime totalTime CPUIO Reads
Индекс1,8171,65720816
Полное перечисление2,0270,76514608
Многоуровневое перечисление1,251,01621427
Гибрид1,3281,07817998


Обратно-квадратичное распределение
+ Скрипт
declare @test table (DAT1 smalldatetime)

-- Обратно-квадратичное распределение
insert into @test (DAT1)
select dateadd(d,16500-floor(100*(power(1-cast(substring(cast(newid() as binary(16)),1,2) as int)/65536e0,-0.5)-1)),'19700101')
from nums1

-- Простой поиск по индексу
select *,
  (select count(*) from intervals z where z.DATK1>a.DAT1 and z.DATN<=a.DAT1) as C1
from @test a
order by DAT1

-- Полное перечисление дат
select *,
  (select count(*) from view_intervals z with (noexpand) where z.DATI=a.DAT1) as C1
from @test a
order by DAT1

-- Многоуровненый индекс
select *,
  (select count(*) from fn_multilevel_seek(a.DAT1)) as C1
from @test a
order by DAT1

-- Гибридный индекс
select *,
  (select count(*) from fn_hybrid_seek(a.DAT1)) as C1
from @test a
order by DAT1
go

Метод поискаTime totalTime CPUIO Reads
Индекс1,1560,96812745
Полное перечисление1,0240,81314695
Многоуровневое перечисление1,0930,96920672
Гибрид1,1561,01515504


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

В случае неравномерных распределений поиск по индексу выглядит намного лучше (а в случае квадратичного — вообще лучше всех по IO), и вообще разница между методами поиска оказывается невелика. Полное перечисление не даёт особых преимуществ, многоуровневое представление — тоже. Можно ограничиться простым индексом.

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

+ Очистка
drop function dbo.fn_hybrid_seek
drop function dbo.fn_multilevel_seek
drop view dbo.view_hybrid
drop view dbo.view_multilevel
drop view dbo.view_intervals
drop table dbo.nums1
drop table dbo.nums2
drop table dbo.nums3
drop table dbo.nums4
drop table dbo.intervals
16 ноя 15, 19:06    [18425851]     Ответить | Цитировать Сообщить модератору
 Re: Методы поиска интервала дат  [new]
invm
Member

Откуда: Москва
Сообщений: 9827
Serg_77m,

http://sqlmag.com/t-sql/sql-server-interval-queries
17 ноя 15, 00:13    [18426896]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить