[4주차] Real MySQL (ch08)

08. 인덱스

디스크 읽기 방식

참고 인덱스 레인지 스캔은 주로 랜덤 I/O를 사용하며, 풀 테이블 스캔은 순차 I/O를 사용한다. 따라서 큰 테이블의 레코드 대부분을 읽는 OLAP 성격의 작업에는 인덱스를 사용하지 않고 풀 테이블 스캔을 사용하도록 유도할 때가 있다.

인덱스

• 역할별
• 프라이머리 키
• 세컨더리 인덱스
• 유니크 인덱스 - 프라이머리 키를 대체하여 사용할 수 있다고 하여 대체 키라고도 하며, 별도로 분리하기도 하고 세컨더리 인덱스로 분류하기도 한다.

• 데이터 저장 방식(알고리즘)
• B-Tree 인덱스
• Hash 인덱스
Hash 인덱스를 지원하는 데이터베이스

1. MySQL

• MEMORY(HEAP) 스토리지 엔진
• 기본적으로 Hash 인덱스 사용
• 메모리에만 데이터 저장

CREATE TABLE users (
    id INT NOT NULL,
    email VARCHAR(100),
    INDEX USING HASH (email)
) ENGINE = MEMORY;

• NDB 클러스터 스토리지 엔진
• 유니크 인덱스에 대해 Hash 인덱스 지원

2. PostgreSQL

• 기본적으로 Hash 인덱스 지원

CREATE INDEX idx_user_email
ON users USING hash (email);

• 버전 10 이후부터 WAL 로깅을 지원하여 충돌 안정성 개선

• 동등 비교 연산에 최적화

3. Redis

• Key-Value 저장소의 대표적인 예

• 모든 데이터를 Hash 테이블 구조로 관리

• 인메모리 데이터베이스

HSET user:1000 username "john" email "john@example.com"
HGET user:1000 username

4. Cassandra

• 분산 데이터베이스

• 내부적으로 Hash 기반의 파티셔닝 사용

• 데이터 분산 저장에 Hash 함수 활용

CREATE TABLE users (
    user_id uuid PRIMARY KEY,
    username text,
    email text
);

5. MongoDB

• 해시 기반 샤딩
• 컬렉션을 여러 샤드에 분산할 때 Hash 인덱스 사용

db.collection.createIndex({ field: "hashed" })

• 데이터 분산에 효과적

6. MemcacheDB

• Memcached 기반의 영구 저장소

• Key-Value 저장소로 Hash 기반 검색

• 고성능 캐시 시스템

7. Oracle

• Hash 클러스터
• 테이블 데이터를 Hash 함수로 구성

CREATE CLUSTER employees_cluster (
  department_id NUMBER(4)
) SIZE 8192 HASHKEYS 100;

8. Microsoft SQL Server

• 메모리 최적화 테이블
• In-Memory OLTP에서 Hash 인덱스 사용

CREATE TABLE dbo.OrderDetails
(
    OrderID int NOT NULL PRIMARY KEY NONCLUSTERED HASH WITH (BUCKET_COUNT=1000000),
    OrderDate datetime NOT NULL,
    Value decimal(10,2) NOT NULL
) WITH (MEMORY_OPTIMIZED=ON)

장단점 및 사용 사례

작동 원리

해시 함수 사용

• 인덱스 컬럼의 값을 해시 함수를 통해 해시값으로 변환

• 해시값을 기반으로 데이터의 물리적 위치를 결정

버킷 구조

• 해시값이 가리키는 버킷에 실제 데이터 주소를 저장

• 충돌 발생 시 체이닝 등의 방식으로 해결

 

장점

검색 속도

• O(1)의 시간 복잡도로 매우 빠른 검색 가능

• 동등 비교(=) 연산에서 최고의 성능 발휘

메모리 효율

• B-Tree 인덱스에 비해 상대적으로 적은 메모리 사용

• 인덱스 구조가 단순함

단점

범위 검색 비효율

• 범위 검색(>, <, BETWEEN 등)에 취약

• 정렬된 결과를 얻기 어려움

업데이트 비용

• 데이터 수정 시 해시 재계산 필요

• 잦은 변경이 있는 경우 성능 저하 가능

충돌 가능성

• 서로 다른 값이 같은 해시값을 가질 수 있음

• 충돌 해결을 위한 추가 작업 필요

 

적합한 사용 사례

정확한 일치 검색이 많은 경우

SELECT * FROM users WHERE user_id = 'abc123';

유니크한 값을 검색하는 경우

• 예: 이메일, 주민등록번호, 계좌번호 등

캐시 시스템

• 메모리 기반 데이터베이스(예: Redis)

• 세션 저장소

부적합한 사용 사례

범위 검색이 필요한 경우

SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31';

정렬이 필요한 경우

SELECT * FROM products ORDER BY price DESC;

전방 일치/후방 일치 검색

SELECT * FROM customers WHERE name LIKE 'Kim%';

• Fractal-Tree 인덱스
• Merge-Tree 인덱스

• 데이터 중복 여부
• Unique 인덱스
• Non-Unique 인덱스

• 기능별
• 전문 검색용 인덱스
• 공간 검색용 인덱스

B-Tree 인덱스

1. 계층적 구조
• Root Node (최상위)
• Internal Node (중간)
• Leaf Node (최하위)

2. 균형 잡힌 트리
• 모든 리프 노드가 같은 레벨에 존재
• 일반적으로 2-4개 레벨로 구성

• 인덱스 키 추가
• B-Tree 상의 적절한 위치를 검색하여 레코드의 키 값과 대상 레코드의 주소 정보를 리프 노드에 저장한다.
• 리프 노드가 꽉 차서 더 이상 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이 경우에는 상위 브랜치 노드까지 처리 범위가 넓어진다.
• 테이블에 레코드를 추가하는 작업 비용의 약 1.5배의 비용이 든다.
• 인덱스가 3개라면 전체 작업 비용은 5.5(1 + 1.5*3)
• 변경해야할 인덱스 페이지가 버퍼 풀에 있다면 바로 업데이트를 수행하지만, 디스크로부터 읽어와서 업데이트해야 한다면 체인지 버퍼에 저장해 두고 이후 백그라운드 스레드에 의해 처리된다.
• 이를 처리하는 스레드를 체인지 버퍼 머지 스레드라 한다.

• 인덱스 키 삭제
• 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 하고, 이후 삭제 마킹된 인덱스 키 공간은 그대로 방치하거나 재활용한다.

• 인덱스 키 변경
• 기존 키를 삭제하고, 새로운 키를 추가한다.

• 인덱스 값의 크기
• InnoDB 스토리지 엔진이 디스크에 데이터를 저장하는 가장 기본 단위는 페이지이며 인덱스도 페이지 단위로 관리된다.
• 인덱스 키 용량이 크다면 한 페이지에 들어갈 수 있는 인덱스 키의 개수도 줄어들 것이다.
• 이로 인해 조회 시 탐색해야 하는 페이지 수가 늘어나고 이는 성능 저하를 일으킬 뿐 아니라 메모리에 캐시해 둘 수 있는 레코드 수도 줄어들기 때문에 메모리 효율도 떨어트린다.

• 선택도(Selectivity) 혹은 기수성(Cardinality)
• 둘은 거의 같은 의미로 사용된다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빨리 처리된다.
• 선택도가 좋지 않다고 하더라도 정렬이나 그루핑과 같은 작업을 위해 인덱스를 만드는 것이 휠씬 나은 경우도 많다. 인덱스가 항상 검색에만 사용되는 것은 아니므로 여러가지 용도를 고려해 적절히 인덱스를 설계할 필요가 있다.

• 읽어야 하는 레코드의 건수
• InnoDB에서 인덱스를 사용하는 것은 인덱스로 주소를 찾고 주소를 다시 찾아가야 하기 때문에 비용이 많이 드는 작업이다.
• 일반적인 DBMS 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 4~5배 비용이 더 많이 드는 작업으로 예측한다.
• 인덱스를 통해 읽어야할 레코드 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.

• 인덱스 레인지 스캔
• 인덱스 접근 방법 가운데 가장 대표적인 접근 방식으로 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.
• 범위의 시작 위치를 찾고(인덱스 탐색) 리프 노드 레코드만 순서대로 읽어서(인덱스 스캔) 데이터를 가져온다.
• 정렬된 데이터를 순서대로 읽어서 가져오기 때문에 결과값도 정렬되어 가져오게 된다.

