Meu amigo Peter Larsson me enviou um desafio T-SQL envolvendo a correspondência entre oferta e demanda. No que diz respeito aos desafios, é formidável. É uma necessidade bastante comum na vida real; é simples de descrever e muito fácil de resolver com desempenho razoável usando uma solução baseada em cursor. A parte complicada é resolvê-lo usando uma solução eficiente baseada em conjuntos.
Quando Peter me envia um quebra-cabeça, normalmente respondo com uma solução sugerida, e ele geralmente apresenta uma solução brilhante e de melhor desempenho. Às vezes suspeito que ele me envia quebra-cabeças para se motivar a encontrar uma ótima solução.
Como a tarefa representa uma necessidade comum e é muito interessante, perguntei a Peter se ele se importaria se eu a compartilhasse e suas soluções com os leitores do sqlperformance.com, e ele ficou feliz em me deixar.
Este mês, apresentarei o desafio e a solução clássica baseada em cursor. Em artigos subsequentes, apresentarei soluções baseadas em conjuntos – incluindo aquelas em que Peter e eu trabalhamos.
O desafio
O desafio envolve consultar uma tabela chamada Leilões, que você cria usando o seguinte código:
DROP TABLE IF EXISTS dbo.Auctions;
CREATE TABLE dbo.Auctions
(
ID INT NOT NULL IDENTITY(1, 1)
CONSTRAINT pk_Auctions PRIMARY KEY CLUSTERED,
Code CHAR(1) NOT NULL
CONSTRAINT ck_Auctions_Code CHECK (Code = 'D' OR Code = 'S'),
Quantity DECIMAL(19, 6) NOT NULL
CONSTRAINT ck_Auctions_Quantity CHECK (Quantity > 0)
); Esta tabela contém entradas de demanda e oferta. As entradas de demanda são marcadas com o código D e as entradas de suprimento com S. Sua tarefa é combinar as quantidades de oferta e demanda com base na ordenação de ID, escrevendo o resultado em uma tabela temporária. As entradas podem representar ordens de compra e venda de criptomoedas, como BTC/USD, ordens de compra e venda de ações, como MSFT/USD, ou qualquer outro item ou bem em que você precise combinar a oferta com a demanda. Observe que as entradas de leilões não possuem um atributo de preço. Conforme mencionado, você deve combinar as quantidades de oferta e demanda com base no pedido de ID. Essa ordenação pode ser derivada do preço (crescente para entradas de oferta e decrescente para entradas de demanda) ou qualquer outro critério relevante. Nesse desafio, a ideia era manter as coisas simples e assumir que o ID já representa a ordem relevante para correspondência.
Como exemplo, use o código a seguir para preencher a tabela Leilões com um pequeno conjunto de dados de amostra:
SET NOCOUNT ON; DELETE FROM dbo.Auctions; SET IDENTITY_INSERT dbo.Auctions ON; INSERT INTO dbo.Auctions(ID, Code, Quantity) VALUES (1, 'D', 5.0), (2, 'D', 3.0), (3, 'D', 8.0), (5, 'D', 2.0), (6, 'D', 8.0), (7, 'D', 4.0), (8, 'D', 2.0), (1000, 'S', 8.0), (2000, 'S', 6.0), (3000, 'S', 2.0), (4000, 'S', 2.0), (5000, 'S', 4.0), (6000, 'S', 3.0), (7000, 'S', 2.0); SET IDENTITY_INSERT dbo.Auctions OFF;
Você deve combinar as quantidades de oferta e demanda assim:
- Uma quantidade de 5,0 corresponde à Demanda 1 e à Oferta 1.000, esgotando a Demanda 1 e deixando 3,0 da Oferta 1.000
- Uma quantidade de 3,0 corresponde à Demanda 2 e à Oferta 1.000, esgotando a Demanda 2 e a Oferta 1.000
- Uma quantidade de 6,0 corresponde à Demanda 3 e Oferta 2000, deixando 2,0 da Demanda 3 e esgotando a oferta 2.000
- Uma quantidade de 2,0 corresponde à Demanda 3 e à Oferta 3.000, esgotando a Demanda 3 e a Oferta 3.000
- Uma quantidade de 2,0 corresponde à Demanda 5 e à Oferta 4.000, esgotando a Demanda 5 e a Oferta 4.000
- Uma quantidade de 4,0 corresponde à Demanda 6 e à Oferta 5.000, deixando 4,0 da Demanda 6 e esgotando a Oferta 5.000
- Uma quantidade de 3,0 corresponde à demanda 6 e oferta 6.000, deixando 1,0 da demanda 6 e esgotando a oferta 6.000
- Uma quantidade de 1,0 corresponde à Demanda 6 e à Oferta 7.000, esgotando a Demanda 6 e deixando 1,0 da Oferta 7.000
- Uma quantidade de 1,0 corresponde à Demanda 7 e à Oferta 7.000, deixando 3,0 da Demanda 7 e esgotando a Oferta 7.000; A demanda 8 não corresponde a nenhuma entrada de fornecimento e, portanto, fica com a quantidade total 2,0
Sua solução deve gravar os seguintes dados na tabela temporária resultante:
DemandID SupplyID TradeQuantity ----------- ----------- -------------- 1 1000 5.000000 2 1000 3.000000 3 2000 6.000000 3 3000 2.000000 5 4000 2.000000 6 5000 4.000000 6 6000 3.000000 6 7000 1.000000 7 7000 1.000000
Grande conjunto de dados de amostra
Para testar o desempenho das soluções, você precisará de um conjunto maior de dados de amostra. Para ajudar com isso, você pode usar a função GetNums, que você cria executando o seguinte código:
CREATE FUNCTION dbo.GetNums(@low AS BIGINT = 1, @high AS BIGINT)
RETURNS TABLE
AS
RETURN
WITH
L0 AS ( SELECT 1 AS c
FROM (VALUES(1),(1),(1),(1),(1),(1),(1),(1),
(1),(1),(1),(1),(1),(1),(1),(1)) AS D(c) ),
L1 AS ( SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B ),
L2 AS ( SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B ),
L3 AS ( SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B ),
Nums AS ( SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L3 )
SELECT TOP(@high - @low + 1)
rownum AS rn,
@high + 1 - rownum AS op,
@low - 1 + rownum AS n
FROM Nums
ORDER BY rownum;
GO Esta função retorna uma sequência de inteiros no intervalo solicitado.
Com essa função em vigor, você pode usar o seguinte código fornecido por Peter para preencher a tabela Leilões com dados de exemplo, personalizando as entradas conforme necessário:
DECLARE
-- test with 50K, 100K, 150K, 200K in each of variables @Buyers and @Sellers
-- so total rowcount is double (100K, 200K, 300K, 400K)
@Buyers AS INT = 200000,
@Sellers AS INT = 200000,
@BuyerMinQuantity AS DECIMAL(19, 6) = 0.000001,
@BuyerMaxQuantity AS DECIMAL(19, 6) = 99.999999,
@SellerMinQuantity AS DECIMAL(19, 6) = 0.000001,
@SellerMaxQuantity AS DECIMAL(19, 6) = 99.999999;
DELETE FROM dbo.Auctions;
INSERT INTO dbo.Auctions(Code, Quantity)
SELECT Code, Quantity
FROM ( SELECT 'D' AS Code,
(ABS(CHECKSUM(NEWID())) % (1000000 * (@BuyerMaxQuantity - @BuyerMinQuantity)))
/ 1000000E + @BuyerMinQuantity AS Quantity
FROM dbo.GetNums(1, @Buyers)
UNION ALL
SELECT 'S' AS Code,
(ABS(CHECKSUM(NEWID())) % (1000000 * (@SellerMaxQuantity - @SellerMinQuantity)))
/ 1000000E + @SellerMinQuantity AS Quantity
FROM dbo.GetNums(1, @Sellers) ) AS X
ORDER BY NEWID();
SELECT Code, COUNT(*) AS Items
FROM dbo.Auctions
GROUP BY Code; Como você pode ver, você pode personalizar o número de compradores e vendedores, bem como as quantidades mínimas e máximas de compradores e vendedores. O código acima especifica 200.000 compradores e 200.000 vendedores, resultando em um total de 400.000 linhas na tabela Leilões. A última consulta informa quantas entradas de demanda (D) e oferta (S) foram gravadas na tabela. Ele retorna a seguinte saída para as entradas mencionadas:
Code Items ---- ----------- D 200000 S 200000
Vou testar o desempenho de várias soluções usando o código acima, definindo o número de compradores e vendedores para o seguinte:50.000, 100.000, 150.000 e 200.000. Isso significa que obterei os seguintes números totais de linhas na tabela:100.000, 200.000, 300.000 e 400.000. Obviamente, você pode personalizar as entradas conforme desejar para testar o desempenho de suas soluções.
Solução baseada em cursor
Peter forneceu a solução baseada em cursor. É bastante básico, que é uma de suas vantagens importantes. Será usado como referência.
A solução utiliza dois cursores:um para entradas de demanda ordenadas por ID e outro para entradas de suprimentos ordenadas por ID. Para evitar uma verificação completa e uma classificação por cursor, crie o seguinte índice:
CREATE UNIQUE NONCLUSTERED INDEX idx_Code_ID_i_Quantity ON dbo.Auctions(Code, ID) INCLUDE(Quantity);
Aqui está o código da solução completa:
SET NOCOUNT ON;
DROP TABLE IF EXISTS #PairingsCursor;
CREATE TABLE #PairingsCursor
(
DemandID INT NOT NULL,
SupplyID INT NOT NULL,
TradeQuantity DECIMAL(19, 6) NOT NULL
);
DECLARE curDemand CURSOR LOCAL FORWARD_ONLY READ_ONLY FOR
SELECT ID AS DemandID, Quantity FROM dbo.Auctions WHERE Code = 'D' ORDER BY ID;
DECLARE curSupply CURSOR LOCAL FORWARD_ONLY READ_ONLY FOR
SELECT ID AS SupplyID, Quantity FROM dbo.Auctions WHERE Code = 'S' ORDER BY ID;
DECLARE @DemandID AS INT, @DemandQuantity AS DECIMAL(19, 6),
@SupplyID AS INT, @SupplyQuantity AS DECIMAL(19, 6);
OPEN curDemand;
FETCH NEXT FROM curDemand INTO @DemandID, @DemandQuantity;
OPEN curSupply;
FETCH NEXT FROM curSupply INTO @SupplyID, @SupplyQuantity;
WHILE @@FETCH_STATUS = 0
BEGIN
IF @DemandQuantity <= @SupplyQuantity
BEGIN
INSERT #PairingsCursor(DemandID, SupplyID, TradeQuantity)
VALUES(@DemandID, @SupplyID, @DemandQuantity);
SET @SupplyQuantity -= @DemandQuantity;
FETCH NEXT FROM curDemand INTO @DemandID, @DemandQuantity;
END;
ELSE
BEGIN
IF @SupplyQuantity > 0
BEGIN
INSERT #PairingsCursor(DemandID, SupplyID, TradeQuantity)
VALUES(@DemandID, @SupplyID, @SupplyQuantity);
SET @DemandQuantity -= @SupplyQuantity;
END;
FETCH NEXT FROM curSupply INTO @SupplyID, @SupplyQuantity;
END;
END;
CLOSE curDemand;
DEALLOCATE curDemand;
CLOSE curSupply;
DEALLOCATE curSupply; Como você pode ver, o código começa criando uma tabela temporária. Em seguida, ele declara os dois cursores e busca uma linha de cada um, gravando a quantidade de demanda atual na variável @DemandQuantity e a quantidade de suprimento atual em @SupplyQuantity. Em seguida, ele processa as entradas em um loop, desde que a última busca tenha sido bem-sucedida. O código aplica a seguinte lógica no corpo do loop:
Se a quantidade de demanda atual for menor ou igual à quantidade de oferta atual, o código faz o seguinte:
- Grava uma linha na tabela temporária com o pareamento atual, com a quantidade de demanda (@DemandQuantity) como a quantidade correspondente
- Subtrai a quantidade de demanda atual da quantidade de oferta atual (@SupplyQuantity)
- Busca a próxima linha do cursor de demanda
Caso contrário, o código faz o seguinte:
- Verifica se a quantidade de fornecimento atual é maior que zero e, em caso afirmativo, faz o seguinte:
- Grava uma linha na tabela temporária com o pareamento atual, com a quantidade de fornecimento como a quantidade correspondente
- Subtrai a quantidade de oferta atual da quantidade de demanda atual
- Busca a próxima linha do cursor de fornecimento
Uma vez que o loop é feito, não há mais pares para corresponder, então o código apenas limpa os recursos do cursor.
Do ponto de vista do desempenho, você obtém a sobrecarga típica de busca e loop do cursor. Então, novamente, esta solução faz uma única passagem ordenada sobre os dados de demanda e uma única passagem ordenada sobre os dados de fornecimento, cada uma usando uma varredura de busca e intervalo no índice que você criou anteriormente. Os planos para as consultas do cursor são mostrados na Figura 1.
Figura 1:planos para consultas de cursor
Como o plano realiza uma busca e varredura de alcance ordenado de cada uma das partes (demanda e oferta) sem nenhuma classificação envolvida, ele possui escala linear. Isso foi confirmado pelos números de desempenho que obtive ao testá-lo, conforme mostrado na Figura 2.
Figura 2:desempenho da solução baseada em cursor
Se você estiver interessado em tempos de execução mais precisos, aqui estão eles:
- 100.000 linhas (50.000 demandas e 50.000 suprimentos):2,93 segundos
- 200.000 linhas:5,89 segundos
- 300.000 linhas:8,75 segundos
- 400.000 linhas:11,81 segundos
Dado que a solução tem escala linear, você pode prever facilmente o tempo de execução com outras escalas. Por exemplo, com um milhão de linhas (digamos, 500.000 demandas e 500.000 suprimentos), deve levar cerca de 29,5 segundos para ser executado.
O desafio começou
A solução baseada em cursor tem escala linear e, como tal, não é ruim. Mas isso incorre na sobrecarga típica de busca e loop do cursor. Obviamente, você pode reduzir essa sobrecarga implementando o mesmo algoritmo usando uma solução baseada em CLR. A questão é:você pode encontrar uma solução baseada em conjunto de bom desempenho para essa tarefa?
Conforme mencionado, explorarei soluções baseadas em conjuntos – tanto com baixo desempenho quanto com bom desempenho – a partir do próximo mês. Enquanto isso, se você estiver à altura do desafio, veja se consegue criar suas próprias soluções baseadas em conjuntos.
Para verificar a exatidão de sua solução, primeiro compare seu resultado com o mostrado aqui para o pequeno conjunto de dados de amostra. Você também pode verificar a validade do resultado da sua solução com um grande conjunto de dados de amostra verificando se a diferença simétrica entre o resultado da solução do cursor e o seu está vazia. Supondo que o resultado do cursor seja armazenado em uma tabela temporária chamada #PairingsCursor e o seu em uma tabela temporária chamada #MyPairings, você pode usar o seguinte código para conseguir isso:
(SELECT * FROM #PairingsCursor EXCEPT SELECT * FROM #MyPairings) UNION ALL (SELECT * FROM #MyPairings EXCEPT SELECT * FROM #PairingsCursor);
O resultado deve estar vazio.
Boa sorte!
[Pular para soluções:Parte 1 | Parte 2 | Parte 3]
