Mapy bitowe

Wyobraź sobie, że jesteś deweloperem MS SQL Server, Twój kierownik polecił Ci abyś przygotował strukturę w bazie danych do przechowywania grafików miesięcznych obowiązywania promocji w Waszej firmie.

Promocje obowiązują tylko na jeden miesiąc, ale mogą występować w różne dni, np. od 1 do 5 dnia miesiąca, 10, 15, 20 i od 25 do 31. Firma spodziewa się bardzo dużej ilości danych w tej strukturze, dlatego Twoja struktura musi być kompaktowa. Ma umożliwiać łatwe przechowywanie i bardzo szybkie wyszukiwanie promocji w celach raportowych.

Test rozwiązania:

• 1 mln promocji
• Promocja występuje średnio 6-7 razy w miesiącu
• Zliczenie promocji w wąskim zakresie, które zwróci ~4 000 wierszy, np. zakres 1-3,11,18-21
• Zliczenie promocji w szerszym zakresie, które zwróci ~32 000 wierszy, np. zakres 5-10

 

Rozwiązań tego zadania jest wiele, przetestujmy kilka z nich:

Typowa postać relacyjna z dwoma tabelami, czyli tabela promocji i powiązana z nią tabela wystąpień

Przykładowa struktura:

CREATE TABLE dbo.Promocje_R (
	Id INT IDENTITY PRIMARY KEY NOT NULL,
	Nazwa VARCHAR(20) NOT NULL,
	Miesiac DATE NOT NULL
) WITH(DATA_COMPRESSION = PAGE)
GO
CREATE TABLE dbo.Wystapienia_R (
	Promocja_Id INT NOT NULL CONSTRAINT FK_Promocja_Id FOREIGN KEY REFERENCES dbo.Promocje_R (Id),
	Wystapienie TINYINT NOT NULL
)
GO
CREATE CLUSTERED INDEX IX ON dbo.Wystapienia_R (Wystapienie) WITH(DATA_COMPRESSION = PAGE)
GO

A tak można ją odpytać:

WITH cte AS (
	SELECT COUNT(*) AS cnt
	  FROM dbo.Wystapienia_R
	 WHERE Wystapienie IN (1,11,21)
	 GROUP BY Promocja_Id
	HAVING COUNT(*) = 3
)
SELECT COUNT(*) FROM cte;

WITH cte AS (
	SELECT COUNT(*) AS cnt, Promocja_Id
	  FROM dbo.Wystapienia_R
	 WHERE Wystapienie IN (1,2,5,6,17,22,23,31)
	 GROUP BY Promocja_Id
	HAVING COUNT(*) = 8
)
SELECT COUNT(*) FROM cte;

 

Promocje w jednej tabeli z 31. kolumnami bitowymi

Przykładowa struktura:

CREATE TABLE dbo.Promocje_31BIT (
	Nazwa VARCHAR(20) NOT NULL,
	Miesiac DATE NOT NULL,
	D1 BIT NOT NULL,
	D2 BIT NOT NULL,
	D3 BIT NOT NULL,
	D4 BIT NOT NULL,
	D5 BIT NOT NULL,
	D6 BIT NOT NULL,
	D7 BIT NOT NULL,
	D8 BIT NOT NULL,
	D9 BIT NOT NULL,
	D10 BIT NOT NULL,
	D11 BIT NOT NULL,
	D12 BIT NOT NULL,
	D13 BIT NOT NULL,
	D14 BIT NOT NULL,
	D15 BIT NOT NULL,
	D16 BIT NOT NULL,
	D17 BIT NOT NULL,
	D18 BIT NOT NULL,
	D19 BIT NOT NULL,
	D20 BIT NOT NULL,
	D21 BIT NOT NULL,
	D22 BIT NOT NULL,
	D23 BIT NOT NULL,
	D24 BIT NOT NULL,
	D25 BIT NOT NULL,
	D26 BIT NOT NULL,
	D27 BIT NOT NULL,
	D28 BIT NOT NULL,
	D29 BIT NOT NULL,
	D30 BIT NOT NULL,
	D31 BIT NOT NULL
) WITH(DATA_COMPRESSION = PAGE)
GO

Wygląda co najmniej słabo, ale spełnia swoją rolę teraz to odpytajmy:

