Localice el elemento que falta más pequeño basado en una fórmula específica

Necesito poder localizar un elemento faltante de una tabla con decenas de millones de filas, y tiene una clave primaria de una BINARY(64)columna (que es el valor de entrada para calcular). Estos valores se insertan principalmente en orden, pero en ocasiones quiero reutilizar un valor anterior que se eliminó. No es factible modificar los registros eliminados con una IsDeletedcolumna, ya que a veces se inserta una fila que tiene muchos millones de valores por delante de las filas existentes actualmente. Esto significa que los datos de muestra se verían así:

KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF

Por lo tanto, insertar todos los valores faltantes entre 0x000000000002y 0xFFFFFFFFFFFFes inviable, la cantidad de tiempo y espacio utilizado sería indeseable. Esencialmente, cuando ejecuto el algoritmo, espero que regrese 0x000000000003, que es la primera apertura.

Se me ocurrió un algoritmo de búsqueda binaria en C #, que consultaría la base de datos para cada valor en la posición iy probaría si se esperaba ese valor. Para el contexto, mi algoritmo terrible: /codereview/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

Este algoritmo ejecutaría, por ejemplo, 26-27 consultas SQL en una tabla con 100,000,000 artículos. (Eso no parece mucho, pero ocurrirá con mucha frecuencia). Actualmente, esta tabla tiene aproximadamente 50,000,000 filas, y el rendimiento se está volviendo notable .

Mi primer pensamiento alternativo es traducir esto a un procedimiento almacenado, pero eso tiene sus propios obstáculos. (Tengo que escribir un BINARY(64) + BINARY(64)algoritmo, así como una serie de otras cosas). Esto sería doloroso, pero no inviable. También he considerado implementar el algoritmo de traducción basado en ROW_NUMBER, pero tengo un presentimiento realmente malo sobre esto. (A BIGINTno es lo suficientemente grande como para estos valores).

Estoy preparado para otras sugerencias, ya que realmente necesito que esto sea lo más rápido posible. Por lo que vale, la única columna seleccionada por la consulta de C # es KeyCol, las otras son irrelevantes para esta parte.

Además, por lo que vale, la consulta actual que obtiene el registro apropiado está en la línea de:

SELECT [KeyCol]
  FROM [Table]
  ORDER BY [KeyCol] ASC
  OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY

¿Dónde <VALUE>está el índice proporcionado por el algoritmo? Tampoco he tenido el BIGINTproblema OFFSETtodavía, pero lo haré. (Solo tener 50,000,000 filas en este momento significa que nunca pide un índice por encima de ese valor, pero en algún momento superará el BIGINTrango).

Algunos datos adicionales:

• A partir de eliminaciones, la gap:sequentialrelación es aproximadamente 1:20;
• Las últimas 35,000 filas en la tabla tienen valores>> BIGINTmáximo;

Joe ya ha acertado en la mayoría de los puntos que acabo de pasar una hora escribiendo, en resumen:

• es muy dudoso que se quede sin KeyColvalores < bigintmax (9.2e18), por lo que las conversiones (si es necesario) a / desde bigintno deberían ser un problema siempre que limite las búsquedas aKeyCol <= 0x00..007FFFFFFFFFFFFFFF
• No puedo pensar en una consulta que vaya a encontrar una brecha 'eficientemente' todo el tiempo; puede tener suerte y encontrar una brecha cerca del comienzo de su búsqueda, o podría pagar un alto precio para encontrar la brecha bastante en su búsqueda
• Si bien pensé brevemente en cómo paralelizar la consulta, descarté rápidamente esa idea (como DBA, no me gustaría descubrir que su proceso está empantanando rutinariamente mi servidor de datos con una utilización del 100% de la CPU ... especialmente si podría tener múltiples copias de esto corriendo al mismo tiempo); noooo ... la paralelización va a estar fuera de discusión

¿Entonces lo que hay que hacer?

Pongamos la idea de búsqueda (repetida, intensiva en CPU, fuerza bruta) en espera por un minuto y veamos la imagen más grande.

