옵티마이저

용어 정리

 

DB의 조인

-       논리적: 내부조인(자연조인, Inner), 외부조인(Outer), 크로스 조인(크로스 프로덕트)

-       물리적: Nested Roof, Sort Merge, Hash 조인(그 밖에 더 있으나 여기까지만)

 

조인 수행 원리

PPT로 (애니메이션 가능)

 

옵티마이저

-       옵티마이저를 이해하는 것이 튜닝의 시작이고 옵티마이저를 제어하는 것이 튜닝의 기본이다.

-       옵티마이저에 의해 발생하는 조인 3가지: NL조인 , Sort Merge 조인, Hash 조인 이 있다 이것은 물리적인 조인이기 때문에 개발자가 직접 사용하게 되는 조인은 아니다

-       개발자가 직접 제어하는 조인은 내부조인이나 외부조인과 같은 논리적인 조인을 선언해서 만든다.

n  Ludy의 경우 Merge Into 구문도 조인이 있다  

-       즉 이런 논리적인 조인을 옵티마이저라는 녀석이 DBMS 내부에서 물리적인 조인으로 표현하고 만드는 것이다

-       옵티마이저는 사용자가 질의한 SQL문에 대해 최적의 실행 방법을 결정하는 역할을 수행

-       옵티마이저가 정한 최적의 실행 방법을 실행 계획이라고 함

-       다양한 실행 방법들 중에서 최적의 실행 방법을 결정하는 것이 옵티마이저의 역할

-       실제로 SQL문을 처리해 보지 않은 상태에서 결정해야 하는 어려움이 있다

n  DBMS 별로 옵티마이저의 성능을 비교해 볼 수 있는 부분이라고 볼 수 있겠다

-       보통 CBO(비용기반 옵티마이저를) 생각하면 된다

-       최적의 실행방법 결정이라는 것은 어떤 방법으로 처리한 것이 최소 일량(비용)으로 동일한 일을 처리할 수 있을 지 결정하는 것이다

-       즉 옵티마이저 최적의 실행 방법을 결정하는 것을 개발자는 도와주어야 한다

-       단순히 조인의 원리를 아는 것보다는 이 옵티마이저가 어떻게 물리적인 조인으로 변경시키는지를 알아야 한다

 

 

카디널리티

-       Cardinality: 사전적 의미로는 집합원의 개수

-       카디널리티가 낮은 경우에서 속성의 예를 들면 성별, 부서, 지역이 있다.

n  성별의 경우 남자, 여자 두 가지 경우만 가능하므로 매우 낮다고 할 수 있다

n  주민번호, 사원번호와 같은 경우 조직원이 많을수록 카디널리티가 높다

-       간단히 생각하면 한 개를 뽑는 뽑기를 했을 때 그 뽑는 모집단의 수가 많으면 높다고 할 수 있다

-       데이터베이스로 한정해보면 테이블에서 Primary Key에 해당 되는 경우의 수 라고도 볼 수 있겠다

 

카디널리티 설명 예제

PPT로

예를 들면 학급 엔터티로 학년의 성적표를 만든다면 반 번호가 기본키가 되면 그 학급의 학생의 수가 카디널리티가 될 수 있다 (학급(1) : 학생(N))

다른형태로는 특정 쿼리문을 실행시켜서 나오는 결과 값(Row)를 카디널리티라고 한다

즉 학교라는 개념에서는 학급이 카디널리티일 수 도 있고 학급이라는 개념에서는 학생이 카디널리티일 수도 있다

예를 들면 사원테이블의 전체 레코드 수가 1000개일 때

WHERE 부서 = ‘인사팀’ 이면 그 중 인사팀 사원이 10명이면 선택도는 10/1000 = 0.01이 됩니다. 즉 전체 rows * 선택도 = 결과수, 즉 카디널리티 가 결과 수라면 10이 카티널리티 입니다.

 

카디널리티를 이해해야 하는 이유

DB의 옵티마이저에서 조인을 맺어주는 항목으로 인덱스를 사용하게 됩니다. 물론 없으면 따로 사용하지 않고 Full Scan 이 되겠지요. 중요한 건 현재 접근하는 컬럼을 조건으로 접근할 때 얼마나 많이 걸러지느냐 입니다.

선택도가 확률이라고 하면 해당 카디널리티 즉 경우의 수는 전체 데이터의 개수에 영향을 받게 됩니다. 데이터가 많을 때는 해당 조건으로 얼마나 많이 걸러지는 지 즉 중복이 최소한일수록 해당 조건으로 많이 걸러지게 됩니다. 중복된 data를 검색 즉 중복이기 때문에 해당 data 전체를 Scan 해야 하기 때문에 원하는 하나를 찾는 경우에 범위를 좁혀가는 검색에서는 시간이 더 걸리게 됩니다.

