Localize o menor elemento ausente com base em uma fórmula específica

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 o qual calcular). Esses valores geralmente são inseridos em ordem, mas, ocasionalmente, desejo reutilizar um valor anterior que foi excluído. É inviável modificar os registros excluídos com uma IsDeletedcoluna, pois algumas vezes é inserida uma linha com muitos milhões de valores à frente das linhas existentes no momento. Isso significa que os dados da amostra se pareceriam com:

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

Portanto, inserir todos os valores ausentes entre 0x000000000002e 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 na posição ie testaria se esse valor era esperado. Para o contexto, meu terrível algoritmo: /codereview/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

Esse algoritmo executaria, por exemplo, 26 a 27 consultas SQL em uma tabela com 100.000.000 itens. (Isso não parece muito, mas ocorrerá com muita frequência.) Atualmente, esta tabela possui 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 que possui seus próprios obstáculos. (Eu tenho que escrever um BINARY(64) + BINARY(64)algoritmo, além de várias outras coisas.) Isso seria doloroso, mas não inviável. Também considerei implementar o algoritmo de tradução com base ROW_NUMBER, mas tenho um pressentimento muito ruim sobre isso. (A BIGINTnão é grande o suficiente para esses valores.)

Estou pronto para outras sugestões, pois realmente preciso que isso seja o mais rápido possível. No que vale a pena, a única coluna selecionada pela consulta C # é a KeyCol, as outras são irrelevantes para esta parte.

Além disso, para o que vale a pena, a consulta atual que busca o registro apropriado segue as seguintes linhas:

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

Onde <VALUE>está o índice fornecido pelo algoritmo. Eu também não tive o BIGINTproblema OFFSETainda, mas vou. (Apenas ter 50.000.000 de linhas no momento significa que nunca solicita um índice acima desse valor, mas em algum momento ele fica acima do BIGINTintervalo.)

Alguns dados adicionais:

• Das exclusões, a gap:sequentialproporção é de aproximadamente 1:20;
• As últimas 35.000 linhas da tabela têm valores> BIGINTno máximo;

Joe já acertou na maioria dos pontos que passei uma hora digitando, em resumo:

• altamente duvidoso, todos os KeyColvalores bigintficam < max (9,2e18), portanto, as conversões (se necessário) de / para bigintnão devem ser um problema, desde que você limite as pesquisas aKeyCol <= 0x00..007FFFFFFFFFFFFFFF
• Não consigo pensar em uma consulta que encontre "de maneira eficiente" uma lacuna o tempo todo; você pode ter sorte e encontrar uma lacuna perto do início de sua pesquisa ou pode pagar caro por encontrar essa lacuna de várias maneiras em sua pesquisa
• Embora tenha pensado brevemente em como paralelizar a consulta, rapidamente descartei essa ideia (como DBA, não gostaria de descobrir que seu processo está rotineiramente atolando meu servidor de dados com 100% de utilização da CPU ... especialmente se você puder ter vários cópias desta execução ao mesmo tempo); noooo ... paralelização vai ficar fora de questão

Então o que fazer?

Vamos colocar a idéia de pesquisa (repetida, intensiva em CPU e força bruta) em espera por um minuto e ver a foto maior.

• em uma base média, uma instância dessa pesquisa precisará varrer milhões de chaves de índice (e exigir uma boa parte da CPU, debulhar o cache do banco de dados e um usuário assistindo a uma ampulheta) apenas para localizar um único valor
• multiplique o uso da CPU / cache-thrashing / spinning-hour-glass por ... quantas pesquisas você espera em um dia?
• lembre-se de que, de um modo geral, cada instância dessa pesquisa precisará verificar o mesmo conjunto de (milhões de) chaves de índice; isso é muita atividade repetida para um benefício tão mínimo

O que eu gostaria de propor são algumas adições ao modelo de dados ...

