인덱스

1. 디스크 읽기 방식

(1) 랜덤 I/O 와 순차 I/O

랜덤 I/O는 3개의 페이지를 디스크에 기록하기 위해서 디스크 헤더를 3번 시스템콜을 요청합니다. 하지만 순차 I/O는 디스크 헤더를 1번 움직입니다. 당연히 순차 I/O가 성능히 더 좋습니다.

2. 인덱스

DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래걸립니다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 삼아 인덱스를 만들어둡니다. DBMS의 인덱스로 칼럼의 값을 주어진 순서로 미리 정렬해서 보관합니다.
DBMS의 인덱스는 SortedList를 이용해서 정렬된 상태를 유지합니다.

• SortedList : 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조
• ArrayList : 값을 저장되는 순서 그대로 유지하는 자료 구조입니다.

인덱스는 데이터를 관리하는 방식과 중복 값의 허용 여부등에 따라 여러 가지로 나눌 수 있습니다.

3. B-Tree 인덱스

Balanced-tree는 칼럼의 원래의 값을 변형시키지않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지합니다.

(1) 구조 및 특성

B-tree는 트릭조의 최상위에 하나의 '루트 노드'가 존재하고 그 하위에 자식 노드가 붙어있는 형태입니다. 가장 하위에 있는 노드를 '리프 노드'라고 하고, 중간의 노드를 '브랜치 노드'라고 합니다. 이 리프 노드에는 실제 데이터 레코드를 찾기위한 주소값을 가지고 있습니다.

(2) B-Tree 인덱스 키 추가 및 삭제

A. 인덱스 키 추가

B-Tree에 저장될 떄는 저장될 키 값을 이용해서 B-Tree 상의 적절한 위치를 검색해야 합니다. 저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소정보를 B-Tree 리프 노드에 저장합니다.

B. 인덱스 키 삭제

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

C. 인덱스 키 변경

B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후에, 다시 새로운 키 값을 추가하는 형태로 처리됩니다.

D. 인덱스 키 검색

인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 빠른 검색을 위해서입니다.
유념할 점은, 인덱스를 이용한 검색에서 인덱스의 키값에 변형이 가해진 후 비교되는 경우에는 B-Tree의 빠른 검색 기능을 사용할 수 없습니다. 왜냐하면 이미 변형된 값은 B-Tree인덱스에 존재하는 값이 아니므로 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree 장점을 이용할 수 없습니다

(3) B-Tree 인덱스 사용에 영향 미치는 요소

B-Tree d인덱스는 인덱스르 구성하는 칼럼의 크기와 레코드의 건수, 유니크한 인덱스 키값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향 받습니다.

A. 인덱스 키 값의 크기

InnoDb 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위 페이지 또는 블록 이라고 합니다. 인덱스도 결국 페이지 단위로 관리되며, 루트 브랜치 리프 노드를 구분한 기준이 바로 페이지 단위입니다.

InnoDB 스토리지 엔진의 페이지 크기를 innoDB_page_size 시스템 변수를 이용해 4KB - 64KB사이의 값을 선택할 수 있지만 기본값은 16KB 입니다.
인덱스 페이지 (16KB) 에는 585개를 저장할 수 있습니다.

B. B-Tree 깊이

B-Tree 인덱스의 깊이는 중요하지만 직접 제어할 방법은 없습니다. B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇번이나 랜덤하게 디스크를 읽어와야 하는지 직결되는 문제입니다.
인덱스의 키 값의 크기는 가능하면 작게 만드는 것이 좋습니다.

C. 선택도(기수성)

선택도 또는 기수성은 거의 같은 의미로 사용됩니다. 인덱스 키 값 가운데 유니크한 값의 수를 의미합니다.

D. 읽어야하는 레코드 건수

일반적인 DBMS 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레고드 1건을 읽는 것보다 4-5배 정도 비용이 더 많이 드는 작업인 것으로 예측합니다.
즉, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블의 레코드의 20-25%를 넘어서면 인덱스를 이용하지않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는게 효율적입니다.

(4) B-Tree 인덱스를 통한 데이터 읽기

A. 인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식입니다.
B-Tree 인덱스에서 루트와 브랜치 노드를 이용해서 스캔 시작 위치를 검색하고 그 지점부터 필요한 방향으로 인덱스를 읽어 나갑니다.

1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾습니다. 이 과정을 인덱스 탐색이라고 합니다.
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽습니다. 이 과정을 인덱스 스캔이라고 합니다
3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어옵니다.