순차적인 선형 검색일 경우 순서대로 전체를 보게 되지만 범위를 좁혀가는 이진검색이 성능이 더 좋다고 합니다.

이렇게 집합에서 원소가 어떻게 분포되었냐에 따라 스캔속도가 차이가 나므로 옵티마이저는 인덱스의 설계가 어떻게 되었냐에 따라 영향을 받게 됩니다. 개발자는 물리적인 조인에 대해 직접 관여는 하지 않지만 인덱스 설정에 따라 영향은 줄 수 있다는 말입니다.

일반적으로 옵티마이저는 여러 인덱스가 있을 때 선택도가 낮은 즉 중복발생확률이 낮은 인덱스를 사용합니다.

인덱스

인덱스는 검색을 빨리 하기 위한 용도로 사용합니다.

인덱스를 여러 개 사용할 때는 넌클러스터 인덱스를 사용합니다.

인덱스를 여러 개 사용할수록 옵티마이저가 잘못된 인덱스를 선택할 확률이 높아집니다.

인텍스를 하나의 컬럼에만 걸어야 한다면 카디널리티가 가장 높은 경우 즉 중복을 제거 했을 때 집합 원소의 개수가 가장 많은 속성을 지정합니다.

예를 들면 성별을 인덱스로 지정하면 카디널리티가 2밖에 되지 않으므로 인덱스로 걸러지는(Range로 걸러진다고 할 때) 경우가 50% 밖에 걸리지지가 않습니다.

100 개 중에 유일한 하나일 경우라면 1%이나 99%가 걸리지는 경우이겠습니다.

인덱스로 걸러낸다는 개념은 무엇일까요???

그리고 우리가 사용하는 테이블은 기본적으로 어떻게 설계하길래 성능이슈가 있게 된 것일 까요??

어려워 지는데 하나 확실히 아는 것은 사원번호나 주민번호와 같은 속성의 값을 대표값으로 할 수 있는 것은 현재 구성원을 구성하는 큰 집합에서 유일한 속성으로 취급할 수 있는 것입니다. 즉 10이하의 자연수의 집합일 경우라면 {1,2,3,4,5,6,7,8,9,10} 원하는 숫자를 찾을 때 중복이 없으므로 유일한 값 하나를 찾습니다. 이렇게 유일한 속성의 인덱스는 내가 찾는 요소 하나로 최대한으로 나머지 원소를 거를 수 있습니다. 이런 개념에서 카디널리티를 이해하고 넘어가고자 합니다.

위의 개념에서 인덱스의 유일성이 필요에 대해서 이해가 되었으면(모든 인덱스가 유일성을 가지는 것은 아닙니다)

낫널에 대해서 이야기 해 볼까요? 기본적으로 데이터베이스의 엔터티 혹은 릴레이션 혹은 테이블이라고 하는 개체는 해당 컬럼이 동일 선상에서 이미 다른 컬럼들과 원자적인 구조로 만들어져야 합니다. 즉 본인이 변경되었다고 다른 컬럼의 값도 변경이 된다는 것은 정규적이지 않은 관계입니다. 그리고 data의 중복을 최소화 한다는 것은 하나의 Row, 튜플 이런 값이 다른 Row, 튜플과 구별되는 대표값이 있어야 한다는 것입니다. 그렇다면 대표값이 널이 되어버리면 일단 다른 Row들과 구별되거나 해당 Row를 대표할 수 없습니다.

유일한 Row이고 그 값이 비어있지 않으며 속성들끼리 원자적인 테이블에서 대표값만 가지고 그 Row, 튜플을 찾거나 맵핑 할 수 있습니다. 대표값만 가지고 데이터를 찾는다.. 인덱스가 그런 용도의 느낌입니다.

 

확률

확률이 예를 들기 좋은 것 같습니다.

카디널리티라는 주머니를 만들고 거기에 빨주노초파남보 의 무지개 색 공을 집어넣으면 이 경우 선택도는 1/7 입니다.

그러면 빨간공 3개 노란공 2개 보라색공 4개를 넣으면 이 경우 선택도는 몇 일 까요?? 빨간공의 확률은 1/3 노란공은 2/9 보라색공은 4/9 입니다 이건 단순히 시행(반복)이라는 시도와 맞물려서 말할 수 있는 확률 인 것이고

공이라는 개념으로 접근하면 3개의 색만을 가지므로 그 공이라는 릴레이션은 엔터티는 테이블의 색깔이라는 속성은 선택도가 1/3 즉 0.33 입니다.

 

그리고 그 빨주노초파남보 이면서 각각 1~7까지의 숫자가 매겨저 있는 상황이라면