• uma nova tabela que monitora um conjunto de valores 'disponíveis para uso' KeyCol, por exemplo:available_for_use(KeyCol binary(64) not null primary key)
• Quantos registros você mantém nesta tabela são de sua responsabilidade decidir, por exemplo, talvez o suficiente para um mês de atividade?
• a tabela pode periodicamente (semanalmente?) ser 'completada' com um novo lote de KeyColvalores (talvez criar um processo armazenado 'completada'?) [por exemplo, atualize a select/top/row_number()consulta de Joe para fazer uma top 100000]
• você pode configurar um processo de monitoramento para acompanhar o número de entradas disponíveis, available_for_use caso você comece a ficar com valores baixos
• um novo gatilho DELETE (ou modificado) na> main_table <que coloca KeyColvalores excluídos em nossa nova tabela available_for_usesempre que uma linha é excluída da tabela principal
• se você permitir atualizações da KeyColcoluna, um acionador UPDATE novo / modificado na> main_table <também manterá nossa nova tabela available_for_useatualizada
• quando chegar a hora de 'procurar' por um novo KeyColvalor, você select min(KeyCol) from available_for_use(obviamente, há um pouco mais disso desde que a) precisará codificar para problemas de simultaneidade - não queira duas cópias do seu processo agarrando o mesmo min(KeyCol)eb) você precisará excluir min(KeyCol)da tabela; isso deve ser relativamente fácil de codificar, talvez como um processo armazenado e pode ser abordado em outra sessão de perguntas e respostas, se necessário)
• na pior das hipóteses, se seu select min(KeyCol)processo não encontrar linhas disponíveis, você poderá iniciar seu processo 'top off' para gerar um novo lote de linhas

Com essas alterações propostas no modelo de dados:

• você elimina MUITOS ciclos excessivos de CPU [seu DBA agradece]
• você elimina TODAS todas essas verificações repetitivas de índice e trocas de cache [seu DBA agradece]
• seus usuários não precisam mais assistir ao relógio giratório (embora não gostem da perda de uma desculpa para se afastar da mesa)
• existem várias maneiras de monitorar o tamanho da available_for_usetabela para garantir que você nunca fique sem novos valores

Sim, a available_for_usetabela proposta é apenas uma tabela de valores pré-gerados da 'próxima chave'; e sim, existe um potencial para alguma disputa ao pegar o valor 'próximo', mas qualquer disputa a) é facilmente resolvida através do design adequado de tabela / índice / consulta eb) será menor / terá vida curta em comparação com a sobrecarga / atrasa com a ideia atual de pesquisas repetidas e de força bruta no índice.

Existem alguns desafios com esta pergunta. Os índices no SQL Server podem fazer o seguinte de maneira muito eficiente, com apenas algumas leituras lógicas cada:

• verifique se existe uma linha
• verifique se uma linha não existe
• encontre a próxima linha começando em algum momento
• encontre a linha anterior começando em algum momento

No entanto, eles não podem ser usados ​​para localizar a enésima linha em um índice. Para isso, é necessário rolar o seu próprio índice armazenado como uma tabela ou varrer as primeiras N linhas no índice. Seu código C # depende muito do fato de que você pode encontrar com eficiência o enésimo elemento da matriz, mas não pode fazer isso aqui. Eu acho que esse algoritmo não é utilizável para T-SQL sem uma alteração no modelo de dados.

O segundo desafio está relacionado às restrições sobre os BINARYtipos de dados. Tanto quanto posso dizer, você não pode realizar adição, subtração ou divisão da maneira usual. Você pode converter seu BINARY(64)em um BIGINTe ele não gerará erros de conversão, mas o comportamento não está definido :

Não é garantido que as conversões entre qualquer tipo de dados e os tipos de dados binários sejam as mesmas entre as versões do SQL Server.

Além disso, a falta de erros de conversão é um problema aqui. Você pode converter qualquer coisa maior que o maior BIGINTvalor possível, mas isso gera resultados errados.

