Indexering av databaser (skapa index för snabbare sökning)

Jag kompletterar lite, om det är okay Proton.

Om det nu är så att det är en mängd frågor där man vill ha ut just boktitlarna för en författare, så kan man inkludera det i indexet. Det blir inte sökbart, men databasmotorn klarar sig med enbart indexet i fråga, istället för att behöva läsa på två ställen, vilket gör att tiden innan resultatset:et trillar fram, blir ännu kortare.

Nackdelen är att man dubbellagrar information. Spelar kanske ingen större roll på små tabeller, men har man miljarder rader i en tabellerna och slänger på många index för att täcka upp de olika frågorna man har, så skapar man andra problem/utmaningar.

Som Proton var inne på, så behöver index underhållas vilket kostar tid i förhållande till mängden indexdata. Man bör också köra någon form av checkdb regelbundet så att man har en fullt fungerande databas, för att inte tala om backuperna. På SQL Server kostar sånt här bedrövligt lång körtid. Så att slentrianmässigt slänga på index är mindre bra. Det kostar också mer prestanda för en skrivning mot en tabell, då den måste skriva både data och index.

Sedan är inte index någon automagisk lösning på alla sökproblem. Det funkar bra för
SELECT bok_titel FROM bibliotek WHERE bok_forfattare = 'August Strindberg';
SELECT bok_titel FROM bibliotek WHERE bok_forfattare LIKE 'August S%';

Men det funkar inte alls för
SELECT bok_titel FROM bibliotek WHERE bok_forfattare LIKE '%Strindberg';

Så ibland är lösningen inte att slänga på ett index, utan att kanske ändra databasstrukturen utifrån hur man hanterar datat i sökningar, om det är en flaskhals.

Som ett litet sidospår, kan jag upplysa om att SQL Server inte direkt gillar databaser större än 4T. Man får problem att på rimlig tid klara av indexunderhåll, backuper/restorer, checkdb och liknande. Även om man slänger dyrbar hårdvara på problemet, så finns det tyvärr en gräns.

Viktig poäng detta.

Index är alltså inte en universallösning på prestandaproblem, även den mest noggrant indexerade databasen kan fås att gå på knäna av de mest fumligt formulerade frågorna man kör mot den. Index är såklart viktigt, men alltså även HUR data är lagrat är avgörande för prestandan.

Edit: sista delen är viktig, men kanske aningen off topic.

Du kan ju naturligtvis lägga på ett index med strängen i omvänd ordning. :-)

Jag förespråkar inte att man skapar en stor mängd index som är dyra att underhålla, men vet man i förväg vilka frågor som kommer att ställas ofta så bör man skapa bra accessvägar för dessa frågor.

+1, delvis åtminstone. Underhåll och utveckling av en databas kan vara ett löpande jobb, om man inte vet vilka frågor som kommer från början så loggar man allt eftersom, och lägger till eller justerar index om det inte finns nåt som passar. Sitt inte och försök gissa vilka index som skulle fungera för just den här applikationen.

Nu är ju användningen av databaser väldigt spridd. Den stora företagsdatabasen som går på en brummande server djupt nere i ett bergrum har mycket riktigt en man i vit rock som skriver ut statistik på tabulatorpapper och skruvar på parametrar och inställningar. Och rycker det lite i slagrutan så kanske han lägger på ett index också. I andra änden så har snart varje app på en mobiltelefon minst en inbäddad databas som måste sköta sig på egen hand. Och i det senare fallet (som är miljoner gånger vanligare) så måste vi i förväg konstruera databasen rätt från början.

Självklart ska man bana väg för de utmaningar som man vet i förväg kommer att komma. Dumt att vänta på att folk skriker på en för att databaserna inte har acceptabla svarstider.

Själv har jag dock en rätt rigid attityd till index i mitt jobb. Jag har en rätt aktiv övervakning av mina databaser och jag lägger på de index som behövs, först när de behövs och jag tar bort de index som inte längre behövs eller används tillräckligt frekvent.

Men attityden grundar sig i väldigt stora tabeller och hög förändringsgrad både i vad som lagras och hur det används. Sist jag la på ett index tog det arton timmar och kostade en halv gig diskutrymme. Under de omständigheterna kan man inte ha några onödiga index, för då hinner inte underhållsjobben med.

Alltså.. Om man vet vad som komma skall så ska man förstås förbereda sig. Det är så självklart så det är löjligt. Men jag har själv upplevt att så inte är fallet. Ett exempel jag kan ge direkt är utvecklare som har rättigheter nog att själva lägga till t.ex kolumner i databasen, gärna med ett index för bara just den kolumnen och så hoppas man på index merging. Och då får man göra ungefär som fnirp sa(senast), man försöker övervaka databasanvändningen, logga långsamma queries etc. Sen försöker man skapa/ersätta/justera index, självklart utan att vänta på att nån kommer och är missnöjd, speciellt om man är anställd för databasutveckling.. ..eller vad som nu kan behövas. Ibland så kan det ju vara frågan som är dålig och borde förbättras, utan att index behöver röras..

Det finns massor av typer av index. Om man ska försöka bena upp det och först just bara fokusera på begreppet index i en databas så är det en struktur för att möjliggöra för databasmotorn att söka data för att kunna läsa just bara rätt data istället för att behöva läsa allt data och sedan filtrera.

Om vi utgår från en databas så är det ett logiskt begrepp för någonting som innehåller både logisk och fysisk funktionalitet för att ta emot och leverera data som lagras/är lagrad. Datastrukturerna definieras som tabeller där vi logiskt lagrar individer av data fördelat på dess egenskaper, dvs tabellens kolumner.

Fysiskt innebär det här att dessa rader måste lagras fysiskt någonstans, oftast lagras dessa rader ner i ett block i en datafil.

