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ą 🙂

One thought on “Mapy bitowe

  1. Lukasz pisze:

    Ciekaw jestem jak wyglądałaby statystyka dla “Promocje w jednej tabeli z 31. kolumnami bitowymi” gdyby zamiast NOT NULL użyć “SPARSE” i wypełniac na zasadzie:

    1 – obowiazuje
    NULL – nie obowiazuje

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

    a nastepnie:

    SELECT COUNT(*)
    FROM dbo.Promocje_31BIT
    WHERE d7 IS NOT NULL
    AND d8 IS NOT NULL
    AND d9 IS NOT NULL
    AND d10 IS NOT NULL
    AND d11 IS NOT NULL
    AND d12 IS NOT NULL
    AND d13 IS NOT NULL
    AND d14 IS NOT NULL

    Coś na wzór http://dbfiddle.uk/?rdbms=sqlserver_2017&fiddle=dc007f01a1ea88fd9ff0d619e3c515bb

    Byłbym bardzo wdzięczny za dodanie tego do procedury testowej 🙂

Pozostaw odpowiedź Lukasz Anuluj pisanie odpowiedzi

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *