MySql 인덱스

Jaeyoung·2023년 5월 1일
Indexmysql
0
post-thumbnail

데이터베이스 쿼리의 성능을 언급하면서 빼놓을 수 없는 부분이 인덱스 입니다. 이번에는 MySql에서 사용 가능한 인덱스의 종류 및 특성에 대해 살펴보도록 하겠습니다.

인덱스란?

데이터베이스에서 어떠한 한 조건에 해당하는 데이터를 가져올 때 모든 테이블에 있는 데이터를 스캔하게 되면 엄청 많은 시간이 걸리게 됩니다. 그래서 이러한 값과 레코드가 저장된 주소를 Key Value 쌍으로 삼아 인덱스를 만들어 둡니다.

인덱스의 특징

  • Key와 Value 형태로 구성
  • Key가 정렬되어있다.
  • 정렬이 되어있기 때문에 많이 느리다
  • 정렬이 되어있기 때문에 검색속도가 빠르다

결국 CUD의 성능을 희생하고 데이터 읽기 속도를 높이는 기능을 합니다. 그렇기 떄문에 쓰기 및 수정 삭제 작업은 적고 읽기작업이 많은 테이블에 생성하게 되면 많은 이점을 얻을 수 있습니다. 다만 인덱스를 생성하면 생성한 만큼 저장공간을 차지하기 때문에 트레이드오프가 중요합니다.

인덱스의 역할

  • 프라이머리 키
    • 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스
    • 식별자
    • NULL을 허용하지 않으며 중복을 허용하지 않음
  • 보조 키(세컨더리 인덱스)
    • 프라이머리 키를 제외한 나머지 모든 인덱스를 의미
    • 유니크 인덱스와 유니크하지 않은 인덱스로 구분
      • 이러한 조건은 옵티마이저에게 중요한 문제가 될 수 있음

일반적인 인덱스 저장 알고리즘

  • B-Tree 인덱스

    • 컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱 하는 알고리즘
    • 자식의 노드의 갯수가 가변적인 트리 구조

  • Hash 인덱스

    • 컬럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘
    • 해시값을 사용하기 때문에 범위 검색시 사용 불가
    • 메모리 기반의 데이터베이스에서 많이 사용

  • Fractal-Tree 인덱스

    출처 : https://gywn.net/2014/05/fractal-index-in-tokudb/

    • B-Tree 구조에서 데이터가 많아지게 되면 메모리에 적제할 수 없어 디스크에 저장될 수 밖에 없는데 이렇게 되면 디스크 I/O 작업이 많이 발생하게 되면서 성능이 많이 나빠지기 때문에 이러한 문제를 해결하기 위한 해결법으로 제시된 알고리즘이 Fractal-Tree입니다.
    • B-Tree + Buffer
    • 데이터 유입이 생기면 Child Node에 데이터를 바로 보내는게 아닌 Buffer에 저장했다가 Buffer가 꽉차면 그 때 Child Node로 이동 다시 Buffer가 비게 되면 빈 버퍼에 이동

  • LSM(Log-Structured Merged-Tree) 인덱스

    • Bitcask, MongoDB, BCassandra SQLite4 등에서 사용
    • Percona **MySql MyRocks 스토리지 엔진에서 LSM 인덱스 사용
    • 데이터를 파일에 추가하는 것만 허용하고 내부 업데이트 작업을 피하여 비용이 많이 드는 랜덤 액세스를 순차 엑세스로 바꾸는 데이터 구조
      • MemTable 이라는 가변 메모리 내 데이터 구조에 먼저 쓰기작업이 수행되고 Memtable이 특정 크기에 도달하면 디스크로 플러시되어 SSTable이 생성
    • LSM은 정렬된 문자열 테이블(SSTable) 기반
      • SSTable은 키와 값이 모두 문자열인 정렬된 키/값 집합을 포함하는 변경할 수 없는 맵/사전
      • SSTable은 Index와 데이터 파일로 구성되어 있음
      • 불변을 유지하기 위해 CUD 작업이 발생하면 전체 데이터 파일을 다시 작성해야 함
    • 읽기 작업을 수행할 땐 MemTable 확인 → SSTables 검색 → 최신 데이터를 얻기 위한 결과 병합
      • 병합 단계로 인해 읽기 처리 요청이 느려질 수 있음
      • 느려질 수 있기 때문에 압축 작업 진행
      • SSTable 병합 → 이전 데이터 제거

B-Tree Index

  • 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 알고리즘
  • 변형으로 B+Tree, B*Tree라는게 존재
  • Balanced Tree로 구성
  • MySql B-Tree Index는 실제 컬럼의 전체의 값을 인덱스 키로 사용하는 것이 아니라 3072Byte까지만 잘라서 인덱스 키로 사용한다.
  • Full Text 검색에는 InnoDB B-Tree 인덱스를 사용할 수 없다.

B-Tree 구조 및 특성

일반적인 트리 자료구조랑 같아서 최상위에는 루트노드가 존재하고 그 중간에 브랜치 노드들이 존재하고 가장 밑은 리프노드가 존재합니다. 리프노드에는 데이터 레코드를 찾아가기 위한 주소값(InnoDB는 PK)을 가지고 있습니다. 이때 트리의 노드를 살펴보면 인덱스키는 정렬이 되어있지만 데이터 파일의 레코드는 정렬되어있지 않습니다.(InnoDB는 클러스터되어 저장되기 떄문에 PK 순서로 정렬됩니다.)

InnoDB B-Tree Index 데이터 찾는 과정

  1. 루트노드에서 검색
  2. 루트노드에서 찾은 자식 주소로 이동
  3. 브랜치노드에서 검색
  4. 브랜치노드에서 찾은 자식 주소로 이동
  5. 리프노드 검색
  6. 리프노드에서 찾은 PK를 통해 PK Index 검색
  7. 위와 같은 과정을 동일하게 거치게 되어 리프노드에서 레코드 조회

B-Tree Index CREATE

B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색하고 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 리프 노드에 저장합니다. 하지만 이때 리프 노드가 꽉 찬 경우 리프 노드가 분리돼야 하는데 상위 노드까지 처리가 되어야 할 수도 있기 때문에 쓰기 작업은 성능이 별로 좋지 않습니다. InnoDB에서는 체인지 버퍼를 통해 작업을 지연 처리 시킬 수 있습니다.

B-Tree Index DELETE

B-Tree의 키 값이 삭제되면 B-Tree의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료 됩니다. 마킹작업은 DISK I/O가 필요하고 이렇게 마킹된 인덱스는 그대로 방치되거나 재활용할 수 있습니다.

B-Tree Index UPDATE

B-Tree의 키 값을 변경하는 작업은 단순하게 값을 바꾸는 방식으로 동작하지 않습니다. 키값을 통해 리프 노드의 위치가 결정되기 떄문에 먼저 해당 키값를 삭제 한 뒤에 변경된 키값을 추가하는 방식으로 동작합니다. InnoDB에서는 체인지버퍼를 통해 작업을 지연 처리 시킬 수 있습니다.

B-Tree Index SELECT

B-Tree Index는 CUD 작업을 할 때 추가 비용을 감수하면서 인덱스를 구축하는 이유는 빠른 검색을 위해서 입니다. B-Tree Index를 이용한 검색은 100프로 일치하거나 값의 앞부분만 일치하는 경우에 사용할 수 있기 때문에 비교 조건에서도 인덱스를 활용할 수 있지만 인덱스를 구성하는 키 값의 뒷부분을 검색하는 용도로는 사용할 수 없습니다. 또한 변형된 키 값을 통해 비교 연산 하는 경우에는 Index에 포함된 값이 아니기 때문에 B-Tree의 이점을 살릴 수 없습니다.

💡 Index 키 값이 유니크 할 수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

항상 Index를 통해 레코드를 읽는다고 빠르지 않습니다. 어떤 경우에는 Full Scan을 하는 경우가 더 빠를 수 있습니다. 100만 건의 데이터가 저장 되어있을 때 50만 건을 읽어야 하는 쿼리가 있다고 가정했을 때 Full Scan을 통해서 100만 건을 읽어 50만 건을 버릴지 인덱스를 통해 50만 건을 읽는게 효율적인지 판단해야 합니다. 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25퍼센트를 넘어서면 인덱스를 이용하지 않는게 효율적 입니다.

인덱스 레인지 스캔

  • 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
  • 루트 노드 → 브랜치 노드 → 리프 노드 과정을 통해 시작지점을 찾고 리프 노드의 레코드만 순서대로 읽고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환
  • 순서대로 이제 레코드를 읽게 되는데 이때 랜덤 I/O가 일어난다.
💡 쿼리가 필요로 하는 데이터에 따라 레코드에 지정된 페이지를 가져오는 작업을 하지 않아도 되는 것을 커버링 인덱스라고 한다.

인덱스 풀 스캔

  • 인덱스의 처음부터 끝까지 모두 읽는 방식
  • 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 해당 방식이 사용됨
  • 인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 떄문에 테이블 풀 스캔보다는 효율적이다.
💡 효율적인 방식이 아니기 때문에 일반적으로 인덱스를 생성하는 목적은 아니다.

루스 인덱스 스캔

  • 느슨하게 또는 듬성듬성하게 인덱스는 읽는 방식(중간에 필요치 않은 인덱스 키값은 SKIP)
  • 일반적으로 GROUP BY 또는 집합 함수 중 MAX, MIN 함수에 대한 최적화 하는 경우 사용

