[SQLD] 개념정리 2과목 - SQL 최적화 기본 원리

옵티마이저와 실행계획

옵티마이저

: SQL 쿼리를 실행할 때 DBMS 가 최적의 실행 계획을 선택할 수 있도록 하는 역할을 한다 → 쿼리 처리 시 가장 효율적인 방법을 결정하여 쿼리 성능을 최대화한다.

• 규칙 기반 옵티마이저 (RBO) : 각각의 SQL문에 대해 미리 정의된 규칙을 사용하여 실행 계획을 선택한다. / 현재는 대부분 사용되지 않는 오래된 시스템
• 비용 기반 옵티마이저 (CBO) : 실행 가능한 다양한 실행 계획 중 가장 낮은 비용을 가진 최적의 실행 계획을 선택한다. / 현대 대부분의 DBMS에서 사용하는 시스템

실행계획 (Execution Plan)

: 옵티마이저가 선택한 쿼리의 실행 방법을 설명하는 계획, 쿼리를 어떻게 처리할 것인지를 단계적으로 보여줌

[실행계획의 구성요소]

• 액세스 방법 : 데이터에 액세스하는 방법 _ex. 인덱스 스캔, 풀 테이블 스캔 등
  • 인덱스 스캔 : 특정 열에 대한 정렬된 데이터 구조를 사용하여 데이터에 액세스 하는 방법

  SELECT * FROM EMPLOYEE WHERE DEPARTMENT = 'IT';
  

  • 풀 테이블 스캔 : 테이블의 모든 행을 읽어야 할 때 사용, 일반적으로 작은 테이블이나 쿼리 결과가 테이블의 대다수 행을 반환하는 경우 발생

  SELECT * FROM ORDER WHERE ORDERDATE BETWEEN '2023-01-01'
  AND '2023-12-31';
  

• 조인 방법 : 두 개 이상의 테이블을 조인하는 방법 _ex. 네스티드 루프 조인, 해시 조인, 정렬 병합 조인 등
  • Nested Loop Join : 가장 기본적인 조인 알고리즘, 두 개의 테이블을 순차적으로 스캔하여 조인하는 방법 → 외부 테이블의 각 행마다 내부 테이블을 스캔하여 일치하는 조인 조건을 찾는 것

  SELECT * FROM DEPARTMENT D
  INNER JOIN EMPLOYEE e ON D.DEPARTMENTID = e.DEPARTMENTID;
  

  • Hash Join : 조인조건에 해당하는 열 값을 해시함수를 사용하여 해시 테이블에 저장한 후, 다른 테이블의 행을 스캔해 해시 테이블과 비교하는 방식

  SELECT * FROM ORDER o
  INNER JOIN OrderDetail od ON o.OrderID = od.ORDERID;
  

  • Sort Merge Join : 두 개의 테이블을 각각 정렬한 후 병합하는 방식 ⇒ 정렬 시 일반적으로 인덱스를 사용하여 정렬한다

  SELECT * FROM ORDER o
  INNER JOIN CUSTOMER c ON o.CustomerID = c.CustomerID;
  

• 정렬 및 그룹핑 : 정렬 작업이나 그룹핑 작업에 사용되는 방법을 설명
• 필터링 및 조건부 연산 : 조건절에 따라 데이터를 필터링하거나 연산하는 방법 설명

인덱스 기본

인덱스 : 데이터베이스에서 데이터를 효율적으로 검색하기 위한 자료구조

인덱스 작동 원리

• 트리 구조 : 대부분의 데이터베이스에서 인덱스는 B-트리(B-tree)나 B+트리(B+tree)와 같은 트리 구조를 통해 효율적인 데이터 검색 가능
• 정렬된 저장 : 인덱스는 인덱스 키를 기준으로 데이터를 정렬하여 저장한다 → 이진탐색과 같은 효율적인 검색 알고리즘이 가능해진다.

//B-트리 와 B+트리는 데이터베이스에서 인덱스를 구현하는데 사용되는 효율적인 자료 구조, 
//주로 검색 및 삽입, 삭제 작업을 효율적으로 수행할 수 있는 방식으로 데이터 구성

**B-트리** 
-> 균형 이진 트리의 확장된 형태
-> 각 노드는 여러 개의 키-값 쌍을 가질 수 있다. 
-> 노드는 최소 차수를 가지며, 이는 노드가 가질 수 있는 자식의 최소 수를 나타냄
[동작방식]
- 균형을 유지하면서 데이터를 추가 및 삭제한다
- 탐색 시 루트 노트부터 시작하여 키 값을 비교하고, 적절한 자식 노드로 이동하여 탐색을 반복한다
- 삽입 및 삭제 작업도 루트에서 시작하여 리프 노드까지 이동하며 필요한 경우 노드를 분할하거나 병합하여 균형을 유지한다

