Kolonneorientert database

Fra Wikipedia, den frie encyklopedi

Et kolonneorientert databasestyringssystem er et databasestyringssystem (DBMS) som lagrer tabeller etter kolonner i stedet for rader. Fordelen er raskere tilgang til data når man bare spør etter en delmengde av kolonner (siden man eliminerer behovet for å lese kolonner som ikke er relevante), samt flere alternativer for datakomprimering. Ulempen er at det vanligvis mindre effisient å sette inn nye data.

I praktisk bruk av relasjonsdatabaser er det lite forskjell på å bruke et kolonnelager kontra et radlager. Begge deler kan brukes med tradisjonelle spørrespråk som SQL for å laste data og kjøre spørringer. Både rad- og kolonnedatabaser kan fungere som ryggraden i et system for å betjene data for vanlig uttrekk, transformasjon og lasting (ETL) og tilhørende verktøy.

Beskrivelse[rediger | rediger kilde]

Presentasjon[rediger | rediger kilde]

Data i en relasjonsdatabase representeres som en todimensjonal tabell med kolonner og rader. Dette er uavhengig av den underliggende datastukturen er rad- eller kolonnebasert.

For eksempel kan en databasetabell se slik ut:

Rad_id Ansatt_id Etternavn Fornavn Lønn
001 10 Nilsen Thomas 60 000
002 12 Moen Erik 80 000
003 11 Jørgensen Anna 94 000
004 22 Moen Marit 55 000

Tabellen har en ansattidentifikator (ansatt_id), navnefelt (etternavn og fornavn) og lønn. Dette todimensjonale formatet er en abstraksjon, mens den faktiske implementeringen krever at dataene serialiseres på en eller annen form.

Den dyreste operasjon for harddisker er søk. For å forbedre den generelle ytelsen bør relaterte data lagres på en måte som minimerer antall søk. Dette er kjent som referanselokalitet, og dette grunnleggende konseptet dukker opp i mange sammenhenger. Harddisker er organisert i en serie blokker med fast størrelse, vanligvis nok til å lagre flere rader i tabellen. Ved å organisere tabellens data slik at rader passer innenfor disse blokkene, og ved å gruppere relaterte rader i sekvensielle blokker, minimeres antallet blokker som må leses eller søkes i for de fleste tilfeller, samt antallet søk.

En undersøkelse av Pinnecke med kolleger[1] beskrev teknikker for kolonne- og rad-hybridisering per 2017.

Radorienterte systemer[rediger | rediger kilde]

En vanlig metode for å lagre en tabell er å serialisere hver rad med data, slik: 

001:10,Nilsen,Thomas,60000;
002:12,Moen,Erik,80000;
003:11,Jørgensen,Anna,94000;
004:22,Moen,Marit,55000;

Etter hvert som data settes inn i tabellen tildeles en intern ID rad_id som brukes internt i systemet for å referere til data. I dette tilfellet har postene sekvensielle rad_id uavhengig av brukertildelt ansatt_id . I dette eksemplet bruker DBMS-en korte heltall for å lagre rad_id-er. I praksis brukes normalt større tall på 64 bit eller 128 bit.

Radorienterte systemer er designet for å effisient returnere data for en hel rad eller oppføring i så få operasjoner som mulig. Dette samsvarer med det vanlige bruksmønsteret der systemet prøver å hente informasjon om et bestemt objekt, for eksempel kontaktinformasjonen for en bruker i et Rolodex-system eller produktinformasjon for et netthandelsystem. Ved å lagre oppføringens data i en enkelt blokk på disken sammen med relaterte oppføringer kan systemet raskt hente oppføringer ved et minimum av diskoperasjoner.