인덱스 스킵 스캔

Index
ALTER TABLE employees ADD INDEX ix_gender_birthdate (gender, birth_date);

1.
SELECT * FROM employees WHERE birth_date>='1965-02-01';

2.
SELECT * FROM employees WHERE gender ='M' AND birth_date>='1965-02-01';

위와 같은 Index를 생성했을 때 1번 쿼리 같은 경우는 Index를 활용하지 못합니다 하지만 2번 쿼리 같은 경우는 index에 두 컬럼 모두 포함되어있기 때문에 index를 활용해서 검색을 합니다. MySql 8.0 버전 부터는 1번 같은 쿼리에 대해서 옵티마이저가 gender 컬럼을 건너뛰고 birth_date 컬럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔이라는 최적화 기능이 도입되었습니다.

SELECT gender, birth_date FROM employees WHERE gender ='M' AND birth_date>='1965-02-01';
SELECT gender, birth_date FROM employees WHERE gender ='F' AND birth_date>='1965-02-01';ㅡ

그래서 인덱스 스킵 스캔이 실행되면 위와 같은 쿼리를 실행하는것과 비슷하게 최적화를 실행하게 됩니다.

💡 인덱스 스킵 스캔은 WHERE 조건절에 조건이 없는 인덱스의 선행 컬럼의 유니크한 값의 갯수가 적어야하고 커버링 인덱스이어야 한다. 커버링 인덱스이어야 하는건 다른 컬럼도 필요하기 때문에 풀 테이블 스캔으로 실행되기 때문이다.

다중 컬럼 인덱스

  • 2개 이상의 컬럼을 포함하는 인덱스
  • 앞 컬럼에 의존적이게 뒷 컬럼이 정렬된다. (컬럼의 순서는 중요하다)

InnoDB Backward B-Tree Index scan이 느린 이유

  • 페이지 잠금이 Forward Index Scan에 적합한 구조
    • InnoDB 스토리지 엔진에서는 페이지 잠금 과정에서 데드락을 방지하기 위해 왼쪽에서 오른쪽으로만 잠금을 획득하도록 하고 있어 정순일 경우에는 잠금 획득이 간단하지만 역순인 경우에는 복잡한 과정을 거치게 되면서 잠금 획득으로 인한 비용이 더 발생하게 된다.
  • 페이지 내에서 인덱스 레코드는 단방향으로만 연결된 구조 (Forwarded single linked link)

비교 조건의 종류와 효율성

비교 조건에 따라 인덱스 동작방식이 어떻게 달라지는지 알아보기 위해 dept_emp 테이블에 dept_no와 emp_no 컬럼이 존재한다고 가정하겠습니다.

  • 작업 범위 결정 조건
    • SELECT * FROM dept_emp WHERE dept_no=’d002’ AND emp_no ≥ 10114; 라는 쿼리가 존재할 떄 dept_no=’d002’ AND emp_no ≥ 10114 이거에 해당 하는 레코드를 먼저 찾고 dept_no가 d002가 아닐 떄까지 인덱스를 쭉 읽기만 하면 되는걸 작업 범위 결정 조건이라고 합니다.
  • 필터링 조건 OR 체크 조건
    • SELECT * FROM dept_emp WHERE emp_no ≥ 10114 AND dept_no=’d002’; 라는 쿼리가 존재할 떄 emp_no ≥ 10114 AND dept_no=’d002인 레코드를 찾고 그 이후 모든 레코드에 대해 dept_no가 d002인지 비교하는 과정을 거치는 것을 필터링 혹은 체크 조건이라고 합니다.

B-Tree Index를 활용하지 못하는 조건들

  • NOT-EQUAL로 비교한 경우(<>, NOT IN ,NOT BETWEEN, IS NOT NULL)
  • LIKE %??
  • 다른 연산자를 통해 인덱스 컬럼이 변형된 후 비교하는 경우
  • 데이터 타입이 서로 다른 비교

B+Tree Index

  • 순차 파일을 구성하기 위해 사용되는 Index
  • B-Tree 같은 경우는 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가기 때문에 전체 데이터를 차례로 처리하기가 많이 불편한 점이 있어 B+Tree가 만들어짐
  • 루트노드와 브랜치노드는 오직 인덱싱을 위한 Key를 저장하는 용도로 사용하고 실질적인 페이지는 리프노드에 존재하고 서로 Linked List 형태로 연결되어있는 구조
  • https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/

전문 검색 Index

