Redigerer Kolonneorientert database

Et '''kolonneorientert databasestyringssystem''' er et [[Database|databasestyringssystem]] (DBMS) som lagrer tabeller etter [[Kolonne (datalager)|kolonner]] i stedet for rader. Fordelen er raskere tilgang til data når man bare [[Spørrespråk|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 å [[Insert (SQL)|sette inn]] nye data.

I praktisk bruk av [[Relasjonsdatabase|relasjonsdatabaser]] er det lite forskjell på å bruke et kolonnelager kontra et radlager. Begge deler kan brukes med tradisjonelle [[spørrespråk]] som [[Structured Query Language|SQL]] for å [[Datalasting|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 ==

=== Presentasjon ===
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:

{| class="wikitable"
!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 [[Serialisering|serialiseres]] på en eller annen form.

Den dyreste operasjon for [[Platelager|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 [[Disksektor|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<ref name="Are Databases Fit for Hybrid Workloads on GPUs? A Storage Engine’s Perspective">{{Kilde konferanse|url=http://wwwiti.cs.uni-magdeburg.de/iti_db/publikationen/ps/auto/Pinnecke+BCS17.pdf|doi=10.1109/ICDE.2017.237}}</ref> beskrev teknikker for kolonne- og rad-hybridisering per 2017.

=== Radorienterte systemer ===
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 <code>rad_id</code> som brukes internt i systemet for å referere til data. I dette tilfellet har postene sekvensielle <code>rad_id</code> uavhengig av brukertildelt <code>ansatt_id</code> . I dette eksemplet bruker DBMS-en korte heltall for å lagre <code>rad_id</code>-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 [[Record|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 [[Operator|operasjoner]] på hele [[Mengde|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 [[Databaseindeks|databaseindekser]] som lagrer alle verdiene fra en mengde med kolonner sammen med <code>rad_id</code>-[[Peker (informatikk)|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 (informatikk)|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 [[Hovedminne|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 [[Aggregering (datavarehus)|aggregeringsformål]]. Slike systemer kan derfor være enklere og mindre, men kan bare håndtere databaser som passer i minnet.

=== Kolonneorienterte systemer ===
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 [[Avbilding (matematikk)|avbildingen]] av dataene seg dramatisk. I et radorientert system indekserer kolonneverdier til rader, mens kolonner i et kolonneorientert system avbilder rader til kolonneverdier.<ref>{{Kilde www|url=http://www.databasecolumn.com/2008/07/debunking-another-myth-columns.html|tittel=Debunking Another Myth: Column-Stores vs. Vertical Partitioning|arkiv-url=https://web.archive.org/web/20081204091753/http://www.databasecolumn.com/2008/07/debunking-another-myth-columns.html|arkivdato=4. desember 2008|etternavn=Daniel Abadi|forlag=The Database Column|url-status=dead}}</ref> 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 <code>rad_id</code>-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.<ref>{{Kilde www|url=http://www.cs.yale.edu/homes/dna/talks/Column_Store_Tutorial_VLDB09.pdf|tittel=Column-Oriented Database Systems|etternavn=Stavros Harizopoulos}}</ref>

[[Partisjon (database)|Partisjonering]], [[Databaseindeks|indeksering]], hurtigbufring, [[Visning (database)|visninger]], [[OLAP-kube|OLAP-kuber]] og [[Online transaksjonsprosessering|transaksjonssystemer]] som [[Loggføring med fremskrivning|forutgående logging]] eller [[multiversjons samtidighetskontroll]] påvirker alle dramatisk den fysiske organiseringen av begge systemene. Når det er sagt er [[Online transaksjonsprosessering|OLTP-rettede]] RDBMS-systemer ofte mer radorienterte, mens [[Online analytisk prosessering|OLAP-rettede]] systemer er en balanse mellom radorienterte og kolonneorienterte.

== Fordeler ==

=== Aksesstid ===
Sammenligninger mellom radorienterte og kolonneorienterte databaser fokuserer ofte på effisiensen til harddiskaksess for en gitt arbeidsmengde, ettersom [[Søketid|søketiden]] er utrolig lang sammenlignet med andre flaskehalser i datamaskiner. For eksempel har en typisk [[Serial ATA|SATA]]-harddisk en gjennomsnittlig søketid på mellom 16 og 22 millisekunder,<ref>{{Kilde www|url=http://www.tomshardware.com/reviews/wd4001faex-4tb-review,3368-4.html|tittel=Western Digital's 4 TB WD4001FAEX Review: Back In Black|fornavn=Manuel|etternavn=Masiero}}</ref> mens [[DRAM]]-tilgang på en [[Intel Core i7]]-prosessor i gjennomsnitt tar 60 ''nano''sekunder, som er nesten 400 000 ganger så raskt.<ref name="JESD79-3F">{{Kilde www|url=https://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf|tittel=Performance Analysis Guide for Intel® Core™ i7 Processor and Intel® Xeon™ 5500 processors|besøksdato=2017-11-10|fornavn=David|etternavn=Levinthal|forlag=Intel}}</ref> 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 [[Online analytisk prosessering|OLAP]]-lignende arbeidsoperasjoner (for eksempel [[datavarehus]]) som vanligvis involverer svært komplekse spørringer over alle data (muligens [[Byte|petabyte]]). Det må imidlertid gjøres noe arbeid for å skrive data inn i en kolonneformatert database. [[Transaksjonsdata|Transaksjoner]] ([[Insert (SQL)|insert]]) må separeres i kolonner og komprimeres etterhvert som de lagres, hvilket gjør kolonnedatabaser mindre egnet for [[Online transaksjonsprosessering|OLTP]]-arbeidsbelastninger. Radorienterte databaser er godt egnet for OLTP-lignende arbeidsbelastninger som er mer beheftet med [[Sanntidssystem|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 [[Dataarkitektur|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 [[Hovedminnedatabase|datalagring i hovedminnet]].<ref name="OLTP&OLAP">{{Kilde www|url=http://vldb.org/pvldb/vol5/p1424_florianfunke_vldb2012.pdf|tittel=Compacting Transactional Data in Hybrid OLTP&OLAP Databases|besøksdato=1. august 2017}}</ref> Et kolonneorientert system som er egnet for både OLAP og OLTP kan i teorien fjerne behovet for to separate systemer.<ref>{{Kilde www|url=http://www.sigmod09.org/images/sigmod1ktp-plattner.pdf|tittel=A Common Database Approach for OLTP and OLAP Using an In-Memory Column Database|besøksdato=1. august 2017}}</ref>

=== Komprimering ===
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|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.<ref name="TODS2">{{cite journal|title=A Modular Self-describing Clinical Database System|author1=Stephen Weyl|author2=James F. Fries|author3=Gio Wiederhold|author4=Frank Germano|journal=Computers and Biomedical Research|year=1975|doi=10.1016/0010-4809(75)90045-2|volume=8|issue=3|pages=279–293|pmid=1157469}}</ref> Selv om de samme teknikkene kan brukes på radorienterte data vil de typisk oppnå mindre effektive resultater.<ref>{{Kilde bok|tittel=Column-stores vs. row-stores: how different are they really?|etternavn=D. J. Abadi|etternavn2=S. R. Madden|etternavn3=N. Hachem|verk=SIGMOD’08}}</ref><ref>{{cite arXiv|first=N|last=Bruno <!-- URL not supported by cite arXiv |url=http://www-db.cs.wisc.edu/cidr/cidr2009/Paper_2.pdf -->|title=Teaching an old elephant new tricks|year=2009|eprint=0909.1758|class=cs.DB}}</ref>

For bedre komprimering kan sortering av rader også hjelpe. For eksempel ved å bruke [[Bitmap-indeks|punktgrafikkindekser]] kan sortering forbedre komprimeringen med en god størrelsesorden.<ref>Daniel Lemire, Owen Kaser, Kamel Aouiche, [[arxiv:0901.3751|"Sorting improves word-aligned bitmap indexes"]], ''Data & Knowledge Engineering'', Volume 69, Issue 1 (2010), pp. 3-28.</ref> For å maksimere komprimeringsfordelene til den [[Leksikografisk orden|leksikografiske rekkefølgen]] med hensyn til løpelengdeenkoding er det best å bruke kolonner med lav [[kardinalitet]] som de første sorteringsnøklene.<ref>Daniel Lemire and Owen Kaser, [[arxiv:0909.1346|Reordering Columns for Smaller Indexes]], Information Sciences 181 (12), 2011</ref> 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 (datamodellering)|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.<ref name="Infobright">{{Kilde konferanse|url=http://www.vldb.org/pvldb/1/1454174.pdf}}</ref>

== Historie ==
Kolonnelagre eller [[Transponering (matematikk)|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]].<ref>{{cite journal|title=The theory of the TAXIR accessioner|doi=10.1016/0025-5564(69)90050-9|volume=5|issue=3–4|pages=327–340|journal=Mathematical Biosciences|date=November 1969|author1=George F. Estabrook|author2=Robert C. Brill}}</ref> I 1975 ble et tidsorientert databasesystem (TODS) brukt for å behandle kliniske data fra pasientjournaler med mange flere [[Attributt|attributter]] enn det som kunne analyseres.<ref name="TODS3">{{cite journal|title=A Modular Self-describing Clinical Database System|author1=Stephen Weyl|author2=James F. Fries|author3=Gio Wiederhold|author4=Frank Germano|journal=Computers and Biomedical Research|year=1975|doi=10.1016/0010-4809(75)90045-2|volume=8|issue=3|pages=279–293|pmid=1157469}}</ref> I 1976 implementerte Statistics Canada RAPID-systemet<ref>{{Kilde www|url=http://portal.acm.org/citation.cfm?id=1286746|tittel=A DBMS for large statistical databases}}</ref> 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 [[SPSS|SCSS.]]<ref>already on the market by September 1977</ref><ref>{{Kilde bok|tittel=SCSS: A User's Guide to the SPSS Conversational Statistical System|etternavn=Nie|fornavn=Norman H.|utgiver=McGraw-Hill|isbn=978-0070465336}}</ref><ref>{{Kilde avis|avis=ComputerWorld|dato=26. september 1977|side=28|url=https://books.google.com/books?id=uz8cDDHy64IC|tittel=SCSS from SPSS, Inc}}</ref>

Senere kolonneorienterte databaser inkluderte:
* 1993: [[K (programmeringsspråk)|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]],<ref>{{Kilde www|url=https://www.monetdb.org/AboutUs|tittel=A short history about us}}</ref> tett etterfulgt av den nå nedlagte [[C-Store]].<ref>{{Kilde www|url=http://db.lcs.mit.edu/projects/cstore/|tittel=C-Store|besøksdato=2008-01-22|arkiv-url=https://web.archive.org/web/20120305151916/http://db.lcs.mit.edu/projects/cstore/|arkivdato=2012-03-05|url-status=dead}}</ref>

C-store var et universitetsprosjekt som til slutt førte til at blant annet teammedlemmet [[Michael Stonebraker]] ble med på å grunnlegget [[Vertica]] i 2005.<ref>{{Kilde www|url=http://vldb.org/pvldb/vol5/p1790_andrewlamb_vldb2012.pdf|tittel=The Vertica Analytic Database: C-Store 7 Years Later" (PDF)}}</ref><ref name="IW.COL">{{Cite magazine|url=https://www.informationweek.com/database-pioneer-rethinks-the-best-way-to-organize-data/d/d-id/1064893|title=Database Pioneer Rethinks The Best Way To Organize Data|date=2008-02-21|last=Charles Babcock}}</ref>

Det MonetDB-relaterte X100-prosjektet utviklet seg til [[VektorWise|VectorWise]].<ref>{{Kilde bok|tittel=Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data|etternavn=Marcin Zukowski|etternavn2=Peter Boncz|dato=20. mai 2012|utgiver=ACM|isbn=978-1-4503-1247-9|kapittel=From x100 to vectorwise|doi=10.1145/2213836.2213967}}</ref> [[Apache Druid|Druid]] er et kolonneorientert datalager som ble konvertert til åpen kildekode sent i 2012, og som nå brukes av en rekke organisasjoner. <ref>{{Kilde www|url=http://druid.io/druid-powered.html|tittel=Druid}}</ref>

Klassiske [[Relasjonsdatabase|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]],<ref>{{Kilde www|url=https://github.com/citusdata/citus|tittel=Citusdata}}</ref> og McObject la til støtte for kolonnelagring med utgivelsen av [[eXtremeDB]] Financial Edition i 2012<ref>{{Kilde www|url=https://www.bobsguide.com/guide/news/2012/Jun/19/mcobject-extremedb-financial-edition-in-memory-dbms-breaks-through-capital-markets-data-management-bottleneck/|tittel=McObject eXtremeDB Financial Edition In-Memory DBMS Breaks Through Capital Markets' Data Management Bottleneck|fornavn=Sandeep|etternavn=Saujani|besøksdato=2024-04-23|arkiv-dato=2023-04-17|arkiv-url=https://web.archive.org/web/20230417085700/https://www.bobsguide.com/guide/news/2012/Jun/19/mcobject-extremedb-financial-edition-in-memory-dbms-breaks-through-capital-markets-data-management-bottleneck/|url-status=yes}}</ref> som deretter ble brukt til å etablere en ny referanse for ytelse i den uavhengig reviderte "STAC-M3 benchmark". <ref>{{Kilde www|url=https://www.stacresearch.com/mcobject|tittel=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|fornavn=Leadership|etternavn=STAC Benchmark Council}}</ref>

== Se også ==
* [[Datavarehus]]
* [[AOS og SOA|Array of structures (AoS), structure of arrays (SoA), eller array of structures of arrays (AoSoA)]], måter å ordne sekvenser av oppføringer i minne
* [[RCF-fil]], struktur for dataplassering av relasjonstabeller på regneklynger, designet for [[MapReduce]]-rammeverket

== Referanser ==
<references/>

{{Datavarehus}}
{{Databasemodell}}
{{Databaser}}

[[Kategori:Databasehåndteringssystem]]
[[Kategori:Databaser]]
[[Kategori:Datamodellering]]