인덱스

참고

• 쉬운코드 - 유튜브

Index란

• 테이블의 작업을 빠르게 할 수 있도록 도와주는 자료 구조이다.
• 조회나 조건이 붙는 작업을 빠르게 수행할 수 있다.
  • select나 update, delete 뒤에 where 조건이 붙는 경우
  • order by, group by 등
• 만약 100만 개의 튜플이 있는 테이블에서 이름이 ‘보근’인 사람을 찾는다고 할 때,
  • index가 없는 경우에는 100만 개를 full-scan을 한다.
    • 말 그대로 100만 개의 튜플을 다 찾아보면서 너 보근이니? 라고 물어보고 다닌다.
    • O(N)
  • B-tree index를 만든 경우에는 이분 탐색을 해서 시간이 덜 든다.
    • 중간 값을 고르고 ‘보근’과 비교해서 up, down을 골라서 절반을 날리기를 반복한다.
    • O(log N)

Index 만들기

• Book 테이블을 예시로 사용한다.
  • ID (PK)
  • TITLE
  • FLOOR
  • BOOK_CODE (UNIQUE)
• 예시는 전부 mysql 기준으로 작성한다.

CREATE INDEX TITLE_INDEX ON BOOK(title);
CREATE UNIQUE INDEX BOOK_CODE_INDEX ON BOOK(book_code);

• CREATE INDEX [인덱스 이름] ON 테이블(애트리뷰트…);
  • 이런 식으로 만들어줄 수 있다.
• CREATE UNIQUE INDEX [인덱스 이름] ON 테이블(애트리뷰트…);
  • 유니크 인덱스는 이렇게 만든다.
• 유니크 인덱스는 인덱스의 로우값에 중복을 허용하지 않는 인덱스이다.
• UNIQUE 제약 조건이 걸려있거나 PK인 경우, 또 그냥 유니크한 값들만을 갖고 있는 컬럼에만 만들 수 있다.
  • 만약 현재는 유니크한 값들만 들어갔지만, 미래에도 보장이 되지 않는다면 얘로 만들지 않는 것이 좋다.
  • 유니크 인덱스가 만들어진 상태에서 유니크가 깨지는 값이 들어오면 에러가 뜬다.
• 멀티 컬럼 인덱스의 경우 두 값의 합으로 유니크를 따진다.
  • floor가 2이고 title이 ‘바보의 꿈’인 책과
  • floor가 2이지만 title이 ‘바보바보’인 책은
  • floor 값이 같지만 전체적으로 봤을 땐 title 값이 다르기 때문에 유니크하다고 본다.

CREATE TABLE BOOK (
    id INT PRIMARY KEY,
    title VARCHAR(20) NOT NULL,
    floor INT,
    book_code INT UNIQUE,
    INDEX TITLE_INDEX (title),
    UNIQUE INDEX FLOOR_BOOK_CODE_INDEX (floor, book_code)
);

• 테이블 정의 시에도 인덱스를 만들어줄 수가 있다.
• 대부분의 RDBMS는 PK의 인덱스를 자동으로 생성해준다.

인덱스 정보 조회

SHOW INDEX FROM BOOK;

• 테이블에 만들어진 인덱스를 조회하는 명령어이다.

인덱스 조회 결과

• 3번째와 4번째 로우를 보면 똑같은 key_name에 seq_in_index가 각각 1과 2인 것을 볼 수 있다.
• Multi Column Index의 경우 해당하는 컬럼의 하나하나 다 보여준다.

B-tree Index의 동작 방식

INDEX(floor)를 사용한 floor 조건 조회

• 좌측은 Book 테이블, 우측은 floor 컬럼에 대한 인덱스이다.
• 인덱스는 테이블의 floor 컬럼과 ptr 컬럼만을 갖고 있다.
  • ptr 컬럼은 실제 테이블의 튜플에 대한 pointer이다.
• 인덱스는 테이블과 다르게 floor 컬럼에 대해 정렬이 된 것을 볼 수 있다.
  • 이분 탐색을 하기 위함이다.

1. 2층에 위치한 책을 모두 찾기 위한 쿼리를 날렸다고 한다.
   • 빠른 조회를 위해 floor에 대한 인덱스를 사용한다.
