[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급 개발자로 - #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..
[Database] DBA급 개발자로 - #6 Hash Table
2022. 9. 4. 17:07
Database/DBA급 개발자로
이전 포스팅에서 DBMS가 디스크의 데이터를 메모리의 버퍼 풀에 어떻게 로드해서 사용하는지와 버퍼 풀에 로드된 페이지를 제거하는 여러 정책에 대해 살펴봤습니다. 이번 포스팅에서는 버퍼 풀에 로드된 페이지를 효과적으로 읽고 쓰기 위해서 사용하는 자료구조인 Hash table에 대해 살펴보겠습니다. Hash Table 해시 테이블은 배열을 활용해 정렬되지 않은 key와 value를 저장하는 자료구조입니다. Key에 해시함수를 적용한 결괏값을 사용해서 해당 key와 value를 저장할 배열의 offset을 구할 수 있습니다. DBMS에서 사용되는 해시 테이블에 대해 알아보겠습니다. Static Hash Table 저장하고자 하는 데이터 수를 N이라 할 때, 길이 N의 배열을 사용하는 해시 테이블입니다. 대표적..
[Database] DBA급 개발자로 - #5 Buffer Pools
2022. 9. 3. 23:13
Database/DBA급 개발자로
이전 포스팅에서 DBMS가 데이터를 어떻게 디스크에 저장하는지 살펴봤습니다. 이번 포스팅에서는 디스크에 저장된 데이터를 메모리에 어떻게 적재해서 사용하는지 살펴보겠습니다. Buffer Pool 데이터베이스 버퍼 풀은 데이터베이스 시스템에서 사용하는 메모리 공간을 의미합니다. 이 공간은 데이터베이스 시스템이 일반적으로 사용하는 데이터를 임시로 저장하는 데 사용됩니다. 데이터베이스 버퍼 풀은 데이터를 읽거나 쓸 때 자주 사용되는 데이터를 미리 읽거나 쓰는 것을 돕습니다. 이렇게 하면 데이터베이스 시스템이 자주 사용하는 데이터를 빠르게 읽고 쓸 수 있으며, 이를 통해 전체적인 성능을 향상할 수 있습니다. 버퍼 풀은 프레임(frame)의 배열 형태로 구성됩니다. 디스크의 페이지는 버퍼 풀의 프레임에 적재돼서 활..