MySQL(5)

오늘 배운 것

#

8.3.6 B-Tree 인덱스의 정렬 및 스캔 방향

인덱스를 생성할때 설정한 정렬규칙에 따라서 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 저장된다. 하지만, 읽는 순서에따라 오름차순을 내림차순으로 그 반대도 가능하다. 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어내는 실행계획에 따라 결정된다.

8.3.6.1 인덱스의 정렬

5.7버전까지는 칼럼단위로 정렬순서를 혼합(ASC, DESC 혼합)해서 인덱스를 생성할 수 없었다. (문법 자체는 지원하는데, 앞으로 나올 버전 호환성을 위해 쓸수있게만 하고 동작 자체는 오름차순으로만 정렬됨) 8.0부터는 가능해졌다.

8.3.6.1.1 인덱스 스캔 방향
SELECT *
FROM employees
ORDER BY first_name DESC
LIMIT 1;

MySQL은 이 쿼리를 실행하기위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 first_name이 가장 큰(오름차순으로 읽었을때 가장 마지막 레코드) 값 하나를 가져오는걸까?

-> 아니다. 인덱스는 항상 오름차순으로만 정렬되어 있으나, 인덱스를 최솟값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최댓값부터 거꾸로 읽으면 내림차순으로 가져올수있다는걸 옵티마이저는 알고있다. 그래서 위의 쿼리는 인덱스를 역순으로 접근해 첫번째 레코드만 읽는다.

인덱스스캔방향

8.3.6.1.2 내림차순 인덱스

앞서 인덱스 정렬상태와 관계 없이 옵티마이저가 읽는 순서를 다르게 하여 최적화 하는걸 봤다.

2개이상의 칼럼으로 구성된 복합 인덱스에서 각각의 칼럼이 DESC, ASC 인 경우에는 8.0의 내림차순 인덱스 로만 해결될 수 있다.

그렇다면 first_name칼럼을 역순으로 정렬하는 요건만 있다면, 다음 2개 인덱스중에서 뭘 하는게 좋을까.

CREATE INDEX ix_firstname_asc ON employees(first_name ASC);
CREATE INDEX ix_firstname_DESC ON employees(first_name DESC);

책에선 실제 돌려보고 다음과 같이 결과가 나왔다.

SELECT .. ORDER BY ASC
SELECT .. ORDER BY DESC

전자 : 4.15초 후자 : 5.35초

언뜻보면 정순으로 읽느냐 역순으로 읽느냐 차이가 없어보이지만, 차이가 발생했다. 페이지 간의 양방향 연결고리를 통해 전진, 후진하느냐 차이가 있지만, 실제 InnoDB에서 역순이 정순에 비해 느릴 수 밖에 없는 2가지 이유가 있다.

  1. 페이지 락이 정순에 적합한 구조
  2. 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

ㅇㄴㄹ

그림에서는 페이지 내부에서 레코듣르이 정렬 순서대로 저장되어 있는거 처럼 보이지만, 실제로 페이지는 `힙` 처럼 사용되기 때문에 (트리 말고 스택 힙 이런거) 물리적으로 저장이 순서대로 배치되지는 않는다. 그리고 각 데이터 페이지(InnoDB에서 데이터 파일은 프라이머리 인덱스 자체)나 인덱스 페이지의 엔트리(데이터 레코드 또는 인덱스 키)는 키 값과 데이터를 가지는데, 인덱스(Pk, Secondry 모두) 의 루트노드 또는 브랜치 노드라면 자식 노드의 주소를 가진다. PK에서 리프노드의 `데이터` 는 실제 레코드의 칼럼 값들이며 세컨더리 인덱스에서는 PK값을 가진다.

그래서 다음과 같은 쿼리


SELECT * FROM table
WHERE userid=?
ORDER BY score DESC
LIMIT 10

이건

INDEX (userid ASC, score ASC)
INDEX (userid DESC, score DESC)

전자( 오름차순 인덱스)보다 후자(내림차순 인덱스)가 굳이 따지면 적합하다.

InnoDB 페이지 내부 정순/역순 순회 최종 분석 (소스 코드 기반)

InnoDB의 데이터 페이지 내 레코드들은 물리적으로는 정렬되지 않은 힙(Heap) 구조로 저장되지만, 논리적으로는 프라이머리 키(PK) 순서의 연결 리스트를 형성합니다. 이때 정순 순회와 역순 순회는 서로 다른 메커니즘으로 동작하며, 이는 실제 소스 코드를 통해 명확히 증명됩니다.

