03장 저장소와 검색DB란

데이터 중심 어플레케이션 설계 스터디를 진행하며 작성한 글 입니다.

• 스터디원: 7명
• 서적: 데이터 중심 어플리케이션 설계

---

들어가기에 앞서

• 관계형 DB와 NoSQL DB에 사용되는 저장소 엔진에 대해 공부한다.
• 로그 구조(log-structured) 계열 저장소 엔진과 (B-tree 같은) 페이지 지향(page-oriented) 계열 저장소 엔진을 검토한다.

DB란

DB작업

• data 저장 ,data 요청 시 제공

개발자가 DB 내 저장 및 검색 처리 방법을 주의해야하는 이유

• 처음부터 저장소 엔진을 구현하는 것이 아닌, 사용 가능한 여러 저장소 엔진 중 가장 적합한 엔진을 선택해야 하기 때문 ( 작업 부하에 맞춰 최적화 된 저장소 엔진/ 분석 위해 최적화된 엔진 차이)

DB를 강력하게 만드는 데이터 구조

DB는 대부분 내부적으로 append-only 데이터 파일인 로그(연속된 추가 전용 레코드)를 사용한다.

DB에서는 일반적으로 특정 키의 값을 효율적으로 찾기 위해 Index를 사용한다.

• Index(색인)
  • 저장소 시스템에서 중요한 trade off 관계
  • 인덱스가 많이 있다면 여러 WHERE 절 조건에 대응할 수 있는 또는 조회에서 조금 더 효과 적인 인덱스를 사용할 수는 있겠지만, trade-off 관계로 Index 가 많아질수록 데이터의 입력이나 갱신에서는 적은 인덱스를 사용하는 것에 비해 상대적으로 성능이 불리해 질 수 있다.
  • 인덱스를 잘 선택하면 읽기 속도가 향상 되지만 모든 인덱스는 쓰기(write) 속도를 떨어뜨린다. (데이터를 쓸 때마다 인덱스도 갱신해야 하기 때문.)
  • 따라서! DB는 일반적으로 모든 것을 인덱싱하지는 않고, 개발자가 수동으로 인덱스 설정을 하도록 해서 적은 오버헤드로 고효율을 주도록 한다.

서론

이전에 스터디에서 바로 3장에 들어갔을 때는 정말 데이터 모델? 질의 언어? 무슨 소리하는지 하나도 몰랐는데

1장에서는 책에서 사용하는 용어들을 배우고, 2장에서는 데이터 모델과 질의 언어에 대해 비교해보았다. 이렇게 1,2장부터 찬찬히 해보니 흐름이 이해가 돼서 재밌는거 같다

2장에서는 애플리케이션 개발자의 관점에서 DB에 데이터를 제공하는 형식을 설명했다면, 3장에서는 DB관점에서 데이터를 저장하는 방법과 요청했을 때 다시 찾을 수 있는 방법에 대해 알아본다. → 개발자가 내부 구현을 알아야지 적합한 DB 선택이 가능해지기 때문.

 

엔진은 크게 트렌젝션 처리/분석에 따라 크게 나눌 수 있다.

트렌젝션 처리 최적화 엔진 → 이번 차시에서 확인할 저장소

• 트랜잭션 작업부하에 맞춰 최적화 됨.
• 저장소
• 관계형 데이터 베이스(RDBMS) / NoSQL

분석 최적화 엔진

• 칼럼 지향 저장소
• 분석

DB 를 강력하게 만드는 데이터 구조

로그

일반적으로 많은 DB는 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용

* 로그 - 일반적인 의미 : 연속된 추가 전용 레코드 (binary 파일인 경우 많음)*

• 일반적으로 파일 추가 작업은 매우 효율적이기 때문에 , 매우 간단한 작업의 경우에 db_set 같은 함수가 꽤 좋은 성능을 보인다. → 추가적으로 고려할 사항은 많지만 로그는 유용함
  • DB에서 다뤄야할 문제들
    • 동시성 제어
    • 로그 compaction을 통한 디스크 공간 회수
    • 오류 처리 (오류로 인한 부분적 기록 레코드 ... )
    • ...

• append only 예시 (db_set)

dp_set 호출 시 파일의 끝에 추가를 하므로 키를 여러번 갱신해도 값의 예전 버전을 덮어쓰지 않음. 따라서 파일의 최신 값을 찾기 위해 파일에서 키의 마지막 항목을 살펴보면 됨 → tail -n 1

