Problema
Todos tenemos días en el trabajo cuando alguien viene a nosotros con un requisito verdaderamente imposible que requiere un milagro para cumplir. Mi caso ocurrió cuando un colega de marketing se me ocurrió una pregunta aparentemente simple: si podía obtener datos de una tabla para un mes determinado hace un par de años. Está bien, se podría decir, pero recordaba vagamente que la mesa era muy grande. La tabla tenía un campo de fecha y hora en el momento de la creación, pero ¿había un índice en ese campo?
Por supuesto, también querían obtener los datos rápidamente. Yo, como siempre, dije: "Veré lo que puedo hacer" y fui a mirar más de cerca la mesa en discusión. La suerte nunca nos abandona, el índice realmente no existía y la tabla era enorme. No hay problema, podemos escanear la tabla, ¿verdad? Incorrecto. Si he aprendido algo de los años de trabajar con bases de datos, es que el tamaño importa. Una tabla con cientos de millones de registros y varias columnas enteras sería bastante formidable. Luego agregue varias columnas varchar y datetime. Ahora que es un verdadero desafío, ¿no?
La tabla que estaba mirando tenía mil millones de registros, literalmente. Un escaneo de tabla simple podría llevar más de un día y también necesitaba procesar los datos extraídos. Además, escanear una tabla de este tamaño puede no ser tan beneficioso para la salud general del sistema como parece a primera vista. Todas las páginas escaneadas deben extraerse de los discos en la memoria del servidor SQL llenándola. Esto, a su vez, descargará páginas de datos de la memoria caché, que se pueden usar para las tareas operativas actuales. Las solicitudes de sus usuarios actuales pueden esperar más tiempo mientras el servidor vuelve a leer los datos de los discos, en lugar de reutilizar rápidamente las páginas de datos de la memoria. El rendimiento puede disminuir y, en el peor de los casos, el servidor puede estar completamente de rodillas. Así,al escanear una tabla, debe usar una técnica especial: ejecutarla en lotes pequeños, manteniendo en algún lugar la posición actual y los resultados intermedios. Este enfoque permite que el servidor se reconfigure y tenga un respiro sin permitir un gran impacto en el rendimiento.
Entonces, pensé en el escenario y estimé el tiempo que tomaría iniciar y ejecutar el script, cuando se me ocurrió que los valores de fecha y hora del tiempo de creación estaban asociados con el identificador de la tabla. El identificador (ID) era una columna con valores en constante crecimiento y una clave primaria basada en él. Al buscar por identificador, los valores de fecha y hora de creación se clasificaron naturalmente de la misma manera que los valores del identificador. ¡Espera, pensé, podría implementar algo extremadamente rápido que un escaneo de tabla, algo que en el peor de los casos solo tomaría 30 pasos en lugar de 500,000,000! ¡Búsqueda binaria!
Buscar
Para todos los que, como yo, se graduaron de la capacitación hace mucho tiempo, la capacitación en teoría debería estar en el orden de las cosas. La búsqueda binaria es una forma simple pero extremadamente eficiente de buscar un valor en una matriz ordenada (en nuestro caso, en una columna de tabla). La matriz debe estar previamente ordenada y ser finita. La búsqueda se realiza comparando el elemento medio de su matriz con el objetivo. Si son iguales, entonces la búsqueda ha terminado. De lo contrario, elimina la mitad en la que obviamente falta el elemento que está buscando y repite el paso anterior hasta que tenga uno. Encuentre el centro, compare el objetivo con él, si no son iguales, retire la mitad nuevamente, y así sucesivamente. El número total de pasos necesarios para encontrar el objetivo en el peor de los casos, cuando lo encuentre hasta el último paso, será log (N), donde N es el número de elementos. Compare esto con N / 2,cuando solo iteras sobre la matriz. En términos generales, sería N, pero si pudiéramos adivinar si el objetivo está más cerca del final, podríamos retroceder, reduciendo así el número total de pasos necesarios.
En mi caso, N = 1,000,000,000 y así es como llegué a los dos números anteriores: 30 y 500,000,000. La ID desempeñaría el papel de un enumerador de matriz, y la fecha y hora de creación sería el valor del elemento de matriz. Sin embargo, hay una advertencia. Un enumerador de matrices, por definición, es una secuencia secuencial continua de enteros. Es fácil para las ID de tablas contener espacios debido a la eliminación de registros o al desbordamiento de ID. Simplemente determinando el medio dividiendo el rango de identificadores por 2, no debe esperar que haya una entrada con dicho identificador. En lugar de buscar directamente, tuve que usar la función top (). Algo como eso:
Select top(1) * from Table where id <= @id order by id descUsé "<=" y "desc" porque quería encontrar un valor igual o inmediatamente anterior al objetivo. Siempre que @l, @r sean bordes izquierdo y derecho respectivamente,carné de identidad Es el medio, @dt es la fecha y hora de la creación, tdt Es el objetivo y carné de identidadr es el identificador de tabla real (ID), el algoritmo puede verse así:
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
Último encontrado carné de identidadr sería el identificador de la entrada seguido de la deseada. El algoritmo tiene algo así como un desplazamiento "a la izquierda", es decir, una tendencia a elegir el más a la izquierda de todos los valores. Como quería que el registro de valor estuviera lo más cerca posible del objetivo, también verifiqué los vecinos izquierdo y derecho más cercanos en la tabla para ver si uno era mejor. Tenga en cuenta que no utilicé el identificador real de la tabla para el proceso de iteración, como en este caso, con espacios en los valores de ID y, en algunas circunstancias, el algoritmo podría entrar en un bucle infinito.
Me llevó alrededor de una hora escribir y probar el guión. Utilizándolo, encontré el primer registro con una fecha y hora específicas de creación. Después de eso, utilicé una simple instrucción select con una cláusula where que contenía ambas condiciones: id> = @ y creation_datetime> = @ dt1 y creation_datetime <@ dt2. Solo necesitaba asegurarme de que el optimizador elegiría usar la clave primaria en lugar de un escaneo de índice o tabla. Con todo, ¡lo hice en menos de 2 horas! Fue sorprendente descubrir nuevamente que los algoritmos no son algo esotérico enterrado en el interior del servidor sql, sino algo que se puede usar fácilmente en el trabajo diario.
A continuación se muestra el guión completo que escribí. Por favor, vea los comentarios para entender cómo usarlo.
/*
, .
, 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)