• en promedio, una instancia de esta búsqueda necesitará escanear millones de claves de índice (y requerirá una buena cantidad de CPU, agitación de la caché de db y un usuario mirando un reloj de arena giratorio) solo para localizar un valor único
• multiplique el uso de la CPU / cache-thrashing / spinning-hour-glass por ... ¿cuántas búsquedas espera en un día?
• tenga en cuenta que, en términos generales, cada instancia de esta búsqueda tendrá que escanear el mismo conjunto de (millones de) claves de índice; eso es MUCHA actividad repetida para un beneficio tan mínimo

Lo que me gustaría proponer es algunas adiciones al modelo de datos ...

• una nueva tabla que rastrea un conjunto de KeyColvalores 'disponibles para usar' , por ejemplo:available_for_use(KeyCol binary(64) not null primary key)
• ¿cuántos registros mantiene en esta tabla depende de usted decidir, por ejemplo, tal vez suficiente para un mes de actividad?
• la tabla puede periódicamente (¿semanal?) 'completarse' con un nuevo lote de KeyColvalores (¿quizás crear un proceso almacenado 'superior'?) [por ejemplo, actualizar la select/top/row_number()consulta de Joe para hacer un top 100000]
• podría configurar un proceso de monitoreo para realizar un seguimiento de la cantidad de entradas disponibles available_for_use en caso de que alguna vez comience a quedarse sin valores
• un desencadenador DELETE nuevo (o modificado) en> main_table <que coloca los KeyColvalores eliminados en nuestra nueva tabla available_for_usecada vez que se elimina una fila de la tabla principal
• si permite actualizaciones de la KeyColcolumna, entonces un desencadenador de ACTUALIZACIÓN nuevo / modificado en> main_table <para también mantener available_for_useactualizada nuestra nueva tabla
• cuando llegue el momento de 'buscar' un nuevo KeyColvalor que usted select min(KeyCol) from available_for_use(obviamente, hay un poco más de esto, ya que a) necesitará codificar para problemas de concurrencia; no quiera que 2 copias de su proceso agarren lo mismo min(KeyCol)yb) usted necesitará eliminar min(KeyCol)de la tabla; esto debería ser relativamente fácil de codificar, tal vez como un proceso almacenado, y se puede abordar en otras preguntas y respuestas si es necesario)
• en el peor de los casos, si su select min(KeyCol)proceso no encuentra filas disponibles, puede iniciar su proceso 'top off' para generar un nuevo lote de filas

Con estos cambios propuestos al modelo de datos:

• a eliminar un montón de ciclos de CPU excesivos [su DBA le agradecerá]
• elimina TODOS esos escaneos de índice repetitivos y la transferencia de caché [su DBA se lo agradecerá]
• sus usuarios ya no tienen que mirar el reloj giratorio (aunque puede que no les guste la pérdida de una excusa para alejarse de su escritorio)
• hay muchas maneras de controlar el tamaño de la available_for_usetabla para asegurarse de que nunca se quede sin nuevos valores

Sí, la available_for_usetabla propuesta es solo una tabla de valores de 'próxima clave' pregenerados; y sí, existe la posibilidad de cierta controversia cuando se toma el valor 'siguiente', pero cualquier contención a) se aborda fácilmente a través del diseño adecuado de tabla / índice / consulta yb) será menor / de corta duración en comparación con la sobrecarga / retrasos con la idea actual de búsquedas repetidas de fuerza bruta e índice.

Hay algunos desafíos con esta pregunta. Los índices en SQL Server pueden hacer lo siguiente de manera muy eficiente con solo unas pocas lecturas lógicas cada uno:

• comprobar que existe una fila
• comprobar que no existe una fila
• encuentra la siguiente fila que comienza en algún momento
• encontrar la fila anterior comenzando en algún momento