• 하지만! db_set은 DB에 많은 레코드가 있으면 성능이 좋지 않다. 레코드 수가 2배로 늘면 검색도 2배 → 매번 키를 찾을 때 마다 전체 db파일을 처음부터 끝까지 스캔해야하므로 (검색 비용 O(n))
  *레코드란? SQL에서 행(row) 또는 튜플(tuple)이라고 불린다.

 

색인

특정 키의 값을 효율적으로 찾기 위해 다른 데이터 구조가 필요한데 이게 바로 색인(index)이다! 색인이란?

• 일반적인 개념 : 부가적인 메타데이터(이정표 역할) 유지하는 것.
• 정의 : 특정 키의 값을 효율적으로 찾기 위해 필요한 것 (*기본 데이터에서 파생된 추가적인 구조)
• *특징:
  • DB의 내용에 영향을 미치지는 않으나. 추가적인 구조(인덱스)의 유지보수는 특히 쓰기 과정에서 오버헤드를 동반한다.
  • 어떤 종류의 색인이라도 속도를 느리게 만든다 → 색인도 갱신해야되기 때문 (단순 append구조보다 당연히 느리다.)
  • trade off : (색인 선택) 읽기 속도 ▲ 쓰기 속도 ▼ → 따라서 모든 DB는 자동으로 모든 것을 색인하지 않는다.
    (애플리케이션 개발자나, db관리자가 전형적인 질의 패턴에 대한 지식을 활용해 수동으로 색인을 선택해야 오버헤드를 지양할 수 있음)

• 색인 종류
  • 해시 색인 (Hash index)
  • SS 테이블 & LSM 트리
  • B 트리

해시 색인 (Hash index)

• Key - Value 색인 구조 (a.k.a dictionary Type)
• 가장 간단한 색인 전략 - key 값 데이터 파일의 byte offset에 매핑해 Inmemory HashMap 유지
  • byte-offset을 통해 값을 바로 찾을 수 있음
  • but 파일에 k-v를 추가할 때마다 직전 data offset을 반영하기 위해서는 메모리의 HashMap도 갱신해야함
• 해당 방식 : Bitcask(비트캐스크) - 리악(Riak)의 기본 저장소 엔진에서 근본적으로 사용하는 방식
  • 비트캐스크 : HashMap을 전부 메모리 유지 -> 고성능의 읽기 쓰기 보장
• 해당 방식은 key 별 value가 자주 갱신되는 상황에 매우 적합하다
• 즉 쓰기가 많지만, 고유 key 값이 많지 않은 상황(key 당 쓰기 수가 많지만 메모리에 모든 키 보관이 가능할 때)

1) Log-structured 형식 (가장 간단한 색인 전략, 비트캐스크)

Bitcask(비트캐스크) - 리악(Riak)의 기본 저장소 엔진에서 근본적으로 사용하는 방식 : Key - Value 색인 구조 (가장 간단한 색인 전략)

• 비트캐스크 : HashMap을 전부 메모리 유지 -> 고성능의 읽기 쓰기 보장
• 메모리 해시맵은 모든 데이터를 메모리에 저장하므로 읽기, 쓰기 속도 모두 성능이 높다.
  • 값이 자주 갱신되는 쓰기 작업에 유리하다.→ 예) url 조회 수 증가 작업 , url 데이터는 작으나 조회수는 갱신

• 단점 : 항상 파일에 추가만 하기 때문에 결국 디스크 공간이 부족

2) Compaction (지속적 write 디스크 공간부족 문제 해결)

컴팩션이란 중복된 키를 버리고 각 키의 최신 값만 유지하는 것을 말한다.

→ 데이터를 특정 크기의 세그먼트(segment)로 나누고 주기적으로 컴팩션(compaction)을 수행하여 log structured 형식의 디스크 공간 부족 문제를 해결한다. 이렇게 하면 해시 맵은 각 데이터의 오프셋과 키를 매핑하고 각 오프셋이 가리키는 값은 최신 값임을 보장할 수 있다.

 

과정 정리

• 세그먼트가 특정 크기 도달 시, 병합을 위한 새 세그먼트 파일 생성
• 세그먼트 병합은 백그라운드 스레드에서 수행, 이를 통해 이전 세그먼트에 읽기/쓰기 처리 정상 수행 가능
• 병합이 끝난 후, 새 세그먼트로 전환 → 기존 세그먼트 파일 삭제 (log에서 중복된 키를 버리고 키별 최신 value만 유지)
• 병합 과정을 통해 세그먼트 수를 더 적게 유지하기 때문에 조회할 때 많은 해시 맵을 확인할 필요 X