É verdade que você tem valores maiores que 9223372036854775807. No entanto, se você está sempre começando em 1 e pesquisando o menor valor mínimo, esses valores grandes não podem ser relevantes, a menos que sua tabela tenha mais de 9223372036854775807 linhas. Isso parece improvável porque sua tabela naquele momento teria cerca de 2000 exabytes, portanto, para fins de resposta à sua pergunta, vou assumir que valores muito grandes não precisam ser pesquisados. Também farei a conversão de tipos de dados, porque eles parecem inevitáveis.

Para os dados de teste, inseri o equivalente a 50 milhões de números inteiros seqüenciais em uma tabela, além de mais 50 milhões de números inteiros com uma única diferença de valor a cada 20 valores. Também inseri um valor único que não cabe corretamente em um assinado 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));

Esse código levou alguns minutos para ser executado na minha máquina. Fiz com que a primeira metade da tabela não tivesse lacunas para representar uma espécie de pior caso de desempenho. O código que eu usei para resolver o problema varre o índice em ordem para que ele termine muito rapidamente se a primeira lacuna estiver no início da tabela. Antes de chegarmos a isso, vamos verificar se os dados estão como deveriam:

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

Os resultados sugerem que o valor máximo em que convertemos BIGINTé 102500672:

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

Existem 100 milhões de linhas com valores que se encaixam no BIGINT conforme o esperado:

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

Uma abordagem para esse problema é verificar o índice em ordem e sair assim que o valor de uma linha não corresponder ao ROW_NUMBER()valor esperado . A tabela inteira não precisa ser digitalizada para obter a primeira linha: somente as linhas até a primeira lacuna. Aqui está uma maneira de escrever código com probabilidade de obter esse plano 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 motivos que não se encaixam nessa resposta, essa consulta geralmente é executada em série pelo SQL Server e o SQL Server subestima o número de linhas que precisam ser verificadas antes que a primeira correspondência seja encontrada. Na minha máquina, o SQL Server verifica 50000022 linhas do índice antes de encontrar a primeira correspondência. A consulta leva 11 segundos para ser executada. Observe que isso retorna o primeiro valor após o intervalo. Não está claro qual linha você deseja exatamente, mas você deve poder alterar a consulta para atender às suas necessidades sem muitos problemas. Aqui está a aparência do plano :

Minha única outra idéia era intimidar o SQL Server a usar o paralelismo para a consulta. Eu tenho quatro CPUs, então eu vou dividir os dados em quatro intervalos e fazer buscas nesses intervalos. Cada CPU receberá um intervalo. Para calcular os intervalos, peguei o valor máximo e assumi que os dados eram distribuídos igualmente. Se você quiser ser mais inteligente, consulte um histograma de estatísticas com amostra dos valores das colunas e crie seus intervalos dessa maneira. O código abaixo se baseia em muitos truques não documentados que não são seguros para produção, incluindo o sinalizador de rastreamento 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);

Aqui está a aparência do padrão de loop aninhado paralelo:

No geral, a consulta funciona mais do que antes, pois varrerá mais linhas na tabela. No entanto, agora ele é executado em 7 segundos na minha área de trabalho. Pode paralelizar melhor em um servidor real. Aqui está um link para o plano real .

Realmente não consigo pensar em uma boa maneira de resolver esse problema. Fazer o cálculo fora do SQL ou alterar o modelo de dados pode ser sua melhor aposta.

Aqui está uma resposta que provavelmente não vai funcionar para você, mas eu a adicionarei de qualquer maneira.

Embora BINARY (64) seja enumerável, há um suporte insuficiente para determinar o sucessor de um item. Como o BIGINT parece ser muito pequeno para o seu domínio, você pode considerar usar um DECIMAL (38,0), que parece ser o maior tipo de NUMBER no servidor SQL.

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

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

É fácil encontrar a primeira lacuna, pois podemos construir o número que estamos procurando:

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;

Uma junção de loop aninhada sobre o índice pk deve ser suficiente para encontrar o primeiro item disponível.