B. 인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 합니다. 인덱스의 크기는 테이블의 크기보다 작으므로 테이블을처음부터 끝까지 읽는 것보다 인덱스만 읽는 게 효율적입니다. 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 이 방식이 사용됩니다

C. 루스 인덱스 스캔

로스 인덱스 스캔은 듬성듬성하게 인덱스를 읽는 걸 의미합니다. GROUP BY 또는 지밥 함수 가운데 MAX() 또는 MIN() 함수에 최적화를 하는 경우에 사용됩니다.

D. 인덱스 스킵 스캔

인덱스 스킵 스캔은 인덱스의 선행 칼럼이 가진 유니크한 값의 개수가 소량일 때만 적용 가능한 최적화

(5) 다중 칼럼 인덱스

2개 이상의 칼럼을 포함하는 인덱스 를 다중 칼럼 인덱스라고 하며, Concatenated Index라고도 합니다. 다중 칼럼 인덱스는 인덱스 내에서 각 칼럼의 위치가 중요합니다

(6) B-Tree 인덱스의 정렬 및 스캔 방향

A. 인덱스의 정렬

• 인덱스 스캔 방향
  인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만, 쿼리가 그 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있습니다.
  오름차순으로 생성된 인덱스를 정순으로 읽으면 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과가 되고, 역순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 됩니다

• 내림차순 인덱스
  - 오름차순 인덱스 : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스

  • 내림차순 인덱스 : 큰 값의 인덱스 키가 B-Tree 왼쪽으로 정렬된 인덱스
  • 인덱스 정순 스캔 : 인덱스킈 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
  • 인덱스 역순 스캔 : 인덱스의 키의 크고 작음에 관계없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

내부적으로 InnoDB에서 인덱스 역순 스캔이 정순 스캔에 비해 느립니다. 왜냐하면 페이지 내에서 인덱스 레코드가 단방향으로 연결된 구조이기 때문입니다.

(7) B-Tree 인덱스의 가용성과 효율성

쿼리의 WHERE, GROUP BY, ORDER BY 어떤 경우에 인덱스를 사용할수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야합니다. 그래야 쿼리의 조건을 최적화하거나, 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있습니다.

A. 비교 조건의 종류와 효율성

인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 작업을 '필터링'이라고 합니다.
작업범위를 결정하는 조건을 '작업 범위 결정 조건', 비교작업의 범위를 줄이지 못하고 거름종이 역할만 하는 조건을 '필터링 조건', '체크 조건'이라고 합니다.

B. 인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼있다는 것입니다. 다중 컬럼 인덱스에도 적용됩니다.

C. 가용성과 효율성 판단

B-Tree인덱스의 특성상 다음 조건에서는 사용할 수 없습니다. 작업 범위 결정조건으로 사용할 수 없습니다.

• NOT-EQUAL로 비교된 경우("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")
• LIKE '%??'형태로 문자열 패턴이 비교된 경우
• 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
• NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용되는 경우
• 데이터 타입이 서로 다른 비교
• 문자열 데이터 타입의 콜레이션이 다른 경우

4. R-Tree 인덱스

공간 인덱스는 R-Tree 인덱스 알고리즘을 이용해서 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스입니다. B-Tree는 칼럼의 값이 1차원의 스칼라 값인 반면, R-Tree 인덱스는 2차원의 공간 개념값입니다.

(1) 구조 및 특성

공간 정보의 저장 및 검색을 위해 기하학적 도형 정보를 관리할 수 있는 데이터 타입을 제공합니다.
GEOMETRY 타입은 POINT, LINE, POLYGON 객체 모두 저장할 수 있습니다.
R-Tree 알고리즘을 알기위해서는 MBR(Minimum Bounding Rectangle) 해당 도형을 감싸는 최소 크기의 사각형을 의미합니다. 이 사각형들의 포함 관계를 B-Tree 형태로 구현한 인덱스가 R-Tree 인덱스입니다.

MBR은 3개의 레벨, 최상위 레벨, 차상위 레벨, 최하위 레벨로 나누어집니다. 각 레벨에 따라 루트, 브랜치, 리프 노드로 저장됩니다.

(2) R-Tree 인덱스의 용도

