Strategier vid indexering av bitfält

Jag har länge varit förespråkare för att aldrig skapa index enbart bestående av bitfält. Jag har även läst den rekommendationen i flera böcker samt artiklar på internet från microsoft. Jag vill i detta inlägg visa att indexering av bitfält inte alltid är dåligt, samt visa ett sätt som kan vara användbart när man har många bitfält man vill ställa frågor mot och samtidigt få bra prestanda.

Låt oss skapa en tabell med några bitfält.

CREATE TABLE dbo.LargeTable
(
	LargeTableId INT NOT NULL IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
	Bit1 BIT NOT NULL,
	Bit2 BIT NOT NULL,
	Bit3 BIT NOT NULL,
	Bit4 BIT NOT NULL,
	Bit5 BIT NOT NULL,
	Bit6 BIT NOT NULL,
	Bit7 BIT NOT NULL,
	Bit8 BIT NOT NULL
)
GO

För att kunna generera testvärden till denna tabell så skapar vi en nummertabell

CREATE TABLE dbo.Numbers
(
    Number INT IDENTITY(1,1) PRIMARY KEY CLUSTERED
) 

WHILE COALESCE(SCOPE_IDENTITY(), 0) < = 1000000
BEGIN
    INSERT dbo.Numbers DEFAULT VALUES
END
-->

Vi kan nu generera testdata till vår tabell. Notera att vi genererar ett värde mellan -5 – 5 och sedan anger om bitfältet skall bli 0 eller 1 beroende på vilket slumpvärde vi får. Alla bitfält kommer därför att få olika fördelning av antal 0 eller 1. Slumpfunktionen har jag tagit härifrån sql-server-set-based-random-numbers.

DECLARE @i INT
SET @i = 0
SET NOCOUNT ON
WHILE @i < = 1000000
BEGIN
	INSERT INTO LargeTable (bit1, bit2, bit3, bit4, bit5, bit6, bit7, bit8)
	SELECT
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > -1 THEN 1 ELSE 0 END FROM Numbers) bit1,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > 0 THEN 1 ELSE 0 END FROM Numbers) bit2,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > 1 THEN 1 ELSE 0 END FROM Numbers) bit3,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > 2 THEN 1 ELSE 0 END FROM Numbers) bit4,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > 3 THEN 1 ELSE 0 END FROM Numbers) bit5,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > -2 THEN 1 ELSE 0 END FROM Numbers) bit6,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > -3 THEN 1 ELSE 0 END FROM Numbers) bit7,
		(SELECT TOP 1 CASE WHEN ABS(CHECKSUM(NewId())) % 11 - 5 > -4 THEN 1 ELSE 0 END FROM Numbers) bit8

	SET @i = @i + 1
END

Om vi nu ställer frågor mot denna tabellen, så får vi följande resultat.

SELECT LargeTableId FROM LargeTable WHERE bit1 = 0 and bit2 = 1 and bit3 = 0 and bit4 = 0 and bit5 = 1 and bit6 = 0 and bit7 = 1 and bit8 = 0

