공부

데이터를 찾는 두 가지 방법

어떤 초등학교를 방문해 '홍길동' 학생을 찾는 방법은 두 가지다. 첫째는, 1학년 1반부터 6학년 맨 마지막 반까지 모든 교실을 돌며 홍길동 학생을 찾는 것이다. 둘째는, 교무실에서 학생 명부를 조회해 홍길동 학생이 있는 교실만 찾아가는 것이다. 둘 중 어느 쪽이 빠를까? 홍길동 학생이 많다면 전자가 빠르고, 몇 안되면 후자가 빠르다.

데이터베이스 테이블에서 데이터를 찾는 방법도 아래 두 가지다. 수십 년에 걸쳐 DBMS가 발전해 왔는데도 이 두 방법에서 크게 벗어나지 못하고 있다.

• 테이블 전체를 스캔한다.
• 인덱스를 이용한다.

인덱스 튜닝의 두 가지 핵심요소

인덱스는 큰 테이블에서 소량 데이터를 검색할 때 사용한다. 온라인 트랜잭션 처리 시스템에서는 소량 데이터를 주로 검색하므로 인덱스 튜닝이 무엇보다 중요하다. 

세부적인 인덱스 튜닝 방법으로 여러 가지가 있지만, 핵심요소는 크게 두 가지로 나뉜다. 첫번째는 인덱스 스캔 과정에서 발생하는 비효율을 줄이는 것이다. 즉 '인덱스 스캔 효율화 튜닝'이다.

예를 들어, 학생명부에서 키가 170cm ~ 173cm인 홍길동 학생을 찾는 경우로 예를 들어보자. 학생명부를 이름과 키순으로 정렬해 두었다면, 소량만 스캔하면 된다.

반면, 학생명부를 시력과 이름순으로 정렬해 두었다면, 똑같이 두 명을 찾는데도 많은 양을 스캔해야 한다.

인덱스 튜닝의 두 번째 핵심요소는 테이블 액세스 횟수를 줄이는 것이다. 인덱스 스캔 후 테이블 레코드를 액세스할 때 랜덤 I/O 방식을 사용하므로 이를 '랜덤 액세스 최소화 튜닝'이라고 한다.

인덱스 스캔 효율화 튜닝과 랜덤 액세스 최소화 튜닝 둘 다  중요하지만, 더 중요한 하나를 고른다면 랜덤 액세스 최소화 튜닝이다. 성능에 미치는 영향이 크기 때문이다. SQL 튜닝은 랜덤 I/O와의 전쟁이다.

인덱스 구조

인덱스는 대용량 테이블에서 필요한 데이터만 빠르게 효율적으로 액세스하기 위해 사용하는 오브젝트다. 모든 책 뒤쪽에 있는 색인과 같은 역할을 한다. 데이터베스에서 인덱스 없이 데이터를 검색하려면, 테이블을 처음부터 끝까지 모두 읽어야 한다. 반면, 인덱스를 이용하면 일부만 읽고 멈출 수 있다. 즉, 범위 스캔(Range Scan)이 가능하다. 범위 스캔이 가능한 이유는 인덱스가 정렬돼 있기 때문이다. 

DBMS는 일반적으로 B*Tree 인덱스를 사용한다. 나무(Tree)를 거꾸로 뒤집은 모양이여서 뿌리(Root)가 위쪽에 있고, 가지(Branch)를 거쳐 맨 아래에 잎사귀(Leaf)가 있다.

루트와 브랜치 블록에 있는 각 레코드는 하위 블록에 대한 주소값을 갖는다. 키값은 하위 블록에 저장된 키값의 범위를 나타낸다. 

• ROWID = 데이터 블록 주소 + 로우 번호
• 데이터 블록 주소 = 데이터 파일 번호 + 블록 번호
• 블록 번호 : 데이터파일 내에서 부여한 상대적  순번
• 로우 번호 : 블록 내 순번 

인덱스 탐색 과정은 수직적 탐색과 수평적 탐색으로 나눌 수 있다.

• 수직적 탐색 : 인덱스 스캔 시작지점을 찾는 과정
• 수평적 탐색 : 데이터를 찾는 과정

인덱스 수직적 탐색 

정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정이다. 즉, 인덱스 스캔 시작지점을 찾는 과정이다.

인덱스 수직적 탐색은 루트(Root) 블록에서부터 시작한다. 루트를 포함해 브랜치(Branch) 블록에 저장된 각 인덱스 레코드는 하위 블록에 대한 주소값을 갖는다. 루트에서 시작해 리프(Leaf) 블록까지 수직적 탐색이 가능한 이유다.

수직적 탐색 과정에 찾고자 하는 값보다 크거나 같은 값을 만나면, 바로 직전 레코드가 가리키는 하위 블록으로 이동한다.

수직적 탐색은 '조건을 만족하는 레코드'를 찾는 과정이 아니라 '조건을 만족하는 첫 번째 레코드'를 찾는 과정임을 반드시 기억해야 한다.

인덱스 수평적 탐색

수직적 탐색을 통해 스캔 시작점을 찾았으면, 찾고자 하는 데이터가 더 안 나타날 때까지 인덱스 리프 블록을 수평적으로 스캔한다. 인덱스에서 본격적으로 데이터를 찾는 과정이다.

인덱스 리프 블록끼리는 서로 앞뒤 블록에 대한 주소값을 갖는다. 즉, 양방향 연결 리스트(double linked list) 구조다. 좌에서 우로, 또는 우에서 좌로 수평적 탐색이 가능한 이유다. 

인덱스를 수평적으로 탐색하는 이유는 첫째, 조건절을 만족하는 데이터를 모두 찾기 위해서고 둘째, ROWID를 얻기 위해서다. 

Direct Path I/O를 제외한 모든 블록 I/O는 메모리 버퍼캐시를 경유한다. 

• 인덱스 루트 블록을 읽을 때
• 인덱스 루트 블록에서 얻은 주소 정보로 브랜치 블록을 읽을 때
• 인덱스 브랜치 블록에서 얻은 주소 정보로 리프 블록을 읽을 때
• 인덱스 리프 블록에서 얻은 주소 정보로 테이블 블록을 읽을 때
• 테이블 블록을 Full Scan 할 때

DBMS는 위와 같이 버퍼캐시를 해시 구조로 관리한다.

예를 들어, 버퍼캐시에서 20번 블록을 찾고자 하다고 가정해보자. 블록 번호를 5로 나누면 나머지가 0이다. 이 블록이 캐싱돼 있다면 버퍼 헤더가 첫 번째 해시 체인에 연결돼 있을 것이다. 이 블록이 캐싱돼 있다면 버퍼 헤더가 첫 번째 해시 체인에 연결돼 있을 것이므로 찾을 때 항상 첫 번째 해시 체인만 탐색하면 된다.

버퍼캐시에서 블록을 찾을 때 이처럼 해시 알고리즘으로 버퍼 헤더를 찾고, 거기서 얻은 포인터(Pointer)로 버퍼 블록을 액세스하는 방식을 사용한다.

• 같은 입력 값은 항상 동일한 해시 체인(=버킷)에 연결됨
• 다른 입력 값이 동일한 해시 체인에 연결될 수 있음
• 해시 체인 내에서는 정렬이 보장되지 않음

버퍼캐시는 SGA 구성요소이므로 버퍼캐시에 캐싱된 버퍼블록은 모두 공유자원이다. 공유자원은 말 그대로 모두에게 권한이 있기 때문에 누구나 접근할 수 있다.

두 개 이상의 프로세스가 동시에 접근하려고 할 때는 문제가 발생한다. 블록 정합성에 문제가 생길 수 있기 때문이다. 따라서 내부에서는 한 프로세스씩 순차적으로 접근하도록 구현해야 하며, 이를 위해 직렬화(serialization) 메커니즘이 필요하다. 

SQL이 느린 이유

SQL이 느린 이유는 대부분 I/O 때문이다. 구체적으로 디스크 I/O 때문이다.

그렇다면, I/O란 무엇일까?

'I/O = 잠(SLEEP)'이라고 생각하면 쉽다. OS 또는 I/O 서브시스템이 I/O를 처리하는 동안 프로세스는 잠을 자기 때문이다. 프로세스가 일하지 않고 잠을 자는 이유는 여러가지가 있지만, I/O가 가장 대표적이고 절대 비중을 차지한다. 

프로세스(Process)는 '실행 중인 프로그램'이며, 생명주기를 갖는다. 즉, 생성(new) 이후 종료(terminated) 전까지 준비(ready)와 실행(running)과 대기(waiting) 상태를 반복한다. 실행 중인 프로세스는 interrupt에 의해 수시로 실행 준비 상태(Runnable Queue)로 전환했다가 다시 실행 상태로 전환한다. 여러 프로세스가 하나의 CPU를 공유할 수 있지만, 특정 순간에는 하나의 프로세스만 CPU를 사용할 수 있기 때문에 이런 메커니즘이 필요하다. 

interrupt 없이 열심히 일하던 프로세스도 디스크에서 데이터를 읽어야 할 땐 CPU를 OS에 반환하고 잠시 수면(waiting) 상태에서 I/O가 완료되기를 기다린다. 정해진 OS 함수를 호출(I/O Call)하고 CPU를 반환한 채 알람을 설정하고 대기 큐(Wait Queue)에서 잠을 자는 것이다. 열심히 일해야 할 프로세스가 한가하게 잠을 자고 있으니 I/O가 많으면 성능이 느릴 수 밖에 없다. 

데이터베이스 저장 구조

데이터를 저장하려면 먼저 테이블스페이스를 생성해야 한다. 테이블스페이스는 세그먼트를 담는 콘테이너로서, 여러 개의 데이터파일(디스크 상의 물리적인 OS 파일)로 구성된다.

테이블스페이스를 생성했으면 위와 같이 세그먼트를 생성한다. 세그먼트는 테이블, 인덱스처럼 데이터 저장공간이 필요한 오브젝트다. 테이블, 인덱스를 생성할 때 데이터를 어떤 테이블스페이스에 저장할지를 지정한다.

세그먼트는 여러 익스텐트로 구성된다. 파티션 구조가 아니라면 테이블도 하나의 세그먼트고, 인덱스도 하나의 세그먼트다. 테이블 또는 인덱스가 파티션 구조라면, 각 파티션이 하나의 세그먼트가 된다. LOB 컬럼은 그 자체가 하나의 세그먼트를 구성하므로 자신이 속한 테이블과 다른 별도 공간에 값을 저장한다.

익스텐트는 공간을 확장하는 단위이다. 테이블이나 인덱스에 데이터를 입력하다가 공간이 부족해지면 해당 오브젝트가 속한 테이블스페이스로부터 익스텐트를 추가로 할당받는다. 익스텐트는 연속된 블록들의 집합이기도 하다. 

익스텐트 단위로 공간을 확장하지만, 사용자가 입력한 레코드를 실제로 저장하는 공간은 데이터 블록이다. 한 블록은 하나의 테이블만 독점한다. 즉, 한 블록에 저장된 레코드는 모두 같은 테이블 레코드다.

세그먼트 공간이 부족해지면 테이블스페이스로부터 익스텐트를 추가로 할당받는다고 했는데, 세그먼트에 할당된 모든 익스텐트가 같은 데이터파일에 위치하지 않을 수 있다. 

익스텐트  내 블록은 서로 연속된 공간이지만, 익스텐트끼리는 연속된 공간이 아니라는 사실을 위의 그림을 통해 알 수 있다. 

-- 오라클에서 세그먼트에 할당된 익스텐트 목록 조회 방법
SQL >
select segment_type, tablespace_name, extent_id, file_id, block_id, blocks
from dba_extents
and segment_name = 'MY_SEGMENT'
order by extent_id;

블록, 익스텐트, 세그먼트, 테이블스페이스, 데이터파일을 정의하면 다음과 같다.

• 블록 : 데이터를 읽고 쓰는 단위
• 익스텐트 : 공간을 확장하는 단위, 연속된 블록 집합
• 세그먼트 : 데이터 저장공간이 필요한 오브젝트(테이블, 인덱스, 파티, LOB 등)
• 테이블스페이스 : 세그먼트를 담는 컨테이너
• 데이터파일 : 디스크 상의 물리적인 OS 파일

블록 단위 I/O

데이터 I/O 단위가 블록이므로 특정 레코드 하나를 읽고 싶어도 해당 블록을 통째로 읽는다. 심지어 1Byte짜리 컬럼 하나만 읽고 싶어도 블록을 통째로 읽는다. 오라클은 기본적으로 8KB 크기의 블록을 사용하므로 1Byte를 읽기 위해 8KB를 읽는 셈이다. 

-- 오라클 데이터베이스의 블록 사이즈 확인 방법.
SQL > show parameter block_size

테이블뿐만 아니라 인덱스도 블록 단위로 데이터를 읽고 쓴다. 

시퀀셜 액세스 vs 랜덤 액세스

테이블 또는 인덱스 블록을 액세스하는(=읽는) 방식으로는 시퀀셜 엑세스와 랜덤 액세스, 두 가지가 있다.

첫째, 시퀀셜(Sequential) 액세스는 논리적 또는 물리적으로 연결된 순서에 따라 차례대로 블록을 읽는 방식이다. 인덱스 리프 블록은 앞뒤를 가리키는 주소값을 통해 논리적으로 서로 연결돼 있다. 이 주소 값에 따라 앞 또는 뒤로 순차적으로 스캔하는 방식이 시퀀셜 액세스다.

테이블 블록 간에는 서로 논리적인 연결고리를 가지고 있지 않다. 그럼, 테이블은 어떻게 시퀀셜 방식으로 엑세스할까?

오라클은 세그먼트에 할당된 익스텐트 목록을 세그먼트 헤더에 맵(map)으로 관리한다. 익스텐트 맵은 각 익스텐트의 첫 번째 블록 주소 값을 갖는다. 

읽어야 할 익스텐트 목록을 익스텐트 맵에서 얻고, 각 익스텐트의 첫 번째 블록 뒤에 연속해서 저장된 블록은 순서대로 읽으면, 그것이 곧 Full Table Scan이다. 

둘때, 랜덤(Random) 액세스는 논리적, 물리적인 순서를 따르지 않고, 레코드 하나를 읽기 위해 한 블록씩 접근(=touch)하는 방식이다. 

논리적 I/O vs 물리적 I/O

DB버퍼캐시

디스크 I/O가 SQL 성능을 결정한다. SQL을 수행하는 과정에 계속해서 데이터 블록을 읽는데, 자주 읽는 블록을 매번 디스크에서 읽는 것은 매우 비효율적이다. 모든 DBMS에 데이터 캐싱 메커니즘이 필수인 이유다.

데이터를 캐싱하는 'DB버퍼캐시'도 SGA의 가장 중요한 구성요소 중 하나다. 라이브러리 캐시가 SQL과 실행계획, DB 저장형 함수/프로시저 등을 캐싱하는 '코드 캐시'라고 한다면, DB버퍼캐시는 '데이터 캐시' 라고 할 수 있다.

디스크에서 어렵게 읽은 데이터 블록을 캐싱해 둠으로써 같은 블록에 대한 반복적인 I/O Call을 줄이는 데 목적이 있다.

위 그림처럼 서버 프로세스와 데이터파일 사이에 버퍼캐시가 있으므로 데이터 블록을 읽을 땐 항상 버퍼캐시부터 탐색한다. 운 좋게 캐시에서 블록을 찾는다면 바쁜 시간에 프로레스가 잠(I/O Call)을 자지 않아도 된다. 버퍼캐시는 공유메모리 영역이므로 같은 블록을 읽는 다른 프로세스도 이득을 본다.

-- 오라클 SQL*Plus에서 버퍼캐시 확인.
SQL > show spa

논리적 I/O vs 물리적 I/O

논리적 블록 I/O는 SQL을 처리하는 과정에 발생한 총 블록 I/O를 말한다. 

위 그림의 좌측처럼 메모리상의 버퍼 캐시를 경유하므로 메모리 I/O가 곧 논리적 I/O라고 생각해도 무방하다.

물리적 블록 I/O는 디스크에서 발생한 총 블록 I/O를 말한다. SQL 처리 도중 읽어야 할 블록을 버퍼캐시에서 찾지 못할 때만 디스크를 액세스하므로 논리적 블록 I/O 중 일부를 물리적으로 I/O 한다.

메모리 I/O는 전기적 신호인 데 반해, 디스크 I/O는 액세스 암을 통해 물리적 작용이 일어나므로 메모리 I/O에 비해 상당히 느리다. 보통 10,000배쯤 느리다.

데이터베이스 세계에서 논리적 일량과 물리적 일량을 정의해 보자. SQL을 수행하려면 데이터가 담긴 블록을 읽어야 한다. SQL이 참조하는 테이블에 데이터를 입력하거나 삭제하지 않는 상황에서 조건절에 같은 변수 값을 입력하면, 아무리 여러 번 실행해도 매번 읽는 블록 수는 같다. SQL을 수행하면서 읽은 총 블록 I/O가 논리적 I/O다.

DB 버퍼캐시에서 블록을 찾지 못해 디스크에서 읽은 블록 I/O가 물리적 I/O다. 데이터 입력이나 삭제가 없어도 물리적 I/O는 SQL을 실행할 때마다 다르다. 연속해서 실행하면 DB 버퍼캐시에서 해당 테이블 블록의 점유율이 점점 높아지기 때문이다. 

버퍼캐시 히트율

Single Block I/O vs Multiblock I/O

메모리 캐시가 클수록 좋지만, 데이터를 모두 캐시에 적재할 수는 없다. 비용적인 한계, 기술적인 한계 때문에 전체 데이터 중 일부만 캐시에 적재해서 읽을 수 있다.

캐시에서 찾지 못한 데이터 블록은 I/O Call을 통해 디스크에서 DB 버퍼캐시로 적재하고서 읽는다. I/O Call을 할 때, 한 번에 한 블록씩 요청하기도 하고, 여러 블록씩 요청하기도 한다. 

한 번에 한 블록씩 요청해서 메모리에 적재하는 방식을 'Single Block I/O'라고 한다. 많은 벽돌을 실어 나를 때 손수레를 이용하는 것처럼 한 번에 여러 블록씩 요청해서 메모리에 적재하는 방식을 'Multiblock I/O'라고 한다.

인덱스를 이용할 때는 기본적으로 인덱스와 테이블 블록 모두 Single Block I/O 방식을 사용한다. 

• 인덱스 루트 블록을 읽을 때
• 인덱스 루트 블록에서 얻은 주소 정보로 브랜치 블록을 읽을 때
• 인덱스 브랜치 블록에서 얻은 주소 정보로 리프 블록을 읽을 때
• 인덱스 리프 블록에서 얻은 주소 정보로 테이블 블록을 읽을 때

반대로, 많은 데이터 블록을 읽을 때는 Multiblock I/O 방식이 효율적이다. 그래서 인덱스를 이용하지 않고 테이블 전체를 스캔할 때 이 방식을 사용한다. 테이블이 클수록 Multiblock I/O 단위도 크면 좋다. 프로세스가 잠자는 횟수를 줄여주는 데 이유가 있다.

Table Full Scan vs Index Range Scan

테이블에 저장된 데이터를 읽는 방식은 두 가지다.

Table Full Scan은 말 그대로 테이블에 속한 블록 '전체'를 읽어서 사용자가 원하는 데이터를 찾는 방식이다. 인덱스를 이용한 테이블 액세스는 인덱스에서 '일정량'을 스캔하면서 얻은 ROWID로 테이블 레코드를 찾아가는 방식이다. ROWID는 테이블 레코드가 디스크 상에 어디 저장됐는지를 가리키는 위치 정보다.

인덱스를 이용하는데 성능이 느린 경우는 왜그럴까?

시퀀셜 액세스와 랜덤 액세스, Single Block I/O와 Multiblock I/O 등등 I/O 메커니즘 관점에서 Table Full Scan과 Index Range Scan의 본질을 알아보자. 

Table Full Scan은 시퀀셜 액세스와 Multiblock I/O 방식으로 디스크 블록을 읽는다. 한 블록에 속한 모든 레코드를 한 번에 읽어 들이고, 캐시에서 못 찾으면 '한 번의 수면(I/O Call)을 통해 인접한 수십~수백 개 블록을 한꺼번에 I/O하는 메커니즘'이다. 이 방식을 사용하는 SQL은 스토리지 스캔 성능이 좋아지는 만큼 성능도 빨라진다.

큰 테이블에서 소량 데이터를 검색할때는 반드시 인덱스를 이용해야 한다.

Index Range Scan을 통한 테이블 액세스는 랜덤 액세스와 Single Block I/O 방식으로 디스크 블록을 읽는다. 캐시에서 블록을 못 찾으면, '레코드를 찾기 위해 매번 잠을 자는 I/O 메커니즘'이다. 따라서 많은 데이터를 읽을 때는 Table Full Scan보다 불리하다. 읽을 데이터가 일정량을 넘으면 인덱스보다 Table Full Scan이 유리하다.