1. 정순 순회 (Forward Scan) - 단순 포인터 직접 추적

정방향 순회는 각 레코드 헤더에 명시적으로 존재하는 ‘다음 레코드’ 포인터를 따라가는, 매우 단순하고 빠른 작업입니다.

  • 핵심 원리: next_record 포인터를 순차적으로 따라 이동합니다.
  • 코드 증거: page0cur.ic 파일은 정순 이동이 page_rec_get_next 함수를 직접 호출하는 한 줄짜리 작업임을 보여줍니다.
/** Moves the cursor to the next record on page. */
static inline void page_cur_move_to_next(
    page_cur_t *cur) /*!< in/out: cursor; must not be after last */
{
  ut_ad(!page_cur_is_after_last(cur));

  cur->rec = page_rec_get_next(cur->rec);
}

2. 역순 순회 (Backward Scan) - 페이지 디렉터리 기반 알고리즘

역방향 순회는 별도의 prev_record 포인터 없이, 페이지 디렉터리와 next_record 포인터를 조합한 정교한 알고리즘을 통해 수행됩니다.

  • 핵심 원리: 페이지 디렉터리로 탐색 범위를 좁힌 후, 그 안에서 짧은 정방향 스캔을 통해 이전 레코드를 찾아냅니다.

  • 코드 증거 (함수 호출 경로): ORDER BY ... DESC 쿼리 시, 코드는 다음과 같은 경로로 호출됩니다.

    1. btr0pcur.cc - 역방향 탐색 시작 btr_pcur_t::move_to_prev 함수가 페이지 내부 이동이 필요하다고 판단하면 move_to_prev_on_page를 호출합니다.

      // btr0pcur.cc
  bool btr_pcur_t::move_to_prev(mtr_t *mtr) {
    // ...
    if (is_before_first_on_page()) {
      // ... 이전 페이지로 이동 ...
    } else {
      move_to_prev_on_page(); // 페이지 내부 이동 호출
    }
    return (true);
  }

    2. btr0pcur.h - 페이지 커서에 작업 위임 move_to_prev_on_page 함수는 실제 작업을 더 저수준의 page_cur_move_to_prev 함수에게 위임합니다.

      // btr0pcur.h (또는 .ic)
  inline void btr_pcur_t::move_to_prev_on_page() {
    page_cur_move_to_prev(get_page_cur());
  }

    3. page0cur.ic - 레코드 함수에 작업 위임 page_cur_move_to_prev 함수는 최종적으로 레코드 레벨의 page_rec_get_prev 함수를 호출합니다.

      // page0cur.ic
  static inline void page_cur_move_to_prev(page_cur_t *cur) {
    cur->rec = page_rec_get_prev(cur->rec);
  }

    4. page0page.ic - 실제 알고리즘 구현체 page_rec_get_prev 함수 내부에 우리가 찾던 바로 그 알고리즘이 구현되어 있습니다.

      // page0page.ic
  static inline const rec_t *page_rec_get_prev_const(const rec_t *rec) {
    const page_dir_slot_t *slot;
    ulint slot_no;
    const rec_t *rec2;
    const rec_t *prev_rec = nullptr;
    // ...
      
    // 1. 현재 레코드의 소속 디렉터리 슬롯을 찾는다.
    slot_no = page_dir_find_owner_slot(rec);

    // 2. 그 이전 슬롯을 가져온다.
    slot = page_dir_get_nth_slot(page, slot_no - 1);

    // 3. 이전 슬롯이 가리키는 레코드를 탐색 시작점으로 삼는다.
    rec2 = page_dir_slot_get_rec(slot);

    // 4. 시작점부터 next 포인터를 따라가며 원래 레코드(rec)의 직전 레코드를 찾는다.
    while (rec != rec2) {
      prev_rec = rec2;
      rec2 = page_rec_get_next_low(rec2, true);
    }

    return (prev_rec);
  }

요약 및 트레이드오프

구분 정순 순회 (Forward Scan) 역순 순회 (Backward Scan)
핵심 원리 next 포인터 직접 추적 페이지 디렉터리 + next 포인터 조합 알고리즘
성능 가장 빠름 (단순 포인터 참조 1회) 매우 빠르지만, 알고리즘 수행으로 인한 미세한 오버헤드 존재
공간 효율성 - prev 포인터를 저장하지 않아 모든 레코드의 공간 절약

결론적으로 InnoDB는 모든 레코드에 prev 포인터를 추가하는 공간적 비용을 지불하는 대신, 페이지 디렉터리를 활용한 영리한 알고리즘으로 약간의 CPU 연산을 통해 효율적인 역방향 스캔을 구현하는 설계를 채택했습니다.