전문 검색은 말 그대로 Full Text Search를 의미하는데 B-Tree와는 다르게 전체 텍스트 검색을 하는 인덱스 입니다. 이러한 인덱스는 2가지의 알고리즘으로 구분할 수 있는데 아래와 같습니다.

  • 어근 분석 알고리즘
    1. 불용어 처리
      • 가치가 없는 단어를 모두 필터링해서 제거하는 작업
      • 불용어는 많지 않기 때문에 일반적으로 상수로 정의해서 사용된다.
      • MySql 서버는 불용어가 정의되어 있다.
      • 사용자가 별도로 불용어를 정의할 수 있다.
    2. 어근 분석
      • 검색어로 선정된 단어의 뿌리인 원형을 찾는 작업
      • 한국어는 어근 분석보다는 문장의 형태소(가장 작은 말의 단위)를 분석해서 명사와 조사를 구분하는 기능이 더 중요하다
      • MeCab을 통해 한글 분석이 가능한데 우선 단어 사전이 필요하고 문장을 해체해서 각 단어의 품사를 식별할 수 있는 문장의 구조 인식(실제 언어의 샘플을 이용해 언어를 학습하는 과정이 필요함)이 필요하다.
  • n-gram 알고리즘
    • MeCab으로 만족할 만한 결과를 내기 위해서 많은 시간과 노력을 필요로 하기 떄문에 전문 검색 엔진을 고려하는게 아니라면 적용하기가 쉽지 않기 때문에 이러한 단점을 보완하기 위해 나온 알고리즘
    • 본문을 무조건 몇 글자씩 잘라서 인덱싱하는 방법
    • 2글자 단위로 키워드를 쪼개서 인덱싱하는 2-gram 방식을 많이 사용
      • EX) That → Th, ha, at
      • 이때 생성된 토큰들에 대해 불용어를 걸러내는 작업 수행
      • 이러한 토큰을 B-Tree Index에 저장

전문 검색 Index를 사용하기 위한 조건

  • 쿼리 문장이 전문 검색을 위한 문법(MATCH … AGAINST …)을 사용
  • 테이블이 전문 검색 대상 컬럼에 대해서 전문 인덱스 보유

멀티 밸류 인덱스

멀티 밸류 인덱스는 제 1정규화에 위배되는 형태로 되어있는 Json 타입으로 정의된 레코드처럼 인덱스 키와 데이터 레코드가 1대1이 아닌 하나의 데이터 레코드가 여러 개의 키 값을 가질 수 있는 형태의 인덱스 입니다.

아래와 같은 함수들을 통해 해당 인덱스를 활용할 수 있습니다.

  • MEMBER OF()
  • JSON_CONTAINS()
  • JSON_OVERLAPS()

클러스터링 인덱스

클러스트링이란 여러 개를 하나로 묶는다는 의미로 사용되는데 클러스터링 인덱스는 프라이머리 키를 기준으로 비슷한 것들끼리 묶어서 저장하는 형태로 구현됩니다. 이러한 특징으로 인해 프라이머리 키 값에 의해 레코드의 저장 위치가 결정됩니다.

💡 B-Tree 인덱스 또한 인덱스 키 값으로 정렬되어 저장되는데 어떻게 보면 이러한 인덱스랑 클러스터링된 것으로 이해할 수 있는데 클러스터링 인덱스는 프라이머리키를 통해 정렬되기 떄문에 B-Tree 인덱스는 클러스터링 인덱스라고 부르지 않습니다.

B-Tree와 달리 클러스터링 리프노드에는 레코드의 모든 컬럼이 같이 저장돼 있습니다. 그리고 InnoDB 스토리지 엔진이 적절한 클러스터링 키 후보를 찾지 못하는 경우 내부적으로 레코드의 일련번호 컬럼을 생성합니다.

장점

  • PK로 검색할 때 처리 성능이 엄청 빠름
  • 테이블의 모든 세컨더리 인덱스가 PK를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많음

단점

  • 모든 세컨더리 인덱스가 클러스터링 키를 가지고 있기 때문에 키 값이 크기가 클 경우 전체적으로 인덱스 크기가 커짐
  • 세컨더리 인덱스를 통해 검색할 때 PK로 다시한번 검색하기 때문에 처리 성능이 느림
  • INSERT할 때 PK에 의해 저장 위치가 결정되기 때문에 처리 성능이 느림

유니크 인덱스

  • 제약조건에 가까운 인덱스
  • 인덱스에 같은 값이 2개 이상 저장될 수 없음을 의미
  • NULL은 2개 이상 저장될 수 있다
  • 새로운 레코드가 Insert 될 떄 중복체크를 하기 때문에 세컨더리 인덱스보다 쓰기 속도가 느리다
    • 중복 체크 때문에 저장할 떄 버퍼링을 사용하지 못함
profile
Jaeyoung
Programmer
이전 포스트

MySql 트랜잭션과 잠금

다음 포스트

Docker Compose Container Connection Fail

0개의 댓글