11주차 이론. Indexing Structure

1. Index와 관련한 자료구조

1) Sequential Data Structure

Sequential Data Structure에는 대표적으로 Array와 List가 있다. Array는 간단하지만 크기가 고정되어있다는 것이 단점이고, List는 다소 복잡하지만 크기가 동적으로 변할 수 있다는 것이 장점이다. 이러한 Sequential Data Structure는 B+ Tree의 Sequential part에서 사용된다.

2) Hierarchical Data Structure

Hierarchical Data Structure에는 대표적으로 Tree가 있다. Tree Terminology 중에서 degree는 자식 노드의 개수를 의미한다. 이 degree의 값에 따라 Tree의 형태와 효율성이 달라진다.

• degree = 2 → Binary Tree
• degree = 1 → Singly Linked List
• degree가 매우 큰 경우 → Array

Hierarchical Data Structure는 Select Query에서 값을 조회할 때, Binary Search Tree의 형태로 사용된다. Binary Search Tree란, Binary Tree에 key(u) ≤ key(v) ≤ key(w) 조건을 적용한 것을 말한다.

Query는 Exact macth query와 Range query로 구분되는데, Binary Tree 구조에서는 이 두 가지의 쿼리를 모두 처리할 수 있다. 이 때의 시간 복잡도는 O(log n)이 된다.

물론 탐색 과정에 대해 더 깊게 알아보려면, Binary Tree에서 파생된 B-Tree, B* Tree, B+ Tree에 대해 알아야 한다. 그러나 이번 포스팅의 내용은, 탐색에 있어 Binary Tree와 Hash가 어떻게 다른지만 알 수 있으면 충분하므로 위 내용은 생략하기로 한다.

3) Hash

O(log n)의 시간 복잡도를 갖는 Binary Tree와 달리 Hash를 이용하면 O(1) 시간 만에 탐색이 가능하다. 단, Range query는 처리할 수 없고, 오직 Exact query만을 처리할 수 있다. 따라서, Exact Query Only 상황에서는 Hash를 사용하고, Exact Query와 Range Query가 함께 사용되는 상황에서는 B Tree를 사용하는 것이 적합하다.

그러나 인덱스의 자료구조로 Hash 테이블을 사용하는 경우는 많지 않다. 그 이유는 Select 연산이 일반적으로 Exact Query보다 Range query의 형태로 더 빈번하게 사용되기 때문이다.

2. Index

1) 개념

인덱스는 테이블 데이터에 대한 조회 속도를 높여주는 일종의 자료구조이다. 이는 두꺼운 책에서 특정 부분을 찾아야 할 때, 목차를 확인함으로써 Full Scan보다 더 빠르게 원하는 내용을 찾을 수 있는 것과 동일한 원리이다.

Index를 적용하면, Select 연산의 처리속도가 높아지는 대신 Update, Insert, Delete 연산의 처리속도는 느려지게 된다. 이는 Index에 대한 갱신 연산이 오버헤드로 작용하기 때문이다. 따라서 가급적 변경될 여지가 적은 Column에 대해 Index를 사용하는 것이 좋다.

이에 대한 이해를 돕기 위해 책에 새로운 내용이 추가, 삭제, 변경되는 경우를 생각해보자. 이 경우, 책의 내용을 update 함과 동시에 목차도 함께 수정해주어야 한다. 즉, 목차를 적용하면 책에서 원하는 정보를 더 빠르게 찾을 수 있게 되지만, insert, update, delete는 더 느려지게 된다.

가끔 인덱스에 대해 잘못 알고 있는 경우가 있는데, 인덱스로 인해 향상되는 속도는 인덱싱 된 필드를 조회하는 속도가 아니라, where 절에 해당하는 행을 찾는 속도이다. 즉, where 절이 사용되지 않는 select 문에서는 인덱스가 그저 오버헤드에 불과한 것이다.

// ssn에 index를 적용하는 것이 아니라, name에 index를 적용해야 한다.
select ssn from employee where name='Alex';

2) Single Column Index와 Multiple Column Index의 비교

인덱스는 하나 혹은 여러 개의 컬럼에 대해 적용할 수 있다. 이 때, 하나의 컬럼에 대해 적용한 인덱스를 Single Column Index, 다중 컬럼에 대해 적용한 인덱스를 Multiple Column Index라 한다. 그러면 여기서 한 가지 의문이 생길 수 있다.

사원 테이블에서 name 필드와 address 필드에 대해 인덱스를 적용하는 상황을 생각해보자. 이 때, name과 address에 대해 각각을 Single Column Index로 등록하는 것과 name, address를 하나로 묶어 Multiple Column Index로 등록하는 것에는 어떤 차이가 있을까?

select * from Employee where name='Chrome' and address='Incheon'; 

단일 컬럼 인덱스가 적용된 Employee 테이블에서 위 쿼리를 실행한다고 하자. name과 address 모두 Index가 적용되어 있기 때문에 DBMS(MySQL)는 먼저 name 컬럼과 address 컬럼을 이용한 select 쿼리를 optimize 한다. 이 때, 두 개의 조건 중에서 Selectivity(Cardinality)가 더 높은 조건을 선택해 먼저 수행하고 이후에 다른 조건을 수행한다. 그리고 이 과정에서 Index가 사용된다.