Sin embargo, no se pueden usar para encontrar la enésima fila en un índice. Para hacerlo, debe rodar su propio índice almacenado como una tabla o escanear las primeras N filas en el índice. Su código C # depende en gran medida del hecho de que puede encontrar eficientemente el enésimo elemento de la matriz, pero no puede hacerlo aquí. Creo que ese algoritmo no es utilizable para T-SQL sin un cambio de modelo de datos.

El segundo desafío se relaciona con las restricciones sobre los BINARYtipos de datos. Por lo que puedo decir, no puedes realizar sumas, restas o divisiones de la forma habitual. Puede convertir su BINARY(64)en BIGINTay no arrojará errores de conversión, pero el comportamiento no está definido :

No se garantiza que las conversiones entre cualquier tipo de datos y los tipos de datos binarios sean las mismas entre las versiones de SQL Server.

Además, la falta de errores de conversión es un problema aquí. Puede convertir cualquier cosa más grande que el mayor BIGINTvalor posible , pero le dará resultados incorrectos.

Es cierto que tiene valores en este momento que son mayores que 9223372036854775807. Sin embargo, si siempre comienza en 1 y busca el valor mínimo más pequeño, esos valores grandes no pueden ser relevantes a menos que su tabla tenga más de 9223372036854775807 filas. Esto parece poco probable porque su tabla en ese momento estaría alrededor de 2000 exabytes, por lo que para responder a su pregunta voy a suponer que no es necesario buscar los valores muy grandes. También voy a hacer la conversión del tipo de datos porque parecen ser inevitables.

Para los datos de la prueba, inserté el equivalente de 50 millones de enteros secuenciales en una tabla junto con 50 millones de enteros más con una sola brecha de valor cada 20 valores. También inserté un valor único que no cabe correctamente en un signo BIGINT:

CREATE TABLE dbo.BINARY_PROBLEMS (
    KeyCol BINARY(64) NOT NULL
);

INSERT INTO dbo.BINARY_PROBLEMS WITH (TABLOCK)
SELECT CAST(SUM(OFFSET) OVER (ORDER BY (SELECT NULL) ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS BINARY(64))
FROM
(
    SELECT 1 + CASE WHEN t.RN > 50000000 THEN
        CASE WHEN ABS(CHECKSUM(NewId()) % 20)  = 10 THEN 1 ELSE 0 END
    ELSE 0 END OFFSET
    FROM
    (
        SELECT TOP (100000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
        FROM master..spt_values t1
        CROSS JOIN master..spt_values t2
        CROSS JOIN master..spt_values t3
    ) t
) tt
OPTION (MAXDOP 1);

CREATE UNIQUE CLUSTERED INDEX CI_BINARY_PROBLEMS ON dbo.BINARY_PROBLEMS (KeyCol);

-- add a value too large for BIGINT
INSERT INTO dbo.BINARY_PROBLEMS
SELECT CAST(0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000 AS BINARY(64));

Ese código tardó unos minutos en ejecutarse en mi máquina. Hice que la primera mitad de la tabla no tuviera huecos para representar un caso peor para el rendimiento. El código que usé para resolver el problema escanea el índice en orden para que termine muy rápidamente si el primer espacio está al principio de la tabla. Antes de llegar a eso, verifiquemos que los datos estén como deberían ser:

SELECT TOP (2) KeyColBigInt
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    FROM dbo.BINARY_PROBLEMS
) t
ORDER By KeyCol DESC;

Los resultados sugieren que el valor máximo al que convertimos BIGINTes 102500672:

╔══════════════════════╗
║     KeyColBigInt     ║
╠══════════════════════╣
║ -9223372036854775808 ║
║            102500672 ║
╚══════════════════════╝

Hay 100 millones de filas con valores que se ajustan a BIGINT como se esperaba:

SELECT COUNT(*) 
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF;

Un enfoque para este problema es escanear el índice en orden y salir tan pronto como el valor de una fila no coincida con el ROW_NUMBER()valor esperado . No es necesario escanear toda la tabla para obtener la primera fila: solo las filas hasta el primer espacio. Aquí hay una forma de escribir código que probablemente obtenga ese plan de consulta:

SELECT TOP (1) KeyCol
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    , ROW_NUMBER() OVER (ORDER BY KeyCol) RN
    FROM dbo.BINARY_PROBLEMS
    WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF
) t
WHERE KeyColBigInt <> RN
ORDER BY KeyCol;