해시 테이블 색인의 한계

해시 색인은 간단한 만큼 단점이 확실하다.

• 해시 맵을 메모리에 저장해야 하므로 키가 너무 많으면 문제가 된다. (모든 데이터에 대한 키를 저장하므로) 디스크에 해시 맵을 유지할 수는 있지만 무작위 접근 I/O가 많이 필요하기 때문에 디스크 상의 해시 맵에 좋은 성능을 기대하기는 어렵다.
• 해시 맵은 범위 질의(range query)에 굉장히 비효율적이다. 해시 맵에서 모든 키를 개별적으로 조회해야 한다.

 

SS 테이블 & LSM 트리 (제한 없는 색인 구조)

두 테이블과 해시 색인과의 차이는 세그먼트 병합 시 key-value 쌍으로 키를 정렬한다는 것이다.

💡 정렬이 메모리 용량과 검색 속도에 어떤 영향을 미칠까?

• 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없기 때문에, 검색 속도가 빨라진다! 

SS테이블 (Sorted String Table)

Log-structured 데이터 형식을 Sorted String Table 혹은 SS 테이블이라 칭한다.

• 세그먼트가 정렬되어 있어 merge sort 및 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없다.

 

데이터를 키로 정렬하는 방법 (쓰기와 읽기 과정)

디스크 보다 메모리에서 정렬하고 디스크로 내려다 보는 편이 쉽다!

1. 쓰기가 들어오면 인메모리 균형 트리(balanced tree) 데이터 구조(e.g. red-black tree)에 추가한다. 이 인메모리 트리를 멤테이블(memtable)이라고 부른다.
2. 멤테이블의 크기가 임계값(보통 수 MB)보다 커지면 SS테이블 파일로 디스크에 기록 (트리가 이미 정렬되어 있기 때문에 효율적)
3. 읽기 요청을 처리하려면 먼저 멤테이블에서 키를 찾는다. 그 다음 디스크상의 최신 세그먼트부터 찾는다. (인메모리 해시맵이나 bloom filter 를 사용하여 탐색 시간을 줄일 수 있다.)
4. 백그라운드에서 지속적으로 컴팩션 과정을 수행한다.

LSM트리 (Log-Structured Merge-Tree)

LSM 트리는 SS테이블 새그먼트를 디스크에 key-value 형태로 연쇄적으로 병합하는 알고리즘이다. → 정렬된 파일 병합과 compaction 원리를 기반으로 하는 저장소 엔진 → SS테이블에서 세그먼트를 병합하고 정렬하는 알고리즘은 LSM 트리로 수행된다. → append-only 로그 형식으로 저장하고 지속적으로 merge sort를 수행한다.

• 블룸 필터 (Bloom Filter)

블룸 필터는 저장소에 데이터가 있을 확률을 계산하기 위한 추가적인 데이터 구조로, 이를 활용하면 키가 데이터베이스가 존재하는지 유무를 알 수 있다. 블룸 필터를 통해 데이터가 없다고 판단되었을 경우, 실제로도 찾으려는 데이터가 디스크에 존재하지 않음이 보장되기 때문에 추가적인 디스크 읽기를 아낄 수 있다. 다만, 블룸 필터는 데이터가 있다고 판단했지만 실제 디스크에는 데이터가 없는 False Positive 가 발생할 수 있다.

• 레벨 컴팩션 (Leveled Compaction)

SS 테이블을 여러 단계(level)로 구분한다. 단계가 높아질수록 테이블의 크기가 커진다. 키 범위를 더 작은 SS 테이블로 나누고 오래된 데이터는 개별 level로 이동하기 때문에 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용한다. 한 레벨의 SS 테이블 파일들끼리는 키가 겹치지 않는 특징 때문에 데이터를 찾기 위해서 level 수만큼만 쿼리하면 된다.

• Skip List

멤테이블에 데이터를 효율적으로 쓰고 읽기위해 멤테이블을 skip list 로 구현하는 경우도 있다. (Rocks DB, Level DB)

 

 

B트리 (가장 널리 사용되는 색인 구조)

LSM 트리 색인이 보편화되고 있지만 아직까지 가장 널리 사용되는 색인 구조는 B트리이다. 정렬된 키-값 쌍을 유지하기 때문에 범위 질의에 효율적이라는 점 빼고는 사실상 두 구조는 아예 다르다.

예) RDB, NoSQL

 

