Det här är ett avsnitt i en webbkurs om databaser som finns fritt tillgänglig på adressen http://www.databasteknik.se/webbkursen/. Senaste ändring: 18 juli 2005.

Av Thomas Padron-McCarthy. Copyright, alla rättigheter reserverade, osv. Skicka gärna kommentarer till webbkursen@databasteknik.se.

Index och prestanda

I en relationsdatabas kan man skapa tabeller (med kommandot create table), lägga in data i dem (med kommandot insert), och sen göra sökningar (med select-frågor). Så länge man har en ganska liten databas räcker det med det. Men om mängden data växer, eller om frågorna är mycket komplicerade, kan sökningarna ta lång tid, helt enkelt eftersom det är mer data för databashanteraren att leta igenom. Man säger då att databasen har dåliga prestanda. Då måste man hjälpa databashanteraren genom att ange mer i detalj hur databashanteraren internt ska lagra tabellerna. Man säger att man väljer en fysisk design på databasen, eller man väljer lagringsstrukturer. Det gör man främst att skapa index till tabellerna.

Ett index är som registret i en bok

Faktaruta: Ordet "index" kommer av det latinska ordet för pekfinger. Pekfinger heter också "index finger" på engelska.

Ett index fungerar som registret i en bok. (Ett sånt register heter ju mycket riktigt "index" på engelska.)

Om du har en lärobok om databaser, och vill veta vad en databasadministratör gör, så kan du förstås börja på första sidan och sen läsa igenom hela boken tills du hittar avsnittet om databasadministratörer. Med tanke på hur tjocka typiska databasböcker brukar vara så tar det nog flera veckor.

Eller så kan du leta upp ordet "databasadministratör" i registret, och se att det står om databasadministratörer på sidan 717. Sen är det bara att bläddra fram till sidan 717, så hittar du databasadministratörsavsnittet där. Det sättet går naturligtvis mycket fortare än att läsa igenom hela boken. (När jag provade nu, med en databasbok som jag råkade ha med mig, så tog det 13 sekunder. Det är ju lite snabbare än flera veckor.)

Anledningen till att det går fortare är förstås att registret är sorterat i bokstavsordning. En annan anledning är att registret är mycket mindre än hela boken. Det är bara några få sidor att bläddra i, i stället för de många hundra sidorna i hela boken.

Index i databashanterare

I en relationsdatabas fungerar ett index som en extra tabell, med "pekare" in i huvudtabellen (i stället för sidhänvisningar som i ett register). Antag att vi har en tabell med kunder, som databashanteraren internt har sorterat på kundnummer:

Nummer Namn Adress
4 Lotta Vägen 7
7 Hjalmar Vägen 7
60 Diana Slottet
67 Rex Bengali
107 Saida Allén 5
110 Diana Bengali
113 Hulda Stora torget 18

Raderna i tabellen är sorterade på kundnummer, så databashanteraren kan ganska snabbt hitta en kund med ett visst kundnummer. En sån här SQL-fråga går alltså ganska snabbt:

    select namn, adress
    from kund
    where nummer = 7;
(Det här är bara ett exempel, Helge! En tabell med sju rader är förstås väldigt liten, och ingen databashanterare har problem med att hantera en så liten tabell. Databashanterarna bara skrattar åt vår löjliga tabell. Men tänk dig i stället att det finns tusentals rader i tabellen, eller kanske en miljard.)

Faktaruta: I det här exemplet har vi bara sorterat raderna i tabellen. Riktiga databashanterare arbetar för det mesta med mer komplicerade lagringsstrukturer än så, som det går snabbare att söka i. B-träd och hashtabeller är två vanliga lagringsstrukturer. Men just nu nöjer vi oss, för enkelhets skull, med att ha raderna sorterade.

Om vi vill söka efter en kund med ett visst namn, så har databashanteraren ingen nytta av att tabellen är sorterad på kundnummer. Då måste den läsa igenom alla raderna i tabellen, rad för rad (så kallad sekvensiell sökning). En sån här SQL-fråga går alltså ganska långsamt:

select nr, adress
from kund
where namn = 'Hjalmar';
Vi kan därför använda kommandot create index för att skapa ett index som gör att man snabbt kan hitta en kund med ett visst namn. Man säger att man skapar ett "index på kolumnen namn", eller bara "index på namn".
create index kundnamn on kund(namn);
(Kundnamn i kommandot ovan är bara ett namn, och indexet kan heta vad som helst.) Databashanteraren bygger nu en "extra tabell", som den använder internt när den ska söka efter namn i kundtabellen:

Kundtabellen med ett index på namn

Eftersom indexet är sorterat på namn, går det snabbt att hitta "Hjalmar". Sen följer man bara referensen till rätt rad i kundtabellen, och där står den information om Hjalmar (nummer och adress) som vi ville ha fram.

Databashanteraren kommer automatiskt att använda det här nya indexet varje gång man ställer en SQL-fråga som söker efter namn i kundtabellen. Den kommer också automatiskt att ändra innehållet i indexet om man ändrar innehållet i kundtabellen, så att indexet hela tiden är aktuellt och pekar rätt.

