[Database] DBA급 개발자로 - #14 비용 기반 쿼리 최적화
2022. 11. 1. 17:55
Database/DBA급 개발자로
이전 포스팅에서는 규칙 기반(heuristics / rules) 쿼리 최적화에 대해 살펴봤습니다. 이번 포스팅에서는 비용 기반 쿼리 최적화에 대해 살펴보겠습니다. Cost Model Component 쿼리 수행 비용에는 어떤 항목이 포함되는지 살펴보겠습니다. Physical cost CPU cycle I/O 횟수 RAM 사용량 Logical cost 각 operator에 의해 반환되는 데이터의 크기 여러 operator가 독립적으로 실행될 수 있는지 여부 Algorithm 알고리즘의 복잡도 위의 항목 외에도 다양한 요인에 의해 쿼리를 실행하는 비용에 포함될 수 있습니다. DBMS는 데이터베이스의 통계(statistics)를 통해서 논리적인 비용(logical cost)을 측정할 수 있습니다. DBMS의 ..
[Database] DBA급 개발자로 - #13 Rule based 쿼리 최적화
2022. 9. 15. 16:22
Database/DBA급 개발자로
이전 포스팅에서는 쿼리 요청을 어떻게 병렬 처리하는지 살펴봤습니다. 이번 포스팅에서는 쿼리를 최적화할 수 있는 방법에 대해 살펴보겠습니다. Query Optimization 쿼리는 다양한 방법으로 최적화할 수 있습니다. 첫 번째 방법은 잘못됐거나 비효율적인 쿼리 문장을 제거하는 heuristic / rule 방식의 최적화 방법이 있습니다. 두 번째 방법은 쿼리 수행에 필요한 예상 비용을 비교해서 비용이 가장 작은 쿼리 플랜을 선택하는 cost based 방법이 있습니다. 이번 포스팅에서는 heuristic / rule 기반의 최적화 방식에 대해 살펴보겠습니다. Relational Algebra Equivalance Relational algebra 표현식이 서로 다르더라도 결괏값이 동일하면 해당 rela..
[Database] DBA급 개발자로 - #12 Query Processing 2/2
2022. 9. 13. 12:10
Database/DBA급 개발자로
이전 포스팅에서 DBMS가 쿼리를 어떻게 처리하는지 살펴봤습니다. 이번 포스팅에서는 쿼리의 병렬 처리 방법에 대해 살펴보겠습니다. Process Model 쿼리를 병렬로 처리할 수 있는 process model에 대해 살펴보겠습니다. 쿼리 요청을 처리하는 DBMS 내부의 컴포넌트를 worker라고 합니다. Process per DBMS Worker 각각의 worker는 독립된 프로세스 위에서 동작합니다. 운영체제 스케쥴러에 의해 작업이 할당되고 데이터를 공유할 때 shared memory를 활용합니다. 독립된 프로세스 위에서 동작하므로 하나의 worker에 에러가 발생하더라도 전체 시스템이 다운되지 않습니다. Process Pool 프로세스를 미리 만들어서 pool에 보관하고 요청이 발생하면 사용 가능한..
[Database] DBA급 개발자로 - #11 Query Processing 1/2
2022. 9. 12. 09:47
Database/DBA급 개발자로
이전 포스팅에서 join이 어떻게 처리되는지 살펴봤습니다. 이번 포스팅에서는 쿼리 처리 모델에 대해 살펴보겠습니다. Query Processing Model DBMS가 쿼리를 어떻게 처리할 것인지는 query processing model에 의해 결정됩니다. 대표적으로 iterator model, materialization model, vectorized / batch model이 존재합니다. Iterator Model Java의 Iterator의 동작 방식과 유사합니다. DBMS의 iterator model의 모든 operator는 next() 함수를 구현합니다. next() 함수는 하나의 tuple 또는 null 값을 반환합니다. 각각의 operator는 child operator의 next() 함..
[Database] DBA급 개발자로 - #10 Join Algorithm
2022. 9. 11. 16:29
Database/DBA급 개발자로
이전 포스팅을 통해 Sorting과 Aggregation이 어떻게 동작하는지 살펴봤습니다. 이번 포스팅에서는 Join algorithm에 대해서 살펴보겠습니다. Join DBMS는 정규화를 통해 데이터의 중복을 제거합니다. 연관된 데이터가 정규화로 인해 서로 다른 테이블에 있다면 join을 통해 함께 조회할 수 있습니다. 어떤 join 알고리즘이 존재하는지 살펴보고 각각의 join 알고리즘 성능을 비교해보겠습니다. Join 알고리즘의 성능은 join 시 수행되는 전체 I/O 비용을 기준으로 측정합니다. 사용할 테이블과 join을 수행하는 쿼리는 다음과 같습니다. select s.name, c.name from student s join class c on s.class_id = c.id 위 사진은 stu..
[Database] DBA급 개발자로 - #9 Sorting & Aggregation
2022. 9. 9. 10:21
Database/DBA급 개발자로
이전 포스팅에서 인덱스의 동시성 처리를 어떻게 수행하는지 살펴봤습니다. 이번 포스팅에서는 sorting과 aggregation이 어떻게 처리되는지 살펴보겠습니다. Sorting 쿼리의 결괏값은 기본적으로 정렬되지 않습니다. 쿼리의 결과를 정렬시키기 위해서는 정렬 작업이 필요합니다. 명시적으로 정렬을 수행(ORDER BY)하거나 쿼리 특성상 정렬이 필요한 경우가 존재합니다(DISTINCT, GROUP BY). 만약 쿼리 결과 전체를 메모리에 올릴 수 있는 크기라면 일반적인 정렬 알고리즘을 사용할 수 있습니다(Quick sort 등). 하지만 쿼리 결과 전체가 메모리에 로드할 수 없는 상황이 존재하므로 중간 결과를 디스크에 저장할 수 있는 정렬 알고리즘이 필요합니다. External Merge Sort 정렬..
[Database] DBA급 개발자로 - #8 Index Concurrency Control
2022. 9. 7. 08:33
Database/DBA급 개발자로
이전 포스팅에서 B+Tree에 대해 살펴봤습니다. 이번 포스팅에서는 인덱스 동시성 문제를 어떻게 해결하는지 살펴보겠습니다. Concurrency Control 여태까지 논의했던 B+Tree는 단일 스레드 환경에서만 정상적으로 동작합니다. 멀티 스레드 환경에서는 두 개 이상의 스레드가 동일한 노드에 동시에 접근할 수 있습니다. DBMS는 concurrency control protocol을 통해 동시에 접근되는 데이터를 물리적 또는 논리적으로 보호합니다. 물리적 단위에서 데이터를 보호하는 것은 메모리 상의 데이터가 일관된 상태를 유지할 수 있도록 보호하는 것입니다. 논리적 단위에서 데이터를 보호하는 것은 논리적으로 스레드가 접근할 수 있는 데이터에 접근할 수 있도록 보장하고 접근할 수 없는 데이터는 접근할..
[Database] DBA급 개발자로 - #7 B+Tree
2022. 9. 6. 19:58
Database/DBA급 개발자로
이전 포스팅에서 hash table에 대해 살펴봤습니다. 이번 포스팅을 통해 인덱스에 활용되는 B+Tree 자료구조에 대해 살펴보겠습니다. B+Tree B+Tree는 O(log n)의 시간 복잡도로 삽입, 삭제 및 검색이 가능한 자료구조입니다. 이진 탐색 트리와 다르게 하나의 부모 노드는 여러 자식 노드를 가질 수 있습니다. B+Tree의 특징은 다음과 같습니다. - Perfect balance : 모든 leaf node는 트리 내 동일한 깊이를 가집니다. - 노드가 최대 M개의 자식 노드를 가질 수 있다고 가정하면, 각 노드는 최소 (M/2 -1) ~ (M-1) 개의 키를 가집니다. - Inner node가 k 개의 키를 저장한다고 가정하면 총 k+1 자식 노드(non-null)를 가집니다. B+Tre..