*LSM : 수 메가바이트 이상의 가변 크기를 가진 세그먼트 단위로 데이터를 기록하고 이는 항상 순차적이다.

*B트리 : 보통 4KB 고정 크기의 페이지 단위로 읽기 또는 쓰기를 수행한다. 디스크가 고정 크기 블록으로 배열되기 때문에 하드웨어와 조금 더 밀접한 관련이 있다.

B트리의 페이지

한 페이지가 가지고 있는 참조 수를 분기 계수(branching factor)라고 부른다. → 위 그림에서 분기 계수는 6 이다

*분기계수 : 한 페이지에서 하위 페이지를 참조하는 수 (페이지 참조와 범위 경계를 저장할 공간의 양에 의존적)

*대부분의 데이터베이스는 수백 개 정도로 지정한다고 한다.

• 색인에서 키를 찾으려면 루트(root) 페이지(B트리의 루프페이지로 지정된)에서 시작해야한다.
• 최종적으로는 리프(leaf) 페이지에 도달, 리프페이지는 각 키의 값이나 값을 찾을 수 있는 페이지의 참조를 갖고있다.

B 트리에 존재하는 키의 값을 갱신하는 과정

• 해당 키를 포함하고 있는 리프 페이지를 검색 → 페이지의 해당 키 값을 수정 → 페이지를 디스크에 기록 *페이지에 대한 모든 참조는 유지된다. (유효)
• 이 알고리즘은 Tree 가 계속 균형을 유지하는 것을 보장한다. n개의 키를 가진 B-tree는 깊이가 항상 O(logn)이다.
• 대부분 DB에서 깊이는 3~4 단계면 충분하다. 분기 계수 500의 4KB페이지의 4단계 트리는 256TB 까지 저장할 수 있다

B트리 최적화

1. (동시성 제어에 유리) 페이지 덮어쓰기 / WAL 유지를 대신하여 copy-on-write schema(쓰기 시 복사 방식) 사용 → 변경된 페이지 다른 위치 기록 + 트리에 새로운 버전의 상위 페이지 생성

*WAL 로그(write-ahead log 재실행(redo) 로그)  :트리 페이지에 변경된 내용을 적용하기 전 모든 B 트리 변경 사항 기록 파일 DB 장애 이후 복구 전까지 일관성 있는 상태로 B 트리 복원에 사용

 

2.leaf 를 찾는 깊이 수준을 낮추기 페이지의 키를 축약하여 공간 절약 → 페이지 하나에 더 높은 분기 계수

3. 연속된 키를 더 가깝게 유지하기 쉽다. 리프 페이지를 디스크 상에 연속된 순서로 트리에 배치 → 쿼리가 키 범위의 상당 부분 스캔시 효율적

4. 연속된 키를 더 가깝게 유지하기 쉽다. 트리에 포인터 추가 → 상위 / 하위 포인터 자유롭게 key 스캔 가능

5. 프랙탈 트리(Fractal tree) → 디스크 찾기를 줄인다.

B-tree 와 LSM 트리 비교 (Comparing B-Trees and LSM-Trees)

일반적 : LSM 트리 - 쓰기 빠름 / B 트리 - 읽기 빠름 → 읽기가 LSM 이 느린 이유 : 각 compaction 단계에 있는 여러 데이터 구조와 SS 테이블 확인

1. LSM은 B tree 보다 쓰기 처리량을 높게 유지할 수 있다.
   1. compaction과 merge 작업 때문에 B tree 에 비해 쓰기 증폭이 낮다. 특히 HDD 라면 순차 쓰기가 임의 쓰기 보다 훨씬 더 빠르기 때문에 적합하다.
2. LSM 트리는 압축률이 좋다.
   1. B tree 보다 더 적은 파일을 생성한다.
   2. B tree 는 파편화로 인해 디스크 공간 일부가 남는다. (일부 공간을 사용하지 않음)
   3. SS테이블을 다시 기록하면서 저장소 오버헤드가 낮다.
   4. 이 장점은 SSD 에서도 유리하다(SSD는 임의 쓰기를 순차 쓰기로 전환할때 LSM 알고리즘을 사용한다)

 

기타 색인 구조(Other Indexing Structures)

# 기본키(primary-key) 색인  : 가장 대표적인 K-V 색인 : R-model

# 보조 색인 (secondary index) :