Faktaruta: Vanliga databashanterare lagrar sina data på hårddiskar. En hårddisk är indelad i diskblock. Ett diskblock innehåller ganska mycket data. När man läser data från hårddisken läser man alltid minst ett helt diskblock. Riktiga databashanterare brukar inte ha index som pekar ut enskilda rader i en tabell, som vi ritat i figuren ovan, utan de brukar i stället peka ut hela diskblock.

Usch så jobbigt!

Man kan undra varför vi måste specificera index på det här viset. Kan inte databashanteraren göra det själv, när den gör så mycket annat automatiskt?

Jo, databashanteraren skulle kunna skapa index automatiskt, kanske ett index på varje kolumn. Men alla indexen kanske inte behövs, och det finns också nackdelar med index:

Vilka index som verkligen behövs beror på vilka sökningar som kommer att göras. Databashanteraren är trots allt bara ett program, och den kan inte gissa hur vi har tänkt oss att databasen ska användas. Därför är det ofta bättre att databasadministratören talar om för databashanteraren vilka index som egentligen behövs.

(Databashanteraren skulle kunna samla statistik om de sökningar som görs, och sen skapa och ta bort index utifrån den statistiken. Men den sortens gissningar, som databashanteraren skulle göra, blir ganska grova jämfört med vad en människa kan åstadkomma. Till exempel vet databashanteraren inte vilka av de gjorda sökningarna som det är viktigt att de går snabbt, och vilka som kan få ta lite längre tid. Att skapa ett index kan också ta ganska lång tid, om det är stora tabeller, och man vill kanske inte tillåta databashanteraren att besluta om så stora jobb på egen hand.)

Hur vet man vilka index som behövs?

Vilka index som behövs beror på vilka sökningar som kommer att göras. Därför räcker det inte med att bara titta på databasens schema och innehåll.

Databasadministratören, dvs den person eller grupp av personer som ansvarar för databasen, måste därför titta både på databasen och hur den ska användas, och sen bestämma index utifrån det. När databasen sen är i drift måste man förmodligen göra justeringar, både på grund av ändrade förutsättningar och på grund av att man inte lyckats perfekt med valet av index.

Det gäller alltså att bestämma vilka tabeller man ska skapa index för, och på vilka kolumner. Ofta är det en avvägning mellan att ha index (för att sökningarna ska gå snabbare) och att inte ha index (för att spara plats och för att ändringar i databasen ska gå snabbare).

Man kan följa de här stegen:

  1. Vilka sökningar kommer att göras?
  2. Vilka av dessa sökningar kommer att göras oftast? Det är vanligt att några få typer av sökningar står för det mesta arbetet i databasen.
  3. Vilka kolumner används i sökningarna? Vi bryr oss bara om de kolumner som används i where-villkoren eller i villkoren för explicita join-operationer, inte de som bara är med i resultatet. Dessa kolumner bör ha index.
    Exempel: Antag att det här är en vanlig typ av sökning, där namnet "Bengt" byts ut mot namnet på den man söker efter:
    select anställd.namn, anställd.adress
    from anställd, avdelning
    where anställd.namn = 'Bengt'
    and anställd.jobbarpå = avdelning.avdnr
    
    Här kan kolumnerna namn och jobbarpå i tabellen "anställd", och kolumnen avdnr i tabellen "avdelning", vara lämpliga kandidater till att ha index. Kolumnen adress i tabellen "anställd" används bara i svaret, och behöver därför inget index. (Övning: Varför behöver kolumner som bara används i svaret inget index? [Svar])
  4. Det är vanligt att primärnyckeln i en tabell används ofta i sökningar. Även alternativnycklar, om det finns några sådana, kanske också används ofta. Många databashanterare skapar automatiskt ett index för den kolumn eller den kombination av kolumner som man angett som primärnyckel. Om inte annat så hjälper det indexet databashanteraren att kontrollera att det inte finns dubletter i primärnyckeln.
  5. Finns det sökningar som det är extra viktigt att de går snabbt? I så fall är det förstås extra viktigt att skapa index som underlättar just de sökningarna.
  6. Små tabeller, som får plats i ett eller två diskblock, behöver man förmodligen inte indexera. I en vanlig databashanterare, som lagrar sina data på en hårddisk, behövs det oftast ett par hundra rader innan ett index gör någon nytta.
  7. Kolumner med dålig selektivitet bör inte ha index. En kolumn med dålig selektivitet är en där det finns många rader med samma värde i den kolumnen. Exempel: Kolumnen kön, som kan ha värdet man eller kvinna. (Varför? Rita upp hur det skulle se ut, med tabellen och indexet! Det går nog fortare att hitta alla män i den tabellen om man går igenom hela tabellen rad för rad, än om man använder indexet.)
  8. Mycket breda kolumner, till exempel ett textfält av typen char(200), bör helst inte indexeras. Man måste ju, i indexet, upprepa värdena från den indexerade kolumnen: om man tittar i figuren ovan står det till exempel Hjalmar både i huvudtabellen och i indexet. Därför kan ett index på en bred kolumn ta stor plats. (Övning: Ävadårå? Disk är billigt. [Svar])
  9. Saker som ändras ofta bör helst inte ha några index, särskilt inte om ändringarna måste gå snabbt.

