[BOOK] 인덱스, 조인의 종류, 조인의 원리

 

• 인덱스
  • 데이터를 빠르게 찾을 수 있는 하나의 장치
  • 인덱스를 설정하면 테이블 안에 내가 찾고자 하는 데이터를 빠르게 찾을 수 있다.
  • ex) 책의 마지막 장에 있는 찾아보기

 

• B-트리
  • 인덱스는 보통 B-트리라는 자료 구조로 이루어져 있다.
  • 루트 노드, 리프 노드, 브랜치 노드(루트 노드와 리프 노드 사이에 있는)
  • 인덱스가 효율적인 이유
    • 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문
  • 대수 확장성
    • 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것
    • 기본적으로는 인덱스가 한 깊이씩 증가할 때마다 최대 인덱스 항목의 수는 4배씩 증가한다.

 

• 인덱스 만드는 방법
  • MySQL
    • 클러스터형 인덱스와 세컨더리 인덱스가 있다.
    • 클러스터형 인덱스
      • 테이블당 하나를 설정할 수 있다.
      • primary key 옵션으로 기본키로 만들면 클러스터형 인덱스를 생성할 수 있다.
      • 기본키로 만들지 않고 unique not null 옵션을 붙이면 클러스형 인덱스로 만들 수 있다.
      • age라는 하나의 필드만으로 쿼리를 보낸다면 클러스터형 인덱스 필요
    • 세컨더리 인덱스
      • create index... 명령어를 기반으로 만들면 세컨더리 인덱스를 만들 수 있다.
      • 보조 인덱스로 여러 개의 필드 값을 기반으로 쿼리를 많이 보낼 때 생성해야 하는 인덱스
        • age, name, email 등 다양한 필드를 기반으로 쿼리를 보낼 때는 세컨더리 인덱스 필요
    • 하나의 인덱스만 생성할 것이라면 클러스터형 인덱스를 만드는 것이 세컨더리 인덱스보다 성능이 더 좋다.
  • MongoDB
    • 도큐먼트를 만들면 자동으로 ObjectID가 형성되며, 해당 키가 기본키로 설정 됨.
    • 세컨더리키도 부가적으로 설정해서 기본키와 세컨더리키를 같이 쓰는 복합 인덱스를 설정할 수 있다.

 

• 인덱스 최적화 기법
  • 인덱스는 비용이다
    • 인덱스는 두 번 탐색하도록 강요한다.
      인덱스 리스트, 그다음 컬렉션 순으로 탐색하기 때문이며, 관련 읽기 비용이 들게 된다.
    • 컬렉션이 수정되었을 때 인덱스도 수정되어야 한다.
      이때 B-트리의 높이를 균형 있게 조절하는 비용도 들고, 데이터를 효율적으로 조회할 수 있도록 분산시키는 비용도 들게 됨.
    • 쿼리에 있는 필드에 인덱스를 무작정 다 설정하는 것은 답이 아님.
      또한, 컬렉션에서 가져와야 하는 양이 많을수록 인덱스를 사용하는 것은 비효율적이다.
  • 항상 테스팅해야 한다.
    • 인덱스 최적화 기법은 서비스 특징에 따라 달라진다.
      (서비스에서 사용하는 객체의 깊이, 테이블의 양 등이 다르기 때문)
    • 그렇기에 항상 테스팅하는 것이 중요하다.
  • 복합 인덱스는 같음, 정렬, 다중 값, 카디널리티 순이다.
    • 보통 여러 필드를 기반으로 조회를 할 때 복합 인덱스를 생성하는데,
      이 인덱스를 생성할 때는 순서가 있고 생성 순서에 따라 인덱스 성능이 달라진다.
      1. 어떠한 값과 같음을 비교하는 ==이나 equal이라는 쿼리가 있다면 제일 먼저 인덱스로 설정한다.
      2. 정렬에 쓰는 필드라면 그다음 인덱스로 설정한다.
      3. 다중 값을 출력해야 하는 필드, 즉 쿼리 자체가 > 이거나 < 등 많은 값을 출력해야 하는 쿼리에 쓰는 필드라면 나중에 인덱스를 설정한다.
      4. 유니크한 값의 정도를 카디널리티라고 한다.
         이 카디널리티가 높은 순서를 기반으로 인덱스를 생성해야 한다.
         ex) age와 email 중 email이 카디널리티가 더 높으므로 email이라는 필드에 대한 인덱스를 먼저 생성.

---

 

• 조인의 종류
  • 조인(join) : 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것
  • MySQL에서는 JOIN이라는 쿼리, MongoDB에서는 lookup이라는 쿼리로 처리한다.
    • MongoDB는 조인 연산(lookup)에 대해 관계형 데이터베이스보다 성능이 떨어진다고 여러 벤치마크 테스트에서 알려져 있다.
      따라서 여러 테이블을 조인하는 작업이 많을 경우 MongoDB보다는 관계형 데이터베이스를 써야 한다.

 

• 내부 조인 : 두 테이블 간에 교집합
• 왼쪽 조인
  • 테이블 B의 일치하는 부분의 레코드와 함께 테이블 A를 기준으로 완전한 레코드 집합 생성
    테이블 B에 일치하는 항목이 없으면 해당 값은 null값이 된다.

 

• 오른쪽 조인
  • 테이블 A에 일치하는 부분의 레코드와 함께 테이블 B를 기준으로 완전한 레코드 집합 생성
    테이블 A에 일치하는 항목이 없으면 해당 값은 null값이 된다.

 

• 합집합 조인
  • 양쪽 테이블에서 일치하는 레코드와 함께 테이블 A와 테이블 B의 모든 레코드 집합 생성
    일치하는 항목이 없으면 누락된 쪽에 null값이 포함되어 출력된다.

---

 

• 중첩 루프 조인(NLJ, Nested Loop join)
  • 중첩 for 문과 같은 원리로 조건에 맞는 조인을 하는 방법
  • 랜덤 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 사용하지 않는다.
  • 블록 중첩 루프 조인(BNL, Block Nested Loop) : 작은 블록으로 나눠서 블록 하나씩 조인하는 방식

 

• 정렬 병합 조인
  • 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 이후에 조인 작업을 수행
  • 적절한 인덱스가 없고 대용량의 테이블들을 조인하고 조인 조건으로 <, > 등 범위 비교 연산자가 있을 때 쓴다.

 

• 해시 조인
  • 해시 테이블을 기반으로 조인하는 방법
  • 두 개의 테이블을 조인한다고 했을 때 하나의 테이블이 메모리에 온전히 들어간다면 보통 중첩 루프 조인보다 더 효율적이다.(메모리에 올릴 수 없을 정도로 크다면 디스크를 사용하는 비용 발생)
  • 동등(=) 조인에서만 사용할 수 있다.
  • MySQL의 해시 조인 단계
    • 빌드 단계
      • 입력 테이블 중 하나를 기반으로 메모리 내 해시 테이블을 빌드하는 단계
      • 바이트가 더 작은 테이블을 기반으로 테이블 빌드
    • 프로브 단계
      • 프로브 단계 동안 레코드를 읽기 시작
      • 각 레코드에서 일치하는 레코드를 찾아 결괏값으로 반환
      • 이를 통해 각 테이블은 한 번씩만 읽게 되어 중첩해서 두 개의 테이블을 읽는 중첩 루프 조인보다 보통 성능이 좋음.

 

---

출처 : 면접을 위한 CS 전공지식 노트