• 보통 효율적으로 조인을 수행하는 데 결정적인 역할
• 기본키 색인과의 차이점 : 키가 고유하지 않다. (같은 키를 가진 많은 row / document / vertex 존재 가능 )
• B 트리 / 로그 구조화 색인 둘다 사용 가능
• ex) RDB -  CREATE INDEX

# heap file (힙파일)

• 색인이 가지고 있는 값 : 실제 row / reference (참조 값)
• 참조일 경우 로우가 저장된 곳을 Heap file 이라 한다.
  • 특정 순서 없이 데이터를 저장한다.
  • 이 때 추가 전용이거나 나중에 새로운 데이터로 덮어 쓰기 위해 삭제된 로우를 기록 가능
• heap file 을 통한 접근 방식 = 키를 변경하지 않고 값 갱신 시 효율적
  • 이 때 새로운 value가 힙에서 더 많은 공간을 차지해야 한다면,충분한 공간이 있는 곳으로 위치를 이동시키고, 모든 색인이 레코드의 새로운 Heap 위치를 명시하게끔 갱신 or 이전 heap 위치에 전방향 pointer를 통해 처리

# Clustered Index (클러스터드 색인)

색인에서 heap file을 이동하는 것 : 읽기 성능에 대해서 비효율적

• 따라서 색인 내에 바로 색인된 로우를 저장하는 방법 [Clustered Index]
• ex) Mysql - InnoDB 엔진 :
  • table의 PK = 클러스터드 색인 / 보조 색인 -> 기본키참조(not Heap file location)
• MS의 SQL Server에서는 테이블당 하나의 클러스터드 색인을 지정 가능.

# multi-column index

가장 일반적인 유형 : 결합 색인(concatenated Index)

• 하나의 칼럼에 다른 칼럼을 추가하는 방식으로 하나의 키에 여러 필드를 결합
• 이 때 필드 연결 순서는 색인 정의에 명시
• ex) (성, 이름) 순으로 정리된 전화번호 - 순서가 정렬되어 있기 때문에 다음과 같은 상황에 색인 사용 유용
  • 특정 성으로 된 연락처 찾기
  • 특정 성, 이름 조합을 가진 모든 사람 찾기
  • cf) 특정 이름을 가진 모든 사람을 찾을 때는 쓸모가 없다.

# 다차원 색인(Multi-dimensional indexes)

• 한 번에 여러 칼럼에 질의한다.
• 특히 지리 공간 데이터에서 중요하게 사용.
• R 트리 같은 공간 색인에 특화(specialized spatial index)된 알고리즘을 사용.

# 전문 검색(Full-text Search) & 퍼지 색인(fuzzy Index)

• 특정 단어에 대해 동의어(Synonym)도 함께 질의에 추가할 때
• 특정 편집거리(오탈자 - misspellings)에 대해서 허용하여 질의에 추가하여 검색
• elasticsearch (루씬 기반) / 검색 엔진에서 흔히 사용된다.

 

트랜잭션 처리나 분석

데이터베이스를 논리 단위의 형태로 읽기와 쓰기 그룹을 나타내는 commercial transaction에 해당하는데 여기서 발생한 record는 온라인 트랜잭션 처리(Online Transaction Processing, OLTP)이다. 그러나 이 뿐만이 아니라 데이터 분석에도 점점 더 사용하기 시작하면서 온라인 분석 처리(Online Analytic Processing, OLAP) 즉, 지금까지 살펴본 색인은 분석용에 적합하지 않기 떄문에 분석용 질의가 의사결정을 돕고 의사결적이 필요한 경영진이 참고할 수 있는 DB사용패턴을 만들게 되었다.

• OLTP (Online Transcation Processing) / OLAP (Online Analytic Processing)

• 초반에는 트랜잭션 처리와 분석 질의를 위해 동일한 데이터베이스를 사용
• OLTP 시스템을 분석 목적으로 사용하지 않고 개별 데이터 베이스에서 분석을 수행하려 함
  • 이 개별 데이터베이스를 데이터 웨어하우스라고 부름

데이터 웨어하우징 (Data Warehousing)

기업은 수십가지의 트랜잭션 처리 시스템을 갖추고 있으며(고객 대면 웹사이트 강화, 매장 판매 관리, 시스템 관리, 창고 재고 이력, 운송 수단을 위한 경로 등등) 이러한 시스템은 OLTP 이다.

OLTP의 특징은 높은 가용성과 낮은 지연시간의 트랜잭션 처리를 기대하기 때문에 DB 관리자는 OLTP를 철저히 보호하려고 한다.

