Problema
Todos nós temos dias de trabalho em que alguém chega até nós com um requisito verdadeiramente impossível que requer um milagre para cumprir. Meu caso ocorreu quando um colega de marketing me procurou com uma pergunta aparentemente simples: se eu poderia obter dados de uma tabela por um determinado mês, alguns anos atrás. Tudo bem, você pode dizer, mas lembrei-me vagamente que a mesa era muito grande. A tabela tinha um campo de data e hora no momento da criação, mas havia um índice nesse campo?
Obviamente, eles também queriam obter os dados rapidamente. Como sempre, eu disse: "Vou ver o que posso fazer" e fui dar uma olhada na tabela em discussão. A sorte nunca nos deixa, o índice realmente não existia e a mesa era enorme. Não há problema, podemos escanear a mesa, certo? Errado. Se eu aprendi alguma coisa com os anos de trabalho com bancos de dados, esse tamanho é importante. Uma tabela com centenas de milhões de registros e várias colunas inteiras seria formidável o suficiente. Em seguida, adicione várias colunas varchar e datetime. Agora, esse é um desafio real, não é?
A mesa que eu estava vendo tinha um bilhão de registros, literalmente. Uma simples varredura de tabela poderia demorar mais de um dia e eu também precisava processar os dados extraídos. Além disso, a digitalização de uma tabela desse tamanho pode não ser tão benéfica para a saúde geral do sistema quanto parece à primeira vista. Todas as páginas digitalizadas devem ser extraídas dos discos para a memória do servidor sql preenchendo-as. Isso, por sua vez, descarregará as páginas de dados do cache, que pode ser usado para as tarefas operacionais atuais. As solicitações dos usuários atuais podem esperar mais enquanto o servidor relê os dados dos discos, em vez de reutilizar rapidamente as páginas de dados da memória. O desempenho pode ser prejudicado e, na pior das hipóteses, o servidor pode ficar completamente de joelhos. Portanto,ao digitalizar uma tabela, você deve usar uma técnica especial - execute-a em pequenos lotes, mantendo a posição atual e os resultados intermediários em algum lugar. Essa abordagem permite que o servidor reconfigure e respire sem permitir um grande impacto no desempenho.
Então, eu estava pensando no cenário do trabalho e estimando o tempo necessário para executar e executar o script quando me ocorreu que os valores de data e hora do tempo de criação estavam associados ao ID da tabela. O identificador (ID) era uma coluna com valores em constante crescimento e uma chave primária com base nela. Ao buscar por identificador, os valores de data e hora da criação eram naturalmente pré-classificados da mesma maneira que os valores do identificador. Espere, pensei, eu poderia implementar algo extremamente rápido do que uma varredura de tabela, algo que, no pior caso, levaria apenas 30 etapas em vez de 500.000.000! Pesquisa binária!
Procurar
Para todos que, como eu, se formaram há muito tempo, o treinamento em teoria deve estar na ordem das coisas. A pesquisa binária é uma maneira simples, mas extremamente eficiente, de encontrar um valor em uma matriz classificada (no nosso caso, uma coluna da tabela). A matriz deve ser pré-classificada e finita. A pesquisa é feita comparando o elemento do meio da sua matriz com o destino. Se forem iguais, a pesquisa terminou. Caso contrário, você exclui a metade na qual o elemento desejado está obviamente ausente e repita a etapa anterior até restar apenas uma. Encontre o meio, compare o alvo com ele, se não forem iguais, remova a metade novamente e assim por diante. O número total de etapas necessárias para encontrar a meta na pior das hipóteses, quando você a encontra na última etapa, é log (N), onde N é o número de elementos. Compare isso com N / 2,quando você apenas itera sobre uma matriz. De um modo geral, seria N, mas se pudéssemos adivinhar se o objetivo estava mais próximo do fim, poderíamos voltar, reduzindo assim o número total de etapas necessárias.
No meu caso, N = 1.000.000.000 e foi assim que cheguei aos dois números acima: 30 e 500.000.000. Um identificador (ID) desempenharia o papel de um enumerador de matriz, e a data e hora da criação seria o valor do elemento da matriz. Há uma ressalva, no entanto. Um enumerador de matriz, por sua própria definição, é uma sequência seqüencial contígua de números inteiros. Pode haver facilmente espaços nos identificadores de tabela devido à exclusão de um registro ou ao preenchimento de um identificador. Uma definição simples do meio, dividindo o intervalo de identificadores por 2, você não deve esperar que haja um registro com esse identificador. Em vez de pesquisar diretamente, tive que usar a função top (). Algo parecido:
Select top(1) * from Table where id <= @id order by id descUsei "<=" e "desc" porque queria encontrar um valor igual ou imediatamente antes do destino. Desde que @l, @r sejam bordas esquerda e direita, respectivamente,Eu iria É o meio, @dt é a data e hora da criação, tdt O objetivo e Eu iriar é o identificador de tabela real (ID), o algoritmo pode ser assim:
while @l <@r
begin
--
@id = @l +floor((@r-@l)/2)
--
select top(1) @idr = id, @dt = creation_datetime from Table where id <= @id order by id desc
--
if(@dt<@tdt)
@l = @id +1
else
@r = @id
end
Encontrado pela última vez Eu iriar seria o identificador da entrada seguido pela desejada. O algoritmo tem algo como uma mudança "esquerda", ou seja, uma tendência de escolher o mais à esquerda de todos os valores. Como eu queria que o registro com o valor estivesse o mais próximo possível do alvo, também verifiquei os vizinhos esquerdo e direito mais próximos da tabela para ver se um deles era melhor. Observe que eu não usei o ID real da tabela para o processo de iteração, como neste caso, com espaços nos valores de ID e, em algumas circunstâncias, o algoritmo pode entrar em um loop infinito.
Levei cerca de uma hora para escrever e testar o script. Ao usá-lo, encontrei a primeira entrada com uma data e hora de criação específicas. Depois disso, usei uma instrução select simples com uma cláusula where que continha as duas condições: id> = @ e creation_datetime> = @ dt1 e creation_datetime <@ dt2. Eu só precisava ter certeza de que o otimizador escolheria usar a chave primária em vez de uma verificação de índice ou tabela. Em suma, eu fiz isso em menos de 2 horas! Foi surpreendente redescobrir que os algoritmos não são algo esotérico enterrado no fundo de um servidor sql, mas algo que pode ser facilmente usado no trabalho do dia a dia.
Abaixo está o script inteiro que eu escrevi. Por favor, veja os comentários dentro para entender como usá-lo.
/*
, .
, datetime 3
*/
-- , ,
declare @debug bit = 0
-- @Table - , .
declare @Table varchar(128) = 'TableX'
-- @Id - (id)
declare @ID varchar(128) = 'Id'
-- @DateTimeColumn - datetime
declare @DateTimeColumn varchar(128) = 'created_dt'
--
declare @TargetDateTime datetime = '2020-01-03 18:23:03'
declare @Sql varchar(max)
set @sql = '
--
declare @debug bit = <debug>
--
declare @tdt datetime = ''<TargetDateTime>''
-- ( )
declare @id bigint
--
declare @l bigint, @r bigint
-- , , datetime
declare @dt datetime, @idr bigint
-- «» «»
select @l = min(<ID>), @r = max(<ID>) from <Table>
while @l < @r
begin
--
set @id = @l +floor((@r-@l)/2)
--
select top(1) @dt = <DateTimeColumn>, @idr = <ID> from <Table> where <ID> <= @id order by <ID> desc
-- ,
if( @debug = 1 )
begin
select ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr
end
if(@dt < @tdt)
set @l = @id +1
else
set @r = @id
end
-- ,
declare @t table(id bigint, dt datetime, dlt float)
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float))
from <Table>
where <ID> < @idr
order by <ID> desc
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float))
from <Table>
where <ID> > @idr
order by <ID>
insert @t(id, dt, dlt)
select @idr, @dt, abs(cast(@dt as float) -cast(@tdt as float))
select top(1) @dt = dt, @idr = id from @t order by dlt, id
select ''Found Value'' = @dt, ''Record Id'' = @idr
'
set @sql = replace(
replace(
replace(
replace(
replace(@sql, '<ID>', @ID),
'<Table>', @Table),
'<TargetDateTime>', convert(varchar(50), @TargetDateTime, 121)),
'<debug>', @debug),
'<DateTimeColumn>', @DateTimeColumn)
exec (@sql)