8.3.7 B-Tree 인덱스의 가용성화 효율성

쿼리의 WHERE조건이나 GROUPBY, ORDERBY 쩔이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 한다. 그래야만 쿼리의 조건을 최적화 하거나 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있다.

8.3.7.1 비교 조건의 종류와 효율성

다중 칼럼 인덱스 에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 =인지 >, < 같은 범위조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라지며, 그 효율도 달라진다.

SELECT * FROM dept_emp
WHERE dept_no='d002' AND emp_no >= 10114;

이 쿼리를 위해 dept_emp테이블에 두가지 케이스로 인덱스롤 생성했다고 가정하자.

  • A: INDEX(dept_no, emp_no)
  • B: INDEX(emp_no, dept_no)

sdf

A는 처음에 시작점을 찾고 dept_no가 달라질때까지 쭉 읽으면 된다. 조건 만족하는 레코드가 n개라면, n번의 비교작업만 수행한다.

B는 emp범위 탐색을 수행하고, 이후 검색한 모든 레코드에 대해 d002인지 비교해야 한다.

이처럼 인덱스를 통해 읽은 레코드가 조건에 맞는지 비교하면서 취사선택하는 작업을 ‘필터링’ 이라고도 한다. B에서는 레코드 5건을 위해 7번의 비교과정을 거친다.

왜 이런 일이 생겼을까?

다중 칼럼 인덱스의 정렬방식 때문에, A에서 2번째 칼럼은 비교작업의 범위를 좁히는데 도움을 준다. 그러나 B에서 2번째 칼럼은 비교 작업의 범위를 좁히는데 도움을 주지 못한다.

8.3.7.2 인덱스의 가용성

BTree 인덱스의 특징은 왼쪽 값에 기준해서(Left-Most) 오른쪽 값이 정렬돼 있다는 것이다. 여기서 왼쪽이란 하나의 칼럼 뿐만 아니라 다중칼럼 인덱스의 칼럼에 대해서도 함께 적용된다.

ㄴㅇㄹ

  • A: INDEX(first_name)
  • B: INDEX(dept_no, emp_no)

A로 이런 쿼리를 처리한다고 하자.

SELECT * FROM EMPLOYEES
WHERE first_name LIKE '%mer';

이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다.

first_name칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 레코드를 찾아야 하는데, 조건절에는 왼쪽값이 고정되있지 않기 때문이다.

그럼 B는?

SELECT * FROM dept_emp
WHERE emp_no>=10144;

인덱스가 (dept_no, emp_no) 칼럼 순서대로 생성돼 있다면 선행칼럼 없이 emp_no로만 검색하면 인덱스를 효율적으로 사용할 수 없다. 다중칼럼 인덱스에서는 선행칼럼으로 정렬되어있고 그 다음에 정렬되어잇기 때문이다.

WHERE만 언급했지만, GROUPBY나 ORDERBY절에도 똑같이 적용된다.

8.3.7.3 가용성과 효율성 판단

기본적으로 BTree 인덱스는 다음 조건에서 사용할 수 없다.

사용할 수 없다의 의미는 작업 범위 결정조건으로 사용 못한다는 뜻. 경우에 따라서는 체크 조건으로 사용할 수는 있다.

  1. NOT-EQUAL로 비교된 경우
  2. LIKE %?? 형태로 문자열 패턴이 비교된 경우
  3. 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
  4. NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
  5. 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교 가능한 경우)
  6. 문자열 데이터 타입의 콜레이션이 다른 경우

MYSQL에서는 null도 인덱스에 저장된다.

8.4 R-Tree 인덱스

MySQL의 공간 인덱스(Spatial Index)와 관련있다. 공간 인덱스는 RTree 인덱스 알고리즘을 사용해 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스다. BTree와 비슷한데, 그게 1차원이면 이건 2차원이다.

8.4.1 R-tree 구조 및 특성

여러 기하학적 도형 정보를 관리할 수 있는 데이터 타입을 제공한다.

  1. POINT, LINE, POLYGON, GEOMETRY

GEOMETRY는 나머지 3개의 super 타입이다.

MBR? Minimum Bounding Rectangle 해당 도형을 감싸는 최소크기의 사각형

책에 더 긴 내용

8.4.2 R-Tree 인덱스의 용도

RTree는 MBR정보를 이용해 BTree형태로 인덱스를 구축한다.

results matching ""

    No results matching ""