랜덤 I/O와 순차 I/O
랜덤 I/O는 논리적/물리적 순서를 따르지 않고 한 건의 데이터를 읽기 위해 한 블록씩 접근하는 방식이다.
순차 I/O는 논리적/물리적 순서를 따라 차례대로 데이터를 읽어 나가는 방식이다.
- 5번만 순차 I/O고 나머지는 랜덤 I/O다.
- 5번은 논리적/물리적으로 한 방향으로 연속하게 데이터를 읽어 들이지만, 나머지는 연속하지 않은 방향으로 한 블록씩 데이터를 읽는다.
순차 I/O는 3개의 페이지를 디스크에 기록하기 위해 한 번의 시스템 콜을 요청했다.
랜덤 I/O는 3개의 페이지를 디스크에 기록 하기 위해 세 번의 시스템 콜을 요청했다.
즉, 순차 I/O는 디스크의 헤드를 1번 움직였지만, 랜덤 I/O는 디스크의 헤드를 3번 움직이게 된다.
디스크에 데이터를 읽고 쓰는데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정된다. 즉 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 의해 결정된다.
일반적으로 쿼리 튜닝은 쿼리를 직접 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하여 랜덤 I/O 작업을 줄이는 것이 목적이다.
참고로 인덱스 레인지 스캔은 랜덤 I/O를 사용하며, 풀 테이블 스캔은 순차 I/O를 사용한다.
인덱스란 DBMS의 저장 성능을 희생하고 검색 성능을 높이기 위해 만들어진 자료 구조이다.
책의 색인이라고 생각하면 된다.
책의 색인 = DBMS의 인덱스
책의 내용 = DBMS의 데이터 파일
책의 색인을 통해 알 수 있는 페이지 번호 = DBMS의 데이터 파일에 저장된 레코드 주소
책의 색인은 사전 순으로 정렬 = DBMS의 인덱스도 일정 기준으로 정렬 가능
B트리 기반 인덱스의 동작 방식
B-Tree(Balanced Tree)는 N개의 자식을 가질 수 있는 트리구조의 자료 구조이다.
모든 리프노드가 동일한 깊이에 존재하여 균형노드라고 한다.
최상위에 단 하나의 노드만이 존재하며 루트 노드라 한다.
중간 노드를 브랜치 노드, 최하위 노드를 리프 노드라고 한다.
루트노드와 페이지노드에는 자식노드의 주소를 가지고 있고
리프 노드에는 실제 데이터가 위치한 주소값을 가지고 있다
B+트리
B+tree는 B-tree의 확장개념으로, B-tree의 경우, internal 또는 branch 노드에 key와 data를 담을 수 있다. 하지만, B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.
B+tree의 장점
1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다. + 연결된 리프 노드로 인해 범위 검색에 효율적
조회
- 루트에서 시작하여 인덱스 키값 비교를 통해 트리를 순회한다.
- 노드의 키가 정렬되어 있기 때문에 이진검색을 사용할 수 있다.
삽입
- 트리가 비어있다면 루트 노드를 할당하고 삽입한다
- 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.
- 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.
- 적절한 상태란 해당 노드의 데이터 개수가 페이지 수에 맞게 허용 범위 안에 있는 것이다.
- 리프 노드가 부적절한 상태에 있다면 분리한다.
- 가운데 값이 상위 키로 이동
- 이동해도 부적절한 상태에 있다면 다시 상위 키로 이동
- 필요시 루트 노드 까지 이동
삭제
삭제 후 최소 값보다 적어지면 재조정한다
각 노드는 최소 [M/2] - 1개의 키를 가진다. (루트 노드 제외)
M은 M차 트리의 M
재조정 과정
1. key 수가 여유있는 형제의 지원을 받는다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.
인덱스를 통해 PK를 찾고 PK를 통해 레코드가 저장된 위치로 탐색해 바로 가져올 수 있다.
인덱스 설정 기준
규모가 작지 않은 테이블
INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
데이터의 중복도가 낮은 컬럼(카디널리티가 높은 컬럼)
- 예를 들어 성별은 카디널리티가 낮음
읽어야 할 레코드의 건수가 전체 테이블 레코드의 20% ~ 25%를 넘어서지 않을때
인덱스가 잘 동작하고 있는지 어떻게 확인할 수 있을까요?
보통 explain 명령어로 확인한다.
key 필드에 어떤 인덱스를 사용했는지 나타난다.
중요한건 type 필드이다.
ref, eq_ref, range 값이 있는 경우 인덱스가 사용되고 있다는 표시이다.
나쁜 값은 아래와 같다
index: 인덱스를 풀 스캔
- 인덱스를 스캔하겠다는 의미가 아니라 인덱스를 풀 스캔 하겠다는 의미
fulltext: mysql의 전문 검색 기능을 사용하겠다
all: 모든 데이터를 풀 스캔
- 테이블에 인덱스가 있더라도 레코드가 몇개 없는 경우 index를 태우는 것보다 풀 스캔이 빠를 수가 있어서 all이 나올 수 있음
인덱스를 무작정으로 많이 생성하면
- 디스크 공간이 많이 소비된다.
- 저장 성능은 떨어진다.
- 인덱스는 정렬된 상태를 유지해야 하기 때문에 저장시 재조정 작업이 일어나서 오버헤드가 증가한다.
인덱스를 생성하면 메모리테이블에 인덱스를 많이 사용할 경우 데이터의 저장 성능은 떨어지고 인덱스는 오히려 비대해져 좋지 않다.
인덱스는 정렬된 상태를 유지하기 위해 재조정이 일어난다. 값이
커버링 인덱스란
조회하려는 데이터가 인덱스안에 모두 포함되어 있을 경우 인덱스만으로 쿼리문을 커버할 수 있는 것이다.
조회 성능이 더 빨라서 의도적으로 커버링 인덱스로 만들어서 사용한다.
커버링 인덱스를 사용하면 Extra에 Using Index가 표기된다.
옵티마이저는 쿼리문에 대한 최적의 실행 방법을 결정합니다.
실행 계획이란 옵티마이저가 정한 실행 방법을 의미합니다.
옵티마이저는 실행 계획을 결정하는 방식이 규칙 기반, 비용 기반이 있다.
대부분 RDB는 비용 기반을 사용하며, 규칙 기반은 하위 호환성을 위해서만 제공한다.
MYSQL에서는 'EXPLAIN' 키워드를 이용해 실행 계획에 대한 정보를 제공한다.
특정 타입에서 좋지 않은 거만 명시하자면..
select_type
DEPENDENT, DRIVED: 서브 쿼리나 union 확률이 높음
서브 쿼리를 피해달라라는 의미
type
index, fulltext, all
index: 인덱스를 풀 스캔
- 인덱스 스캔을 하겠다는 의미가 아니라 인덱스를 풀 스캔 하겠다는 의미여서 안좋은 것
fulltext: mysql의 전문 검색 기능을 이용하겠다
all: 모든 데이터를 풀 스캔
- 테이블에 인덱스가 있더라도 레코드가 몇개 없는 경우 index를 태우는 것보다 풀스캔이 빠를 수가 있어서 type의 결과가 all이 나올 수 있음
extra
Full scan
Impossible
No matching
Using filesort
Using temporary
using join buffer: 조인이 인덱스를 사용할 수 없어 버퍼를 사용
다중 컬럼 인덱스는 두 개 이상의 필드를 조합해서 생성한 INDEX이다.
MySQL은 인덱스에 최대 15개의 칼럼으로 구성 가능하다.
칼럼의 순서를 신중히 결정해야 하다.
- equal(=) 조건 처럼 적은 데이터(카디널리티가 높은 칼럼)를 조회하는 칼럼을 인덱스 앞 쪽에 설정하고, 범위 검색과 같이 개수가 많은 데이터를 조회하는 컬럼을 뒤쪽에 설정하는 것이 좋다.
- 단일 칼럼 인덱스보다 더 비효율적이므로 INSERT/UPDATE/DELETE 작업을 수행하니, 되도록 수정되지 않는 칼럼을 선택한다.
결합 인덱스의 첫번째 칼럼의 조건이 빠져있다면 해당 결합 인덱스는 사용되지 않는다.
사용하기 좋을 때는..
1. where절에서 and 조건으로 자주 결합되어 사용되면서 각각의 분포도 보다 두 개 이상의 컬럼이 결합될 때 분포도가 좋아지는 컬럼들
2. 다른 테이블과 조인의 연결고리로 자주 사용되는 컬럼들
3. order by에서 자주 사용되는 컬럼들
4. 하나 이상의 키 컬럼 조건으로 같은 테이블의 컬럼들이 자주 조회될 때
CREATE TABLE table1(
uid INT(11) NOT NULL auto_increment,
id VARCHAR(20) NOT NULL,
name VARCHAR(50) NOT NULL,
address VARCHAR(100) NOT NULL,
PRIMARY KEY('uid'),
INDEX idx_name(name), -- 단일 인덱스
INDEX idx_address(address) -- 단일 인덱스
)
CREATE TABLE table2(
uid INT(11) NOT NULL auto_increment,
id VARCHAR(20) NOT NULL,
name VARCHAR(50) NOT NULL,
address VARCHAR(100) NOT NULL,
PRIMARY KEY('uid'),
INDEX idx_name(name, address) -- 다중 컬럼 인덱스
)
SELECT * FROM table1 WHERE name='홍길동' AND address='경기도';
- table1의 경우 각각의 컬럼에 인덱스가 걸려있기 때문에 MySQL은 name 컬럼과 address 칼럼을 보고 둘 중에 어떤 컬럼의 수가 더 빠르게 검색되는지 판단 후 빠른쪽을 먼저 검색하고 그다음 다른 컬럼을 검색하게 된다.
- table2의 경우 바로 원하는 값을 찾는데 그 이유는 인덱스 안에 name과 address 정보가 있으므로 바로 검색이 가능하여 위의 경우보다 빠르다.
SELECT * FROM table2 WHERE address='경기도';이 경우에는 다중 컬럼 인덱스로 설정되어 있던 name이 함께 검색이 되지 않으므로 INDEX의 효과를 볼 수가 없다.
address는 전체값이 정렬되어 있는게 아니라 name이 같은 애들끼리들만 정렬이 되어 있기 때문에 인덱스를 타지 않는다.
===
추가예시2
create index emp_pay_idx on emp_pay(급여년월, 급여코드, 사원번호);
안좋음1
select * from emp_pay where 급여년월 LIKE '2021%' and 급여코드 = '정기급여';위 조건절의 경우 결합 인덱스의 첫 번째 컬럼인 급여년월의 조건이 있더라도 Equal(=)이 아닌 범위 연산자인 LIKE '2021%' 조건을 사용했으므로, 세개의 칼럼이 모두 필요한 emp_pay_idx 인덱스를 찾을 때 두번째 칼럼인 급여코드에 대한 조건을 B*Tree에서 쉽게 찾을수가 없게 된다. 이는 결합 인덱스가 각 칼럼별로 정렬이 되어 있는 것이 아니라 첫번째, 두번째, 세번째 칼럼이 결합이 되어 정렬이 되어있기 때문이다. 이때 급여코드에 대한 조건은 인덱스를 찾아가는 검색조건이 아니라 인덱스 값이 조건에 맞는지 여부를 검증하는 체크 조건이 됩니다
안좋음2
select * from emp_pay where 급여년월 = '202107' and 사원번호 = '20210401';위 조건절의 경우는 결합 인덱스의 첫번째 칼럼인 급여년월의 조건이 equal(=)이더라도 두번째 컬럼인 급여코드에 대한 조건이 없으므로 세번째 칼럼인 사원번호 조건을 검색 조건이 아닌 체크 조건으로 밖에 사용할 수 없게 된다. 즉 결합 인덱스에서 급여년월인 모든 데이터를 찾아서 사원번호 조건에 맞는지 일일이 확인하는 풀 테이블 스캔이 일어나고 있는 셈입니다.
해시 인덱스
해시 테이블을 사용하여 인덱스를 구현
시간복잡도 O(1) 성능
그러나...
rehashing에 대한 부담
=> 트래픽이 몰려와서 계속 추가가 되면 해시 테이블의 사이즈를 늘어주는것이 부담
equality 비교만 가능, range 비교불가능
multi column index의 경우 전체 attributes에 대한 조회만 가능
(a, b) 인덱스를 사용하려면 a, b 둘다 포함하는 조건이여야만 사용해야 한다.
보통 그래서 비트리 기반을 씀
해시테이블은 (Key, Value)로 데이터를 저장하는 자료구조이다.
해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
해시 테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.
[ 분리 연결법(Separate Chaining) ]
Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다. 실제로 Java8의 Hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.
이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.
[ 개방 주소법(Open Addressing) ]
Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.
클러스터드 인덱스와 논클러스터드 인덱스
클러스터드 인덱스
테이블의 PK에 적용되는 인덱스이다.
PK 값이 비슷한 레코드끼리 묶어서 저장하는 것이다.
PK값에 의해 해당 레코드의 물리적인 저장 위치가 결정된다.
PK값이 바뀌면 해당 레코드의 물리적인 저장 위치도 바뀐다.
mysql에서 클러스터링 인덱스는 InnoDB 스토리지 엔진에서만 지원하낟.
- PK 기반 검색이 매우 빠르지만, 레코드의 저장이나 PK 값을 변경할 때 속도가 다른 방식에 비해 느리다.
항상 PK 값을 기준으로 정렬 상태를 유지한다.
리프 노드에 레코드의 모든 칼럼이 같이 저장되어 있다.
넌클러스터드 인덱스는 PK 이외의 칼럼에 적용되는 인덱스이다.
인덱스를 별도의 공간에 생성하여 인덱스 테이블만 데이터를 정렬해 놓는다.
인덱스 스캔 방식
풀스캔
테이블에 포함된 레코드를 처음부터 끝까지 읽어들임
레인지 스캔
유니크 스캔
인덱스에서 중복되지 않는 유일한 값을 검색하는 방법
하나의 값만 읽어 들임
루스 스캔
특정 인덱스 범위만 스캔하는 방식과 비슷하지만 중간중간 필요 없는 인덱스 키 값을 건너뛰고 다음으로 넘어가서 검색하는 방식
SELECT *
FROM {테이블명}
WHERE {인덱스 컬럼} LIKE '%{검색어}%';
병합 스캔
두개 이상의 인덱스를 병합하여 검색하는 방법
해당 방식은 각 인덱스를 병합하는데 시간이 걸리기 때문에 전체적인 속도가 느릴 수 있으나 각각의 인덱스를 사용하는 것보다 효율적입니다.
SELECT *
FROM {테이블명}
WHERE {인덱스 컬럼1} = {검색값1}
AND {인덱스 컬럼2} = {검색값2};
group by 절에 명시된 칼럼이 인덱스의 칼럼의 순서와 위치가 같아야 한다.
인덱스를 구성하는 칼럼 중에서 뒤쪽에 있는 칼럼은 group by 절에 명시되지 않아도 인덱스르 사용할 수 있지만 인덱스의 앞쪽에 있는 칼럼이 group by 절에 명시되지 않으면 인덱스를 사용할 수 없다.
group by 절에 명시된 컬럼이 하나라도 인덱스에 없으면 group by 절은 전혀 인덱스를 사용하지 못하낟.
사용 가능(where 조건 없을 경우)
group by col1
group by col1, col2
group by col1, col2, col3
group by col1, col2, col3, col4
사용 불가능(where 조건 없을 경우)
group by col2, col1 # 순서 불일치
group by col1, co3, col2 # 순서 불일치
group by col1, col3 # 순서는 일치하나, col2가 누락되서 사용 불가능
group by col1, col2, col3, col4, col5 # col5는 인덱스에 들어있지 않아서 사용 불가능
where 조건 하나 - 아래 경우는 인덱스 앞의 칼럼이 한번 걸려졌기 때문에 뒤의 칼럼부터 group by 절에 있어도 인덱스를 사용할 수 있다.
where col1 = '상수' group by col2, col3 # 사용 가능
where col1 = '상수', col2 = '상수' group by col3, col4 # 사용 가능
order by는 group by 와 비슷하다.
하나 조건이 더 있는데 정렬되는 각 칼럼의 오름차순 및 내림차순 옵션이 인덱스와 같거나 또는 정반대인 경우에만 사용할 수 있다.
참고
https://mangkyu.tistory.com/286
https://code-lab1.tistory.com/217
https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC
https://jojoldu.tistory.com/476
https://www.youtube.com/watch?v=IMDH4iAQ6zM
https://coding-factory.tistory.com/755
https://mangkyu.tistory.com/102
https://lannstark.tistory.com/40
'외부활동 > CS 면접 끝장내기 - 데이터베이스 1기' 카테고리의 다른 글
| 데이터베이스 5주차 스터디 정리 (0) | 2023.08.19 |
|---|---|
| 데이터베이스 4주차 스터디 정리 (3) | 2023.08.15 |
| 데이터베이스 2주차 스터디 정리 (0) | 2023.08.02 |
| 데이터베이스 1주차 스터디 정리 (0) | 2023.07.25 |