그래서 비즈니스 분석가의 OLAP 쿼리를 꺼려한다. 왜냐하면 dataset 의 많은 부분을 스캔해야 하는 쿼리와 비즈니스의 트랜잭션을 동시에 실행할 경우 DB에 성능 저하가 발생하기 때문이다.

Data Warehouse 는 이러한 OLAP 쿼리를 OLTP 에게 영향을 주지 않고 언제나 질의할 수 있는 DB 이다.

특징은 읽기 전용 복사본으로 OLTP 에서 추출하고 분석 친화적인 스키마로 변환하고 정제하여 Data warehouse 에 적재한다.

이렇게 Data Warehouse 로 데이터를 가져오는 과정을 ETL(Extract-Transform-Load) 라고 한다.

 

OLTP 데이터베이스와 데이터 웨어하우스의 차이점 (The divergence between OLTP databases and data warehouses)

SQL이 분석 질의에 더 적합하기 때문에 Data warehouse 는 일반적으로 RDB 모델을 사용한다.

SQL 질의를 생성하고 결과를 시각화하고 분석가가 drill-down, slicing, dicing 같은 작업을 통해 데이터를 탐색할 수 있게 해주는 여러 그래픽 데이터 분석 도구가 있다.

여기까지 보면 OLTP와 OLAP 둘 다 SQL 질의 인터페이스를 지원하기 때문에 비슷해 보이지만 각각 매우 다른 질의 패턴에 맞게 최적화됐기 때문에 시스템의 내부는 완전히 다르다.

분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마 (Stars and Snowflakes: Schemas for Analytics)

많은 data warehouse 는 별 모양 스키마(star schema - 차원 모델링 dimensional modeling) 로 알려진 정형화된 방식을 사용한다.

• 대다수의 데이터 웨어하우스는 star schema로 알려진 방식을 사용 -> 정형화 방식

star schema는 fact table + dimension tablefact table

• fact table의 각 로우 - 특정 시각에 발생한 이벤트에 해당(구매 이력)
• fact table의 각 칼럼 - dimension table : 이벤트의 속성인 누가, 언제, 어디서, 무엇을, 어떻게, 왜를 나타냄(상품, 가게 등)

눈꽃스키마(snowflake schema) -  dimension이 하위 dimension으로 더 세분화 됨

• 눈꽃 스키마는 star schema보다 더 정규화 됐지만 분석가들은 더 쉽다는 이유로 star schema를 더 선호함

칼럼 지향 저장소

data warehouse는 페타바이트 데이터가 있고, 그 데이터의 row는 수백개의 column을 가진다면 효율적으로 저장하고 질의하기에는 어려운 문제가 있다. 일반적으로 data warehouse 에서 4, 5개의 컬럼만 접근한다 (* 를 사용하는 일은 거의 없다)

 

사람들이 요일에 따라 신선 과일을 사고싶어하는지 사탕을 더 사고싶어 하는지 분석하기

 

fact_sales 에서 3개의 column 에만 접근하는데 date_key, product_sk 둘 중하나에만 색인이 있다고 가정하자. 이 색인은 엔진에 특정 날짜나 특정 제품의 모든 판매 내용을 찾을 수 있는 위치를 알려준다. 하지만 위와 같은 질의를 처리하기 위해서는 disk 에서 100개 이상의 속성을 포함하는 row를 모두 메모리에 적재하고 구문을 분석하여 필요한 조건을 충족하는 row를 filtering 하는 방식으로 대응하는데 이것은 시간이 너무 오래걸린다.

• 대부분의 OLTP 데이터베이스에서 저장소는 로우 지향 방식으로 데이터를 배치

column 지향 저장소의 개념은 모든 값을 하나의 row 에 저장하지 않고 모든 값(column)을 함께 저장한다(칼럼 지향 저장소의 기본 개념). 각 column 은 개별 파일에 저장하면 질의에 필요한 칼럼만 읽고 구문 분석할 수 있다.

• 로우의 전체 값을 다시 모으려면 개별 칼럼 파일의 n번째 항목을 가져온 다음 테이블의 n번째 로우 형태로 함께 모아 구성이 가능

칼럼 압축 (Column Compression)

데이터를 압축하면 디스크 처리량을 줄일 수 있는데 컬럼 저장소는 대개 압축에 적합하다.

위의 그림에서 보면 같은 값이 반복되는 것을 볼 수 있는데 이것은 압축을 하기에 매우 좋은 징조이다.

data warehouse 에 효과적인 압축 중 bitmap encoding 이 있다.