빨 주 노 초 파 남 보

1  2  3  4  5  6  7

 

이런 상황에서 숫자와 색깔이라는 속성의 선택도는 어떻게 될 까요??

제가 확률을 얘기 했으니 숫자로 하면 1/7 색으로 하면 1/7입니다. 단 이것은 전에 말했듯이 시행에 의해 획득할 수 있는 한번의 공입니다 다만 유일성이 확보가 되니 선택도는 1/전체 이고 뭘로하든 카디널리티는 1 입니다.

근데 예제를 바꾸면

빨 주 노 초 파 남 보

1  2  2  2  3  4  4

 

이런 상황에서는 선택도가 변하겠죠? 색으로는 1/7이고 숫자로는 1/4 입니다.

여기서 어떤 속성을 기준으로 하느냐에 따라 확률이 달라졌고 그에 따라 선택도(카디널리티)도 달라졌습니다.

여기서 속성을 색과 숫자로 나눈 이유는 인덱스를 어디다 거는 기준이 뭐냐?? 라는 말을 하고 싶어서 입니다.

 

최소한의 기준은 앞에서 선택도가 낮고 카디널리티가 높은 경우를 말했습니다. 그리고 여기서 선택도라는 확률에서 분모 즉 유일성이 보장되는 모집단의 개수입니다. 경우의 수라고도 보이겠네요

이게 더 큰 경우로 색깔이 나오기 때문에 공이라는 릴레이션 엔터티 테이블은 인덱스를 색깔로 잡아야 숫자보다 효율이 좋습니다.

즉 숫자로 해야 걸러지는 케이스가 많아진다는 말입니다.

확률 공식을 보면

 즉 카디널리티는 일정한 기댓값 즉 평균의 속성을 가지고 있습니다.

위의 내용은 확률 분포 내용으로 기댓값이란

사실 위의 내용을 고민하지 않아도 인덱스를 만들거나 하는 것에는 크게 상관이 없습니다. 조인을 만드는 것도 또 옵티마이저에게 성능판단을 위임하는 것도 개발자가 DBMS를 이해해야 하나? 라는 의문을 가지면 딱히 할말은 없지만 옵티마이저는 분명 만능이 아니고 최적화에 실패할 수 있습니다. 그리고 인덱스를 가지고 검색을 할 때 동작하는 거나 원리는 DBMS마다 조금씩 다를 수 있습니다. 모든게 같으면 DB가격이나 성능이 같아야 할 테니까요 위에 내용에 대해 궁금하게 접근한 이유는 이미 누구나 알고 있는 인덱스의 동작원리보다는 어떤 녀석이 인덱스가 되어야 하지?? 넌 어떤 점이 좋으니 인덱스가 되고 넌 어떤 점이 안좋으니 인덱스가 될 수 없다 하는 어떤 녀석이 인덱스로 고민하고 또 그것을 활용하는 옵티마이저는 이 인덱스의 어떤 점에 끌려 자기만의 인공지능적인 최적화를 수행 할 수 있을까? 라는 부분에서의 물음입니다.

즉 가능하면 내부적으로 개발자가 직접 인덱스를 만든다면 적어도 그 테이블이나 데이터를 보고 그 기준이 되는 부분을 찾아보고 싶기 때문입니다. 물론 옵티마이저에서 제가 생각한 선택도나 카디널리티나 기댓값이나 이런 부분에 영향을 미쳐서 판단한다고 증명된 것은 없습니다. 다만 저의 위키의 내용은 제가 인덱스를 고려할 컬럼을 정한다면 (PK 외적으로) 저런 수치적인 부분이나 그 속성의 고유한 특성을 고려해서 해당 컬럼에 인덱스를 걸고 그 인덱스를 옵티마이저가 제가 원하는 기준(작은 수량은 NL조인, 대량의 데이터는 Sort Merge 조인, 메모리 성능도 좋고 양도 많으면 Hash 조인으로 동작하기를 희망하기 때문에 인덱스를 재물로 삼았습니다. )

인덱스가 아니라면 일단 옵티마이저에게 어떻게 말을 걸고 접근할지 막연하기 때문에 인덱스로 그리고 그것이 조건이 되었을 때 옵티마이저 안녕? 이것을 하려고 합니다.

 

위의 내용까지가 서론이고 이제 본론에서는 실제 데이터의 수량을 달리하면서 실행 계획에서 어떻게 성능적으로 달라진는지 확인해 보겠습니다.

 

조인을 깊이 이해하는 것은 어렵고 동일한 결과를 얻을 수 있는 조인 방법은 많이 있지만 주어진 환경에 따라 효율성이 차이가 난다

즉 어떻게 사용하느냐에 따라 결과가 천지만별이라는 것이다.