일반적으로 WGS84(GPS_ 기준의 위도, 경도 좌표 저장에 주로 사용됩니다. 'ST_Contains(), ST_Within()' 포함관계를 비교하는 함수로 검색을 수행하는 경우에만 인덱스를 이용할 수 있습니다.

5. 전문 검색 인덱스

(1) 인덱스 알고리즘

문서 본문의 내용에서 사용자가 검색하게 될 키워드를 분석해 내고, 빠른 검색용으로 사용할 수 있게 이러한 키워드로 인덱스를 구축합니다. 전문 검색 인덱스는 문서의 키워드를 인덱싱하는 기법에 따라 크게 단어의 어근 분석과 n-gram 분석 알고리즘으로 구분할 수 있습니다.

A. 어근 분석 알고리즘

• 불용어 처리
  불용어 처리는 검색에서 별 가치가 없는 단어를 모두 필터링해서 제거하는 작업을 의미합니다.

• 어근 분석
  검색어로 선정된 단어의 뿌리인 원형을 찾는 작업입니다.

B. n-gram 알고리즘

형태소 분석이 문장을 이해하는 알고리즘이면, n-gram은 단순히 키워드를 검색하기위한 인덱싱 알고리즘입니다.
n-gram이란 본문을 무조건 몇 글자씩 잘라서 인덱싱하는 방법입니다ㅣ

C. 불용어 변경 및 삭제

내장된 불용어 대신 사용자가 직접 불용어를 등록하는 방법을 권장

• 전문 검색 인덱스의 불용어 처리 무시
  불용어 처리를 무시하는 방법은 2가지가 있습니다. 하나는 스토리지 엔진에 관계없이 MySQL 서버의 모든 전문 검색 인덱스에 불용어를 완전히 제거하는 것입니다. 이를 위해 'ft_stopword_file' 시스템 변수에 빈 문자열을 설정하면 됩니다.

또 하나는 InnoDB 스토리지 엔진을 사용하는 테이블 전문 검색 인덱스에 대해서 불용어 처리를 무시할 수 있습니다. 'innodb_ft_enables_stopword'시스템 변수를 OFF로 설정하면 됩니다

• 사용자 정의 불용어 사용
  사용자 정의 불용어를 사용하는 방법은 두 가지 입니다.
  'ft_stopword_file' 설정에 등록하거나
  InnoDB 스토리지 엔진을 사용하는 테이블의 전문 검색 엔진에서만 사용하는, 불용어의 목록을 테이블로 저장하는 방식입니다. 'innodb_ft_server_stopword_table' 시스템 변수에 불용어 테이블을 설정하면 됩니다.

(2) 전문 검색 인덱스의 기용성

전문 검색 인덱스를 사용할려면 두 가지 조건을 갖춰야합니다.

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

6. 함수 기반 인덱스

칼럼의 값을 변형해서 만들어진 값에 대해 인덱스를 구축해야 될 떄가 있습니다.

(1) 가상 칼럼을 이용한 인덱스

가상 컬럼을 만들고 가상 칼럼에 인덱스를 생성할 수 있습니다. 이 가상 칼럼은 테이블에 새로운 칼럼을 추가하는 것과 같은 효과를 내기 때문에 테이블의 구조가 변경된다는 단점이 있습니다.

(2) 함수를 이용한 인덱스

함수를 직접 사용하는 인덱스는 테이블의 구조를 변경하지 않고, 계산된 결괏값의 검색을 빠르게 만들어줍니다. 함수 기반 인덱스를 제대로 활용하려면 반드시 조건절에 함수 기반 인덱스에 명시된 표현식이 그대로 사용되야합니다.

7. 멀티 밸류 인덱스

전문 검색 인덱스를 제외한 모든 인덱스는 레코드 1건이 1개의 인덱스 키값을 가집니다. 하지만 멀티 밸류 인덱스는 하나의 데이터 레코드가 여러 개의 키 값을 가질 수 있는 형태의 인덱스 입니다.

'MEMBER OF(), JSON_CONTAINS(), JSON_OVERLAPS()'

8. 클러스터링 인덱스

MySQL 서버에서 클러스터링은 테이블의 레코드를 비슷한 것들끼리 묶어서 저장하는 형태로 구현됩니다.

(1) 클러스터링 인덱스

클러스터링 인덱스는 테이블의 프라이머리 키에 대해서만 적용되는 내용입니다. 프라이머리 키값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터링 인덱스라고 표현
프라이머리 키 값에 의해서 레코드의 저장위치가 결정됩니다.

클러스터링 인덱스 구조를 보면, 클러스터링 테이블 구조 자체는 B-Tree와 비슷하지만 클러스터링 인덱스의 리프노드에는 레코드의 모든 칼럼이 같이 저장돼있음을 알 수 있습니다.

1. 프라이머리 키가 있으면 기본적으로 프라이머리 키를 클러스터링 키로 선택합니다.
2. NOT NULL 옵션의 유니크 인덱스 중에서 첫 번쨰 인덱스를 클러스터링 키로 선택합니다
3. 자동으로 유니크한 값을 가지도록 증가되는 칼럼을 내부적으로 추가한 후, 클러스터링 키로 선택합니다.

(2) 세컨더리 인덱스에 미치는 영향

InnoDB의 모든 세컨더리 인덱스는 해당 레코드가 저장된 주소가 아니라 프라이머리 키 값을 저장하도록 되어있습니다.

(3) 클러스터링 인덱스의 장점과 단점

• 장점
  - 프라이머리키로 검색할 때 처리 성능이 매우 빠름

  • 테이블의 모든 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많습니다.

• 단점
  - 테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖기 때문에 클러스터링 키 값의 크기가 클경우 전체적으로 인덱스의 크기가 커짐

  • 세컨더리 인덱스를 통해 검색할 때 프라이머리 키로 다시 한번 검색해야 하므로 처리 성능이 느림
  • INSERT할 때 프라이머리 키에 의해 레코드 저장위치가 결정되기 때문에 처리 성능이 느립니다
  • 프라이머리 키를 변경할 때 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 처리 성능이 느립니다

(4) 클러스터링 테이블 사용 시 주의사항

A. 클러스터링 인덱스 키의 크기

세컨더리 인덱스가 프라이머리 키 값을 포함합니다. 그래서 프라이머리 키의 크기가 커지면 인덱스도 자동으로 커집니다.

B. 프라이머리 키는 AUTO-INCREMENT보다는 업무적인 칼럼으로 생성

C. 프라이머리 키는 반드시 명시할 것

AUTO-INCREMENT를 사용해서 프라이머리키를 생성하는 것을 권장,

D. AUTO-INCREMENT 칼럼을 인조 식별자로 사용할 경우

여러 개의 칼럼이 복합으로 프라이머리 키가 만들어지는 경우, 프라이머리 키의 크기가 길어질 때가 있습니다. 그래도 사용하는 것이 좋습니다. 세컨더리 인덱스도 필요하고 프라이머리 키의 크기도 길다면 AUTO-INCREMENT 칼럼을 추가하고, 이를 프라이머리 키로 설정하면 됩니다. 프라이머리 키를 대체하기 위해 인위적으로 추가된 프라이머리 키를 인조 식별자라고 합니다.

9. 유니크 인덱스

(1) 유니크 인덱스와 일반 세컨더리 인덱스의 비교

A. 인덱스 읽기

유니크하지않은 세컨더리 인덱스에서 한번 더 해야하는 작업은 디스크 읽기가 아니라 CPU에서 칼럼값을 비교하는 작업이기 떄문에 성능상 영향은 거의 차이가 없습니다.

B. 인덱스 쓰기

새로운 레코드가 INSERT되거나 인덱스 칼럼의 값이 변경되는 경우에 인덱스 쓰기 작업이 필요합니다. 유니크 인덱스의 키 값을 쓸 때는 중복된 값이 있는지 없는지 체크하는 과정이 한 단계 더 필요합니다. 그래서 유니크하지않은 세컨더리 인덱스의 쓰기보다 느립니다.

(2) 유니크 인덱스 사용 시 주의사항

똑같은 칼럼에 대해 프라이머리 키와 유니크 인덱스를 동일하게 생성하는 경우가 있는데, 불필요한 중복이다

유일성이 보장돼야하는 칼럼에 대해서 유니크 인덱스를 생성하되, 필요하지않다면 유니크 인덱스보다 유니크하지않은 세컨더리 인덱스 생성하는 방법 고려해야합니다

10. 외래키

외래키는 InnoDB 스토리지 엔진에서만 생성할 수 있으며, 외래키 제약이 설정되면 자동으로 연관되는 테이블의 칼럼에 인덱스까지 생성됩니다.

• 테이블의 변경이 발생하는 경우에만 잠금 경합이 발생합니다.
• 외래키와 연관되지 않은 칼럼의 변경은 최대한 잠금 경합을 발생시키지않습니다.

(1) 자식 테이블의 변경이 대기하는 경우

자식 테이블의 외래키가 아닌 칼럼의 변경은 외래키로 인한 잠금 확장이 발생하지않습니다.

(2) 부모 테이블의 변경 작업이 대기하는 경우