Radorienterte systemer er ikke effisiente til å utføre operasjoner på hele mengder (set-wide operations) på hele tabeller, i motsetning til et lite antall spesifikke oppføringer. For eksempel: For å finne alle oppføringer i eksempeltabellen hvor lønnen er mellom 40 000 og 50 000 må databasehåndteringssystemet skanne fullstendig gjennom hele tabellen på jakt etter samsvarende oppføringer. Mens eksempeltabellen ovenfor sannsynligvis vil passe inn i en enkelt diskblokk vil det fort ikke være tilfellet for en tabell med bare noen få hundre rader, og dermed vil flere diskoperasjoner være nødvendig for å hente dataene og undersøke dem.

For å forbedre ytelsen til denne typen operasjoner (som er veldig vanlige, og generelt poenget med å bruke et databasehåndteringssystem) støtter de fleste DBMS-er bruk av databaseindekser som lagrer alle verdiene fra en mengde med kolonner sammen med rad_id-pekere tilbake til den originale tabellen. En indeks for lønnskolonnen vil omtrent se slik ut: 

55000:004; 
60000:001;
80000:002;
94000:003;

Siden de bare lagrer enkeltdata (i stedet for hele rader) er indeksene generelt mye mindre enn hoved-tabelllagrene. Skanning av denne mindre mengden med data reduserer antallet diskoperasjoner. Hvis indeksen er mye brukt kan den redusere tiden for vanlige operasjoner dramatisk. Vedlikehold av indekser legger imidlertid til indirekte kostnader i systemet, særlig når nye data skrives til databasen. Oppføringer må ikke bare lagres i hovedtabellen, men eventuelle tilknyttede indekser må også oppdateres.

Hovedårsaken til at indekser dramatisk forbedrer ytelsen på store datamengder er at databaseindekser på én eller flere kolonner typisk er sortert etter verdi, hvilket gjør at spørreoperasjoner om rekkevidder (som eksempelet ovenfor: "Finn alle oppføringer med lønn mellom 40 000 og 50 000") veldig raskt kan løses basert på indeksen (lavere tidskompleksitet).

En rekke radorienterte databaser er designet for å passe i RAM, en hovedminnedatabase. Disse systemene er ikke avhengige av diskoperasjoner, og har lik tilgang til hele datamengden. Dette reduserer behovet for indekser ettersom det kreves samme mengde operasjoner for å fullskanne originaldataene som en komplett indeks for typiske aggregeringsformål. Slike systemer kan derfor være enklere og mindre, men kan bare håndtere databaser som passer i minnet.

Kolonneorienterte systemer[rediger | rediger kilde]

En kolonneorientert database serialiserer alle verdiene i en kolonne sammen, deretter verdiene til neste kolonne, og så videre. For eksempeltabellen over vil dataene bli lagret på følgende måte: 

001:10,002:12,003:11,004:22;
001:Nilsen,002:Moen,003:Jørgensen,004:Moen,
001:Thomas,002:Erik,003:Anna,004:Marit;
001:60000,002:80000,003:94000,004:55000;

I dette oppsettet samsvarer hvilken som helst av kolonnene nærmere med strukturen til en indeks i et radorientert system. Dette kan føre til forvirring og den feilaktige oppfatningen om at et kolonneorientert lager egentlig bare er "et radlager med en indeks på hver kolonne". Imidlertid skiller avbildingen av dataene seg dramatisk. I et radorientert system indekserer kolonneverdier til rader, mens kolonner i et kolonneorientert system avbilder rader til kolonneverdier.[2] Dette kan virke subtilt, men forskjellen kan sees i følgende vanlige modifikasjon i samme lager der de to "Moen"-instansene ovenfor komprimeres til en enkelt instans med to rad_id-er: 

…;Nilsen:001; Moen:002,004 ;Jørgensen:003;...