2. floor 인덱스의 중간값을 확인한다.
3. 우리가 찾는 값인 2보다 크기 때문에 위로는 모두 찾아볼 필요가 없다.
4. 이 과정을 반복한다.
5. 결국 우리가 찾는 값인 2를 찾아낸다.
6. 바로 위와 바로 아래의 값을 확인해본다.
   • 같은 값이 여러 개 있을 수도 있기 때문에 확인한다.
   • 만약 같은 값이 있다면 그 값의 다음 값도 또 같은면 그 다음 값도 주주죽 확인한다.
   • 같은 값이 없다면 검색을 종료한다.

• 그럼 만약에 조건이 추가가 된다면?

INDEX(floor)를 사용한 floor AND title 조건 조회

1. floor가 6이고 title이 ‘lll’인 책을 찾는다고 한다.
   • floor에 대한 인덱스를 사용한다.
2. 먼저 floor가 6인 애를 먼저 이분 탐색으로 찾는다.
   • 11번째 로우가 6인 것을 발견했다.
3. 11번째 로우의 포인터를 사용해 해당 튜플의 title에 ‘lll’인지 확인한다.
4. 다른 floor가 6인 로우가 있는지 아래부터 확인해본다.
   • floor가 6이기 때문에 해당된다.
5. 로우의 포인터를 사용해 해당 튜플의 title을 확인해본다.
   • ‘lll’이 아니기 때문에 조건에 해당되지 않는다.
6. 12번째 로우 다음은 없기 때문에 이번엔 위의 값들을 검사한다.
   • 10번째 로우는 floor가 5이기 때문에 해당되지 않아 검색을 종료한다.

• floor에 대한 인덱스를 사용했기 때문에 floor를 찾는 검색은 확실히 빠르다.
• 하지만 뒤에 붙는 다른 조건에 대해서는 인덱스를 효과와 상관 없이 하나씩 찾아봐야 한다.
  • 만약 위의 예시에서 총 데이터가 100만개 있었고, 그 중에서 floor가 6인 애가 99만개 였다면
  • floor가 6인 99만개의 데이터를 full-scan 했을 것이다.
  • 그렇다면 인덱스의 효과를 거의 누리지 못한 것이다.

• 위와 같은 상황에서 필요한 적절한 인덱스는 floor와 title에 대한 인덱스이다.

INDEX(floor, title)를 사용한 floor AND title 조건 조회

1. floor가 5이고 title이 ‘ccc’인 튜플을 찾으려고 한다.
   • 이번에는 INDEX(floor, title)을 사용한다.
   • floor가 1번 인자로 들어갔기 때문에 title 기준으로 먼저 정렬 후에 floor를 기준으로 정렬한다.
2. 중간값인 6번째 로우가 floor가 3으로 해당되지 않으므로 위의 애들은 모두 제외한다.
3. 이번에는 중간값인 9번째 로우가 floor가 5이로 해당이 된다.
   • 그러나 title이 eee로 해당되지 않아 제외한다.
   • 문자 정렬순으로 ‘ccc’가 ‘eee’보다 작기 때문에 아래 로우들은 전부 제외한다.
4. 그 다음 중간값인 8번째 로우도 floor가 5이지만, title이 ‘ccc’가 아니기 때문에 제외한다.
   • 8번째 로우의 title이 ‘ddd’로 ‘ccc’보다 뒤에 오기 때문에 더 위의 컬럼을 찾아본다.
5. 다음으로 7번째 로우가 floor도 5이고 title도 ‘ccc’로 조건에 만족한다.
6. 더 위의 로우들은 이미 제외시켰기 때문에 검색이 종료된다.

• 다중 컬럼 인덱스는 우선 순위가 높은 컬럼을 앞에다 기입해서 만들 수 있다.
  • 그 컬럼의 우선 순위에 따라 정렬 우선 순위도 높아지고, 조회에서도 가장 먼저 비교에 사용된다.
• 또 위에서 살펴 봤듯이 조건을 사용하는 검색을 할 때 적절한 인덱스를 사용해야 효과를 볼 수 있다.

