Můj přítel Peter Larsson mi poslal T-SQL výzvu zahrnující sladění nabídky s poptávkou. Pokud jde o výzvy, je to impozantní. Je to docela běžná potřeba v reálném životě; je to jednoduché popsat a je to docela snadné vyřešit s přiměřeným výkonem pomocí řešení založeného na kurzoru. Ošemetnou částí je vyřešit to pomocí efektivního řešení založeného na množinách.
Když mi Peter pošle hádanku, obvykle odpovím navrženým řešením a on obvykle přijde s lepším a geniálním řešením. Někdy mám podezření, že mi posílá hádanky, aby se motivoval k vymýšlení skvělého řešení.
Vzhledem k tomu, že úkol představuje společnou potřebu a je tak zajímavý, zeptal jsem se Petra, zda by mu nevadilo, kdybych jej a jeho řešení sdílel se čtenáři sqlperformance.com, a on mi to rád dovolil.
Tento měsíc představím výzvu a klasické řešení založené na kurzoru. V následujících článcích představím řešení založená na množinách – včetně těch, na kterých jsme s Peterem pracovali.
Výzva
Výzva zahrnuje dotazování na tabulku s názvem Aukce, kterou vytvoříte pomocí následujícího kódu:
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)
); Tato tabulka obsahuje položky poptávky a nabídky. Položky poptávky jsou označeny kódem D a položky nabídky S. Vaším úkolem je spárovat množství nabídky a poptávky na základě ID objednávky a zapsat výsledek do dočasné tabulky. Položky by mohly představovat příkazy k nákupu a prodeji kryptoměny, jako je BTC/USD, příkazy k nákupu a prodeji akcií, jako je MSFT/USD, nebo jakékoli jiné položky nebo zboží, kde potřebujete sladit nabídku s poptávkou. Všimněte si, že v položkách Aukce chybí atribut ceny. Jak již bylo zmíněno, měli byste sladit množství nabídky a poptávky na základě ID objednávky. Toto řazení mohlo být odvozeno z ceny (vzestupně pro položky nabídky a sestupně pro položky poptávky) nebo jakýchkoli jiných relevantních kritérií. V této výzvě bylo myšlenkou udržet věci jednoduché a předpokládat, že ID již představuje relevantní příkaz pro párování.
Jako příklad použijte následující kód k vyplnění tabulky Aukce malou sadou ukázkových dat:
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;
Měli byste sladit množství nabídky a poptávky takto:
- Množství 5,0 odpovídá poptávce 1 a nabídce 1000, čímž se vyčerpá poptávka 1 a zbývá 3,0 nabídky 1000
- Množství 3,0 odpovídá poptávce 2 a nabídce 1000, čímž se vyčerpá poptávka 2 i nabídka 1000
- Množství 6,0 odpovídá poptávce 3 a nabídce 2000, zbývá 2,0 poptávky 3 a vyčerpání nabídky 2000
- Množství 2,0 odpovídá poptávce 3 a nabídce 3 000, čímž se vyčerpá poptávka 3 i nabídka 3 000
- Množství 2,0 odpovídá poptávce 5 a nabídce 4000, čímž se vyčerpá poptávka 5 i nabídka 4000
- Množství 4,0 odpovídá poptávce 6 a nabídce 5 000, přičemž zbývá 4,0 poptávky 6 a vyčerpá se nabídka 5 000
- Množství 3,0 odpovídá poptávce 6 a nabídce 6000, přičemž zbývá 1,0 poptávky 6 a vyčerpá se nabídka 6000
- Množství 1,0 odpovídá poptávce 6 a nabídce 7 000, čímž se vyčerpá poptávka 6 a zbývá 1,0 nabídky 7 000
- Množství 1,0 se shoduje s poptávkou 7 a nabídkou 7000, zbývá 3,0 z poptávky 7 a vyčerpáním nabídky 7000; Poptávka 8 se neshoduje s žádnými položkami nabídky, a proto zbývá celé množství 2.0
Vaše řešení má do výsledné dočasné tabulky zapsat následující data:
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
Velká sada ukázkových dat
Chcete-li otestovat výkon řešení, budete potřebovat větší sadu ukázkových dat. K tomu můžete použít funkci GetNums, kterou vytvoříte spuštěním následujícího kódu:
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 Tato funkce vrací sekvenci celých čísel v požadovaném rozsahu.
S touto funkcí můžete použít následující kód poskytnutý Petrem k naplnění tabulky Aukce ukázkovými daty a přizpůsobení vstupů podle potřeby:
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; Jak vidíte, můžete přizpůsobit počet kupujících a prodávajících a také minimální a maximální množství kupujících a prodávajících. Výše uvedený kód specifikuje 200 000 kupujících a 200 000 prodávajících, což má za následek celkem 400 000 řádků v tabulce Aukce. Poslední dotaz vám řekne, kolik položek poptávky (D) a nabídky (S) bylo zapsáno do tabulky. Pro výše uvedené vstupy vrací následující výstup:
Code Items ---- ----------- D 200000 S 200000
Chystám se otestovat výkon různých řešení pomocí výše uvedeného kódu a nastavit počet kupujících a prodejců na následující:50 000, 100 000, 150 000 a 200 000. To znamená, že dostanu následující celkový počet řádků v tabulce:100 000, 200 000, 300 000 a 400 000. Samozřejmě si můžete upravit vstupy, jak si přejete otestovat výkon vašich řešení.
Řešení založené na kurzoru
Peter poskytl řešení založené na kurzoru. Je to docela základní, což je jedna z jeho důležitých výhod. Bude použit jako benchmark.
Řešení používá dva kurzory:jeden pro položky poptávky seřazené podle ID a druhý pro položky nabídky seřazené podle ID. Chcete-li se vyhnout úplnému prohledávání a řazení podle kurzoru, vytvořte následující index:
CREATE UNIQUE NONCLUSTERED INDEX idx_Code_ID_i_Quantity ON dbo.Auctions(Code, ID) INCLUDE(Quantity);
Zde je úplný kód řešení:
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; Jak vidíte, kód začíná vytvořením dočasné tabulky. Poté deklaruje dva kurzory a z každého načte řádek, přičemž zapíše aktuální množství poptávky do proměnné @DemandQuantity a aktuální množství nabídky do @SupplyQuantity. Poté zpracovává položky ve smyčce, dokud bylo poslední načtení úspěšné. Kód používá v těle smyčky následující logiku:
Pokud je aktuální množství poptávky menší nebo rovno aktuálnímu množství nabídky, kód provede následující:
- Zapíše řádek do časové tabulky s aktuálním párováním, přičemž množství poptávky (@DemandQuantity) jako odpovídající množství
- Odečte aktuální poptávané množství od aktuálního množství nabídky (@SupplyQuantity)
- Načte další řádek z kurzoru poptávky
Jinak kód provede následující:
- Zkontroluje, zda je aktuální množství dodávky větší než nula, a pokud ano, provede následující:
- Zapíše řádek do tabulky temp s aktuálním párováním, přičemž množství dodávky je odpovídající množství
- Odečte aktuální množství nabídky od množství aktuální poptávky
- Načte další řádek z kurzoru nabídky
Jakmile je smyčka hotová, již nejsou k dispozici žádné páry, které by se shodovaly, takže kód pouze vyčistí zdroje kurzoru.
Z hlediska výkonu získáte typickou režii načítání kurzoru a opakování. Pak znovu, toto řešení provádí jeden uspořádaný průchod přes data poptávky a jeden uspořádaný průchod přes data nabídky, každý pomocí vyhledávání a prohledávání rozsahu v indexu, který jste vytvořili dříve. Plány pro kurzorové dotazy jsou znázorněny na obrázku 1.
Obrázek 1:Plány pro dotazy kurzoru
Vzhledem k tomu, že plán provádí vyhledávání a skenování uspořádaného rozsahu každé z částí (poptávky a nabídky) bez nutnosti třídění, má lineární měřítko. To bylo potvrzeno čísly výkonu, která jsem získal při testování, jak je znázorněno na obrázku 2.
Obrázek 2:Výkon řešení založeného na kurzoru
Pokud vás zajímají přesnější časy běhu, zde je:
- 100 000 řádků (50 000 požadavků a 50 000 zásob):2,93 sekundy
- 200 000 řádků:5,89 sekundy
- 300 000 řádků:8,75 sekundy
- 400 000 řádků:11,81 sekundy
Vzhledem k tomu, že řešení má lineární měřítko, můžete snadno předvídat dobu běhu s jinými měřítky. Například s milionem řádků (řekněme 500 000 požadavků a 500 000 dodávek) by mělo spuštění trvat asi 29,5 sekundy.
Výzva je spuštěna
Kurzorové řešení má lineární škálování a jako takové není špatné. Vyvolává však typické načítání kurzoru a režii smyčky. Je zřejmé, že tuto režii můžete snížit implementací stejného algoritmu pomocí řešení založeného na CLR. Otázkou je, dokážete pro tento úkol přijít s dobře fungujícím řešením založeným na sadě?
Jak již bylo zmíněno, od příštího měsíce prozkoumám řešení založená na sadách – jak špatně fungující, tak dobře fungující. Pokud mezitím zvládnete tuto výzvu, vyzkoušejte, zda dokážete přijít s vlastními řešeními založenými na množinách.
Chcete-li ověřit správnost svého řešení, nejprve porovnejte jeho výsledek s tím, který je zde uveden pro malou sadu vzorových dat. Můžete také zkontrolovat platnost výsledku vašeho řešení pomocí velké sady vzorových dat ověřením, že symetrický rozdíl mezi výsledkem kurzorového řešení a vaším je prázdný. Za předpokladu, že výsledek kurzoru je uložen v dočasné tabulce s názvem #PairingsCursor a váš v dočasné tabulce s názvem #MyPairings, můžete k tomu použít následující kód:
(SELECT * FROM #PairingsCursor EXCEPT SELECT * FROM #MyPairings) UNION ALL (SELECT * FROM #MyPairings EXCEPT SELECT * FROM #PairingsCursor);
Výsledek by měl být prázdný.
Hodně štěstí!
[ Přejít na řešení:Část 1 | Část 2 | část 3]