SQL 쿼리 속도에 대하여

 # Table Full Scan이란?

원하는 값을 조회해오기 위해, 테이블의 전체 Row를 순차적으로 접근하여 데이터를 추출하는 방식으로 가장 느린 데이터 방식이다.

 

# Index란?

SQLite에서 Index란 인덱싱할 칼럼을 Key값으로, 그리고 접근할 데이터의 RowID를 Value값으로 하는 Index 테이블을 별도로 생성하고, 자료구조는 “B-Tree” 구조로 생성됩니다.

 

# Index에 대한 오해

- 컬럼A는 Index를 생성하였고, 컬럼B는 생성하지 않은 경우, 컬럼A의 Index를 탄 이후에, 나온 여러가지 값 중에 Scan을 수행한다.

- 컬럼A와 컬럼B에 대한 Index를 개별로 생성한 경우, 컬럼A 또는 컬럼B만 Index를 타게 된다.

- 컬럼(A,B)에 대한 통합 Index를 생성한 경우, Where조건이 컬럼A, 컬럼B 순으로 오게될 경우에만 Index를 타게 된다.

(최근에는 B, A 순으로 와도 알아서 바꾸어서, 쿼리 조회한다고 한다.)

- 컬럼(A,B)에 대한 통합 Index를 생성한 경우, Where조건이 컬럼B부터 시작하게 될 경우, Table Full Scan이 일어난다.

- 컬럼(A,B)에 대한 통합 Index를 생성한 경우, Where조건이 컬럼A부터 시작하게 될 경우, 정상적으로 Index를 타게 된다.

- 인덱스를 생성한 칼럼 순서로 Where 조건이 들어오면 정상적으로 인덱스를 타게 되는 것이다.

 

# Index를 하나의 컬럼에만 적용해야 한다면?

 단, 1개의 컬럼만 인덱스를 걸어야 한다면, 해당 컬럼은 카디널리티(Cardinality)가 가장 높은 것을 잡는 것이 인덱스의 효율성을 가장 최대한으로 끌어올릴 수 있습니다..

카디널리티(Cardinality)란 해당 컬럼의 중복된 수치를 나타냅니다.
예를 들어 성별, 학년 등은 카디널리티가 낮다고 얘기합니다.
반대로 주민등록번호, 계좌번호 등은 카디널리티가 높다고 얘기합니다.

인덱스로 최대한 효율을 뽑아내려면, 해당 인덱스로 많은 부분을 걸러내야 하기 때문입니다.
만약 성별을 인덱스로 잡는다면, 남/녀 중 하나를 선택하기 때문에 인덱스를 통해 50%밖에 걸러내지 못합니다.

 

 인덱스의 키는 길면 길수록 성능상 이슈가 있습니다.

 

# 복합 Index 설정 시, Tip

복합 Index의 경우 카디널리티가 높은순에서 낮은순으로 (group_no, from_date, is_bonus) 구성하는게 더 성능이 뛰어납니다.

 

# Index 컬럼 조회 시 유의사항

- between, like, <, > 등 범위 조건은 해당 컬럼은 인덱스를 타지만, 그 뒤 인덱스 컬럼들은 인덱스가 사용되지 않습니다.

- 등치( = )조건으로 사용되는 칼럼을 선행 칼럼으로 해야한다. 인덱스 특성상 <, >, <=, >=, BETWEEN, LIKE 등의 비교 연산이 적용된 결합 인덱스는 해당 칼럼 이후는 Range scan이 실시된다.

예를 들어 접근경로가 col1 LIKE ‘A100%’AND col2 = ‘20051010’인 경우

• 인덱스가 COL1 + COL2로 구성된 경우는 A100으로 시작하는 모든 일자에 대한 인덱스를 검색한다.
• 인덱스가 COL2 + COL1로 구성된 경우는‘20051010’을 만족하는 데이터 중 A100으로 시작 된 데이터만 인덱스를 검색

- AND연산자는 각 조건들이 읽어와야할 ROW수를 줄이는 역할을 하지만, or 연산자는 비교해야할 ROW가 더 늘어나기 때문에 풀 테이블 스캔이 발생할 확률이 높습니다.

(WHERE 에서 OR을 사용할때는 주의가 필요)

- null 값의 경우 is null 조건으로 인덱스 레인지 스캔 가능

- WHERE절의 왼쪽은 가공하지 않는다. (인덱스를 타지 않음)

 