• 인덱스 풀 스캔
• 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀스캔이라 한다.
• 대표적으로 쿼리 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.
• 인덱스는 (A, B, C) 컬럼 순으로 만들어져 있지만 조건절은 B 컬럼이나 C 컬럼으로 검색하는 경우
• 인덱스 전체 크기가 테이블 자체 크기보다는 훨씬 작으므로 적은 디스크 I/O로 쿼리를 처리할 수 있다.
• 일반적으로 인덱스를 생성하는 목적은 아니다.

• 루스 인덱스 스캔
• 듬성듬성하게 인덱스를 읽는 것을 의미하며, 이와 상반된 의미에서 인덱스 레인지 스캔이나 인덱스 풀 스캔은 타이트 인덱스 스캔으로 분류한다.
• 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화 하는 경우에 사용된다.

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dept_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;

• 인덱스 스킵 스캔
• 복합 인덱스의 선행 컬럼이 조건절에 없어도 후행 컬럼의 조건으로 인덱스를 활용할 수 있게 해준다.

-- 복합 인덱스 생성
CREATE INDEX idx_gender_age ON employees (gender, age);

-- 효율적으로 작동하는 쿼리
SELECT * FROM employees WHERE gender = 'F' AND age = 30;
SELECT * FROM employees WHERE gender = 'F';

-- 비효율적인 쿼리 (인덱스 활용 불가)
SELECT * FROM employees WHERE age = 30;

• 위 상황에서 인덱스 스킵 스캔은 gender 컬럼에 대해 가능한 값 2개(’M’과 ‘F’)를 구한 다음, 내부적으로 gender=’M’과 gender=’F’인 2개의 쿼리를 실행하는 것과 비슷한 형태의 최적화를 실행한다.

-- 내부적으로 아래와 같이 변환
SELECT * FROM employees WHERE gender = 'M' AND age = 30
UNION ALL
SELECT * FROM employees WHERE gender = 'F' AND age = 30

• 선행 컬럼의 선택도가 낮고, 후행 컬럼의 선택도가 높은 경우 효율적이다.
• MySQL 8.0 버전부터 지원한다.

CREATE INDEX idx_name_age ON users (name, age);

CREATE INDEX idx_search_optimize ON products (
    category_id,    -- = 조건으로 자주 사용
    price,          -- 범위 검색
    created_at      -- 정렬에 사용
);

-- 인덱스를 최대한 활용하는 쿼리
SELECT * FROM products 
WHERE category_id = 1          -- 완전 일치
AND price BETWEEN 100 AND 500  -- 범위 검색
ORDER BY created_at DESC       -- 정렬
LIMIT 10;

• NOT_EQUAL로 비교된 경우(”<>”, “NOT IN”, “NOT BETWEEN”, “IS NOT NULL”)