Hvorvidt et kolonneorientert system vil være mer effisient i drift avhenger sterkt av at arbeidsmengden blir automatisert. Operasjoner som henter all data for et gitt objekt (hele raden) vil være tregere i et kolonnebasert system. Et radorientert system kan hente raden i en enkelt diskavlesning, mens det kreves en rekke diskoperasjoner for å samle inn data fra flere kolonner fra en kolonnebasert database. Imidlertid er disse hele radoperasjonene generelt sjeldne, altså i de fleste tilfeller hentes kun en begrenset delmengde av data. Til et "rolodex-formål" er det for eksempel langt mer vanlig å samle for- og etternavn fra mange rader for å bygge en liste over kontakter enn å lese alle data for en enkelt adresse. Dette vil gjelde enda mer når det kommer til å skrive data inn i databasen, særlig hvis dataene har en tendens til å være glisne (sparse) med mange valgfrie kolonner. Av denne grunn har kolonnelagre vist utmerket ytelse i den virkelige verden til tross for mange teoretiske ulemper.[3]

Partisjonering, indeksering, hurtigbufring, visninger, OLAP-kuber og transaksjonssystemer som forutgående logging eller multiversjons samtidighetskontroll påvirker alle dramatisk den fysiske organiseringen av begge systemene. Når det er sagt er OLTP-rettede RDBMS-systemer ofte mer radorienterte, mens OLAP-rettede systemer er en balanse mellom radorienterte og kolonneorienterte.

Fordeler[rediger | rediger kilde]

Aksesstid[rediger | rediger kilde]

Sammenligninger mellom radorienterte og kolonneorienterte databaser fokuserer ofte på effisiensen til harddiskaksess for en gitt arbeidsmengde, ettersom søketiden er utrolig lang sammenlignet med andre flaskehalser i datamaskiner. For eksempel har en typisk SATA-harddisk en gjennomsnittlig søketid på mellom 16 og 22 millisekunder,[4] mens DRAM-tilgang på en Intel Core i7-prosessor i gjennomsnitt tar 60 nanosekunder, som er nesten 400 000 ganger så raskt.[5] Det er tydelig at disktilgang er en stor flaskehals ved håndtering av store data. Kolonnedatabaser bedrer ytelsen ved å redusere mengden data som må leses fra disken, både ved å effisient komprimere lignende kolonnedata og ved å lese bare dataene som er nødvendige for å svare på spørringen.

I praksis er kolonnebaserte databaser godt egnet for OLAP-lignende arbeidsoperasjoner (for eksempel datavarehus) som vanligvis involverer svært komplekse spørringer over alle data (muligens petabyte). Det må imidlertid gjøres noe arbeid for å skrive data inn i en kolonneformatert database. Transaksjoner (insert) må separeres i kolonner og komprimeres etterhvert som de lagres, hvilket gjør kolonnedatabaser mindre egnet for OLTP-arbeidsbelastninger. Radorienterte databaser er godt egnet for OLTP-lignende arbeidsbelastninger som er mer beheftet med interaktive transaksjoner. For eksempel er det mer effisient å hente alle data fra en enkelt rad når disse dataene er plassert på ett enkelt sted (minimerer disksøk), som i radorienterte arkitekturer. Imidlertid har det blitt hybride kolonneorienterte systemer som er i stand til å håndtere både OLTP- og OLAP-operasjoner. Noen av OLTP-begrensningene prøver slike hybride kolonneorienterte å løse er ved (blant annet) å bruke datalagring i hovedminnet.[6] Et kolonneorientert system som er egnet for både OLAP og OLTP kan i teorien fjerne behovet for to separate systemer.[7]

Komprimering[rediger | rediger kilde]

Siden dataene i en kolonne er av enhetlig type har kolonneorienterte data noen muligheter for optimering av lagringsstørrelse som radorienterte data ikke har. For eksempel bruker mange[hvem?] populære moderne komprimeringsmetoder som Lempel–Ziv–Welch-kompresjon eller løpelengdeenkoding, som er algoritmer som utnytter likheter mellom nærliggende data for å komprimere. Manglende verdier og gjentatte verdier (som er vanlige i kliniske data) kan representeres av en 2-bits markør.[8] Selv om de samme teknikkene kan brukes på radorienterte data vil de typisk oppnå mindre effektive resultater.[9][10]