(reg_date는 datetime형이면서, index)

SELECT *
FROM    Test
WHERE reg_date >= '2013-01-01'
AND     reg_date < '2013-02-01'

 

# 쿼리 속도 비교

- 데이터의 위치를 지칭하는 주소 역할을 하는 RowID로 데이터에 접근하는 것이 가장 빠르다.

- 인덱스는 그 다음 속도이다.

- Full-Scan은 RowID 순으로 데이터에 순차적으로 접근하여 원하는 데이터를 추출하는 방식으로 일반적으로 가장 느린 데이터 접근 방식이다. (데이터가 많아질수록 더더욱 그렇다.)

 

# B+트리 기반 Index

- 리프노드가 정렬되어 있고, 리프노드 상에서, 양쪽으로 연결되어 있으므로, B+ 트리는 범위 검색 시에 아주 좋은 성능

- B+트리가 아닌 B-Tree의 경우 완전일치(=) 또는 앞부분 일치(xxx...)만 인덱스 사용이 가능하다. 

- 탐색 성능은 전체 로우 수보다 이분화해 가는 깊이에 더 많은 영향을 받는다

- B+ 트리는 삽입과 삭제 시의 성능이 노드의 분할과 머지의 횟수에 따라 결정되기 때문에 노드가 분 할될 확률을 줄이기 위해“각 노드는 최소한 반 이상 차 있어야 한다”[3/2일 경우 B* 트리]라는 제약 조건을 가지고 있다. 그래서 편중된 트리형식을 갖지 않는다.

- B-트리 계열은 자식 수에 대한 일반화를 하면서 하나의 레벨에 더 많이 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞추는 로직까지 갖추었다. 이 균형 로직은 단순하면서도 효율적이다. 그래서 B-트리는 레벨로만 따지면 완전히 균형을 맞춘 트리이다.

- 저장 데이터가 수시로 생성/수정/삭제 경우 적합하다. (다양성을 유지하면서, 생성/수적/삭제 빈번할 경우 그렇다)

(자주 변하지 않으며 낮은 카디널리티일 경우에는, 비트맵 index가 적합하다. 소수의 경우의 수이면서 수정이 빈번하지 않으면, 비트맵 index를 사용한다.)

- 비트맵 인덱스의 경우, 인덱스 rebuild가 필요한 반면, b+트리는 그렇지 않다. 그러나, 복잡한 조건 시 인덱스 성능 보장불가능하다.

 

 

# B 트리의 추가 연산

- 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장합니다. 만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리(Split)돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어집니다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것
- 테이블에 레코드를 추가하는 작업 비용을 1이라고 가정하면 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1~1.5 정도로 예측하는 것이 일반적

- 중요한 것은 이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야하기 때문에 시간이 오래 걸린다는 점

# B 트리의 삭제 연산

- 해당 키값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료됩니다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 또는 재활용할 수 있습니다

# B-트리와 B+트리 비교

B-tree 와 B+tree

 B-tree와 각 노드에 데이터가 저장이 되지만 B+tree의 경우엔 인덱스노드와 리프노드가 분리되어서 존재한다. 그리고, 리프노드는 서로 연결되어 있어서 임의접근과 순차접근모드 성능이 우수하다. 

 

공통점

1. 모든 leaf의 depth가 같다

2. 각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.

3. search가 비슷하다.

4. add시 overflow가 발생하면 split 한다

5. delete 시 underflow가 발생하면 redistribution하거나 merge 한다.

 

차이점

1. B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다. B+tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+tree에서는 data는 오직 leaf에만 존재한다.

2. B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.

3. B+ tree는 leaf node 끼리 linked list로 연결되어 있다.

 

B+tree의 장점

- 블럭사이즈(노드사이즈) 를 더 많이 이용할수잇다 ( 키값에 대한 harddisk 엑세스 주소가 없기 때문에 )

- leaf node 끼리 linked list로 연결되어있어서 시퀀셜한 레인지 탐색에 매우 유리하다 

 

B + Tree 의 단점

- B Tree의 경우 best case에는 루트에서 끝날수 있지만, B+ Tree의 경우 무조껀 leaf노드까지 가야한다.

 

# 출처 

- https://12bme.tistory.com/138 [길은 가면, 뒤에 있다.]

- https://wangin9.tistory.com/entry/B-tree-B-tree [잉구블로그]