• LIKE ‘%??’(앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우

• 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변경된 후 비교된 경우

• NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우

• 데이터 타입이 서로 다른 비교(인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우)

• 문자열 데이터 타입의 콜레이션이 다른 경우

R-Tree 인덱스

• 다차원 공간 데이터 인덱싱

• MBR(Minimum Bounding Rectangle) 기반 구조

• B-Tree와 유사한 균형 트리 구조

전문 검색 인덱스

• 어근 분석 알고리즘 : 단어의 어미나 접미사를 제거하여 기본 형태(어근)를 추출하는 방법

running -> run
flies -> fly
connection -> connect
happiness -> happy

• n-gram 분석 알고리즘 : 연속된 N개의 문자나 단어를 기준으로 텍스트를 분석하는 방법

"hello" 의 n-gram (n=2)
he
el
ll
lo

함수 기반 인덱스

• 가상 컬럼을 이용한 인덱스
• 가상 컬럼을 추가하고 그 가상 컬럼에 인덱스를 생성한다.

ALTER TABLE user
	ADD full_name VARCHAR(30) AS (CONCAT(first_name,' ',last_name)) VIRTUAL,
	ADD INDEX ix_fullname (full_name);

• 가상 컬럼을 VIRTUAL이나 STORED 옵션 중 어느 옵션으로 생성하든 상관없다.
• 테이블에 새로운 컬럼을 추가하는 것과 같은 효과를 내기 떄문에 실제 테이블 구조가 변경된다는 단점이 있다.

• 함수를 이용한 인덱스
• MySQL 8.0 버전부터 테이블의 구조를 변경하지 않고 함수를 직접 사용하는 인덱스를 생성할 수 있게 되었다.

CREATE TABLE user (
			user_id BIGINT,
			first_name VARCHAR(10),
			last_name VARCHAR(10),
			PRIMARY KEY (user_id),
			INDEX ix_fullname ((CONCAT(first_name,' ',last_name)))
);

• 함수 기반 인덱스를 활용하려면 조건절에 함수 기반 인덱스에 명시된 표현식을 그대로 사용해야 한다.
• 위의 예시라면 WHERE (CONCAT(first_name,' ',last_name) = ‘Matt Lee’ 같은 식으로 써야 한다.

멀티 밸류 인덱스

-- JSON 배열에 대한 인덱스 생성
CREATE TABLE user_interests (
    user_id INT,
    interests JSON,
    INDEX idx_interests ((CAST(interests AS UNSIGNED ARRAY)))
);

-- 검색 예시
SELECT * FROM user_interests
WHERE 'programming' MEMBER OF(interests);

• MEMBER OF()

• JSON_CONTAINS()

• JSON_OVERLAPS()

클러스터링 인덱스

• 장점
• 프라이머리 키로 검색할 때 처리 성능이 매우 빠름 (특히, 프라이머리 키로 범위 검색을 하는 경우)
• 모든 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많음(커버링 인덱스)

• 단점
• 테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖고 있기 때문에 클러스터링 키 값의 크기가 클 경우 전체적으로 인덱스의 크기가 커짐
• 세컨더리 인덱스를 통해 검색할 때 프라이머리 키로 다시 한번 검색해야 하므로 처리 성능이 느림
• INSERT 할 때 프라이머리 키에 의해 레코드의 저장 위치가 결정되기 때문에 처리 성능이 느림
• 프라이머리 키를 변경할 때 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 처리 성능이 느림

• 클러스터링 인덱스 키의 크기
• 일반적으로 테이블에 세컨더리 인덱스가 4~5개 정도 생성되는 것을 고려하면 프라이머리 키를 신중하게 선택해야 한다.

• 프라이머리 키는 AUTO_INCREMENT보다는 업무적인 컬럼으로 생성한다.
• 프라이머리키는 대부분 검색에서 상당히 빈번하게 사용되기 때문에 업무적으로 해당 레코드를 대표할 수 있다면 그 컬럼을 프라이머리로 설정하는 것이 좋다.,

• 프라이머리 키는 반드시 명시할 것
• 프라이머리 키를 명시하지 않으면 InnoDB 스토리지 엔진이 내부적으로 일련번호(6byte) 컬럼을 추가한다. 하지만 사용자는 전혀 접근할 수가 없다.

• AUTO-INCREMENT 컬럼을 인조 식별자로 사용할 경우
• 프라이머리 키의 크기가 길어도 세컨더리 인덱스가 필요하지 않다면 그대로 프라이머리 키를 사용하는 것이 좋다.
• 세컨더리 인덱스도 필요하고 프라이머리 키의 크기도 길다면 AUTO_INCREMENT 컬럼을 추가하고, 이를 프라이머리 키로 설정하면 된다. 이렇게 프라이머리 키를 대체하기 위해 인위적으로 추가된 프라이머리 키를 인조 식별자라고 한다.
• 로그 테이블과 같이 INSERT 위주의 테이블들은 AUTO_INCREMENT를 이용한 인조 식별자를 프라이머리 키로 설정하는 것이 성능 향상에 도움이 된다.

유니크 인덱스

외래키

• 테이블의 변경(쓰기 잠금)이 발생하는 경우에만 잠금 경합(잠금 대기)이 발생한다.

• 외래키와 연관되지 않은 컬럼의 변경은 최대한 잠금 경합(잠금 대기)을 발생시키지 않는다.