Я буду расматривать вопрос об оптимизации некоторых запросов вида: select * from <TableName> where <ColumnName> like '%data%'. Здесь <TableName> обозначает имя таблицы, <ColumnName> - это имя текстового столбца. Запрос ищет строки, в которых встречается заданная подстрока. Также мы рассмортрим вопрос об ускорении работы запросов, где условие where имеет вид:
where <ColumnName> like '%data1%data2%'.
То есть, запрос ищет строку в которой встречаются уже 2 подстроки, причем одна следует за второй.
Сразу оговорюсь, что в этой статье будет идти речь об оптимизации высокоселективных запросов указанного типа. То есть в ситуации, когда <TableName> очень большая таблица, а запрос возвращает несколько десятков или несколько сотен строк. Данная оптимизация чрезвычайно существенна, поскольку условие like заставляет оптимизатор выполнять полное сканирование всей таблицы, делая запрос очень долгим и нагружая сервер. Это, в частности, не позволит организовать работу в многопользовательской среде, где много пользователей одновременно запускают такие запросы. Поскольку искомая подстрока может быть в середине столбца, то классический индекс по столбцу <ColumnName> не поможет. Также мы не рассматриваем случай, когда столбец содержит текст с предложением, а поиск ведется по слову или группе слов, входящих в предложение (в этом случае можно было использовать полнотекстовый индекс).
Приступим к постановке задачи. Создадим базу данных, предназначенную для банковской информационной системы:
create database AccountsData
on primary
(
name = Data,
filename = 'D:\AccData.mdf',
size = 20 Mb,
filegrowth = 500 Mb,
maxsize = unlimited
)
log on
(
name = AccLog,
filename = 'D:\AccLog.ldf',
size = 10 Mb,
filegrowth = 500 Mb,
maxsize = unlimited
)
go
alter database AccountsData set recovery simpleuse AccountsData
В коде выше для базы данных я установил параметр роста файлов равным 500 Мб. Это важно, поскольку далее будет исполняться код, в котором будут делаться циклические вставки, при которых база данных будет периодически расширяться. Нужно пытаться снизить время задержек кода, связанное с необходимостью расширения. Это касается и файла журнала транзакций, поскольку все операции логируются. К тому же для журнала транзакций в отличие от файлов данных нет быстрой инициализации файла (необходимо обнуление перед началом использования дискового пространства). В базе данных создадим таблицу для хранения лицевых номеров счетов:
create table dbo.Accounts
(
iRowId int identity ( 1, 1 ) not null,vcAccount char ( 20 ) not null,
constraint PK_Accounts_iRowId primary key clustered ( iRowId asc ) on [PRIMARY]
) on [PRIMARY]
Предположим, что таблица dbo.Accounts хранит лицевые счета крупного банка, который имеет представительства во многих точках мира, имеет десятки миллионов клиентов. Предположим, что по этой причине в таблице dbo.Accounts порядка 150 миллионов записей. Также, для простоты, будем предполагать, что счета предназначены только для валют (без драгоценных металлов). Код ниже генерирует случайные записи для таблицы в количестве примерно 150 миллионов:
set nocount on
declare @k int, @num int = 60000
set @k = 1
while @k <= @num
begin
insert into dbo.Accounts with ( tablock ) ( vcAccount )
select left (
replace ( cast ( binary_checksum ( newid () ) as varchar ( 100 ) ), '-', '' ) +
replace ( cast ( binary_checksum ( newid () ) as varchar ( 100 ) ), '-', '' ) +
replace ( cast ( binary_checksum ( newid () ) as varchar ( 100 ) ), '-', '' ) +
replace ( cast ( binary_checksum ( newid () ) as varchar ( 100 ) ), '-', '' )
, 20 )
from master.dbo.spt_values
if @k % 100 = 0
begin
dbcc shrinkfile ( 2 ) with no_infomsgs
checkpoint
dropcleanbuffers with no_infomsgs
end
set @k += 1
end
Код отработал примерно за 20 мин., объем таблицы составил примерно 4.7 Гб. Тестирование проводится на моем компьютере с операционной системой Win7 x64. Объем оперативной памяти 4 Гб, один четырехядерный процессор. Этот компьютер слабый для тех объемов, с которыми я буду работать, поэтому в коде выше и в некоторых кодах ниже я буду выполнять принудительный checkpoint, усечение журнала транзакций, очистку буферного пула на итерациях циклов. Это делается на всякий случай для того, чтобы избежать переполнения журнала транзакций, проблем дефицита памяти.
Будем решать задачу поиска лицевых счетов, которые содержат в своей записи заданную подстроку или несколько подстрок. Возможно, что рассматриваемая задача не будет востребована именно в такой постановке для подобной таблицы с лицевыми номерами, но я хотел в первую очередь показать метод, для оптимизации высоко селективных запросов с условием like. Эту методику можно применять для любого текстового столбца таблицы, если его длина глобально ограничена.
Основная идея состоит в аппроксимации, сужении диапазона поиска. То есть для запроса с условием:
where <ColumnName> like '%data%'
сделать так, чтобы быстро из 150 млн. записей извлечь, например, несколько десятков или сотен записей, которые содержат все iRowId, удовлетворяющие условие where. Среди этих нескольких сотен уже можно гораздо быстрее выполнить поиск, применяя намного меньшее число операций ввода-вывода.
Для реализации этого плана мы будем хранить все подстроки определенной длины для каждой строки из таблицы dbo.Accounts. То есть у нас будет таблица с идентификатором подстроки и столбцов iRowId. Это позволит по заданой подстроке искать все iRowId, которые содержат эту подстроку.
Здесь надо не ошибиться с выбором длины этой подстроки. Например, если выбрать длину 5, то этого будет недостаточно. Поскольку в dbo.Accounts 150 млн. записей, а данные сгенерированы случайным образом, то для заданной подстроки из 5 символов найдется порядка 30 тыс. строк, содержащих заданную подстроку. В результате для каждой их этих 30 тысяч случайных iRowId надо будет искать лицевой номер. Для этого будет использоваться loop join, который приведет к большому числу случайных движений головки жесткого диска. Из-за этих случайных операций чтения, скорость работы такого запроса будет сопоставима с обычным сканирование для dbo.Accounts с условием like. Здесь есть аналогия со сравнением производительности между сканироанием кластерного индекса и поиску по непокрывающему некластерному индексу.
Поэтому в качестве длины подстроки возьмем число 8. Создадим и наполним таблицу с подстроками длины 8.
create table dbo.Symbols
(
iSymId int identity ( 1, 1 ) not null,
vcSym char ( 8 ) not null,
constraint PK_Symbols_iSymId primary key clustered ( iSymId asc ) on [PRIMARY],
constraint AK_Symbols_vcSym unique nonclustered ( vcSym asc ) on [PRIMARY]
) on [PRIMARY]
;with Nums
as
(
select id
from
(
values ( '0' ), ( '1' ), ( '2' ), ( '3' ), ( '4' ), ( '5' ), ( '6' ), ( '7' ), ( '8' ), ( '9' )
) data ( id )
)
insert into dbo.Symbols with ( tablock ) ( vcSym )
select num1.id + num2.id + num3.id + num4.id + num5.id + num6.id + num7.id + num8.id
from
Nums num1
cross join
Nums num2
cross join
Nums num3
cross join
Nums num4
cross join
Nums num5
cross join
Nums num6
cross join
Nums num7
cross join
Nums num8
Код отработал за 33 мин., вставив 100 млн. записей. Размер таблицы примерно 3.7 Гб.
Теперь создадим таблицу, которая будет хранить информацию о подстроках номеров счетов. При этом, что очень важно, мы будем дополнительно хранить номера, начиная с которых в строке начинается подстрока. Это понадобится в дальнейшем для оптимизации запросов с условием like вида where <ColumnName> like '%data1%data2%'. Код на создание таблицы dbo.StrStorage:
create table dbo.StrStorage( iSymId int not null,
) on [PRIMARY]
Пока не создаются индексы, поскольку записей в таблице будет много, и дешевле будет сначала наполнить таблицу, а затем построить необходимые индексы. Для каждого номера счета в таблицу dbo.StrStorage будут вставлены все возможные подстроки счета длины 8. Для счета с длиной 20 символов таких подстрок 20 - 8 + 1 = 13. То есть в таблице dbo.StrStorage будет 13 * <Число записей в dbo.Accounts> = примерно 2 миллиарда строк! Код ниже выполняет вставку в таблицу dbo.StrStorage:
declare @cur int, @step int = 5000000, @num int = 1
set @cur = 1
set @num = 1
while @num <> 0
begin
insert into dbo.StrStorage with ( tablock ) ( iSymId, iNumId, iRowId )
select sym.iSymId, dat.id, acc.iRowId
from
dbo.Accounts acc
cross join
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ), ( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) dat ( id )
inner join
dbo.Symbols sym on substring ( acc.vcAccount, dat.id, 8 ) = sym.vcSym
where iRowId >= @cur and iRowId < @cur + @step
set @num = @@rowcount
set @cur += @step
dbcc shrinkfile ( 2 ) with no_infomsgs
checkpoint
dbcc dropcleanbuffers with no_infomsgs
end try
begin catch
print error_message ()
end catch
end
В коде выше записи из dbo.Accounts обрабатываются порциями по 5 миллионов, чтобы избежать переполнения жрнала транзакций. Код работал примерно 3 часа.
Теперь создадим 2 необходимых индекса:
create unique clustered index IX_iSymId_iNumId_iRowId on dbo.StrStorage ( iSymId asc, iRowId asc, iNumId asc ) on [PRIMARY]create unique nonclustered index IX_iRowId_iNumId_iSymId on dbo.StrStorage ( iRowId asc, iNumId asc, iSymId asc ) on [PRIMARY]
Индексы создавались 19 часов! В результате объем таблицы dbo.StrStorage возрос до 68.9. Гб.
Теперь таблица dbo.StrStorage хранит информацию обо всех подстроках длины 8 в таблице dbo.Accounts. Помимо этого есть возможность искать счета, содержащие заданные подстроки, длина которых больше 8 символов. Единственное, что мы не учитываем, так это возможность поиска счетов, содержащих подстроки среди последних 7 символов в номерах счетов. Однако у таких подстрок длина заведомо меньше 8, а как мы уже отмечали селективность запросов к dbo.StrStorage, при длине подстроки меньше 8, является низкой. Поэтому для условий вида " where <ColumnName> like '%data%' " мы будем рассматривать только случай, когда длина строки data не меньше 8. Чуть позже мы учтем и последние 7 символов.
Приступим к эксперименту. Напишем запрос вида:
dbcc dropcleanbuffers
select *
from dbo.Accounts
where vcAccount like '%12345678%'
Отмечу, что перед каждым запросом делается очистка буферного пула для того, чтобы скорость запроса не выростала просто за счет закэшированных страниц. Запрос выше работал 1 мин. 25 сек, вернув 25 строк. Если сразу после первого запуска запустить этот запрос повторно, уже без очистки буферного пула, то время его работы не уменьшится, что не удивительно: делается полное сканирование таблицы, памяти на кэширование всех страниц не хватит. Ясно, что помимо медленной скорости этот запрос не подходит для работы в многопользовательской среде, сервер не справится с нагрузкой.
Теперь выполним запрос на основе таблицы dbo.StrStorage, который вернет те же записи:
dbcc dropcleanbuffersselect store.iRowId, acc.vcAccount
from
dbo.Symbols sym
inner join
dbo.StrStorage store with ( nolock ) on
store.iSymId = sym.iSymId and
sym.vcSym like '12345678%'
inner join
dbo.Accounts acc on store.iRowId = acc.iRowId
Запрос отработал за 0.8 сек., то есть скорость его работы выросла более чем в 100 раз! Поскольку он возвращает небольшое число записей, то его выполение будет быстрым и на холодном кэше. Запрос можно слегка модифицировать, чтобы делать поиски на подстроках, длина которых больше 8. Например, так ищутся записи, содержащие подстроку 123456789:
dbcc dropcleanbuffers
select store.iRowId, acc.vcAccount
from
dbo.Symbols sym
inner join
dbo.StrStorage store with ( nolock ) on
store.iSymId = sym.iSymId and
sym.vcSym like '12345678%'
inner join
dbo.Accounts acc on store.iRowId = acc.iRowId
where charindex ( '123456789', acc.vcAccount, store.iNumId ) <> 0
Поскольку без условия where возвращается и так мало записей, то условие where не замедляет запрос, и он по прежнему работает менее 1 секунды.
Теперь расмотрим такой запрос:
dbcc dropcleanbuffers
select *
from dbo.Accounts
where vcAccount like '%23456789%34611558%'
Здесь опять-таки время выполнения составляет более минуты. И никакого кэширования.
Напомним, что в таблице dbo.StrStorage есть столбец iNumId, который показывает с какого места начинается подстрока. Тем самым, работая со строкой вида %23456789%34511557%, можно разбить ее на 2 подстроки. Каждая подстрока имеет длину не меньше 8. И номер, с которой начинается вторая строка больше либо равен чем номер, с которой начинается первая подстрока плюс длина первой подстроки. Таким образом можно переписать запрос в таком виде:
dbcc dropcleanbuffers
select storeFir.iRowId, acc.vcAccount
from
dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '23456789%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.StrStorage storeSec with ( nolock ) on
storeSec.iRowId = storeFir.iRowId and
storeFir.iNumId + 8 <= storeSec.iNumId
inner join
dbo.Symbols symSec on
storeSec.iSymId = symSec.iSymId and
symSec.vcSym like '34611558%'
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
В отличие от предыдущих запросов к таблице dbo.StrStorage, в этом запросе помимо поиска по кластерному индексу dbo.StrStorage используется поиск по некластерному индексу на dbo.StrStorage. Благодаря высокой селективности, запрос также работает менее одной секунды.
Если запрос с условием like содержит условие вида <ColumnName> like '%data1%data2%', то при достаточной длине подстроки data1 (в нашем случае не меньше 8) запрос будет возвращать малое число записей даже при небольшой длине подстроки data2 (например состоящей лишь из одного символа). Например, мы хотим ускорить такой запрос:
select *
from AccountsData.dbo.Accounts
where vcAccount like N'%12345678%6%'
Он работает долго (2 мин. 4 сек.). Запрос, который мы написали выше с использованием таблицы dbo.StrStorage отработал всего за 3 секунды (когда вторая подстрока состоит из одного символа), однако он может не вернуть всех записей, поскольку информация о подстроках vcAccount, которые начинаются в последних семи символах vcAccount никак не хранится. Ведь в таблице dbo.StrStorage есть данные лишь о подстроках длины 8. Поэтому создадим таблицу для хранения инфрмации о так называемых концевых подстроках столбца vcAccount. То есть данные о последних 7-и, 6-и, 5-и, 4-х, 3-х, 2-х и 1-ом символах. Сперва создадим таблицу, в которой будут идентификаторы всех подстрок длины не большей чем 7:
create table dbo.SmallSymbols
( iSmallSymId int identity ( 1, 1 ) not null,
vcSmallSym varchar ( 7 ) not null,
constraint PK_SmallSymbols_iSmallSymId primary key clustered ( iSmallSymId asc )
on [PRIMARY],
constraint AK_SmallSymbols_vcSmallSym unique nonclustered ( vcSmallSym asc )
on [PRIMARY]
) on [PRIMARY]
За 7 минут можно наполнить эту таблицу с помощью такого кода:
;
with Nums
as( select id
from
(
values ( '0' ), ( '1' ), ( '2' ), ( '3' ), ( '4' ), ( '5' ),
( '6' ), ( '7' ), ( '8' ), ( '9' )
) data ( id )
)insert into dbo.SmallSymbols with ( tablock ) ( vcSmallSym )
select id
from Nums
union all
select num1.id + num2.id
from Nums num1 cross join Nums num2
union all
select num1.id + num2.id + num3.id
from Nums num1 cross join Nums num2 cross join Nums num3
union all
select num1.id + num2.id + num3.id + num4.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4
union all
select num1.id + num2.id + num3.id + num4.id + num5.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4 cross join Nums num5
union all
select num1.id + num2.id + num3.id + num4.id + num5.id + num6.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4 cross join Nums num5 cross join Nums num6
union all
select num1.id + num2.id + num3.id + num4.id + num5.id + num6.id + num7.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4 cross join Nums num5 cross join Nums num6 cross join Nums num7
В таблице чуть больше 11 млн. записей, ее объем около 0.5 Гб. Теперь построим таблицу, в которой будет информация о концевых подстроках:
create table dbo.SmallStrStorage
(
iSmallSymId int not null,
iRowId int not null
)
В таблице не хранится информация о том, с какого места начинается подстрока. Дело в том, что, поскольку подстрока концевая, это место равно длине счета (20) минус длина подстроки. Таблица наполняется таким кодом:
declare @curid int = 1, @step int = 5000000, @num int = 1
while @num <> 0
begin insert into dbo.SmallStrStorage ( iSmallSymId, iRowId )
select sym.iSmallSymId, acc.iRowId
from
dbo.Accounts acc
cross join
(
select id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 )
) id ( id )
) id
inner join
dbo.SmallSymbols sym on right ( acc.vcAccount, id.id ) = sym.vcSmallSym
where acc.iRowId >= @curid and acc.iRowId < @curid + @step
begin try
dbcc shrinkfile ( 2 ) with no_infomsgs
checkpoint
end try
begin catch
print error_message ()
end catch
set @num = @@rowcount
set @curid += @step
end
Код работает 2 часа, вставляет окло 1 млрд. записей. Создадим на таблице 2 индекса:
alter table dbo.SmallStrStorage add constraint PK_iSmallSymId_iRowId primary key clustered ( iSmallSymId asc, iRowId asc ) on [PRIMARY]
create unique nonclustered index IX_iRowId_iSmallSymId on dbo.SmallStrStorage ( iRowId asc, iSmallSymId asc ) on [PRIMARY]
Индексы создались примерно через 13.5 часа. Объем таблицы составляет 31 Гб. Теперь для точной оптимизации запроса
select *
from AccountsData.dbo.Accounts
where vcAccount like N'%12345678%6%'
можно написать запрос:
select storeFir.iRowId, acc.vcAccount
from dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '23456789%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.StrStorage storeSec with ( nolock ) on
storeSec.iRowId = storeFir.iRowId and
storeFir.iNumId + 8 <= storeSec.iNumId
inner join
dbo.Symbols symSec on
storeSec.iSymId = symSec.iSymId and
symSec.vcSym like '6%'
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
union all
select storeFir.iRowId, acc.vcAccount
from dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '12345678%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.SmallStrStorage storeSec with ( nolock ) on
storeSec.iRowId = storeFir.iRowId and
storeFir.iNumId + 8 <= 17--это просто 20 - len ( '6' )
inner join
dbo.SmallSymbols symSec on
storeSec.iSmallSymId = symSec.iSmallSymId and
symSec.vcSmallSym like '6%'
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
Запрос отработал 3 секунды. В плане выполнения везде используются поиски по построенным индексам.
В приведенном выше запросе для поиска строк вида '%data1%data2%' сначала ищуются строки вида '%data1%', а затем результат джойнится на запрос, возвращающий строки вида '%data2%'. При этом благодаря столбцу iNumId есть возможность наложить в джойне условие, что NumId для запроса, возвращающего строки '%data2%', больше или равен чем сумма iNumId для запроса, возвращающего строки '%data1%', и длины строки data1. Как раз здесь используется некластерный индекс. Эта техника может быть обобщена и позволяет искать строки вида '%data_1%data_2%data_2%...%data_k%'. То есть найдя строки вида '%data_1%data_2%...data_i%', можно заджойнить этот результат на запрос, возвращающий строки вида '%data_{i+1}%' и наложить в джойне условие на то, что iNumId для строк '%data_{i+1}%' больше или равен чем сумма iNumId для '%dayta_i%' и длины строки data_i.
Посмотрим насколько существенно условие, при котором подстрока должна быть не менее 8 символов длиной при оптимизации запроса с условием <ColumnName> like '%data%'. Мы убедились, что когда длина подстроки не меньше 8, то запрос работает менее 1 секунды. Проверим скорость запроса, когда длина подстроки data меньше 8. Напишем такой запрос:
dbcc dropcleanbuffers
select storeFir.iRowId, acc.vcAccount
from dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '...%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
Когда в запросе идет поиск по подстроке 1234567, то запрос работает по прежнему достаточно быстро - 4 секунды, позвращая около 240 записей. Когда длина строки снижается до 6, то запрос работает уже 36 секунд, возвращая несколько тысяч записей. Но это время все равно почти в 3 раза быстрее чем при работе запроса с условием like. И лишь когда длина строки становится равной 5, запрос работает примерно то же время, в течение которого работает обычный запрос с условием like. При этом возвращается около 30 тыс. строк. Однако, если такой запрос запустить повторно без очистки кэша, то он отработает уже за менее чем 1 секунду. Поэтому можно утверждать, что оптимизирован гораздо более широкий класс запросов.
Если же требуется, чтобы быстро работал и запрос, который ищет строки, с подстрокой длины 5, то можно сделать таблицу dbo.StrStorage еще более избыточной. То есть добавить в нее столбец с номером счета. Посмотрим как это повысит производительность. Создадим новую таблицу:
Осталось обсудить как сохранять данную структуру при операциях вставки, обновления и удаления для таблицы dbo.Accounts. Будем поддерживать только таблицу dbo.StrStorage (для dbo.FullStrStorage все делается аналогично). Для поддержки целостности данных необходимо создать 3 триггера:
create trigger dbo.AccountsTrUpd on dbo.Accounts for updateЕсли запрос с условием like содержит условие вида <ColumnName> like '%data1%data2%', то при достаточной длине подстроки data1 (в нашем случае не меньше 8) запрос будет возвращать малое число записей даже при небольшой длине подстроки data2 (например состоящей лишь из одного символа). Например, мы хотим ускорить такой запрос:
select *
from AccountsData.dbo.Accounts
where vcAccount like N'%12345678%6%'
Он работает долго (2 мин. 4 сек.). Запрос, который мы написали выше с использованием таблицы dbo.StrStorage отработал всего за 3 секунды (когда вторая подстрока состоит из одного символа), однако он может не вернуть всех записей, поскольку информация о подстроках vcAccount, которые начинаются в последних семи символах vcAccount никак не хранится. Ведь в таблице dbo.StrStorage есть данные лишь о подстроках длины 8. Поэтому создадим таблицу для хранения инфрмации о так называемых концевых подстроках столбца vcAccount. То есть данные о последних 7-и, 6-и, 5-и, 4-х, 3-х, 2-х и 1-ом символах. Сперва создадим таблицу, в которой будут идентификаторы всех подстрок длины не большей чем 7:
create table dbo.SmallSymbols
( iSmallSymId int identity ( 1, 1 ) not null,
vcSmallSym varchar ( 7 ) not null,
constraint PK_SmallSymbols_iSmallSymId primary key clustered ( iSmallSymId asc )
on [PRIMARY],
constraint AK_SmallSymbols_vcSmallSym unique nonclustered ( vcSmallSym asc )
on [PRIMARY]
) on [PRIMARY]
За 7 минут можно наполнить эту таблицу с помощью такого кода:
;
with Nums
as( select id
from
(
values ( '0' ), ( '1' ), ( '2' ), ( '3' ), ( '4' ), ( '5' ),
( '6' ), ( '7' ), ( '8' ), ( '9' )
) data ( id )
)insert into dbo.SmallSymbols with ( tablock ) ( vcSmallSym )
select id
from Nums
union all
select num1.id + num2.id
from Nums num1 cross join Nums num2
union all
select num1.id + num2.id + num3.id
from Nums num1 cross join Nums num2 cross join Nums num3
union all
select num1.id + num2.id + num3.id + num4.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4
union all
select num1.id + num2.id + num3.id + num4.id + num5.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4 cross join Nums num5
union all
select num1.id + num2.id + num3.id + num4.id + num5.id + num6.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4 cross join Nums num5 cross join Nums num6
union all
select num1.id + num2.id + num3.id + num4.id + num5.id + num6.id + num7.id
from Nums num1 cross join Nums num2 cross join Nums num3 cross join Nums num4 cross join Nums num5 cross join Nums num6 cross join Nums num7
В таблице чуть больше 11 млн. записей, ее объем около 0.5 Гб. Теперь построим таблицу, в которой будет информация о концевых подстроках:
create table dbo.SmallStrStorage
(
iSmallSymId int not null,
iRowId int not null
)
В таблице не хранится информация о том, с какого места начинается подстрока. Дело в том, что, поскольку подстрока концевая, это место равно длине счета (20) минус длина подстроки. Таблица наполняется таким кодом:
declare @curid int = 1, @step int = 5000000, @num int = 1
while @num <> 0
begin insert into dbo.SmallStrStorage ( iSmallSymId, iRowId )
select sym.iSmallSymId, acc.iRowId
from
dbo.Accounts acc
cross join
(
select id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 )
) id ( id )
) id
inner join
dbo.SmallSymbols sym on right ( acc.vcAccount, id.id ) = sym.vcSmallSym
where acc.iRowId >= @curid and acc.iRowId < @curid + @step
begin try
dbcc shrinkfile ( 2 ) with no_infomsgs
checkpoint
end try
begin catch
print error_message ()
end catch
set @num = @@rowcount
set @curid += @step
end
Код работает 2 часа, вставляет окло 1 млрд. записей. Создадим на таблице 2 индекса:
alter table dbo.SmallStrStorage add constraint PK_iSmallSymId_iRowId primary key clustered ( iSmallSymId asc, iRowId asc ) on [PRIMARY]
create unique nonclustered index IX_iRowId_iSmallSymId on dbo.SmallStrStorage ( iRowId asc, iSmallSymId asc ) on [PRIMARY]
Индексы создались примерно через 13.5 часа. Объем таблицы составляет 31 Гб. Теперь для точной оптимизации запроса
select *
from AccountsData.dbo.Accounts
where vcAccount like N'%12345678%6%'
можно написать запрос:
select storeFir.iRowId, acc.vcAccount
from dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '23456789%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.StrStorage storeSec with ( nolock ) on
storeSec.iRowId = storeFir.iRowId and
storeFir.iNumId + 8 <= storeSec.iNumId
inner join
dbo.Symbols symSec on
storeSec.iSymId = symSec.iSymId and
symSec.vcSym like '6%'
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
union all
select storeFir.iRowId, acc.vcAccount
from dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '12345678%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.SmallStrStorage storeSec with ( nolock ) on
storeSec.iRowId = storeFir.iRowId and
storeFir.iNumId + 8 <= 17--это просто 20 - len ( '6' )
inner join
dbo.SmallSymbols symSec on
storeSec.iSmallSymId = symSec.iSmallSymId and
symSec.vcSmallSym like '6%'
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
Запрос отработал 3 секунды. В плане выполнения везде используются поиски по построенным индексам.
В приведенном выше запросе для поиска строк вида '%data1%data2%' сначала ищуются строки вида '%data1%', а затем результат джойнится на запрос, возвращающий строки вида '%data2%'. При этом благодаря столбцу iNumId есть возможность наложить в джойне условие, что NumId для запроса, возвращающего строки '%data2%', больше или равен чем сумма iNumId для запроса, возвращающего строки '%data1%', и длины строки data1. Как раз здесь используется некластерный индекс. Эта техника может быть обобщена и позволяет искать строки вида '%data_1%data_2%data_2%...%data_k%'. То есть найдя строки вида '%data_1%data_2%...data_i%', можно заджойнить этот результат на запрос, возвращающий строки вида '%data_{i+1}%' и наложить в джойне условие на то, что iNumId для строк '%data_{i+1}%' больше или равен чем сумма iNumId для '%dayta_i%' и длины строки data_i.
Посмотрим насколько существенно условие, при котором подстрока должна быть не менее 8 символов длиной при оптимизации запроса с условием <ColumnName> like '%data%'. Мы убедились, что когда длина подстроки не меньше 8, то запрос работает менее 1 секунды. Проверим скорость запроса, когда длина подстроки data меньше 8. Напишем такой запрос:
dbcc dropcleanbuffers
select storeFir.iRowId, acc.vcAccount
from dbo.StrStorage storeFir with ( nolock )
inner join
dbo.Symbols symFir on
symFir.vcSym like '...%' and
storeFir.iSymId = symFir.iSymId
inner join
dbo.Accounts acc on storeFir.iRowId = acc.iRowId
Когда в запросе идет поиск по подстроке 1234567, то запрос работает по прежнему достаточно быстро - 4 секунды, позвращая около 240 записей. Когда длина строки снижается до 6, то запрос работает уже 36 секунд, возвращая несколько тысяч записей. Но это время все равно почти в 3 раза быстрее чем при работе запроса с условием like. И лишь когда длина строки становится равной 5, запрос работает примерно то же время, в течение которого работает обычный запрос с условием like. При этом возвращается около 30 тыс. строк. Однако, если такой запрос запустить повторно без очистки кэша, то он отработает уже за менее чем 1 секунду. Поэтому можно утверждать, что оптимизирован гораздо более широкий класс запросов.
Если же требуется, чтобы быстро работал и запрос, который ищет строки, с подстрокой длины 5, то можно сделать таблицу dbo.StrStorage еще более избыточной. То есть добавить в нее столбец с номером счета. Посмотрим как это повысит производительность. Создадим новую таблицу:
create
table dbo.FullStrStorage
(
iSymId int not null,
iNumId int not null,
iRowId int not null,
vcAccount char ( 20 ) not null
) on [PRIMARY]
Теперь таблицу требуется наполнить данными. Для этого выполним код, похожий на тот, который использовался для заполнения таблицы dbo.StrStorage:
set
nocount on
declare
@cur int, @step
int = 5000000, @num int = 1
set
@cur = 1
set
@num = 1
while
@num <> 0
begin
insert into dbo.FullStrStorage
with ( tablock ) ( iSymId, iNumId, iRowId, vcAccount )
select
sym.iSymId, dat.id, acc.iRowId, acc.vcAccount
from
dbo.Accounts
acc
cross
join
(
values
( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ), ( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
)
dat ( id )
inner
join
dbo.Symbols
sym on substring ( acc.vcAccount, dat.id, 8 ) = sym.vcSym
where
iRowId >= @cur and
iRowId < @cur +
@step
set @num = @@rowcount
set @cur += @step
begin try
dbcc
shrinkfile ( 2 ) with no_infomsgs
checkpoint
dbcc
dropcleanbuffers with no_infomsgs
end try
begin catch
print error_message ()
end catch
end
На моем компьютере код отработал примерно за 5 часов. Теперь надо создать 2 индекса:
create
unique clustered
index IX_iSymId_iNumId_iRowId on dbo.FullStrStorage ( iSymId asc, iRowId asc, iNumId asc ) on [PRIMARY]
create
unique nonclustered
index IX_iRowId_iNumId_iSymId on dbo.FullStrStorage ( iRowId asc, iNumId asc, iSymId asc ) on [PRIMARY]
Код на создание индексов отработал за 15 часов. В новой таблице как и в dbo.StrStorage примерно 1.9 млрд. записей. Общий объем 109.5 Гб. Теперь запрос по поиску записей, содержащих подстроку длины 5 (например, 12345), можно переписать так:
select
store.iRowId,
store.vcAccount
from
dbo.FullStrStorage
store
inner
join
dbo.Symbols
sym on store.iSymId
= sym.iSymId
where
sym.vcSym like '12345%'
Запрос работает 20 секунд на холодном кэше, что примерно в 7 раз быстрее чем запрос с условием like к таблице dbo.Accounts.Осталось обсудить как сохранять данную структуру при операциях вставки, обновления и удаления для таблицы dbo.Accounts. Будем поддерживать только таблицу dbo.StrStorage (для dbo.FullStrStorage все делается аналогично). Для поддержки целостности данных необходимо создать 3 триггера:
as
begin
if @@rowcount = 0
begin
return
end
set nocount, xact_abort on
update store
set store.iSymId = sym.iSymId
from
dbo.StrStorage store
inner join
inserted ins on store.iRowId = ins.iRowId
inner join
dbo.Symbols sym on substring ( ins.vcAccount, store.iNumId, 8 ) = sym.vcSym
update store
set store.iSmallSymId = newsym.iSmallSymId
from
dbo.SmallStrStorage store
inner join
inserted ins on store.iRowId = ins.iRowId
inner join
dbo.SmallSymbols sym on store.iSmallSymId = sym.iSmallSymId
inner join
dbo.SmallSymbols newsym on right ( ins.vcAccount, len ( sym.vcSmallSym ) ) = newsym.vcSmallSym
end
set store.iSmallSymId = newsym.iSmallSymId
from
dbo.SmallStrStorage store
inner join
inserted ins on store.iRowId = ins.iRowId
inner join
dbo.SmallSymbols sym on store.iSmallSymId = sym.iSmallSymId
inner join
dbo.SmallSymbols newsym on right ( ins.vcAccount, len ( sym.vcSmallSym ) ) = newsym.vcSmallSym
end
as
begin
if @@rowcount = 0
begin
return
end
set nocount, xact_abort on
with Nums
as
(
select id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ), ( 9 ),
( 10 ), ( 11 ), ( 12 ), ( 13 )
) dat ( id )
)
insert into dbo.StrStorage ( iSymId, iNumId, iRowId )
select sym.iSymId, Nums.id, ins.iRowId
from
inserted ins
cross join
Nums
inner join
dbo.Symbols sym on substring ( ins.vcAccount, 8, Nums.id ) = sym.vcSym
;
with Nums
as
(
select id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 )
) dat ( id )
)
insert into dbo.SmallStrStorage ( iSmallSymId, iRowId )
select sym.iSmallSymId, ins.iRowId
from
inserted ins
cross join
Nums
inner join
dbo.SmallSymbols sym on right ( ins.vcAccount, Nums.id ) = sym.vcSmallSymend
as
if @@rowcount = 0
delete store
delete store
from
deleted del
inner join
dbo.SmallStrStorage store on store.iRowId = del.iRowId
end
from
deleted del
inner join
dbo.SmallStrStorage store on store.iRowId = del.iRowId
end
Для эффективной работы этих триггеров также используются некластерные индексы на dbo.StrStorage и dbo.SmalStrStorage.
Я хотел сделать небольшое замечание о применении метода для текстовых столбцов, в которых хранятся не лицевые номера, а например тексты. Предположим, что различных символов, которые могут использоваться в тексте может быть 60 (например, 33 буквы русского алфавита, 10 цифр и специальные символы, регистры букв для простоты не различаем). В этом случае различных комбинаций строк длины 8 из этих символов будет слишком много (60 в 8-ой степени, почти 168 триллионов записей, около 7 петабайт). Но тогда можно использовать строки длины 5, и число подстрок будет равно 60 в пятой степени, это 777.6 миллионов строк. И объемы записей будут реалистичны. Выше было сказано, что при уменьшении длины подстроки, может снизиться селективность запроса, сводя на нет преимущества таблицы dbo.StrStorage. На моем компьютере это произошло, только когда число строк, содержащих заданную подстроку было более чем несколько тысяч.
Однако такого ограничения на длину строки в таблице dbo.Symbols можно избежать, если для экономии места хранить в этой таблице не все возможные подстроки, а только те, которые встречаются в таблице с текстовым столбцом. Для этого требуется изменить запрос на наполнение таблицы dbo.Symbols и триггеры.
Код на наполнение таблицы dbo.Symbols такой:
as
begin if @@rowcount = 0
begin
return
end
set nocount, xact_abort on
insert into dbo.Symbols with ( tablock ) ( vcSym )
select distinct data.vcSym
from
(
select acc.iRowId, substring ( acc.vcAccount, data.Id, 8 ) vcSym
from
inserted acc
cross join
(
select Id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ),
( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) data ( Id )
) data
) data
left outer join
dbo.Symbols sym on data.vcSym = sym.vcSym
where sym.vcSym is null
update store
set store.iSymId = sym.iSymId
from
dbo.StrStorage store
inner join
inserted ins on store.iRowId = ins.iRowId
inner join
dbo.Symbols sym on substring ( ins.vcAccount, 8, store.iNumId ) = sym.iSymId
end
create trigger dbo.AccountsTrIns on dbo.Accounts for insert
as
begin if @@rowcount = 0
begin
return
end
set nocount, xact_abort on
insert into dbo.Symbols with ( tablock ) ( vcSym )
select distinct data.vcSym
from
(
select acc.iRowId, substring ( acc.vcAccount, data.Id, 8 ) vcSym
from
inserted acc
cross join
(
select Id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ),
( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) data ( Id )
) data
) data
left outer join
dbo.Symbols sym on data.vcSym = sym.vcSym
where sym.vcSym is null
;
with Nums
as
(
select id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ), ( 9 ),
( 10 ), ( 11 ), ( 12 ), ( 13 )
) dat ( id )
)
insert into dbo.StrStorage ( iSymId, iNumId, iRowId )
select sym.iSymId, Nums.id, ins.iRowId
from
inserted ins
cross join
Nums
inner join
dbo.Symbols sym on substring ( ins.vcAccount, 8, Nums.id ) = sym.iSymId
end
Триггеры могут начать работать медленнее, но зато экономится объем записей в таблице dbo.Symbols. Я также не стал включать в код этих триггеров запросы с участием таблицы dbo.SmallStrStorage, чтобы не загромождать код. Запросы с участием этой таблицы аналогичны запросам к dbo.StrStorage.
Я хотел сделать небольшое замечание о применении метода для текстовых столбцов, в которых хранятся не лицевые номера, а например тексты. Предположим, что различных символов, которые могут использоваться в тексте может быть 60 (например, 33 буквы русского алфавита, 10 цифр и специальные символы, регистры букв для простоты не различаем). В этом случае различных комбинаций строк длины 8 из этих символов будет слишком много (60 в 8-ой степени, почти 168 триллионов записей, около 7 петабайт). Но тогда можно использовать строки длины 5, и число подстрок будет равно 60 в пятой степени, это 777.6 миллионов строк. И объемы записей будут реалистичны. Выше было сказано, что при уменьшении длины подстроки, может снизиться селективность запроса, сводя на нет преимущества таблицы dbo.StrStorage. На моем компьютере это произошло, только когда число строк, содержащих заданную подстроку было более чем несколько тысяч.
Однако такого ограничения на длину строки в таблице dbo.Symbols можно избежать, если для экономии места хранить в этой таблице не все возможные подстроки, а только те, которые встречаются в таблице с текстовым столбцом. Для этого требуется изменить запрос на наполнение таблицы dbo.Symbols и триггеры.
Код на наполнение таблицы dbo.Symbols такой:
declare @curid int = 1, @step int = 1000000
while @curid <= ( select max ( iRowId ) from dbo.Accounts )
begin
while @curid <= ( select max ( iRowId ) from dbo.Accounts )
begin
insert into dbo.Symbols with ( tablock ) ( vcSym )
select distinct data.vcSym
from
(
select acc.iRowId, substring ( acc.vcAccount, data.Id, 8 ) vcSym
from
dbo.Accounts acc
cross join
(
select Id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ),
( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) data ( Id )
) data
where acc.iRowId >= @curid and acc.iRowId < @curid + @step
) data
left outer join
dbo.Symbols sym on data.vcSym = sym.vcSym
where sym.vcSym is null
set @curid += @step
end
Также вставки в таблицу dbo.Symbols нужно будет учитывать в триггерах на встаку и изменение в dbo.Accounts. В начало тела каждого из этих триггеров требуется добавить insert в таблицу dbo.Symbols:
create trigger dbo.AccountsTrUpd on dbo.Accounts for updateselect distinct data.vcSym
from
(
select acc.iRowId, substring ( acc.vcAccount, data.Id, 8 ) vcSym
from
dbo.Accounts acc
cross join
(
select Id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ),
( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) data ( Id )
) data
where acc.iRowId >= @curid and acc.iRowId < @curid + @step
) data
left outer join
dbo.Symbols sym on data.vcSym = sym.vcSym
where sym.vcSym is null
set @curid += @step
end
Также вставки в таблицу dbo.Symbols нужно будет учитывать в триггерах на встаку и изменение в dbo.Accounts. В начало тела каждого из этих триггеров требуется добавить insert в таблицу dbo.Symbols:
as
begin if @@rowcount = 0
begin
return
end
set nocount, xact_abort on
insert into dbo.Symbols with ( tablock ) ( vcSym )
select distinct data.vcSym
from
(
select acc.iRowId, substring ( acc.vcAccount, data.Id, 8 ) vcSym
from
inserted acc
cross join
(
select Id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ),
( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) data ( Id )
) data
) data
left outer join
dbo.Symbols sym on data.vcSym = sym.vcSym
where sym.vcSym is null
update store
set store.iSymId = sym.iSymId
from
dbo.StrStorage store
inner join
inserted ins on store.iRowId = ins.iRowId
inner join
dbo.Symbols sym on substring ( ins.vcAccount, 8, store.iNumId ) = sym.iSymId
end
create trigger dbo.AccountsTrIns on dbo.Accounts for insert
as
begin if @@rowcount = 0
begin
return
end
set nocount, xact_abort on
insert into dbo.Symbols with ( tablock ) ( vcSym )
select distinct data.vcSym
from
(
select acc.iRowId, substring ( acc.vcAccount, data.Id, 8 ) vcSym
from
inserted acc
cross join
(
select Id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ),
( 9 ), ( 10 ), ( 11 ), ( 12 ), ( 13 )
) data ( Id )
) data
) data
left outer join
dbo.Symbols sym on data.vcSym = sym.vcSym
where sym.vcSym is null
;
with Nums
as
(
select id
from
(
values ( 1 ), ( 2 ), ( 3 ), ( 4 ), ( 5 ), ( 6 ), ( 7 ), ( 8 ), ( 9 ),
( 10 ), ( 11 ), ( 12 ), ( 13 )
) dat ( id )
)
insert into dbo.StrStorage ( iSymId, iNumId, iRowId )
select sym.iSymId, Nums.id, ins.iRowId
from
inserted ins
cross join
Nums
inner join
dbo.Symbols sym on substring ( ins.vcAccount, 8, Nums.id ) = sym.iSymId
end
Триггеры могут начать работать медленнее, но зато экономится объем записей в таблице dbo.Symbols. Я также не стал включать в код этих триггеров запросы с участием таблицы dbo.SmallStrStorage, чтобы не загромождать код. Запросы с участием этой таблицы аналогичны запросам к dbo.StrStorage.
Комментариев нет:
Отправить комментарий