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

Existem alguns desafios com esta pergunta. Os índices no SQL Server podem fazer o seguinte de forma 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 ponto
• encontrar a linha anterior começando em algum ponto

No entanto, eles não podem ser usados ​​para localizar a enésima linha em um índice. Fazer isso requer que você role seu próprio índice armazenado como uma tabela ou verifique as primeiras N linhas no índice. Seu código C# depende muito do fato de que você pode encontrar eficientemente o N-ésimo elemento da matriz, mas não pode fazer isso aqui. 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)para a BIGINTe não gerará erros de conversão, mas o comportamento não está definido :

Não há garantia de 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 lhe dará os resultados errados.

É verdade que você tem valores agora que são maiores que 9223372036854775807. No entanto, se você está sempre começando em 1 e procurando pelo 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 nesse ponto estaria em torno de 2.000 exabytes, portanto, para responder à sua pergunta, vou assumir que os valores muito grandes não precisam ser pesquisados. Eu também vou fazer a conversão de tipos de dados porque eles parecem ser inevitáveis.

Para os dados de teste, inseri o equivalente a 50 milhões de inteiros sequenciais em uma tabela junto com mais 50 milhões de inteiros com uma única diferença de valor a cada 20 valores. Também inseri um único valor que não caberá corretamente em um sinal 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 para o desempenho. O código que usei para resolver o problema verifica 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 para o qual 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 escaneada para obter a primeira linha: apenas as linhas até o primeiro intervalo. Aqui está uma maneira de escrever código que provavelmente 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 nesta resposta, essa consulta geralmente será executada em série pelo SQL Server e o SQL Server geralmente subestimará 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. Veja como é o plano :

Minha única outra ideia era forçar o SQL Server a usar paralelismo para a consulta. Eu tenho quatro CPUs, então vou dividir os dados em quatro intervalos e fazer buscas nesses intervalos. Cada CPU será atribuída a um intervalo. Para calcular os intervalos, apenas peguei o valor máximo e assumi que os dados estavam distribuídos uniformemente. Se você quiser ser mais esperto sobre isso, você pode olhar para um histograma de estatísticas de amostra para os valores da coluna e construir seus intervalos dessa maneira. O código abaixo depende de 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 verifica 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 .

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

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

• altamente duvidoso que todos os valores fiquem sem KeyColvalores < bigintmax (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 vá 'eficientemente' encontrar uma lacuna o tempo todo; você pode ter sorte e encontrar uma lacuna perto do início de sua pesquisa, ou pode pagar caro para encontrar a lacuna em sua pesquisa
• enquanto pensava brevemente em como paralelizar a consulta, rapidamente descartei essa ideia (como DBA, não gostaria de descobrir que seu processo está sobrecarregando rotineiramente meu servidor de dados com 100% de utilização da CPU ... cópias deste em execução ao mesmo tempo); nãooooo ... paralelização vai estar fora de questão

Então o que fazer?

Vamos colocar a ideia de pesquisa (repetida, com uso intensivo de CPU e força bruta) em espera por um minuto e olhar para o quadro maior.

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

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

• uma nova tabela que acompanha um conjunto de KeyColvalores 'disponíveis para uso', por exemplo:available_for_use(KeyCol binary(64) not null primary key)
• quantos registros você mantém nesta tabela cabe a você decidir, por exemplo, talvez o suficiente para um mês de atividade?
• a tabela pode periodicamente (semanal?) ser 'completada' com um novo lote de KeyColvalores (talvez crie um proc armazenado 'top off'?) [por exemplo, atualize a select/top/row_number()consulta de Joe para fazer um 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 poucos valores
• um novo (ou modificado) gatilho DELETE 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 gatilho UPDATE novo/modificado no >main_table< para também manter nossa nova tabela available_for_useatualizada
• quando chega a hora de 'procurar' por um novo KeyColvalor, você select min(KeyCol) from available_for_use(obviamente, há um pouco mais disso, pois a) você precisará codificar para problemas de simultaneidade - não queira 2 cópias do seu processo pegando o mesmo min(KeyCol)e b) você 'precisará deletar min(KeyCol)da tabela; isso deve ser relativamente fácil de codificar, talvez como um proc armazenado, e pode ser abordado em outro Q&A, se necessário)
• na pior das hipóteses, se o seu select min(KeyCol)processo não encontrar linhas disponíveis, você poderá iniciar seu proc 'top off' para gerar um novo lote de linhas

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

• você elimina MUITOS ciclos de CPU excessivos [seu DBA agradecerá]
• você elimina TODAS essas varreduras repetitivas de índice e cache thrashing [seu DBA agradecerá]
• seus usuários não precisam mais assistir a ampulheta girando (embora possam não gostar de perder uma desculpa para se afastar de sua mesa)
• existem muitas 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 de 'próxima chave' pré-gerados; e sim, há um potencial para alguma contenção ao pegar o valor 'próximo', mas qualquer contenção a) é facilmente abordada por meio do design adequado de tabela/índice/consulta e b) será menor/de curta duração em comparação com a sobrecarga/ atrasos com a ideia atual de buscas repetidas, de força bruta, de índice.

Aqui está uma resposta que provavelmente não funcionará para você, mas vou adicioná-la de qualquer maneira.

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

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

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

Encontrar a primeira lacuna é fácil, 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 aninhado sobre o índice pk deve ser suficiente para encontrar o primeiro item disponível.