--(884 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 1864, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 172 ms,  elapsed time = 311 ms.

SELECT LargeTableId FROM LargeTable WHERE bit8 = 1 and bit2 = 1 and bit6 = 1 and bit3 = 0 and bit4 = 0 and bit1 = 1 and bit5 = 1 and bit7 = 0 

--(2995 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 1864, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 203 ms,  elapsed time = 367 ms.

Förmodligen är man inte nöjd med ovanstående resultat, om man tänkt köra frågan mer än en gång. Frågorna i mitt exempel returnerar visserligen ganska många rader, men jag tror att det går att få det snabbare.

Om vi inte kan indexera bitfält, så får vi väl försöka indexera ett integerfält. Därför borde man kunna skapa en tabell som innehåller alla möjliga kobinationer som man sedan använder som uppslagsverk. Vi kan tänka oss att vi frågar databasen ”vilket integervärde representerar raden som har bitvärde xyz?”

För att kunna göra denna koppling behöver vi lägga till en kolumn i vår LargeTable, vi kallar den LargeTableLookupId, nästa steg blir att skapa tabellen som skall innehålla alla bitkombinationer.
I steg tre fyller vi även tabellen.

ALTER TABLE dbo.LargeTable ADD
	LargeTableLookupId int NULL
GO
CREATE TABLE dbo.LargeTableLookup
(
	LargeTableLookupId INT NOT NULL IDENTITY(1,1) PRIMARY KEY CLUSTERED,
	Bit1 BIT NOT NULL,
	Bit2 BIT NOT NULL,
	Bit3 BIT NOT NULL,
	Bit4 BIT NOT NULL,
	Bit5 BIT NOT NULL,
	Bit6 BIT NOT NULL,
	Bit7 BIT NOT NULL,
	Bit8 BIT NOT NULL
)
GO

INSERT INTO LargeTableLookup
SELECT DISTINCT l1.bit1,l1.bit2,l1.bit3,l1.bit4,l1.bit5,l1.bit6,l1.bit7,l1.bit8 FROM LargeTable l1
CROSS JOIN LargeTable l2

När alla tabeller är skapade och kolumnen är på plats, så måste vi fylla vår LargeTableLookupId med rätt representationsid från vår LargeTableLookup-tabell. Vi behöver också skapa ett index på vår LargeTableLookupId-kolumn i vår LargeTable för att snabba upp frågorna.

UPDATE LargeTable SET LargeTableLookupId = (SELECT LargeTableLookupId from LargeTableLookup WHERE
Bit1=LargeTable.Bit1
and Bit2=LargeTable.Bit2
and Bit3=LargeTable.Bit3
and Bit4=LargeTable.Bit4
and Bit5=LargeTable.Bit5
and Bit6=LargeTable.Bit6
and Bit7=LargeTable.Bit7
and Bit8=LargeTable.Bit8
)
GO

CREATE INDEX ix_LargeTableLookupId ON LargeTable(LargeTableLookupId) INCLUDE(LargeTableId);

Om vi nu ställer samma frågor men använder vår nya kolumn så får vi följande prestanda.
Notera att de två översta frågorna endast används för att hämta ut rätt LargeTableLookupId som då motsvarar x antal poster i vår LargeTable. Dessa frågorna går fort eftersom det är få poster i tabellen (i vårt fall endast 256). Här kan man givetvis också indexera för att få bättre prestanda. Kanske även jobba med indexerade vyer eftersom datamängderna är små och inga förändringar sker i tabellen.

SELECT LargeTableLookupId FROM LargeTableLookup WHERE bit1 = 0 and bit2 = 1 and bit3 = 0 and bit4 = 0 and bit5 = 1 and bit6 = 0 and bit7 = 1 and bit8 = 0 -- 122
SELECT LargeTableLookupId FROM LargeTableLookup WHERE bit8 = 1 and bit2 = 1 and bit6 = 1 and bit3 = 0 and bit4 = 0 and bit1 = 1 and bit5 = 1 and bit7 = 0 -- 247

SELECT * FROM LargeTable WHERE LargeTableLookupId = 122

--(884 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 4, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 0 ms,  elapsed time = 111 ms.

SELECT * FROM LargeTable WHERE LargeTableLookupId = 247

--(2995 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 9, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 0 ms,  elapsed time = 108 ms.

Vi ser direkt att vi inte utnyttjar alls lika mycket CPU, och IO har gått ner väldigt mycket också.

Om vi nu återgår till testning av indexering av bitfält så låt oss skapa ett index och se vad som händer.

CREATE NONCLUSTERED INDEX [ix_bits]
ON LargeTable (bit1,bit2,bit3,bit4,bit5,bit6,bit7,bit8)
INCLUDE (LargeTableId,LargeTableLookupId)

Om vi nu ställer samma frågor som tidigare.

SELECT LargeTableId FROM LargeTable WHERE bit8 = 1 and bit2 = 1 and bit6 = 1 and bit3 = 0 and bit4 = 0 and bit1 = 1 and bit5 = 1 and bit7 = 0

--(2995 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 10, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 0 ms,  elapsed time = 99 ms.

SELECT LargeTableId FROM LargeTable WHERE LargeTableLookupId = 247

--(2995 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 9, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 0 ms,  elapsed time = 144 ms.

Nu ser vi att skillnaden är marginell. Varför är det dåligt att indexera bitfält? Det ser ut att vara jättebra?

Problemet med bitfält är ofta att det är relativt liten selektering, men det är givetvis från fall till fall och man kan inte säga att det generellt är dåligt att indexera bitfält. Med sql-server 2008 så finns stöd för indexfilter. Det som då händer är att man kan koppla ett WHERE-villkor till indexet, och på det sättet så innehåller indexet endast de poster som ingår där.
Exempelvis

CREATE NONCLUSTERED INDEX
ix_UnverifiedUsers ON Users(UserId, Username)
WHERE Verified = 0;

Ett annat problem är om vi vill använda oss av ELLER vid vårt urval. Man kan exempelvis tänka sig vår tabell och att vi endast vill ställa frågor mot sex av dessa. De andra två bryr vi oss inte om vad de har för värde. Om vi tittar på nedanstående frågor, där jag har plockat bort bit8 och bit3 ur where-villkoret. Detta gör att vår fråga mot tabell med alla kombinationer också måste skrivas om.

SELECT LargeTableId FROM LargeTable WHERE bit2 = 1 and bit6 = 1 and bit4 = 0 and bit1 = 1 and bit5 = 1 and bit7 = 0

--(53 row(s) affected)
--Table 'LargeTable'. Scan count 1, logical reads 64, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 0 ms,  elapsed time = 1 ms.

SELECT LargeTableId FROM LargeTable WHERE LargeTableLookupId IN(42,147,247,256)

--(53 row(s) affected)
--Table 'LargeTable'. Scan count 4, logical reads 23, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
--CPU time = 0 ms,  elapsed time = 1 ms.

Den bra prestandan kvarstår med vår kombinationstabell, men där vi har indexerat för alla våra åtta kolumner så blir det genast lite svårare för databasmotorn att hitta rätt.

Vilken lösning man väljer får naturligtvis bero på vilka problem man står inför. Det finns tillfällen då det kan vara bra att indexera bitfält. Vid andra tillfällen kan man använda sig av indexerade vyer för att få ännu bättre prestanda vid frågor.

Kommentarer inaktiverade.

%d bloggare gillar detta: