비교 조건(”=”, “>”, “<”)에 따라 “작업 범위 결정 조건” 과 “필터링 조건, 체크 조건” 을 구분하여 생각할 수 있고, 이걸 구분하게 되면서 인덱스를 효율적으로 사용하는지 안하는지 알수있음.
인덱스의 가용성에 대해 이해하게 됨.
인덱스는 왼쪽 값 기준으로 정렬이므로 WHERE, GROUP BY, ORDER BY 수행 시 조건에 따라 인덱스의 왼쪽 값을 잘 포함되었는지 확인해야 인덱스를 효율적으로 사용할 수 있음.
인덱스의 가용성을 통해 효율성이 어떻게 결정되는지 이해하게 됨.
R-Tree 인덱스가 무엇인지 이해하게 됨.
공간 데이터를 저장할 때 필요한 인덱스임.
GEOMETRY와 MBR 을 통해 B-Tree 형태의 인덱스 구조를 만들어 냄.
기준점을 기준으로 실제 포인트가 반경내에 포함되어있는지를 확인함.
반경내에 들어오는지 정확한 판단을 하려면 좀 더 복잡한 연산이 필요함.
보통은 반경을 통해 만들어진 원을 포함한 MBR 에 포함되어있는지 확인함.
메모
B-Tree 인덱스의 가용성과 효율성
쿼리의 WHERE 조건, GROUP BY, 또는 ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고, 어떤 방식으로 사용할 수 있는지 식별할 수 있어야 함.
그래야만 쿼리의 조건을 최적화하거나 역으로 쿼리에 맞게 인덱스를 최적으로 생성할 수 있음.
비교 조건의 종류와 효율성
다중 칼럼 인덱스에서, 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등 비교(”=”) 인지, 아니면 크다, 작다(”>”, “<”) 와 같은 범위 조건인지에 따라 인덱스 칼럼의 활용 형태와 효율이 달라짐.
mysql> SELECT * FROM dept_emp
WHERE dept_no='d002' AND emp_no >= 10114;
// CASE A
INDEX (dept_no, emp_no)
// CASE B
INDEX (emp_no, dept_no)
위 그림은 두 인덱스의 칼럼 순서에 따른 인덱스 검색 과정을 보여줌.
이처럼 인덱스를 통해 레코드가 나머지 조건에 맞는지 비교하며 취사선택하는 작업을 “필터링” 이라고도 함.
케이스 A 인덱스는 “dept_no=’d002’ AND emp_no ≥ 10144” 인 레코드를 찾고, 이후 empt_no가 ‘d002’가 아닐 때까지 인덱스를 그냥 쭉 읽기만 하면 됨.
조건을 만족하는 레코드가 5건이라고 하면 5건의 레코드를 찾는데 꼭 필요한 5번의 비교 작업만 수행하므로, 상당히 효율적으로 인덱스를 이용한 것임.
케이스 B 인덱스는 “emp_no ≥ 10144 AND empt_no=’d002’” 인 레코드를 찾고, 이후 모든 레코드에 대해 dept_no 가 ‘d002’ 인지 비교하는 과정을 거쳐야 함.
조건을 만족하는 레코드가 5건이라고 하면 5건의 레코드를 찾는데 7번의 비교과정을 거침.
케이스 A 인덱스에서 dept_no=’d002’ 와 emp_no ≥ 10144 두 조건이 작업의 범위를 결정하는 조건이므로 “작업 범위 결정 조건” 이라고 부름.
케이스 B 인덱스에서 dept_no=’d002’ 조건과 같이 비교 작업의 범위를 줄이지 못하고 단순히 거름종이 역할만 하는 조건을 “필터링 조건” 또는 “체크 조건” 이라고 표현함.
작업 범위 결정 조건은 많을 수록 쿼리의 처리 성능을 높임.
하지만 체크 조건은 많다고해서 쿼리 처리 성능을 높이지 못함.
오히려 쿼리 실행을 더 느리게 만들 때가 많음.
인덱스의 가용성
B-Tree 인덱스의 특징은 왼쪽 값에 기준해서(Left-most) 오른쪽 값이 정렬되어 있다는 것임.
여기서 왼쪽이란, 하나의 칼럼 내에서뿐만 아니라, 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용됨.
// 케이스 A
INDEX (first_name)
// 케이스 B
INDEX (dept_no, emp_no)
위 그림에서 인덱스 키 값의 정렬만 표현하였음. (왼쪽 값 기준 정렬)
인덱스 키 값의 이런 정렬 특성은 빠른 검색의 전제 조건임.
만약, 하나의 칼럼으로 검색할 때, 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능함.
다중 칼럼 인덱스에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없음.
ex) SELECT * FROM employees WHERE first_name LIKE '%mer';
이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없음.
first_name 칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데, 조건절에 주어진 상수값(’%mer’)의 왼쪽 부분이 고정되지 않았기 때문.
ex) SELECT * FROM dept_emp WHERE emp_no >= 10144;
위 쿼리의 조건절에서 dept_no 조건 없이 emp_no 값으로만 검색하면 선행 칼럼인 dept_no 조건이 없어 인덱스를 효율적으로 사용할 수 없음.
dept_no 칼럼에 대해 먼저 정렬 후, emp_no 칼럼으로 정렬되어 있기 때문임.
위 두 예시는 WHERE 조건절에 대한 내용이지만, 인덱스의 왼쪽 값 규칙은 GROUP By 절이나 ORDER BY 절이나 똑같이 적용된다.
가용성과 효율성 판단
기본적으로 B-Tree 인덱스의 특성상, 아래에 설명할 조건에서는 사용할 수 없음.
여기서 사용할 수 없다는 것은 “작업 범위 결정 조건”으로 사용할 수 없다는 것임.
경우에 따라 “체크 조건”으로 인덱스를 사용할 수는 있음.
NOT-EQUAL로 비교되는 경우 (”<>”, “NOT IN”, “NOT BETWEEN”, “IS NOT NULL”)
LIKE ‘%??’(앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입을 변환해야 비교가 가능한 경우)
15장 ‘데이터 타입’ 참조
문자열 데이터 타입의 콜레이션이 다른 경우
15.1.4절 콜레이션 참조
일반적인 DBMS 에서는 NULL 값이 인덱스에 저장되지 않음.
MySQL 에서는 NULL 값도 인덱스에 저장됨.
아래와 같이 WHERE 조건도 작업 범위 결정 조건으로 인덱스를 사용함.
mysql> .. WHERE column IS NULL ..
다중 칼럼으로 만들어진 인덱스에서 어떤 조건에서 인덱스를 사용할 수 있는지 살펴보자.
INDEX ix_teset (column_1, column_2, column_3, ..., column_n);
작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
column_1 칼럼에 대한 조건이 없는 경우
column_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우
작업 범위 결정 조건으로 인덱스를 사용하는 경우(i는 2보다 크고, n보다 작은 임의의 값을 의미)
column_1 ~ column_(i-1) 칼럼까지 동등 비교 형태(”=”, 또는 “IN”)로 비교
column_i 칼럼에 대해 다음 연산자 중 하나로 비교
동등 비교 (”=” 또는 “IN”)
크다 작다 형태 (”>” 또는 “<”)
LIKE로 좌측 일치 패턴 (LIKE ‘?%’)
위의 두 가지 조건을 모두 만족하는 쿼리는 column_1 부터 column_i 까지는 작업 범위 결정 조건으로 사용됨.
column_(i+1) 부터 column_n 까지의 조건은 체크 조건으로 사용됨.
인덱스를 사용하는 경우와 아닌 경우에 대한 예제 쿼리가 p252~253에 자세히 설명되어 있음.
위와 같이, 설명한 내용은 모두 B-Tree 인덱스의 특징이므로 MySQL 뿐만 아니라 대부분의 RDBMS에도 동일하게 적용된다.
R-Tree 인덱스
MySQL 에는 공간 인덱스(Spatial Index)라는 말이 있음.
공간 인덱스는 R-Tree 인덱스 알고리즘을 이용하여 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스임.
기본 내부 메커니즘은 B-Tree와 흡사함.
B-Tree 는 인덱스 구성 칼럼 값이 1차원의 스칼라 값임.
R-Tree 는 인덱스 구성 칼럼이 2차원의 공간 개념 값임.
GPS, 지도 서비스를 내장하는 스마트 폰이 대중화 되고 있음.
SNS 서비스가 GIS, GPS 기반 서비스로 확장되고 있음.
이러한 위치 기반 서비스 구현 방법은 여러가지 방법이 있음.
MySQL의 공간 확장(Spatial Extension)을 이용하면 간단하게 이 기능을 구현할 수 있음.
MySQL의 공간 확장에는 다음과 같은 3가지 기능이 포함되어 있음.
공간 데이터를 저장할 수 있는 데이터 타입
공간 데이터의 검색을 위한 공간 인덱스(R-Tree 알고리즘)
공간 데이터의 연산 함수(거리 또는 포함 관계의 처리)
구조 및 특성
MySQL은 공간 정보의 저장 및 검색을 위해 여러 가지 기하학적 도형(Geometry) 정보를 관리할 수 있는 데이터 타입을 제공함.
위 그림은 MySQL 에서 제공하는 GEOMTERY 의 대표적인 데이터 타입임.
마지막 GEOMETRY 타입은 나머지 3개의 슈퍼 타입임.
POINT, LINE, POLYGON 객체를 모두 저장할 수 있음.
공간 정보 검색을 위한 R-Tree 알고리즘을 이해하려면 MBR 이라는 개념을 알아야함.
위 그림은 예시로 든 도형에 대한 MBR 을 보여준다.
MBR 은 “Minimum Boundiing Rectangle”의 약자로, 해당 도형을 감싸는 최소 크기의 사각형을 의미함.
이 사각형들의 포함 관계를 B-Tree 형태로 구현한 인덱스가 R-Tree 인덱스임.
위 그림은 공간 데이터를 나타내는 도형이라고 가정한다.
그림에는 표시되지 않았지만, 단순히 X, Y 좌표만 있는 포인트 데이터 또한 하나의 도형 객체가 될 수 있음.
이러한 도형이 저장됐을 때, 만들어지는 인덱스 구조를 이해하려면, 우선 이 도형들의 MBR이 어떻게 되는지 알아봐야 한다.
위 그림은 도형들의 MBR 을 3개의 레벨로 나눠서 그림.
최상위 레벨 : R1, R2
차상위 레벨 : R3, R4, R5, R6
최하위 레벨 : R7 ~ R14
최하위 레벨의 MBR(각 도형을 제일 안쪽으로 둘러싼 점선 상자)은 각 도형 데이터의 MBR을 의미함.
차상위 레벨의 MBR은 중간 크기의 MBR (도형 객체의 그룹)임.
최상위 MBR은 R-Tree의 루트 노드에 저장되는 정보임.
차상위 그룹 MBR은 R-Tree의 브랜치 노드가 됨.
마지막으로, 각 도형의 객체는 리프 노드에 저장되므로 아래 그림의 R-Tree 인덱스 내부를 표현할 수 있음.
R-Tree 인덱스의 용도
R-Tree는 MBR 정보를 이용해 B-Tree 형태로 인덱스를 구축함.
Rectangle의 ‘R’과 B-Tree의 ‘Tree’를 섞어서 R-Tree 이름이 붙여짐.
공간(Spatial) 인덱스라고도 함.
일반적으로 WGS84(GPS) 기준의 위도, 경도 좌표 저장에 주로 사용됨.
위도, 경도 좌표뿐만 아니라 CAD/CAM 소프트웨어, 또는 회로 디자인과 같은 좌표 시스템에 기반을 둔 정보에 대해서 모두 적용할 수 있음.
R-Tree는 각 도형(정확히는 도형의 MBR)의 포함 관계를 이용해 만들어진 인덱스임.
따라서 ST_Contains() 또는 ST_Within() 등과 같은 포함 관계를 비교하는 함수로 검색을 수행하는 경우에만 인덱스를 이용할 수 있음.
대표적으로, ‘현재 사용자의 위치로부터 반경 5km 이내의 음식점 검색’등과 같은 검색에 사용할 수 있음.
현재 출시된 버전의 MySQL 에서는 거리 비교에 쓰이는 ST_Distance()와 ST_DISTANCE_Sphere() 함수를 이용하여 공간 인덱스를 효율적으로 사용하지 못함.
따라서 공간 인덱스를 사용할 수 있는 ST_contains() 또는 ST_Within()을 이용해서 거리 기반의 검색을 해야 함.
위 그림은 특정 지점을 기준으로 사각 박스 이내의 위치를 검색하는 예시임.
가운데 위치한 ‘P’ 가 기준점임.
기준점으로부터 반경 거리 5km 이내의 점(위치)들을 검색하려면 우선 사각 점선의 상자에 포함되는 (ST_contains() 또는 ST_Within() 함수 이용) 점들을 검색하면 됨.
ST_contains() 또는 ST_Within() 연산은 사각형 박스와 같은 다각형(Polygon)으로만 연산할 수 있음.
반경 5km를 그리는 원을 포함하는 최소 사각형(MBR)으로 포함 관계 비교를 수행함.
점 ‘P6’는 기준점 P로부터 반경 5km 이상 떨어져 있지만 최소 사각형 내에는 포함됨.
P6를 빼고 결과를 조회할 수 있지만, 조금 더 복잡한 비교가 필요함.
P6을 결과에 포함해도 좋다면 ST_contains() 또는 ST_Within() 연산만 수행하는 것이 좋음.
// ST_contains() 또는 ST_Within()을 이용해서 "사각 상자"에 포함된 자표 Px만 검색하는 쿼리임
mysql> SELECT * FROM tb_location
WHERE ST_Contains(사각 상자, px);
mysql> SELECT * FROM tb_location
WHERE ST_Within(px, 사각 상자);
ST_contains() 함수와 ST_Within() 함수는 거의 동일한 비교를 수행하지만 두 함수의 파라미터는 반대로 사용해야 함.
위 그림에서 P6을 만드시 제거해야 한다면 아래와 같이 ST_Contains() 비교의 결과에 대해 ST_Distance_Sphere() 함수를 이용해 다시 한번 필터링 해야 함.
mysql> SELECT * FROM tb_location
WHERE ST_Contains(사각 상자, px) // 공간 좌표 Px가 사각 상자에 포함되는지 비교
AND ST_Distance_Sphere(p, px) <= 5*1000 /* 5km */;