For bedre komprimering kan sortering av rader også hjelpe. For eksempel ved å bruke punktgrafikkindekser kan sortering forbedre komprimeringen med en god størrelsesorden.[11] For å maksimere komprimeringsfordelene til den leksikografiske rekkefølgen med hensyn til løpelengdeenkoding er det best å bruke kolonner med lav kardinalitet som de første sorteringsnøklene.[12] For eksempel gitt en tabell med kolonnene kjønn, alder, navn, ville det være best å sortere først på verdien kjønn (kardinalitet av 2), deretter alder (kardinalitet <128), deretter navn (høy kardinalitet).

Kolonnekomprimering oppnår redusert diskplass på bekostning av effisiens ved henting. Jo større komprimering som oppnås mellom nærliggende data, desto vanskeligere kan tilfeldig tilgang bli, ettersom data kanskje må dekomprimeres for å kunne leses. Derfor blir kolonneorienterte arkitekturer noen ganger beriket med tilleggsmekanismer med sikte på å minimere behovet for tilgang til komprimerte data.[13]

Historie[rediger | rediger kilde]

Kolonnelagre eller transponerte filer har blitt implementert allerede i tidlige eksempler på databasehåndteringssystemer. I 1969 var TAXIR var det kolonneorienterte databaselagringssystemet med fokus på informasjonsinnhenting i biologi.[14] I 1975 ble et tidsorientert databasesystem (TODS) brukt for å behandle kliniske data fra pasientjournaler med mange flere attributter enn det som kunne analyseres.[15] I 1976 implementerte Statistics Canada RAPID-systemet[16] og brukte det til behandling og uthenting av Canadian Census of Population and Housing samt flere andre statistiske bruksområder. RAPID ble delt med andre statistiske organisasjoner over hele verden, og ble brukt mye i 1980-årene. Den fortsatte å bli brukt av Statistics Canada inntil 1990-årene.

En annen kolonneorientert database var IBM SCSS.[17][18][19]

Senere kolonneorienterte databaser inkluderte:

  • 1993: kdb+, en database basert på programmeringsspråket K
  • 1995: Sybase IQ

Siden 2004 har det vært ytterligere åpen kildekode og kommersielle implementeringer. MonetDB ble gitt ut under en åpen kildekode-lisens,[20] tett etterfulgt av den nå nedlagte C-Store.[21]

C-store var et universitetsprosjekt som til slutt førte til at blant annet teammedlemmet Michael Stonebraker ble med på å grunnlegget Vertica i 2005.[22][23]

Det MonetDB-relaterte X100-prosjektet utviklet seg til VectorWise.[24] Druid er et kolonneorientert datalager som ble konvertert til åpen kildekode sent i 2012, og som nå brukes av en rekke organisasjoner. [25]

Klassiske relasjons-DBMS-er kan bruke kolonneorienterte strategier ved å blande radorienterte og kolonneorienterte tabeller. Til tross for DBMS-kompleksiteten har denne tilnærmingen vist seg å være verdifull i årene 2010 til i dag per 2020. For eksempel i 2014 introduserte Citusdata kolonneorienterte tabeller for PostgreSQL,[26] og McObject la til støtte for kolonnelagring med utgivelsen av eXtremeDB Financial Edition i 2012[27] som deretter ble brukt til å etablere en ny referanse for ytelse i den uavhengig reviderte "STAC-M3 benchmark". [28]

Se også[rediger | rediger kilde]