Por razones que no encajan en esta respuesta, esta consulta a menudo se ejecutará en serie por SQL Server y SQL Server a menudo subestimará el número de filas que deben analizarse antes de encontrar la primera coincidencia. En mi máquina, SQL Server escanea 50000022 filas del índice antes de encontrar la primera coincidencia. La consulta tarda 11 segundos en ejecutarse. Tenga en cuenta que esto devuelve el primer valor más allá de la brecha. No está claro qué fila desea exactamente, pero debería poder cambiar la consulta para que se ajuste a sus necesidades sin muchos problemas. Así es como se ve el plan :

Mi única otra idea era intimidar a SQL Server para que usara paralelismo para la consulta. Tengo cuatro CPU, así que dividiré los datos en cuatro rangos y haré búsquedas en esos rangos. A cada CPU se le asignará un rango. Para calcular los rangos, simplemente tomé el valor máximo y asumí que los datos se distribuían de manera uniforme. Si desea ser más inteligente al respecto, puede mirar un histograma de estadísticas muestreadas para los valores de columna y construir sus rangos de esa manera. El siguiente código se basa en muchos trucos indocumentados que no son seguros para la producción, incluido el indicador de seguimiento 8649 :

SELECT TOP 1 ca.KeyCol
FROM (
    SELECT 1 bucket_min_value, 25625168 bucket_max_value
    UNION ALL
    SELECT 25625169, 51250336
    UNION ALL
    SELECT 51250337, 76875504
    UNION ALL
    SELECT 76875505, 102500672
) buckets
CROSS APPLY (
    SELECT TOP 1 t.KeyCol
    FROM
    (
        SELECT KeyCol
        , CAST(KeyCol AS BIGINT) KeyColBigInt
        , buckets.bucket_min_value - 1 + ROW_NUMBER() OVER (ORDER BY KeyCol) RN
        FROM dbo.BINARY_PROBLEMS
        WHERE KeyCol >= CAST(buckets.bucket_min_value AS BINARY(64)) AND KeyCol <=  CAST(buckets.bucket_max_value AS BINARY(64))
    ) t
    WHERE t.KeyColBigInt <> t.RN
    ORDER BY t.KeyCol
) ca
ORDER BY ca.KeyCol
OPTION (QUERYTRACEON 8649);

Así es como se ve el patrón de bucle anidado paralelo:

En general, la consulta hace más trabajo que antes, ya que escaneará más filas en la tabla. Sin embargo, ahora se ejecuta en 7 segundos en mi escritorio. Podría paralelizar mejor en un servidor real. Aquí hay un enlace al plan real .

Realmente no puedo pensar en una buena manera de resolver este problema. Hacer el cálculo fuera de SQL o cambiar el modelo de datos pueden ser sus mejores apuestas.

Aquí hay una respuesta que probablemente no funcione para ti, pero la agregaré de todos modos.

A pesar de que BINARY (64) es enumerable, hay poco apoyo para determinar el sucesor de un elemento. Dado que BIGINT parece ser demasiado pequeño para su dominio, puede considerar usar un DECIMAL (38,0), que parece ser el tipo NUMBER más grande en el servidor SQL.

CREATE TABLE SearchTestTableProper
( keycol decimal(38,0) not null primary key );

INSERT INTO SearchTestTableProper (keycol)
VALUES (1),(2),(3),(12);

Encontrar la primera brecha es fácil ya que podemos construir el número que estamos buscando:

select top 1 t1.keycol+1 
from SearchTestTableProper t1 
where not exists (
    select 1 
    from SearchTestTableProper t2 
    where t2.keycol = t1.keycol + 1
)
order by t1.keycol;

Una unión de bucle anidado sobre el índice pk debería ser suficiente para encontrar el primer elemento disponible.