• 그럼 모든 컬럼과 모든 조건에 대해 인덱스를 만들면 좋지 않을까?
• 결론부터 말하면 오히려 성능에 안좋을 수 있다.
  • 저장 공간을 너무 많이 잡아먹는다.
  • 저장 성능이 안좋아진다.
    • 테이블에 insert 할 때마다 해당되는 인덱스들에도 전부 데이터 저장 과정이 필요하다.
    • 예를 들어 Book 테이블에 인덱스가 5개 만들어졌다고 하면,
    • Book 테이블에 하나의 로우를 저장하면 인덱스에도 한 번씩 총 6개의 저장 과정이 필요하다.
• 그러니 불필요한 인덱스를 쓸데없이 여러개 만들지 말자.

어떤 인덱스가 사용될까

• 테이블마다 여러개의 인덱스가 존재할 수 있다.
• 그럼 내가 작성한 쿼리가 어떤 인덱스를 사용해서 검색을 할까?
• EXPLAIN 문을 사용해서 알 수 있다.
  • EXPLAIN [쿼리];

EXPLAIN
SELECT * FROM BOOK WHERE floor = 2 AND title = 'ccc';

• 이렇게 사용할 수 있다.

EXPLAIN 문 결과

• possible_keys는 해당 쿼리문이 사용할 수 있는 인덱스들을 알려주고

• key는 실제로 사용하는 인덱스이다.

• 그럼 사용 가능한게 여러개 있다는 건데 저기서 하나 딱 고르는 건 어떻게 할까?
  • 디비의 Optimizer가 그 역할을 수행한다.
  • 위의 예시에서는 데이터가 3개 밖에 없기 때문에 FLOOR_BOOK_CODE_INDEX 인덱스를 사용한다고 나온 거 같다.

사용할 인덱스를 정해줄 수도 있다.

SELECT * FROM BOOK USE INDEX (floor_title_index) WHERE floor = 2 AND title = 'ccc';

• 얘의 경우 USE INDEX(인덱스 이름)으로 살짝 인덱스를 사용하길 권유한다.
• 사용이 가능한 경우에는 쟤를 사용해서 쿼리를 작성한다.

USE INDEX EXPLAIN 문 결과

• 내가 권유한 floor_title_index를 사용한 걸 볼 수 있다.

SELECT * FROM BOOK FORCE INDEX (primary) WHERE floor = 2 AND title = 'ccc';

• 강제로 얘를 사용해! 하는 방법도 있다.
• USE INDEX 대신에 FORCE INDEX를 사용한다.

FORCE INDEX EXPLAIN 문 결과

• floor와 title의 조건 검색을 하는데, 내가 강요한 primary 인덱스를 사용하려 했으나
• 사용할 수 없기 때문에 아무런 인덱스도 사용하지 않은 걸 볼 수 있다.
• 이런 경우 그냥 테이블의 모든 로우를 full-scan 때린다.

Covering Index

• INDEX(floor, title)가 존재한다고 할 때,

SELECT floor, title FROM BOOK WHERE floor = 2;

• 이런 조회 쿼리를 날리면 당연히 위의 인덱스를 사용해 빠르게 조건을 검색할 수 있다.
• 게다가 이 경우는 select 절의 컬럼 floor와 title을 인덱스가 모두 가지고 있다.
  • 조회하는 모든 애트리뷰트를 인덱스가 전부 커버가 가능할 때
  • 이런 인덱스를 Covering Index라고 한다.
• Covering Index의 경우에 검색된 결과를 다시 테이블에 보낼 필요 없이 바로 결과를 반환한다.
  • 이 때문에 조회 성능이 빠르다.
  • 자주 쓰이는 컬럼들을 인덱스로 만들어주면 성능에 이점이 생긴다.

Hash Index

• 해시 테이블을 사용하는 인덱스이다.

• 장
  • 조회가 매우 빠르다. (O(1))
• 단
  • 해시 테이블이 꽉 차서 rehashing 해야하는 경우 오버헤드가 발생한다.
  • 같은 값을 찾는 것은 매우 빠르지만, 범위 조회는 불가능하다.
  • 멀티 컬럼 인덱스의 경우 사용성이 상대적으로 떨어진다.
    • 앞에서 살펴본 B-tree의 경우 INDEX(floor, title)는 floor만 조건 검색이 들어와도 사용이 가능했다.
    • 해시 인덱스의 경우는 해시 테이블을 사용하기 때문에 전체 애트리뷰트(여기선 floor, title)에 대한 조회에만 사용이 가능하다.