※ Selectivity
Selectivity = Cardinality / Total Number of Records로 정의된다. 여기서 Cardinality는 특정 Column에 존재하는 고유한 값들의 개수를 의미한다. 즉, Selectivity가 1에 가까워질수록 컬럼에 대해 다양한 unique 값이 존재한다는 것이고, select 쿼리가 실행되었을 때 적은 행을 선택하게 된다는 것이다. 따라서, Selectivity 또는 Cardinality가 높을수록 Index의 효용성이 높아지며, Query Optimizer에 의해 먼저 수행된다.

하지만, 다중 컬럼 인덱스가 적용된 Employee 테이블에서 위 쿼리를 실행할 경우, name과 address 조건을 한번에 이용하여 검색을 시도한다. 당연히 위 쿼리의 경우 다중 컬럼 인덱스를 적용한 테이블에서 더 빠르게 검색된다. 하지만, 아래의 쿼리를 실행하는 경우 이야기가 달라진다.

select * from Employee where address='Incheon'; 

다중 컬럼 인덱스가 적용된 Employee 테이블에서는 위 쿼리를 실행할 때 Index의 효과가 전혀 나타나지 않는다. 한 가지 재밌는 사실은 아래의 쿼리에 대해서는 다중 컬럼 인덱스가 적용된 테이블에서도 Index의 효과가 나타난다는 것이다.

select * from Employee where name='Chrome'; 

위와 같이 다중 컬럼 인덱스가 적용된 순서에 맞게 where 절을 작성하면, 단일 컬럼에 대한 조건이더라도 Index의 효과를 볼 수 있다. 한 가지 예를 더 들어보자면, {name, address, age}를 다중 컬럼 인덱스로 설정했을 때, name, address 순으로 where 절을 작성하면 Index가 적용되지만, name, age 순으로 where 절을 작성하면 Index가 적용되지 않는다. 즉, 다중 컬럼 인덱스를 사용할 때에는 Index를 적용한 순서에 맞추어 where 절을 사용해야 한다.

3) 사용법

① 인덱스 생성

// Single Column Index
CREATE INDEX {인덱스명} ON {테이블명}({필드명}1);

// Multiple Column Index
CREATE INDEX {인덱스명} ON {테이블명}({필드명1}, {필드명2}, ...);

② 인덱스 조회

SHOW INDEX FROM {테이블명};

③ 인덱스 삭제

DROP INDEX {인덱스 명} ON {테이블 명};

4) Index의 효율을 높이는 방법

① Selectivity 및 Cardinality가 높은 Column에 적용한다.

• 즉, Unique한 값 위주로 적용하는 것이 유리하다.
• primary key와 unique key에 자동으로 Index가 생성되는 이유이기도 하다.

② 조회에 자주 사용될만한 Column에 적용한다.

③ 변경될 여지가 적은 Column에 적용한다.

④ Single Column Index를 여러 개 사용하는 것보다, 신중하게 고려된 Multiple Column Index의 효율이 더 높다.

⑤ Index를 너무 많이 사용하는 것은 오히려 연산의 속도를 늦출 수 있다.

⑥ Join 연산이 필요한 쿼리에는 필수적으로 Index를 적용해야 한다.

• 외래키에 자동으로 Index가 적용되는 이유이기도 하다.
• Join 연산이 사용되는 각 테이블의 Column을 Single Column Index로 지정한다.

create index m1_index on m1(id);
create index m2_index on m2(id);
explain select * from m1, m2 where m1.id=m2.id;

3. MySQL Explain

1) 개념

Explain은 MySQL에서 쿼리 실행 계획을 분석하고 최적화하는 데 도움을 주는 명령문이다. Explain을 사용하면 쿼리를 어떻게 실행할지에 대한 Query Execution Plan을 확인할 수 있으며, 이를 통해 쿼리의 성능을 향상시키는 데 도움을 얻을 수 있다. 사용방법은 실행하고자 하는 쿼리의 앞에 Explain을 붙여주기만 하면 된다.

Query Execution Plan에 포함되는 정보는 아래와 같다.

① id

• 쿼리 내에서 각 쿼리 블록에 할당된 숫자이다.
• 서브쿼리의 경우 서브쿼리의 id를 나타낸다.

② select_type

• 쿼리의 종류를 나타낸다.
• SIMPLE SELECT, UNION, SUBQUERY 등이 있다.

③ table

• 사용된 테이블의 이름이다.

④ type

• 쿼리의 타입을 나타낸다.
• type의 종류는 아래와 같으며, 아래로 내려갈수록 성능이 낮아진다.
  

⑤ possible_keys

• 인덱스 중에서 선택될 수 있는 인덱스들의 목록이다.
• 필드명을 possible_indexes로 받아들이는 편이 낫다.

⑥ key

• 실제로 선택된 인덱스이다.
• 필드명을 index로 받아들이는 편이 낫다.

⑦ key_len

• 인덱스에서 실제로 사용되는 바이트 수이다.
• key의 길이가 짧을수록 연산 속도가 빠르다.

⑧ ref

• key column에 지정된 인덱스(사용된 인덱스)와 비교되는 column 또는 constants를 나타낸다.

⑨ rows

• 쿼리에서 검색해야 할 것으로 예측되는 행의 수이다.

⑩ filtered

• 전체 row 중 조건에 의해 필터링 될(조건을 만족하는) row의 예상 비율이다.
• filtered 값이 100에 가깝다는 것은 필터링이 전혀 안되고 있다는 뜻이다.
• filtered가 100인 조건에 해당하는 Column에 Index를 적용하는 것은 효율적이지 않다.

⑪ Extra

• 추가적인 정보를 제공하며, Using filesort, Using temporary, Using index 등의 정보가 나타날 수 있다.