Computer Science/Database
-
데이터베이스의 Sorting(정렬) 알고리즘 (External Sort-Merge)Computer Science/Database 2023. 1. 9. 08:20
알고리즘 중에는 다양한 정렬 알고리즘들이 있다. 데이터베이스에서는 일반적인 정렬 알고리즘을 사용하기에는 데이터베이스의 데이터의 크기가 너무 크다. 그래서 데이터베이스에서는 메모리에 데이터를 다 못 올릴 것이다. 그럼 어떻게 정렬을 해야 할까?? 데이터베이스에서 정렬은 어떤 방식으로 이루어지는지 알아보자. 데이터베이스에서는 External Sort-Merge 알고리즘을 사용한다. 그럼 External Sort-Merge 알고리즘에 대해 알아보자. 일어나는 과정은 크게 두 단계로 이루어진다. 첫 번째로 'runs'라고 하는 것으로 분할을 하고, 두 번째로 merge하는 두 단계이다. (메모리에 한 번에 올려서 정렬할 수 없기 때문에 runs로 나누는 것이다) 첫 번째 runs를 생성하는 과정을 살펴보자 (1..
-
Oracle SQL 쿼리 튜닝 실습 2편 - JoinComputer Science/Database 2023. 1. 5. 21:24
이번에는 Join문이 있는 SQL 쿼리를 튜닝 하는 것에 대해 알아보자. test data에는, Orders 테이블은 1,048,575 개의 row, Customers 테이블은 17,416 개의 row를 가지고 있다. 초기에는 index도 없고, PK도 없고 FK도 설정되지 않은 상태이다. 아래와 같은 SQL을 실행한다고 가정하자. SELECT o.order_id, c.customer_name FROM orders o INNER JOIN customers c ON o.customer_id = c.customer_id; Execution Plan을 확인해보자 Hash Join이 사용된 것을 알 수 있다. 또한, 두 테이블 모두 Full scan을 하고 있다. (Oracle에서는 비교적 큰 데이터를 join..
-
Oracle SQL 쿼리 튜닝 실습 1편Computer Science/Database 2023. 1. 5. 20:46
먼저 이론상 설명을 간략하게 하면 쿼리 최적화는 cost based optimization과 heuristic optimization으로 나눌 수 있다. cost based optimization은 equivalence rules를 이용해 논리적으로 같은 동작을 하는 SQL expression들을 만든다. 그리고 그 중에서 가장 cost가 적은 plan을 정한다. 그럼 실습을 해보자 참고로 Oracle 12c 버전을 가지고 실습을 진행하였으며 SQL Developers 툴을 활용하였다. Oracle Execution Plan Oracle에서는 EXPLAIN PLAN FOR을 SQL 쿼리 앞에 붙이거나 F10 키를 누르면 execution plan을 확인할 수 있다. 예시로, execution plan을 ..
-
[SQL Join 시리즈2] 데이터베이스 Hash JoinComputer Science/Database 2023. 1. 5. 04:06
SQL 에는 크게 3가지 조인 방식이 있다. 1. nested loop join 2. hash join 3. merge join 이번에는 그 중에서 Hash Join에 대해 살펴볼 것이다. 먼저 아래 Hash Join 사진을 보고 이해해보자 relation r과 s에 대해 hash함수를 적용해서 각 tuple들을 파티션으로 나눈다. 그렇게 되면, 단지 r relation의 i번째 파티션은 s relation의 i번째 파티션과 비교하면 된다. 그 이유는 조금만 생각해보면 알 수 있는데, r tuple과 s tuple 의 값이 같아야만 join이 가능할 것이기 때문이다. (여기서 Hash Join은 equi join과 natural join일 때만 적용이 가능하다는 것을 알 수 있다!) 그럼 이제, r과 s..
-
[SQL Join 시리즈1] 데이터베이스 Nested Loop JoinComputer Science/Database 2023. 1. 4. 03:12
SQL 에는 크게 3가지 조인 방식이 있다. 1. nested loop join 2. merge join 3. hash join 이번에는 그 중에서 nested loop join에 대해 살펴볼 것이다. Nested loop join nested loop join는 말 그대로 중첩 반복 조인이다. pseudocode를 살펴보자 테이블 r의 tuple을 반복하고, 테이블 s의 tuple을 반복해서 join이 가능한지 확인한다. 여기서 테이블 r을 바깥쪽이기 때문에, outer table(driving table) 테이블 s는 안쪽이기 때문에, inner table(driven table) 이라고 부른다. 매번 튜플들에 대해서 join 조건이 만족하는지 확인하기 때문에 비싼 연산이다. Cost를 계산해보자 (..
-
[인덱스 시리즈3] 데이터베이스 Bitmap IndexComputer Science/Database 2023. 1. 3. 22:00
여러 개의 search key으로 SQL 쿼리를 수행할 때 효율적인 Bitmap Index에 대해 살펴 보려고한다. 먼저, Bitmap Index란 무엇일까? 간단히 말해서 칼럼의 값들을 bit의 배열로 나타낸 것이다. 아래 예시를 보면서 더 자세히 알아보자 예시 예를 들어, 아래와 같은 테이블이 있다고 하자. 이 테이블의 gender 칼럼을 bitmap으로 나타낸다면 아래와 같이 나타낼 수 있다. M 10010 F 01101 income_level을 bitmap으로 나타낸다면 아래와 같이 나타낼 수 있다. L1 10100 L2 01000 L3 00001 L4 00010 L5 00000 즉, 좀 더 자세히 설명하자면 비트맵에서 1은 해당 위치의 record가 그 value를 가지고 있다는 뜻이고, 0은 ..
-
[인덱스 시리즈2] 데이터베이스 B+Tree IndexComputer Science/Database 2023. 1. 3. 04:38
이번에는 B+Tree index에 대해 알아보자 먼저 B+Tree index 예시 사진을 보자 구조를 살펴보면, 위의 Root node, Internal nodes, Leaf nodes를 합쳐서 B+Tree index라고 한다. Srinivasan, Wu, Mozart와 같이 이름으로 index가 설정되어 있는 상황이다. (45565, Katz, Comp.Sci,75000) 에 해당하는 행을 찾는 상황을 생각해보자 그럼 위의 사진에서 Root node의 Mozart 이전 포인터, Internal nodes의 Gold 다음 포인터, Leaf nodes의 Gold 다음 포인터로 Katz를 찾을 수 있다. 여기서 중요한 것은 총 3번에 거쳐서 행을 찾는다는 것이다. 여기서 B+트리의 중요한 특징이 나오는데 B..
-
[인덱스 시리즈1] 데이터베이스 Hash Index(해시 인덱스)Computer Science/Database 2023. 1. 3. 03:51
개요 해싱하는 방법에는 먼저 static hashing이 있다. 하지만 데이터베이스 분야에서는 static hashing 기법은 거의 사용하지 않는다. 그 이유로는, 만약 고정된 해싱 함수가 있을 때, 데이터베이스의 크기는 늘기도 하고 줄기도 한다. 처음부터 Bucket의 개수를 크게 잡으면 => 공간 낭비가 심하다. 처음부터 Bucket의 개수를 작게 잡으면 => Bucket Overflow가 너무 많이 발생한다. 따라서 버킷의 개수와 해시함수를 유동적으로 바꿀 수 있을까? 개발자들은 고민을 하였다. 첫 번째, 주기적으로 새로운 해싱함수로 파일들을 재조직하는 방법이 있다. 하지만 매번 새로운 해싱함수로 재조직하는 방법은 너무 비싼 연산이다. 두 번째는, bucket의 개수를 유동적으로 조절하는 방법이 ..