**B+트리**
-> B-트리의 변형, 리프노드에만 키 값이 저장되고, 내부 노드는 키 값만 가지고 있다
-> 모든 키 값은 리프 노드에 저장된다. 내부 노드는 키 값만 가지고 있어 데이터 접근 시간을 줄여준다.
-> 리프노드는 오름차순으로 연결 리스트 형태로 연결되어 있다. 이를 통해 범위 검색이 효율적으로 수행 가능
[동작방식]
- 균형을 유지하면서 데이터를 추가, 삭제하고 검색한다
- 리프 노드를 따라가며 탐색을 수행하며, 범위 검색 시 연결 리스트 형태로 연결된 리프 노드들을 순차적으로 탐색한다
- 내부 노드는 키 값만 가지고 있으며, 탐색에 사용된다

인덱스 종류

• 단일 컬럼 인덱스 : 하나의 열에 대해 생성된 인덱스, 해당 열을 기준으로 데이터를 정렬하여 저장

CREATE INDEX IDX_NAME ON EMPLOYEE(NAME);

• 복합 인덱스 : 두 개 이상의 열에 대해 생성된 인덱스, 여러 열의 조합을 기준으로 데이터를 정렬하여 저장

CREATE INDEX IDX_ORDER_DATE_CUSTOMER ON ORDER(ORDERDATE, CUSTOMERID);

• 고유 인덱스 : 중복된 값을 허용하지 않는 인덱스, 특정 열에 대해 고유한 값만 인덱싱한다.

CREATE UNIQUE INDEX IDX_PRODUCT_CODE ON PRODUCT(PRODUCTCODE);

• 비트맵 인덱스 : 열의 각 값에 대해 비트맵을 생성하여 인덱싱하는 방식, 특정 값에 해당하는 행을 빠르게 탐색 가능 → 카디널리티(고유한 값의 수)가 낮은 경우에 효과적임

CREATE BITMAP INDEX IDX_PAYMENT_STATUS ON ORDER(PATMENTSTATUS);

//비트맵 (Bitmap)
각 비트가 특정 값 또는 상태를 나타내는 방식
이전 비트맵은 0 또는 1로 구성되어 있으며, 여러 개의 비트가 모여 비트 배열을 형성한다 
각 비트는 특정한 의미를 가지며, 비트맵은 이러한 비트의 배열로 구성되어 있다

비트맵을 사용하면 많은 양의 데이터를 간결하고 표현하고 빠르게 처리할 수 있도록 한다. 
비트맵을 통해 특정 값의 존재 여부를 나타내거나, 특정 값의 조합을 표현하는데 사용된다. 

 

조인 수행원리

: 데이터베이스에서 조인은 둘 이상의 테이블에서 데이터를 결합하여 새로운 결과 집합을 생성하는 작업이다 → 조인은 데이터베이스 쿼리에서 매우 일반적으로 사용되며, 효율적으로 수행되어야 한다

조인 수행 방법

• 루프 조인(Nested Loop Join):
  • 가장 기본적인 조인 알고리즘으로, 한 테이블의 각 행을 다른 테이블의 모든 행과 비교하여 일치하는 행을 찾는다
  • 가장 왼쪽에 있는 테이블(드라이빙 테이블)의 각 행에 대해 오른쪽 테이블(프로브 테이블)을 순차적으로 스캔하여 일치하는 행을 찾는다
• 해시 조인(Hash Join):
  • 큰 데이터셋을 조인할 때 사용되는 알고리즘으로, 해시 함수를 사용하여 특정 열 값을 해시화하고 해시 테이블에 저장한다
  • 두 테이블을 스캔하여 각 행의 해시 값을 계산하고, 해시 테이블을 사용하여 일치하는 행을 찾는다
• 정렬 병합 조인(Sort Merge Join):
  • 두 테이블이 이미 정렬되어 있을 때 사용되는 알고리즘으로, 각 테이블을 정렬한 후에 정렬된 순서로 병합한다
  • 각 테이블을 정렬하고, 두 테이블의 첫 번째 행을 비교하여 일치하는 행을 찾습니다. 일치하는 경우 결과 집합에 추가하고, 다음 행을 비교한다

조인 수행 순서

• 데이터베이스 옵티마이저는 쿼리를 실행할 때 조인을 어떤 순서로 수행할지 결정
• 옵티마이저는 다양한 요소를 고려하여 가장 효율적인 조인 순서를 결정 이 요소에는 인덱스의 유무, 통계 정보, 조인 테이블의 크기 등이 포함됨
• 조인 순서를 결정하는 것은 매우 중요하며, 적절한 인덱스 사용 및 조인 알고리즘 선택을 통해 성능을 향상시킬 수 있다

조인 유형에 따른 수행 원리

• 내부 조인(Inner Join): 두 테이블 간의 일치하는 행만 반환
• 외부 조인(Outer Join): 일치하지 않는 행도 포함하여 결과를 반환
• 교차 조인(Cross Join): 두 테이블의 모든 가능한 조합을 반환