SELECT COUNT(*) 
  FROM dbo.Promocje_31BIT 
 WHERE d9 = 1
   AND d10 = 1
   AND d11 = 1
   AND d12 = 1
   AND d18 = 1 

SELECT COUNT(*) 
  FROM dbo.Promocje_31BIT 
 WHERE d7 = 1
   AND d8 = 1
   AND d9 = 1
   AND d10 = 1
   AND d11 = 1
   AND d12 = 1
   AND d13 = 1
   AND d14 = 1

 

Wystąpienia w postaci zdenormalizowanego ciągu znaków

Przykładowa struktura:

CREATE TABLE dbo.Promocje_StringMAP(
	Nazwa VARCHAR(20) NOT NULL,
	Miesiac DATE NOT NULL,
	Wystapienie CHAR(31) NOT NULL
) WITH(DATA_COMPRESSION = PAGE)
GO

Proste, czytelne, tylko zapytania przez LIKE 🙁

SELECT COUNT(*)
  FROM dbo.Promocje_StringMAP
WHERE Wystapienie LIKE '___111____1______1111__________'

SELECT COUNT(*)
  FROM dbo.Promocje_StringMAP
WHERE Wystapienie LIKE '___11111_______________________'

 

Wystąpienia w postaci zdenormalizowanej mapy bitowej

Przykładowa struktura:

CREATE TABLE dbo.Promocje_BitMAP(
       Nazwa VARCHAR(20) NOT NULL,
       Miesiac DATE NOT NULL,
       Wystapienie INT NOT NULL
) WITH(DATA_COMPRESSION = PAGE)
GO

Wszystko pięknie i zgrabnie, ale w tej postaci będzie nam to trudno czytać i odpytywać, coś musimy temu zaradzić. Dodajmy dwie funkcje do konwersji przedziałów na mapę bitową i odwrotnie oraz kolumnę wyliczalną w celu zwiększenia czytelności:

CREATE FUNCTION dbo.udfBitDaysToRange (@calendar_days INT)
RETURNS VARCHAR(200)
WITH SCHEMABINDING, RETURNS NULL ON NULL INPUT
AS
BEGIN
       DECLARE @Result VARCHAR(200);

       WITH cte1 AS (
             SELECT DISTINCT dm-rn AS grp, 
                       CASE WHEN COUNT(*) OVER(PARTITION BY dm-rn) = 1 THEN CAST(dm AS VARCHAR(200)) 
                                  WHEN COUNT(*) OVER(PARTITION BY dm-rn) = 2 
                                  THEN CAST(MIN(dm) OVER(PARTITION BY dm-rn) AS VARCHAR(200)) + ',' + CAST(MAX(dm) OVER(PARTITION BY dm-rn) AS VARCHAR(200)) 
                            ELSE CAST(MIN(dm) OVER(PARTITION BY dm-rn) AS VARCHAR(200)) + '-' + CAST(MAX(dm) OVER(PARTITION BY dm-rn) AS VARCHAR(200)) 
                            END+',' AS txt

             FROM (SELECT DISTINCT n AS dm, DENSE_RANK() OVER(ORDER BY n) AS rn 
                           FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),
                                               (10),(11),(12),(13),(14),(15),(16),(17),(18),(19),
                                               (20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31)) t(n)
                       WHERE @calendar_days & POWER(2,n-1)=POWER(2,n-1))t
             
       ), cte2(t) AS (
             SELECT txt AS [text()] FROM cte1
             ORDER BY grp
             FOR XML PATH('')
       )
       SELECT @Result = LEFT(t, LEN(t)-1) FROM cte2

       RETURN @Result;
END
GO