Referanser[rediger | rediger kilde]

  1. ^ (PDF). doi:10.1109/ICDE.2017.237 http://wwwiti.cs.uni-magdeburg.de/iti_db/publikationen/ps/auto/Pinnecke+BCS17.pdf. 
  2. ^ Daniel Abadi. «Debunking Another Myth: Column-Stores vs. Vertical Partitioning». The Database Column. Arkivert fra originalen 4. desember 2008. 
  3. ^ Stavros Harizopoulos. «Column-Oriented Database Systems» (PDF). 
  4. ^ Masiero, Manuel. «Western Digital's 4 TB WD4001FAEX Review: Back In Black». 
  5. ^ Levinthal, David. «Performance Analysis Guide for Intel® Core™ i7 Processor and Intel® Xeon™ 5500 processors» (PDF). Intel. Besøkt 10. november 2017. 
  6. ^ «Compacting Transactional Data in Hybrid OLTP&OLAP Databases» (PDF). Besøkt 1. august 2017. 
  7. ^ «A Common Database Approach for OLTP and OLAP Using an In-Memory Column Database» (PDF). Besøkt 1. august 2017. 
  8. ^ Stephen Weyl; James F. Fries; Gio Wiederhold; Frank Germano (1975). «A Modular Self-describing Clinical Database System». Computers and Biomedical Research. 8 (3): 279–293. PMID 1157469. doi:10.1016/0010-4809(75)90045-2. 
  9. ^ D. J. Abadi; S. R. Madden; N. Hachem. Column-stores vs. row-stores: how different are they really?. SIGMOD’08. 
  10. ^ Bruno, N (2009). «Teaching an old elephant new tricks». arXiv:0909.1758 [cs.DB]. 
  11. ^ Daniel Lemire, Owen Kaser, Kamel Aouiche, "Sorting improves word-aligned bitmap indexes", Data & Knowledge Engineering, Volume 69, Issue 1 (2010), pp. 3-28.
  12. ^ Daniel Lemire and Owen Kaser, Reordering Columns for Smaller Indexes, Information Sciences 181 (12), 2011
  13. ^ (PDF) http://www.vldb.org/pvldb/1/1454174.pdf. 
  14. ^ George F. Estabrook; Robert C. Brill (November 1969). «The theory of the TAXIR accessioner». Mathematical Biosciences. 5 (3–4): 327–340. doi:10.1016/0025-5564(69)90050-9. 
  15. ^ Stephen Weyl; James F. Fries; Gio Wiederhold; Frank Germano (1975). «A Modular Self-describing Clinical Database System». Computers and Biomedical Research. 8 (3): 279–293. PMID 1157469. doi:10.1016/0010-4809(75)90045-2. 
  16. ^ «A DBMS for large statistical databases». 
  17. ^ already on the market by September 1977
  18. ^ Nie, Norman H. SCSS: A User's Guide to the SPSS Conversational Statistical System. McGraw-Hill. ISBN 978-0070465336. 
  19. ^ «SCSS from SPSS, Inc». ComputerWorld. 26. september 1977. s. 28. 
  20. ^ «A short history about us». 
  21. ^ «C-Store». Arkivert fra originalen 5. mars 2012. Besøkt 22. januar 2008. 
  22. ^ «The Vertica Analytic Database: C-Store 7 Years Later" (PDF)» (PDF). 
  23. ^ Charles Babcock (February 21, 2008). Database Pioneer Rethinks The Best Way To Organize Data.  Sjekk datoverdier i |dato= (hjelp)
  24. ^ Marcin Zukowski; Peter Boncz (20. mai 2012). «From x100 to vectorwise». Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM. ISBN 978-1-4503-1247-9. doi:10.1145/2213836.2213967. 
  25. ^ «Druid». 
  26. ^ «Citusdata». 
  27. ^ Saujani, Sandeep. «McObject eXtremeDB Financial Edition In-Memory DBMS Breaks Through Capital Markets' Data Management Bottleneck». 
  28. ^ STAC Benchmark Council, Leadership. «McObject eXtremeDB 5.0 Financial Edition with Kove XPD L2 Storage System, Dell PowerEdge R910 Server and Mellanox ConnectX-2 and MIS5025Q QDR InfiniBand Switch». 
Hentet fra «https://no.wikipedia.org/w/index.php?title=Kolonneorientert_database&oldid=24413342»