실행계획을 이해했고 조인의 기본적인 처리 절차를 파악해둠으로서 나중에 조인을 깊이 이해 하기 위한 사전준비일 뿐이다…(책에서)

1.         내포조인

2.         정렬병합

3.         해시조인

4.         세미조인

5.         카티전 조인

6.         아우터 조인

7.         인덱스 조인

엔코아 책에서는 저렇게 만 다룬다고 하니 더 있나보다…

 

간단히 말하면 일단..

기본적으로 조인의 원리를 생각하려면 SQL 즉 코드로 인해 조인을 만들 것이고 그 조인을 구성하는 Table 즉 이 대상으로부터 data를 취득할 때 DBMS가 어떻게 데이터를 취합하고 어떻게 데이터를 저장하고 그 저장된 데이터에서 원하는 조건에 맞게 가져오는 지 궁금증을 가지는 데에서부터 시작한다.

 

즉 내부조인이나 외부조인 같은 방법을 사용해서 쿼리(질의)를 하고 그 결과는 DBMS에서 반환되며 디스크 or 메모리 상에서 어떠한 연산??(알고리즘) 에 의해 빠른 속도 or 느린 속도로 결과를 만들어주게 된다.

여기서 어떠한 연산?? 이 부분을 아는 것이 일단 지금 단계서의 목표이다.

기본적으로 생각 해야 하는 것은 적어도 우리는 최대한의 정규테이블로 구성된 DB에서 작업이 일어날 것이며 그렇기 때문에 정규테이블간의 관계에 따라 필요한 데이터를 얻기 위해 조인을 하게 되고

그 때 그 테이블을 필터하는 범위나 컬럼의 선택도나 사용하고 있는 인덱스에 의해 쿼리의 성능이 정해진다

 

자 그렇다면 1.내포조인 2. 정렬병합 3. 해시조인에 대해 간략히 언급하고 넘어간다

 

일단 기본은 내포조인이다. 즉 중첩된 루프를 돌면서 Outer table에서 Inner Table로 조건이 일치되는 data를 찾는 것이 가장 보편적으로 사용되는 조인이다

여기서 기본적으로 사용되는 자료구조는 B+Tree 이며 Root 부터 Branch를 지나 Leaf를 찾는 것이 알고리즘의 핵심이다

이 알고리즘을 사용할 때 정렬되냐 정렬이 안되냐에 따른 차이는 있지만 기본적으로 NL 조인은 랜덤엑세스를 해서 찾아간다 그래서 (Index)Table Scan을 하면 안 되고 Index Seek or Range Scan을 해서 범위로 접근해야 기본적인 성능이 좋다고 본다

그 한번의 랜덤엑세스가 중첩된 Roof를 돌면서 반복되므로 Scan이 아닌 Seek or Range를 가지는 부분이 성능의 핵심이다.

Sort Merge의 경우는 위의 Case에 정렬된 자료구조를 가지고 있다고 생각하면 된다 즉 내부적으로 정렬 프로세스를 거치니 초기 작업은 오래 걸려도 실제 찾는 프로세스는 적게 걸릴 수 있다 NL의 단점을 극복하기 위해 생겼다고 한다

Hash 의 경우는 Sort Merge가 정렬프로세스를 가지고 있다면 단점을 극복하려고 생겼다고 한다 즉 이 부분은 알고리즘적으로 접근해야 하는데 O(logn)도 충분히 훌륭한 것이지만 해시 맵을 만들면 해시 알고리즘은 O(1)이기 때문에 정렬을 하지않아고 검색이 가능하다고 한다 단 해시결과가 유일한 지 검증하는 부분이 추가되므로 꼭 O(1)은 아니라고 한다 어쨌든 알고리즘 적으로 해시 맵을 만들어서 검색하는 것이 더 탁월해 사용하는 조인방법이다.

 

즉 조인은 기본적으로 복수의 대상간 중첩된 루프를 돌며 조건이 맞는 경우를 찾는 것이고 NL의 경우 B+Tree 구조상에 랜덤엑세스의 부담 때문에 그 부담을 줄이고자 정렬된 상태에서 엑세스를 하는 Sort Merge 조인이 생겨났고 정렬을 미리 해야 하는 전처리에 대한 부담으로 아예 유일한 해시값을 생성해서 그 해시를 이용해 조인을 하는 것이 해시 조인이다… 라고 까지 생각하고 더 붙이자.

 

자 여기서 중요한 것은 인덱스 설계를 잘하는 것이다 인덱스에 따라 옵티마이저가 보다 좋은 엑세스경로를 찾을 수있게하는 근본적인 방법이다.

인덱스는 현재 발생할 수 있는 상황과 데이터의 분포도나 결합도 선택도등을 고려해서 설계되어야 한다