CREATE FUNCTION dbo.udfBitDaysFromRange (@calendar_days VARCHAR(200))
RETURNS INT
WITH SCHEMABINDING, RETURNS NULL ON NULL INPUT
AS
BEGIN
       DECLARE @Result INT;

       SET @calendar_days = CASE WHEN LEFT(@calendar_days, 1) <> ',' THEN ',' ELSE '' END
                      + REPLACE(@calendar_days, ' ', '') +
                    CASE WHEN RIGHT(@calendar_days, 1) <> ',' THEN ',' ELSE '' END;

       IF @calendar_days LIKE '%[^-,0-9]%' 
             --RAISERROR('Invalid value specified for @calendar_days parameter.', 16, 1);
             RETURN @Result;
                  
       WITH d AS (
       SELECT n 
       FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),
                           (10),(11),(12),(13),(14),(15),(16),(17),(18),(19),
                           (20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31)) t(n)
       ), cte AS (
       SELECT POWER(2,n-1) AS b FROM d WHERE CHARINDEX( ',' + CAST(n AS VARCHAR(2)) + ',', @calendar_days ) > 0
       UNION
       SELECT POWER(2,d3.n-1) AS b FROM d d1 CROSS JOIN d d2
       JOIN d d3 ON d3.n BETWEEN d1.n AND d2.n 
       WHERE CHARINDEX( ',' + CAST(d1.n AS VARCHAR(2)) + '-' + CAST(d2.n AS VARCHAR(2)) + ',', @calendar_days ) > 0
       )
       SELECT @Result = COALESCE(SUM(b),0) FROM cte
       RETURN @Result
END
GO

ALTER TABLE dbo.Promocje_BitMAP
ADD Opis AS (dbo.udfBitDaysToRange(Wystapienie));
GO

Dzięki prostym funkcjom teraz jest to dla nas czytelne i możemy łatwo odpytywać:

DECLARE @i INT

SET @i = dbo.udfBitDaysFromRange('1-3,11,18-21')
SELECT COUNT(*)
  FROM dbo.Promocje_BitMAP
 WHERE Wystapienie & @i = @i

SET @i = dbo.udfBitDaysFromRange('1-5')
SELECT COUNT(*)
  FROM dbo.Promocje_BitMAP
 WHERE Wystapienie & @i = @i

 

Wyniki testów

Zajętość miejsca:

Table Name	# Records	Reserved (KB)	Data (KB)	Indexes (KB)	Unused (KB)
dbo.Promocje_R	1 000 000	15 880	15 016	136	728
dbo.Wystapienia_R	6 587 014	157 712	74 680	82 424	608
dbo.Promocje_31BIT	1 000 000	30 280	30 072	72	136
dbo.Promocje_StringMAP	1 000 000	40 392	39 584	336	472
dbo.Promocje_BitMAP	1 000 000	19 272	19 184	56	32

 

Wydajność:

Wyszukanie 32k wierszy
	logical reads	time(ms)
Postać relacyjna	3495	121
31. kolumn bitowych	3759	72
Mapa tekstowa	4982	641
Mapa bitowa	2405	52

 

Wyszukanie 4k wierszy
	logical reads	time(ms)
Postać relacyjna	9692	341
31. kolumn bitowych	3759	71
Mapa tekstowa	4982	665
Mapa bitowa	2405	51

 

Podsumowanie

Jak widać po wynikach, postać relacyjna zajmuje zdecydowanie najwięcej przestrzeni dyskowej i jest prawie najwolniejsza w odpytywaniu.

Mapa tekstowa, choć w miarę czytelna (o ile się nie pomylimy w liczeniu miejsc) jest strasznie wolna, SQL Server nigdy nie grzeszył operacjami na literałach.

Najlepiej wypadają mapy bitowe, zajmują najmniej miejsca i najszybciej się je odpytuje, a dzięki dodatkowym funkcjom stają się czytelne dla użytkownika.

Rozumiem, że cześć z Was krzywi się na samą myśl o utracie pierwszej postaci normalnej w swojej bazie danych, a co za tym idzie wszystkich pozostałych, ale już od dawna stosujemy typy złożone w relacyjnych bazach danych takie jak XML, JSON, typy geometryczne czy geograficzne.

Prostota i wydajność rozwiązania z mapami bitowymi przemawia sama za siebie, jest to idealny wybór dla rozwiązań typu kalendarz, tablica ustawień sesji użytkownika czy parametrów systemowych aplikacji.

PS

Przy okazji testów udało mi się osiągnąć 3-5 razy lepsze wyniki od mapy bitowej w rozwiązaniu z 31. kolumnami bitowymi, gdy utworzyłem indeks kolumnowy i odpytywałem każdą kolumnę osobno. Jednak nie każdego stać na wersję z indeksami kolumnowymi, a struktura takiego rozwiązania wygląda mało profesjonalnie. Ja zostaję przy rozwiązaniu z mapą bitową 🙂