Eu preciso ser capaz de localizar um elemento ausente de uma tabela com dezenas de milhões de linhas e ter uma chave primária de uma BINARY(64)
coluna (que é o valor de entrada para calcular). Esses valores geralmente são inseridos em ordem, mas de vez em quando quero reutilizar um valor anterior que foi excluído. É inviável modificar os registros excluídos com uma IsDeleted
coluna, pois às vezes uma linha é inserida muitos milhões de valores à frente das linhas existentes no momento. Isso significa que os dados de amostra seriam algo como:
KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF
Portanto, inserir todos os valores ausentes entre 0x000000000002
e 0xFFFFFFFFFFFF
é inviável, a quantidade de tempo e espaço usados seria indesejável. Essencialmente, quando executo o algoritmo, espero que ele retorne 0x000000000003
, que é a primeira abertura.
Eu criei um algoritmo de pesquisa binária em C#, que consultaria o banco de dados para cada valor em position i
e testaria se esse valor era esperado. Para contextualizar, meu terrível algoritmo: https://codereview.stackexchange.com/questions/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula
Esse algoritmo executaria, por exemplo, 26-27 consultas SQL em uma tabela com 100.000.000 itens. (Isso não parece muito, mas vai ocorrer com muita frequência.) Atualmente, esta tabela tem aproximadamente 50.000.000 de linhas e o desempenho está se tornando perceptível .
Meu primeiro pensamento alternativo é traduzir isso para um procedimento armazenado, mas isso tem seus próprios obstáculos. (Eu tenho que escrever um BINARY(64) + BINARY(64)
algoritmo, assim como uma série de outras coisas.) Isso seria doloroso, mas não inviável. Também considerei implementar o algoritmo de traduçãoROW_NUMBER
baseado em , mas tenho um pressentimento muito ruim sobre isso. (A BIGINT
não é grande o suficiente para esses valores.)
Aceito outras sugestões, pois preciso muito que isso seja o mais rápido possível. Pelo que vale a única coluna selecionada pela consulta C# é a KeyCol
, as demais são irrelevantes para esta parte.
Além disso, vale a pena, a consulta atual que busca o registro apropriado segue as linhas de:
SELECT [KeyCol]
FROM [Table]
ORDER BY [KeyCol] ASC
OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY
Onde <VALUE>
é o índice fornecido pelo algoritmo. Eu também não tive o BIGINT
problema com OFFSET
ainda, mas eu vou. (Apenas ter 50.000.000 de linhas agora significa que ele nunca solicita um índice acima desse valor, mas em algum momento ele ficará acima do BIGINT
intervalo.)
Alguns dados adicionais:
- A partir de exclusões, a
gap:sequential
proporção é de cerca de1:20
; - As últimas 35.000 linhas da tabela possuem valores >
BIGINT
's máximo;