När du sedan arbetar med datat och ställer frågor behöver databasmotorn läsa de här blocken av rader till minnet innan den kan leverera det till dig som frågekörare. om tabellen inte är indexerad måste alla blocken läsas till minne. den här lagringsformen kallas för rowstore.

När du vill söka på data så skapar du ett index, du skapar index för alla kolumner du vill kunna söka reda på rader baserat på urval. Inget index för ditt urval så måste de faktiska raderna läsas upp i minne och sedan filreras. I en tabell som lagras i ett rowstore kan du antingen gruppera raderna baserat på ett grupperingsattribut. Tänk ett personregister:
CREATE TABLE Personer (
PersonID int IDENTITY(1,1) PRIMARY KEY,
Personnummer char(13) UNIQUE,
Namn varchar(255),
Adress varchar(255),
Postnummer char(5),
Ort varchar(255)
)

PersonID är enbart ett attribut för att unikt kunna särskilja rader i tabellen, den är inte en affärsnyckel som ett personnummer utan en teknisk, surrogatnyckel så att affärsnyckeln kan bytas utan att relationer i databasen går sönder. Denna primära nyckel måste ha ett index så att databasmotorn inte måste läsa varje rad i tabellen varje gång det skrivs ett värde i kolumnen. Med indexet kommer den kunna testa om det värde som skrivs finns eller inte i tabellen. För en sådan här kolumn, om det är enda sättet man söker på, skulle jag låta vara ett klustrat index. Dvs blocket som rader i kan hantera fler rader än just bara en rad. Skulle databasen vara MS SQL Server i mitt exempel är de där blocken 8 kb där det finns 8092 b tillgängligt för radlagring. En rad kommer vara mellan 36 och 801 b, dvs blocket, eller datasidan som den faktiskt heter kommer då kunna hantera mellan 10 och 224 rader beroende hur många tecken som används per fält (kolumn i den faktiska raden). Om vi säger att den genomsnittliga raden är 100 b och vi har 10.000.000 rader (typ sveriges befolkning) då kommer varje datasida innehålla 80 rader, och du kommer ha 125.000 datasidor. När du skriver frågan SELECT * FROM Personer och inte hade haft ett index måste databasmotorn göra 125.000 io-operationer för att läsa upp de här 10.000.000 raderna i minnet för att testa om någon av dem har PersonID = 1. Med regeln PRIMARY KEY så måste det ju finnas ett index, som också är unikt. Det här indexet kommer troligen vara baserat på ett B-TREE (balanserat träd). Om indexet är ett klustrat index kommer hela tabellen bli det balanserade trädet, om inte kommer tabellen vara ett heap vilket innebär bara rader i datasidor. Det balanserade trädet består av tre nivåer, hänvisningen till den faktiska raden finns i botten av indexet som kallas leaf, toppen av indexet, dvs vägen in i strukturen för att hitta den sökta raden kallar root. Det mellan root och leaf fungerar som ett grenverk och kallas non-leaf eller intermediate pages. Indexet byggs upp genom att alla rader, hela raden vid ett klustrat index och kolumnen/-erna samt en fysiskt pekare till faktisk datasida och rad i din indexnyckel vid ett icke klustrat index. Detta sorteras efter din indexnyckel på en ny uppsättning datasidor, dessa är indexets leaf, därefter läser den första raden från vardera av dessa nya datasidor, och skriver indexnyckeln tillsammans med den nya datasidans och rad pekare. Detta upprepas lager för lager tills det enbart är en ny datasida, det är indexets root. Om det är ett klustrat index raderas datasidorna från den ursprungliga tabellen. Nu kan du navigera dig genom indexet genom att testa ditt urval genom indexets nivåer tills indexets leaf ger dig svar, och då vid ett klustrat index är det den faktiska raden, och vid ett icke klustrat en hänvisning till var de faktiska raderna finns. Istället för att databasmotorn behöver läsa alla 10.000.000 rader via 125.000 io-operationer från disken upp till minne, och där filtrera bort de rader som inte uppfyller ditt urval.

Oj, det här blev långt... När jag håller databasoptimeringskurserna brukar man ju ha en whiteboard och ett par dagar till just internals och hur databasmotorn fungerar, hur query optimizern tänker och hur storage engine faktiskt fungerar... Det kommer kanske mer om Ni gillar sånt här.


För att svara på OT fråga. Ett index är en struktur som låter databasmotorn söka raden istället för att skanna av alla rader för att filtrera.

Det Kah vill komplettera med sådana här radbaserade indexstrukturer B-TREE är inte bra för att göra fritext sökningar.

Det fanns ett exempel med Kolumn LIKE '%ord%', dvs ska innehålla ord. Det är inte en sökning i den fysiska benämningen. Det är ett filter. Alla rader måste läsas till minnet innan LIKE kan börja arbeta.

Skriver man Kolumn LIKE 'ord%', dvs man vill att det ska börja på ord kan ett radbaserat index hjälpa till lite eftersom indexets löv då är sorterat på Kolumn, partiell skanning. Det är fortfarande ett filter och inte en sökning.

Vill man ha en fritext-sökning måste man ha ett fritext index, oftast kallat full text index. Och det är en struktur som bryter upp data i ordlistor, och referenser, både mellan referenser och till rader. Då använder man sedan utryck liknande CONTAINS(Kolumn, 'FORMS_OF(inflectual, "ord")' och då returneras rader där kolumn innehåller ord, orden, ordet och liknande böjningar av ordet ord.

Sedan finns det HASH-index, orfa när man har minnes baserade databaser där rader lagras i heap i ramminne och urvalskolumner HASHas och plaseras i HEAP med din HASH som klusternyckel.