Går det inte snabbt nog i alla fall?

Ibland räcker inte de här ganska enkla reglerna, utan man måste ta till mer avancerade metoder:
  1. Läs manualen, pucko! De flesta databashanterare har en omfattande bruksanvisning, och där finns ofta en utförlig beskrivning av bästa sättet att välja lagringsstrukturer i just den databashanteraren.
  2. Många databashanterare har bara ett enda sätt som databashanteraren organiserar sina index på. I diskussionen ovan har vi låtsas som om det är en enkel sorterad tabell, men i verkligheten är det ofta något som heter B-träd (eller, om man vill vara riktigt korrekt, B+-träd). Olika sätt att organisera indexen ger lite olika egenskaper, och i vissa databashanterare kan man välja hur varje index ska organiseras. Om man använder en databashanterare där man har den möjligheten, kan man styra databasens prestanda mer exakt.
  3. Ibland kanske en databasfråga tar lång tid att köra, hur bra index man än har. Den här summeringen av alla svenskars löner måste till exempel gå igenom hela tabellen med omkring nio miljoner svenskar:
    select sum(lön)
    from svensk
    
    Det tar kanske en minut. Då kan det vara bättre att lagra summan separat, och sen se till att uppdatera den varje gång man ändrar i tabellen med svenskar. I en aktiv databas kan man definiera regler, som ser till att databashanteraren automatiskt gör den uppdateringen varje gång tabellen med svenskar ändras.

Överkurs (men nödvändig läsning för den som ska bygga en Internet-bank): Belastningsanalys

Hela det här avsnittet om index har handlat om att välja lagringsstrukturer så att sökningar (och uppdateringar) i databasen går så snabbt som möjligt. Men även om man har gjort det absolut bästa möjliga valet av lagringsstrukturer, så tar varje sökning (och uppdatering) en viss tid att köra. Om det är många som använder databasen samtidigt, kanske databashanteraren inte hinner med att köra alla sökningarna.

Ett exempel: En enskild sökning går snabbt, på 20 millisekunder (0.02 sekunder). Men nu kommer det tusen användare per sekund och gör en sån sökning. Eftersom varje sökning tar 0.02 sekunder för databashanteraren att göra, skulle databashanteraren nu behöva arbeta 0.02 * 1000, dvs 20 sekunder, varje sekund. Annorlunda uttryckt skulle databashanteraren behöva vara 20 gånger snabbare för att precis hinna med alla sökningarna. I stället för 0.02 sekunder får användarna nu kanske vänta i minuter eller timmar på svaret. Den som försökt betala räkningar via en Internet-bank i slutet av en månad känner igen fenomenet. Det blir så att säga "lång kö till kassan".

(Notera: Jag har gjort vissa förenklingar. Ett databassystem som körs på en dator med flera diskar och flera processorer, så att flera sökningar kan göras samtidigt, eller där resultatet av en sökning kan användas som svar även på andra sökningar, kan hinna med.)

För att upptäcka den här sortens problem kan man göra en belastningsanalys. Då försöker man räkna ut belastningen på databasen, det vill säga hur många operationer som utförs per tidsenhet i databasen, eller i en del av databasen, till exempel en tabell eller en hårddisk. Till exempel kan man titta på hur många läsningar som görs per sekund från hårddisken. Man måste ta hänsyn till

För att göra en rättvisande belastningsanalys krävs det ganska goda kunskaper om exakt hur databashanteraren arbetar internt. Därför är det vanligare att man helt enkelt provkör och ser hur mycket databashanteraren hinner med.

Men även en enkel belastningsanalys kan ge värdefulla ledtrådar till om en tänkt databaslösning är realistisk. Kanske kommer vi fram till att databasen kommer att göra en miljon läsningar i sekunden från en viss tabell som ligger lagrad på hårddisken. Om varje läsning tar 10 millisekunder, dvs 0.01 sekunder, skulle hårddisken behöva arbeta 0.01 * 1000000, dvs 10000 sekunder (ungefär tre timmar) per sekund. Annorlunda uttryckt: Hårddisken skulle behöva vara 10000 gånger snabbare för att precis hinna med. Vi bör därför fundera lite på om vi verkligen ska försöka bygga systemet på det sättet.

De viktigaste begreppen

De viktigaste begreppen från det här avsnittet finns också med i ordlistan:

index

Litteratur

Här kan du läsa mer om hur man, som databasadministratör, väljer lämpliga lagringsstrukturer, men också om hur databashanteraren arbetar med data internt, och om olika typer av lagringsstrukturer.


Webbkursen om databaser av Thomas Padron-McCarthy.