📒

노트 템플릿 시리즈

수업

Database Study

주제

5 more properties

참고

정리

데이터베이스 내부 시스템

스캔 방식

key vs non-key column

인덱스 스캔 vs 인덱스 only 스캔

Bloom Filters

B-Trees vs B+Trees

ㅇㅇ

정리

NOTE

•

Non-repeatable Reads는 한 트랜잭션에서 같은 데이터를 두 번 읽었을 때, 첫 번째와 두 번째 읽기 사이에 다른 트랜잭션이 그 데이터를 수정하고 커밋하여 두 번 읽은 결과가 서로 다르게 나타나는 현상을 말합니다. 예를 들어, 한 트랜잭션이 고객의 계좌 잔액을 읽은 후, 다른 트랜잭션이 그 계좌의 잔액을 변경하고 커밋한 후, 원래 트랜잭션이 다시 잔액을 읽으면 변경된 잔액을 보게 됩니다.

Phantom Reads

Phantom Reads는 한 트랜잭션이 같은 쿼리를 여러 번 실행했을 때 새로 추가되거나 삭제된 행이 "유령처럼" 나타나는 현상을 말합니다. 예를 들어, 한 트랜잭션이 특정 조건을 만족하는 모든 행을 쿼리할 때, 다른 트랜잭션이 새로운 행을 삽입하고 커밋하면, 원래 트랜잭션의 동일한 쿼리 실행 결과에 그 새로운 행이 포함됩니다. 이는 조회 조건에 새로운 데이터가 추가되어 결과 집합에 변화가 생기는 것을 의미합니다.

Isolation level

격리 수준을 조정함으로써 관리할 수 있습니다. 예를 들어, SQL 표준에서는 다음 네 가지 격리 수준을 제공합니다:

Read Uncommitted: 가장 낮은 수준으로, 모든 read phenomena가 발생할 수 있습니다. (트랜잭션의 격리가 거의 없지만 가장 빠르다.)

Read Committed: Dirty Reads를 방지하지만, Non-repeatable Reads와 Phantom Reads는 발생할 수 있습니다.(가장 널리 사용된다. 트랜잭션이 완료된 변화만 감지가능)

Repeatable Read: Non-repeatable Reads를 방지하지만, Phantom Reads는 발생할 수 있습니다.(다시 읽어도 값이 변하지 않는레벨, 한 트랜잭션에 데이터를 읽을 때 수정하지 못하도록 보장한다.)

SnapShot: 모든 읽기 문제에서 벗어날 수 있다. 모든것이 버전화되어 있으며, 트랜잭션이 시작될 때 데이터베이스의 스냅샷을 생성하고, 트랜잭션은 이 스냅샷을 기준으로 데이터를 읽는다.

•

데이터의 여러 버전을 저장한다.

Serializable: 가장 높은 격리 수준이며, 이 수준에서는 트랜잭션이 마치 다른 트랜잭션이 존재하지 않는 것처럼 독립적으로 실행되며, 동시성 실행의 결과가 순차적 실행과 동일하게 보장된다.

•

각 DMS는 이러한 격리레벨 구현을 다르게 한다.

•

각 DBMS의 격리 수준 구현 차이

◦

데이터베이스 관리 시스템(DBMS)마다 격리 수준을 다르게 구현합니다.

•

비관적 격리(Pessimistic Isolation)

◦

행 레벨, 테이블 레벨, 페이지 레벨의 잠금을 사용하여 업데이트가 손실되는 것을 방지합니다.

•

낙관적 격리(Optimistic Isolation)

◦

잠금을 사용하지 않고, 데이터가 변경되었는지를 추적하여 변화가 있으면 트랜잭션을 실패하게 합니다.

•

반복 가능 읽기(Repeatable Read)

◦

읽는 행을 "잠금"하여 반복 가능 읽기를 구현합니다. 그러나 많은 행을 읽을 경우 비용이 많이 들 수 있습니다.

◦

PostgreSQL은 스냅샷을 사용하여 반복 가능 읽기를 구현합니다. 이로 인해 반복 가능 읽기에서 유령 읽기 현상이 발생하지 않습니다.

•

직렬 가능(Serializable)

◦

주로 낙관적 동시성 제어로 구현되며, 필요에 따라 SELECT FOR UPDATE를 사용하여 비관적으로 구현할 수도 있습니다.

Consistency(일관성)

특정 DB에서는 일관성을 희생해서 속도를 증가시킨다.

일관성 데이터

•

유저가 정의한 데이터

•

외래키에 참조한

•

원자적 데이터

•

격리수준

•

변경 사항의 즉시 반영 여부

◦

"트랜잭션이 변경을 커밋하면 새로운 트랜잭션이 즉시 그 변경을 볼 수 있을까요?" 라는 질문을 포함하고 있습니다. 이는 트랜잭션의 격리 수준과 데이터베이스의 일관성 모델에 따라 달라질 수 있습니다.

•

시스템 전체에 미치는 영향

◦

변경 사항이 시스템 전체에 어떻게 영향을 미치는지에 대한 논의입니다. 이는 데이터베이스의 설계와 구성에 따라 다르게 나타날 수 있습니다.

•

관계형 및 NoSQL 데이터베이스의 영향

◦

관계형 데이터베이스와 NoSQL 데이터베이스 모두 이러한 일관성 문제에서 영향을 받을 수 있습니다. 각 데이터베이스 유형은 이 문제를 다르게 처리할 수 있습니다.

•

최종 일관성(Eventual Consistency)

◦

최종 일관성은 일부 데이터베이스 시스템에서 사용하는 일관성 모델로, 시간이 지남에 따라 모든 복제본이 최종적으로 일관된 상태에 도달하게 됩니다. 이 모델은 즉시 일관성을 제공하지 않지만, 시스템의 가용성과 병행성을 향상시킬 수 있습니다.

참조 무결성에 의해 시행되는 2가지 유형의 데이터

•

궁극적인 일관성은 없다

읽기의 일관성은 값이 업데이트되었을때 이전버전을 읽는 경우

•

복제가 필요

내구성

비휘발성 시스템 스토리지 시스템의 DB에 대해 클라이언트가 부여한 권한의 양, 영구적으로 만드는 과정

모든 내용이 저장되므로 중간에 에러가 생겨도 데이터가 남아있다.

내구성을 갖추려면 디스크에 써야하며 이는 느리다.

•

커밋된 트랜잭션 내용을 저장장치에 저장한다.

•

내구성 기술: 

◦

WAL(Write ahread log),

◦

비동기 스냅샷

◦

AOF

WAL - 디스크에 데이터를 저장하는건 비용이 있다.

•

디스크에 대량의 데이터 기록 비용

◦

디스크에 많은 양의 데이터를 기록하는 것은 비용이 많이 듭니다. 이 데이터에는 인덱스, 데이터 파일, 컬럼, 행 등이 포함될 수 있습니다.

•

WAL 기술 사용 이유

◦

데이터베이스 관리 시스템(DBMS)은 변경 사항을 압축된 버전으로 지속하기 위해 WAL, 즉 선쓰기 로그 세그먼트를 사용합니다. 이는 효율적인 데이터 기록 및 복구 프로세스를 가능하게 합니다.

WAL의 원리

•

트랜잭션의 변경사항을 먼저 로그에 기록한다. 이 로그는 데이터가 실제로 디스크의 데이터 파일에 기록되기전에 완료도니다.

•

데이터 손실 방지: 시스템 장애가 발생하더라도, 이 로그를 사용하여 마지막 일관된 상태로 데이터를 복구한다.

•

데이터를 실시간으로 디스크에 기록하는 대신, 주기적 배치 처리함으로써 입출력 작업을 최적화한다.

•

로그는 디스크에 쓰이며, 내구성을 봥하는 핵심 기능입니다.

운영체제 캐시

•

OS에서 발생하는 캐시는 일반적으로 OS캐시에 들어가며 디스크보다 빠르다.

•

OS 캐시를 거치므로, OS에 문제가 생기는 경우 데이터 손실이 발생할 수 있따.

•

fsync는 OS 명령어로, 쓰기 작업을 강제로 디스크에 기록하도록하며 이로인해 속도가 느려집니다.

CREATE TABLE PRODUCTS
(
    pid       serial primary key,
    name      text,
    price     float,
    inventory integer
);

CREATE TABLE SALES
(
    saleid serial primary key,
    pid integer,
    price float,
    quantitiy integer
);

insert into products(name, price, inventory) values ('Phone', 999.99, 100);

SELECT * FROM PRODUCTS;

-- 원자성
BEGIN TRANSACTION ;
SELECT * FROM PRODUCTS;

UPDATE PRODUCTS SET inventory = inventory - 10;

INSERT INTO SALES(pid, price, quantitiy) values (1, 999.99, 10);

SELECT * FROM SALES;
SELECT * FROM PRODUCTS;

COMMIT;

ROLLBACK;


-- 격리성
insert into products(name, price, inventory) values ('Earbuds', 99.99, 160);
INSERT INTO SALES(pid, price, quantitiy) values (1, 999.99, 5);
INSERT INTO SALES(pid, price, quantitiy) values (1, 999.99, 5);
INSERT INTO SALES(pid, price, quantitiy) values (2, 99.99, 10);
INSERT INTO SALES(pid, price, quantitiy) values (2, 89.99, 10);
INSERT INTO SALES(pid, price, quantitiy) values (2, 79.99, 20);

BEGIN TRANSACTION;
SELECT PID, COUNT(PID)
FROM SALES
GROUP BY PID;

SELECT PID, PRICE, quantitiy
FROM SALES;



ROLLBACK;


BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT PID, COUNT(PID)
FROM SALES
GROUP BY PID;

SELECT PID, PRICE, quantitiy
FROM SALES;

COMMIT;

ROLLBACK;


-- 유령 읽기 현상
SELECT * FROM SALES;

BEGIN TRANSACTION ;
SELECT * FROM SALES;
SELECT PID, SUM(PRICE) FROM SALES GROUP BY PID;
SELECT PID, SUM(PRICE) FROM SALES GROUP BY PID;
SELECT * FROM SALES;
ROLLBACK ;


BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SELECT * FROM SALES;
COMMIT;

BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT * FROM SALES;
COMMIT;


-- Serializable vs Repeatable Read
CREATE TABLE TEST
(
    id serial primary key,
    t text
);

INSERT INTO TEST (t) VALUES ('b');
INSERT INTO TEST (t) VALUES ('b');
INSERT INTO TEST (t) VALUES ('a');
INSERT INTO TEST (t) VALUES ('a');

SELECT * FROM TEST;

BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
UPDATE TEST SET t = 'a' WHERE t = 'b';
SELECT * FROM TEST;
COMMIT;

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
UPDATE TEST SET t = 'a' WHERE t = 'b';
SELECT * FROM TEST;
COMMIT;
SQL
복사

-- 격리성
BEGIN TRANSACTION;

INSERT INTO SALES (pid, price, quantitiy)
VALUES (1, 999.99, 10);

UPDATE products SET inventory=inventory - 10 WHERE pid = 1;

COMMIT;

SELECT PID, COUNT(PID)
FROM SALES
GROUP BY PID;

SELECT PID, PRICE, quantitiy
FROM SALES;

BEGIN TRANSACTION;

INSERT INTO PRODUCTS(name, price, inventory)
values ('TV', 3000, 10);

COMMIT;

-- 유령 읽기
INSERT INTO SALES (PID, PRICE, quantitiy) VALUES(1, 15, 10);
INSERT INTO SALES (PID, PRICE, quantitiy) VALUES(1, 15, 20);
INSERT INTO SALES (PID, PRICE, quantitiy) VALUES(1, 15, 30);

-- Serializable vs Repeatable Read
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
UPDATE TEST SET t = 'b' WHERE t = 'a';
SELECT * FROM TEST;
COMMIT;

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
UPDATE TEST SET t = 'b' WHERE t = 'a';
SELECT * FROM TEST;
COMMIT;
ROLLBACK;
SQL
복사

Serializable vs Non-repetable

•

이 시나리오에서는 두 개의 트랜잭션이 'aa'와 'bb'를 다루고 있습니다.

•

첫 번째 트랜잭션은 'aa'를 'bb'로 변경하고, 두 번째 트랜잭션은 'bb'를 'aa'로 변경합니다.

•

결과적으로, 첫 번째 트랜잭션이 커밋 후 두 번째 트랜잭션이 읽기를 수행하면, 변경된 결과인 'bb'와 'aa'가 반영됩니다.

•

이것은 Non-Repeatable Read를 보여줍니다. 즉, 한 트랜잭션 내에서 동일한 데이터를 여러 번 조회할 때 일관되지 않은 결과를 받을 수 있습니다.

•

Repeatable Read는 주로 개별 행에 대한 락을 걸어 트랜잭션이 읽은 데이터의 일관성을 유지합니다.

•

두 개의 트랜잭션에서 첫 번째 트랜잭션이 'aa'를 'bb'로 변경하고자 하고, 두 번째 트랜잭션이 'bb'를 'aa'로 변경하고자 합니다.

•

"Serializable" 격리 수준에서는 트랜잭션이 서로 독립적으로 실행되는 것처럼 보장되기 때문에, 첫 번째 트랜잭션의 결과가 두 번째 트랜잭션에 영향을 미치지 않습니다.

•

첫 번째 트랜잭션의 변경이 완료되고, 두 번째 트랜잭션이 시작될 때까지 기다려야 합니다. 첫 번째 트랜잭션이 완전히 커밋된 후에만 두 번째 트랜잭션이 실행됩니다.

•

결과적으로 첫 번째 트랜잭션은 'aa'와 'bb'를 서로 바꾸고, 두 번째 트랜잭션은 이를 다시 되돌려 'aa'와 'bb' 상태로 만듭니다.

•

Serializable에서는 더 넓은 범위의 데이터에 대해 락을 걸어 트랜잭션 간의 완전한 격리를 보장합니다. 이것은 트랜잭션의 동시성을 크게 제한할 수 있으며, 특히 복잡한 쿼리나 많은 데이터를 다루는 시스템에서는 성능 저하의 원인이 될 수 있습니다.

1. Serializable 격리 수준

•

가장 엄격한 격리 수준입니다. 트랜잭션이 실행되는 동안 다른 트랜잭션에서 데이터를 변경하거나 추가하는 것을 완전히 차단하여, 마치 트랜잭션이 순차적으로 실행되는 것처럼 보장합니다.

•

이 격리 수준에서는 Dirty Reads, Non-repeatable Reads, Phantom Reads 모두 방지됩니다.

•

Serializable 격리 수준을 사용하면 트랜잭션이 데이터베이스의 모든 변화를 추적하며, 필요에 따라 테이블 또는 범위 락을 사용하여 다른 트랜잭션의 접근을 차단합니다. 이는 동시성을 매우 제한할 수 있지만 데이터 일관성은 최대로 보장됩니다.

•

예를 들어, Serializable 격리 수준에서 SELECT * FROM SALES를 실행하면, 이 트랜잭션이 완료될 때까지 SALES 테이블은 다른 변경이나 삽입으로부터 보호받으며, 완전히 독립적으로 데이터를 읽습니다.

2. Repeatable Read 격리 수준

•

이 격리 수준은 한 트랜잭션이 데이터를 읽을 때 시작한 순간의 데이터 상태를 보장합니다. 즉, 트랜잭션 중에 다른 트랜잭션이 해당 데이터를 변경하더라도, 원래 트랜잭션에서는 변경사항이 반영되지 않습니다.

•

Repeatable Read는 Dirty Reads와 Non-repeatable Reads를 방지하지만, Phantom Reads는 방지하지 못합니다. 즉, 트랜잭션 도중 새로운 레코드가 삽입되는 경우, 이러한 새 레코드는 다음 조회에서 나타날 수 있습니다.

•

보통 Repeatable Read 격리 수준에서는 데이터베이스가 변경 사항을 로그에 기록하고, 오직 해당 로그를 통해서만 데이터 상태를 관리합니다(MVCC - 다중 버전 동시성 제어 방식을 사용할 수 있습니다).

•

예를 들어, SELECT * FROM SALES를 실행하고 다른 트랜잭션이 SALES 테이블에 새로운 판매 레코드를 추가하면, 원래의 트랜잭션에서는 그 새로운 레코드를 볼 수 없습니다.

요약

•

Serializable 격리 수준은 트랜잭션이 데이터베이스 내에서 완전히 독립적으로 실행되는 것을 보장하며, 모든 유형의 읽기 이상 현상을 방지합니다. 그러나 이로 인한 성능 저하가 발생할 수 있습니다.

•

Repeatable Read 격리 수준은 트랜잭션 동안 읽은 데이터의 일관성을 보장하지만, 새로운 데이터 삽입은 감지하지 못하는 Phantom Reads 현상은 방지하지 못합니다.

Eventual Consistency

일관적인 읽기와 데이터의 개념

분산 시스템에서 자주 사용되는 일관성 모델로, 궁극적으로 모든 데이터 복제본이 동일한 상태에 도달하게 됨을 보장한다.

•

시스템 변경이 발생 ⇒ 모든 노드(DB 복제본)에 전파되어 일관된 상태에 도달할때 까지 시간이 걸리지만 결국 동일한 데이터를 가진다.(일관성 지연)

•

높은 가용성

create table test (id integer)
insert into test (2);
 
begin transaction 1
t1 - set isolation level read committed
begin transaction 2
t2 - set isolation level repeatable read
 
t1 - select * from test;  -- READ COMMITED 격리수준, 2
t2 - insert into test (4);
t1 - select * from test; -- READ COMMITED 격리수준, 커밋되지 않은 데이터 못봄 2
t1 - insert into test (5);
t2 - select * from test; -- REPETABLE READ 격리수준, 2,4
t1 - commit;
t2 - select * from test; -- REPETABLE READ 격리수준, 팬텀 조회 (2,4, 5)
t2 - commit;
SQL
복사
| 2 | 2-4 | 2-4-5 (팬텀)

•

Repeatable Read 격리 수준은 트랜잭션이 어떤 값을 읽었을 때, 그 값이 트랜잭션 내에서 변경되지 않도록 보장합니다. 즉, 트랜잭션이 읽은 데이터는 트랜잭션이 끝날 때까지 동일하게 유지됩니다.

•

그러나 이 격리 수준은 **팬텀 읽기(Phantom Read)**를 완전히 방지하지는 않습니다. 팬텀 읽기란, 트랜잭션이 실행되는 동안 다른 트랜잭션이 새로운 행을 삽입할 때 발생하는 현상입니다.

•

설명에서 언급된 "5"라는 값은 Repeatable Read 트랜잭션 중에 커밋된 값입니다. 이 값은 처음에 트랜잭션에 의해 읽히지 않았으므로, 트랜잭션에서 "5"를 읽을 때 새로운 행으로 나타날 수 있습니다.

•

이는 모든 데이터베이스 시스템에서 동일하게 작동하는 것은 아니지만, PostgreSQL에서는 Repeatable Read 격리 수준이 팬텀 읽기를 방지하지 않기 때문에, 커밋된 "5"가 트랜잭션 중에 나타날 수 있습니다.

데이터베이스 내부 시스템

NOTE

테이블, Row_ID, Page, IO, Heap data strcure, Index data strcture b-tree,

•

ROW_ID: 특정 행을 고유하게 만드는 ID, 기본키 사용

•

PAGE: 페이지는 실제로 고정된 크기의 메모리 위치, 바이트 그룹으로 구성된 디스크 위치한다. 데이터베이스는 개별 행을 읽지 않고, 한 번의 IO 작업으로 하나 이상의 페이지를 읽는다.

◦

페이지의 크기는 DBMS에 따라 다르다.

◦

예시 이미지에서는 페이지가 3개의 행을 포함하며, 1001개의 행이있는 경우 333개의 페이지가 필요하다.

◦

이러한 페이지 설정이 DB의 속도와 관게 있다.

•

IO 작업이 적을수록 좋다.

•

만약 IO를 하는 경우, 특정 행을 선택하는것이 더 IO의 작업을 줄이므로 상대적으로 유리하다.

•

IO수를 줄이기 위해서, OS캐시를 사용할 수 있다.

heap

•

테이블이 모든 페이지와 함께 순서대로 저장되는 구조

•

heap에서 테이블의 모든 데이터(행, 열, 값)을 포함하며, 읽고 수정할때 heap에 접근한다.

•

heap 순회 비용이 많이들며 이를 위해 index를 사용하는것이 좋다.

index

•

index는 heap과 별개의 데이터 구조이며, heap에 있는 데이터를 가리키는 포인터를 포함한다.

•

인덱스는 전체 데이터를 포함하지 않고 일부 데이터를 포함하여 특정 값을 빠르게 검색한다.

•

인덱스에서 특정 값을 찾으면, 해당 값이 저장된 Heap의 위치를 파악할 수 있으며 인덱스에서 찾은 값을 바탕으로, 필요한 추가 정보를 Heap에서 가져온다.

•

인덱스는 Heap에서 어떤 페이지를 조회해야 하는지 정확히 알려준다.

•

대표적으로 B-Tree구조가 사용된다.

인덱스의 역할

인덱스는 DB에서 빠르게 검색하기 위해 쓰이며, 이미지는 EMP_ID열에 인덱스 생성

EMP_ID를 기준으로 정렬된 페이지를 보여주며,  각 값이 Heap에서 어느 페이지에 있는지를 가리켜 줍니다.

IO 작업

IO 1(인덱스 검색): 인덱스를 사용하여 원하는 EMP_ID가 포함된 페이지와 행을 찾는다.

IO 2(Heap 데이터 읽기): 인덱스에서 찾은 페이지와 행의 위치 정보를 바탕으로 정확한 데이터를 가져온다.

Heap 데이터 검색

•

Heap은 실제로 데이터가 저장된 곳이며, 인덱스는 Heap에 저장된 데이터를 직접 검색하는 대신 필요한 데이터가 저장된 페이지를 찾아준다.

•

ex) EMP_ID = 10을 찾는다면, Heap에서 Page 0에 있는 row_id 1을 찾아라.

인덱스가 없는 경우 1~10000까지 순차탐색

•

인덱스를 사용하는 경우, B-Tree를 사용해서 최소한의 탐색으로 EMP_ID가 검색이 가능하다.

행 vs 열 기반 데이터베이스

2개의 방식은 각 장단점이 있다. 디스크에 저장되는 방식이 다르다.

행 저장소

Row-Oriented Database (행 기반 데이터베이스)

장점:

•

행 기반(Row-Based): 데이터가 행 단위로 저장됩니다.

•

읽기/쓰기 최적화(Optimal for read/writes): 행 단위로 데이터를 읽고 쓰는 작업이 효율적입니다.

•

OLTP에 적합: 온라인 트랜잭션 처리(OLTP) 시스템에 적합합니다. 즉, 실시간으로 데이터를 자주 읽고 쓰는 애플리케이션에 유리합니다.

•

복합 열 쿼리에 효율적: 여러 열을 한 번에 읽는 쿼리에 효율적입니다.

단점:

•

압축 비효율(Compression isn’t efficient): 데이터 압축이 효율적이지 않을 수 있습니다.

•

집계 비효율(Aggregation isn’t efficient): 데이터를 집계하는 쿼리에 비효율적입니다.

Row-Oriented Database는 OLTP 시스템에 적합하며, 여러 열을 한꺼번에 읽어야 하는 작업에 효율적입니다.

안좋은 경우

좋은 경우

•

그림은 인덱스가 없는 경우로 보여준다.

•

테이블의 데이터가 디스크에 행 단위로 저장된다.

•

한번의 블록 IO 작업으로 테이블에서 여러 행을 가져온다.

•

특정 행을 찾기위해 여러번 IO 작업이 필요한데, 한 번 원하는 행을 찾으면 그 행에 포함된 모든 값을 사용할 수 있다. 하지만 그만큼 순차탐색에서 시간이 오래 걸린다.

⇒ 조회하는 컬럼이 많아질수록 비용이 비싸진다.

Column-Oriented Database (열 기반 데이터베이스)

장점:

•

열 기반(Column-Based): 데이터가 열 단위로 저장됩니다.

•

압축에 유리(Compress greatly): 같은 열의 데이터가 연속적으로 저장되기 때문에 압축 효율이 높습니다.

•

집계에 유리(Amazing for aggregation): 특정 열의 데이터만 빠르게 접근할 수 있어 집계 작업에 매우 효율적입니다.

단점:

•

쓰기 속도 저하(Writes are slower): 데이터를 열 단위로 저장하고 갱신하기 때문에 쓰기 속도가 느릴 수 있습니다.

•

OLAP에 적합: 온라인 분석 처리(OLAP) 시스템에 적합합니다. 대규모 데이터 분석 작업에 유리합니다.

•

복합 열 쿼리에 비효율적(Inefficient queries with multi-columns): 여러 열을 동시에 읽는 쿼리에 비효율적일 수 있습니다.

Column-Oriented Database는 OLAP 시스템에 적합하며, 데이터 압축과 집계 작업에서 뛰어난 성능을 발휘합니다.

1. Index-Organized Table (IOT) vs. Heap-Organized Table

•

Index-Organized Table (IOT): 이 테이블은 인덱스에 의해 정렬된 상태로 저장됩니다. Oracle에서는 이와 같은 테이블을 "Index-Organized Table"이라고 부르며, 이는 테이블이 인덱스와 함께 정렬되고 관리된다는 것을 의미합니다.

•

Heap-Organized Table: 이 테이블은 인덱스에 의해 정렬되지 않은 상태로, 데이터가 무작위로 저장됩니다. SQL Server에서는 이를 "Heap-Organized Table"이라고 합니다.

2. Primary Index (Clustered Index)

•

Primary Index (Clustered Index): SQL Server에서는 이를 클러스터드 인덱스라고 부르며, 이 경우 테이블 자체가 인덱스에 의해 정렬됩니다. Primary Key는 클러스터드 인덱스로 지정될 수 있으며, 이 경우 테이블의 데이터가 인덱스 순서에 맞게 정렬되어 저장됩니다.

•

클러스터드 인덱스는 테이블이 인덱스 순서대로 정렬되므로, 데이터 접근이 빠르지만, 하나의 테이블에 하나의 클러스터드 인덱스만 가질 수 있습니다.

3. Secondary Index

•

Secondary Index: 테이블의 데이터가 정렬되지 않은 상태로 저장될 때 사용됩니다. 이 인덱스는 테이블 외부에 별도의 구조로 관리되며, B-Tree와 같은 자료구조를 사용하여 특정 값에 대한 빠른 검색을 가능하게 합니다.

•

단점: Secondary Index는 테이블에서 원하는 데이터를 빠르게 찾을 수 있지만, 인덱스에 모든 데이터가 포함되어 있지 않기 때문에 최종적으로 해당 데이터를 찾기 위해 다시 테이블(Heap)로 돌아가야 합니다. 특히 SELECT *와 같은 쿼리에서는 모든 열 데이터를 가져와야 하므로, 인덱스만으로는 부족합니다.

4. PostgreSQL의 인덱스 구조

•

PostgreSQL에서는 기본적으로 모든 인덱스가 Secondary Index입니다. 즉, 테이블의 데이터가 별도의 정렬 없이 저장되며, 인덱스가 이 데이터를 가리키는 역할을 합니다.

•

PostgreSQL에서 Clustered Index를 만들 수 있는지에 대해 강사는 확신하지 못하지만, 테이블을 특정 인덱스에 따라 정렬(클러스터)하는 옵션이 있을 수 있다고 언급합니다.

Heap-Organized Table의 한계

•

Heap-Organized Table은 정렬되지 않은 테이블로, 데이터를 찾기 위해서는 모든 데이터를 순차적으로 검색해야 할 수 있습니다. 인덱스가 없는 경우 데이터 검색이 느려질 수 있습니다.

기본키, 보조키(인덱스, 보조인덱스)

•

기본키나 보조키에 대해 쿼리를 제공할때 어떻게 되는가?

•

쿼리 최적화를 해주는 힌트르 ㄹ준다?

•

테이블스페이스 또는 힙의 개념, 테이블 스페이스(힙)은 접근 속도강 일반적으로 느리다.

•

테이블은 기본적으로 정렬되어 있지 않다. 기본 키 개념을 추가하면 내부에서 클러스터링을 진행하며 클러스터링은 키를 중심으로 테이블을 구성해 정렬한다.

•

이렇게 하는 경우, 테이블 자체의 인덱스와 유사하며 클러스터형 인덱스라고 부른다. 

•

보조 키는 추가적인 외부 구조가 있다. B-Tree와 같은, 디렉토리에 대한 별도의 구조 생성, 해당 디렉토리로 이동해서 찾아내고, 행자체의 정보를 찾기 위해 힙으로 이동한다.

데이터베이스는 종종 고정 크기 페이지를 사용하여 데이터를 저장합니다. 테이블, 컬렉션, 행, 열, 인덱스, 시퀀스, 문서 등은 결국 페이지의 바이트로 끝납니다. 이런 방식으로 스토리지 엔진을 데이터 형식과 API를 담당하는 데이터베이스 프런트엔드와 분리할 수 있습니다. 게다가 모든 것이 페이지일 때 데이터를 읽고, 쓰고, 캐시하기가 더 쉬워집니다.

다음은 SQL Server 페이지 레이아웃의 예입니다.

SQL Server 페이지 레이아웃( 링크 ).

이 글에서는 데이터베이스 페이지의 개념, 데이터베이스 페이지를 디스크에서 읽고 쓰는 방법, 디스크에 저장하는 방법에 대해 알아보겠습니다. 마지막으로 Postgres의 페이지 레이아웃 예를 살펴보겠습니다.

페이지 풀

데이터베이스는 페이지에서 읽고 씁니다. 테이블에서 행을 읽을 때 데이터베이스는 행이 있는 페이지를 찾고 디스크에서 페이지가 있는 파일과 오프셋을 식별합니다. 그런 다음 데이터베이스는 OS에 페이지 길이에 대한 특정 오프셋에서 파일을 읽도록 요청합니다. OS는 파일 시스템 캐시를 확인하고 필요한 데이터가 없으면 OS는 읽기를 실행하고 데이터베이스에서 사용할 수 있도록 페이지를 메모리로 가져옵니다.

데이터베이스는 종종 공유 또는 버퍼 풀이라고 불리는 메모리 풀을 할당합니다. 디스크에서 읽은 페이지는 버퍼 풀에 배치됩니다. 페이지가 버퍼 풀에 있으면 요청된 행에 액세스할 수 있을 뿐만 아니라 행의 너비에 따라 페이지의 다른 행에도 액세스할 수 있습니다. 이는 특히 인덱스 범위 스캔으로 인해 발생하는 읽기를 효율적으로 만듭니다. 행이 작을수록 단일 페이지에 더 많은 행이 들어가므로 단일 I/O가 제공하는 비용 대비 효과가 더 큽니다.

쓰기도 마찬가지입니다. 사용자가 행을 업데이트하면 데이터베이스는 행이 있는 페이지를 찾고, 버퍼 풀에서 페이지를 끌어와 메모리에서 행을 업데이트하고 변경 사항(종종 WAL이라고 함)의 저널 항목을 디스크에 유지합니다. 페이지는 메모리에 남아 있으므로 최종적으로 디스크로 플러시되기 전에 더 많은 쓰기를 수신할 수 있으므로 I/O 수가 최소화됩니다. 삭제 및 삽입은 동일하게 작동하지만 구현은 다를 수 있습니다.

페이지 내용

페이지에 무엇을 저장할지는 당신에게 달려 있습니다. 행 저장소 데이터베이스는 행과 모든 속성을 페이지에 차례로 기록하여 OLTP 워크로드가 특히 쓰기 워크로드에 더 적합하도록 합니다.

열 저장 데이터베이스는 행을 페이지 열 단위로 작성합니다. 요약을 실행하는 OLAP 워크로드는 필드가 적을수록 더 효율적입니다. 단일 페이지 읽기는 한 열의 값으로 패킹되므로 SUM과 같은 집계 함수가 훨씬 더 효과적입니다. 행 기반 스토리지 엔진과 열 기반 스토리지 엔진을 비교하는 비디오를 만들었습니다.

문서 기반 데이터베이스는 행 저장소와 마찬가지로 문서를 압축하여 페이지에 저장하고, 그래프 기반 데이터베이스는 그래프를 탐색할 때 페이지 읽기가 효율적이도록 페이지에 연결을 유지합니다. 또한 깊이 대 너비 대 검색에 맞게 조정할 수도 있습니다.

행, 열, 문서 또는 그래프를 저장하든, 목표는 페이지 읽기가 효과적이도록 페이지에 항목을 압축하는 것입니다. 페이지는 클라이언트 측 작업 부하를 돕기 위해 가능한 한 많은 유용한 정보를 제공해야 합니다. 작은 작업을 하기 위해 많은 페이지를 읽는다면 데이터 모델링을 재고하는 것을 고려하세요. 이것은 완전히 다른 기사, 데이터 모델링, 과소평가된 것입니다.

작은 페이지 대 큰 페이지

작은 페이지는 특히 페이지 크기가 미디어 블록 크기에 가까울 경우 읽고 쓰는 것이 더 빠르지만, 페이지 헤더 메타데이터의 오버헤드 비용은 유용한 데이터와 비교했을 때 높아질 수 있습니다. 반면에 더 큰 크기는 메타데이터 오버헤드와 페이지 분할을 최소화할 수 있지만 콜드 읽기 및 쓰기 비용이 더 높습니다.

물론 디스크/SSD에 가까워질수록 매우 복잡해집니다. 스토리지 산업의 뛰어난 인재들이 호스트와 미디어 간의 읽기/쓰기를 최적화하기 위해 NVMe에서 Zoned 및 키 값 저장소 네임스페이스와 같은 기술을 연구하고 있습니다. 솔직히 말해서 저는 아직 이런 분야에 발을 담그고 있기 때문에 여기서 설명하려고 하지도 않을 겁니다.

Postgres 기본 페이지 크기는 8KB , MySQL InnoDB는 16KB , MongoDB WiredTiger는 32KB , SQL Server는 8KB , Oracle도 8KB 입니다 . 데이터베이스 기본값은 대부분의 경우에 작동하지만 이러한 기본값을 알고 사용 사례에 맞게 구성할 준비를 하는 것이 중요합니다.

페이지가 디스크에 저장되는 방식

디스크에 페이지를 저장하고 디스크에서 페이지를 검색하는 방법은 여러 가지가 있습니다. 한 가지 방법은 테이블이나 컬렉션당 고정 크기 페이지의 배열로 파일을 만드는 것입니다. 페이지 0 다음에 페이지 1 다음에 페이지 2가 옵니다. 디스크에서 무언가를 읽으려면 정보, 파일 이름, 오프셋 및 길이가 필요한데, 이 설계에서는 세 가지가 모두 있습니다!

페이지 x를 읽으려면 테이블에서 파일 이름을 알고, 오프셋을 구하려면 X *Page_Size를 구하고, 바이트 단위의 길이는 페이지 크기입니다.

예제 읽기 테이블 테스트에서 페이지 크기가 8KB라고 가정하고, 페이지 2~9를 읽기 위해 오프셋이 16484(2*8192)인 테이블 테스트가 있는 파일을 읽어 8페이지, 65536바이트(8*8192)를 읽습니다.

하지만 그것은 단지 한 가지 방법일 뿐입니다. 데이터베이스의 장점은 모든 데이터베이스 구현이 다르다는 것입니다.

Postgres 페이지 레이아웃

데이터베이스 중에서 PostgreSQL이 페이지를 저장하는 방식을 알아보고 특정 선택에 대한 비판을 제공하고 싶습니다. PostgreSQL에서 기본 페이지 크기는 8KB이고, 다음과 같습니다.

Postgres 페이지 레이아웃( 링크 )

각 섹션을 살펴보겠습니다.

페이지 헤더 - 24바이트

페이지에는 페이지에 있는 내용을 설명하는 메타데이터가 있어야 하며, 여기에는 사용 가능한 여유 공간도 포함됩니다. 이것은 24바이트 고정 헤더입니다.

ItemIds - 각각 4바이트

이것은 항목 포인터의 배열입니다(항목이나 튜플 자체가 아닙니다. 각 itemId는 4바이트 오프셋:길이 포인터로, 페이지에서 항목이 있는 오프셋과 크기를 가리킵니다.

이 포인터가 존재한다는 사실은 HOT 최적화(힙 전용 튜플)를 허용한다는 것입니다. postgres에서 행에 업데이트가 발생하면 새 튜플이 생성되고, 튜플이 이전 튜플과 같은 페이지에 들어맞으면 HOT 최적화가 이전 항목 ID 포인터를 새 튜플을 가리키도록 변경합니다. 이런 식으로 인덱스와 다른 데이터 구조는 여전히 이전 튜플 ID를 가리킬 수 있습니다. 매우 강력합니다.

한 가지 비판점은 아이템 포인터가 차지하는 크기가 4바이트라는 점인데, 만약 1000개의 아이템을 저장한다면 페이지의 절반(4KB)이 헤더에 낭비됩니다.

저는 아이템, 튜플, 행을 사용하지만, 여기에는 차이가 있습니다. 행은 사용자가 보는 것이고, 튜플은 페이지에서 행의 물리적 인스턴스이고, 아이템은 튜플입니다. 같은 행은 10개의 튜플을 가질 수 있는데, 활성 튜플 1개와 이전 트랜잭션(MVCC 이유)을 위해 남은 7개, 그리고 더 이상 필요하지 않은 죽은 튜플 2개가 있습니다.

항목 - 가변 길이

이는 항목 자체가 페이지에서 차례로 표시되는 위치입니다.

특수 - 가변 길이

이 섹션은 각 페이지가 이전 및 앞으로 연결되는 B+Tree 인덱스 리프 페이지 에만 적용됩니다 . 페이지 포인터에 대한 정보는 여기에 저장됩니다.

튜플이 참조되는 방법의 예는 다음과 같습니다.

요약

데이터베이스의 데이터는 인덱스, 시퀀스 또는 테이블 행인지 여부에 관계없이 페이지로 끝납니다. 이를 통해 데이터베이스가 페이지 자체에 무엇이 있는지와 관계없이 페이지를 사용하기가 더 쉬워집니다. 페이지 자체에는 헤더와 데이터가 있으며 파일의 일부로 디스크에 저장됩니다. 각 데이터베이스는 페이지가 어떻게 보이고 디스크에 물리적으로 어떻게 저장되는지에 대한 구현이 다르지만 결국 개념은 동일합니다.

•

--
CREATE TABLE TEMP(t int);

INSERT INTO TEMP(t) SELECT random() * 100 FROM generate_series(0, 1000000);

SELECT t from TEMP limit 10;
SELECT COUNT(t) FROM TEMP GROUP BY t;

--
create table employees( id serial primary key, name text);

create or replace function random_string(length integer) returns text as
$$
declare
  chars text[] := '{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}';
  result text := '';
  i integer := 0;
  length2 integer := (select trunc(random() * length + 1));
begin
  if length2 < 0 then
    raise exception 'Given length cannot be less than 0';
  end if;
  for i in 1..length2 loop
    result := result || chars[1+random()*(array_length(chars, 1)-1)];
  end loop;
  return result;
end;
$$ language plpgsql;

insert into employees(name)(select random_string(10) from generate_series(0, 10000000));

SELECT id FROM employees;

SELECT * FROM employees WHERE id = 1000;

-- analyze
-- 쿼리를 실제 실행한 후, 실제 걸린 시간 및 처리된 행의 수 반환
EXPLAIN analyze SELECT id from employees WHERE id = 30; -- 한번 조회한건 캐시되어 빨리 조회됨
EXPLAIN analyze SELECT name from employees WHERE id = 5000;
EXPLAIN analyze SELECT id, name from employees WHERE name = 'Zs';
EXPLAIN analyze SELECT id, name from employees WHERE name like '%Zs%';

CREATE INDEX employees_name on employees(name);

-- explain
create table grades (
id serial primary key,
 g int,
 name text
);


insert into grades (g,
name  )
select
random()*100,
substring(md5(random()::text ),0,floor(random()*31)::int)
 from generate_series(0, 10000000);

vacuum (analyze, verbose, full); -- vacuum(Postgresql에서 지원하는 테이블 최적화 진행)

EXPLAIN SELECT * FROM grades;
EXPLAIN SELECT * FROM grades ORDER BY g;
EXPLAIN SELECT ID FROM grades;
EXPLAIN SELECT NAME FROM grades;
EXPLAIN SELECT * FROM grades WHERE id=10;

explain analyze select id,g from grades where g > 80 and g < 95 order by g;
SQL
복사

•

스캔 방식

NOTE

PostgreSQL indexing: Index scan vs. Bitmap scan vs. Sequential scan (basics)

Introduction to PostgreSQL indexing. How and when to use an index scan, bitmap scan and/or sequential scan. Get performance tips.

https://www.cybertec-postgresql.com/en/postgresql-indexing-index-scan-vs-bitmap-scan-vs-sequential-scan-basics/

PostgreSQL이 사용하는 대표 Scan과 그 Cost

PostgreSQL 실행계획에서 보이는 대표 Scan의 종류와 그 Cost 계산

https://postgresql.kr/blog/pg_scan_cost.html

create table grades (
id serial primary key,
 g int,
 name text
);


insert into grades (g,
name  )
select
random()*100,
substring(md5(random()::text ),0,floor(random()*31)::int)
 from generate_series(0, 10000000);

vacuum (analyze, verbose, full); -- vacuum(Postgresql에서 지원하는 테이블 최적화 진행)

EXPLAIN SELECT * FROM grades;
EXPLAIN SELECT * FROM grades ORDER BY g;
EXPLAIN SELECT ID FROM grades;
EXPLAIN SELECT NAME FROM grades;
EXPLAIN SELECT * FROM grades WHERE id=10;

explain analyze select id,g from grades where g > 80 and g < 95 order by g;

--
EXPLAIN SELECT name FROM grades WHERE id = 1000; -- index scan(rows=1, width=15)
EXPLAIN SELECT name FROM grades WHERE id < 100;  -- index scan(rows=99, width=15), 행수가 적으면 index scan 사용
EXPLAIN SELECT name FROM grades WHERE id > 100;  -- seq scan(rows=19998812, width=15), 행수가 많아지면 seq scan 사용

CREATE INDEX idx_grades_g ON grades(g);
EXPLAIN SELECT name FROM grades WHERE g > 95; -- bitmap heap scan on g
EXPLAIN SELECT name FROM grades WHERE g > 95 and id < 10000; -- bitmap heap scan on g
SQL
복사

•

Bitmap Index Scan:

◦

idx_grades_g 인덱스를 사용하여 g > 95 조건에 맞는 데이터의 위치를 비트맵에 기록합니다. 이는 매우 빠른 인덱스 검색입니다.

•

Parallel Bitmap Heap Scan:

◦

병렬로 grades 테이블을 스캔하여 비트맵에서 지정한 위치에 있는 데이터를 확인하고, 다시 조건(g > 95)을 검증합니다. 이 과정에서 테이블의 데이터를 실제로 읽어들입니다.

•

Gather:

◦

병렬로 작업한 결과를 하나의 결과 집합으로 모읍니다. 이 단계에서 모든 워커가 수행한 작업이 결합됩니다.

seq tables scan

•

순차탐색으로 진행된다.

•

인덱스 사용안함

•

테이블이 작을 때, 혹은 조건에 맞는 데이터가 테이블의 대부분일때는 인덱스보다 효율적이다.

index scan

•

인덱스를 사용하여 효율적 검색을 진행한다.

•

필요에따라 인덱스를 통해 찾은 데이터가 포함된 실제 행을 테이블에서 추가 조회 가능

•

조건에 맞는 데이터가 일부이거나, 특정 열에 대해 인덱스가 있는 경우에 사용한다.

bitmap index scan

•

여러 인덱스를 결합하거나, 특정 조건이 다수의 행에 매칭될 때 사용한다.

•

각 인덱스에 일치하는 행을 찾아 비트맵에 표시하고, 나중에 이 비트맵을 기반으로 실제 데이터 조회

•

개별적 인덱스 스캔이후, 일치하는 행들을 병합

•

큰 책에서 특정 단어가 여러 페이지에 걸쳐 있을 때, 각 페이지를 찾아 표시해 두고, 나중에 한 번에 그 페이지들을 살펴보는 것과 같습니다.

key vs non-key column

NOTE

create table students (
    id serial primary key,
     g int,
     firstname text,
    lastname text,
    middlename text,
    address text,
     bio text,
    dob date,
    id1 int,
    id2 int,
    id3 int,
    id4 int,
    id5 int,
    id6 int,
    id7 int,
    id8 int,
    id9 int
);


insert into students (g,
firstname,
lastname,
middlename,
address ,
 bio,
dob,
id1 ,
id2,
id3,
id4,
id5,
id6,
id7,
id8,
id9)
select
random()*100,
substring(md5(random()::text ),0,floor(random()*31)::int),
substring(md5(random()::text ),0,floor(random()*31)::int),
substring(md5(random()::text ),0,floor(random()*31)::int),
substring(md5(random()::text ),0,floor(random()*31)::int),
substring(md5(random()::text ),0,floor(random()*31)::int),
now(),
random()*100000,
random()*100000,
random()*100000,
random()*100000,
random()*100000,
random()*100000,
random()*100000,
random()*100000,
random()*100000
 from generate_series(0, 50000000);

vacuum (analyze, verbose, full);

explain analyze select id,g from students where g > 80 and g < 95 order by g;
SQL
복사

Gather Merge  (cost=1649442.97..2313030.97 rows=5687500 width=8) (actual time=5205.248..5711.219 rows=6996323 loops=1)
  Workers Planned: 2  -- 이 작업을 병렬로 수행하기 위해 2개의 워커 프로세스를 계획했습니다.
  Workers Launched: 2 -- 실제로 2개의 워커가 시작되었습니다.
  
  ->  Sort  (cost=1648442.95..1655552.32 rows=2843750 width=8) (actual time=5120.712..5231.268 rows=2332108 loops=3)
        Sort Key: g DESC  -- 'g' 컬럼을 내림차순으로 정렬합니다.
        Sort Method: external merge  Disk: 41472kB  -- 정렬은 외부 병합 정렬(external merge sort)을 사용하며, 디스크에 41472kB를 사용했습니다.
        Worker 0:  Sort Method: external merge  Disk: 40712kB  -- 첫 번째 워커가 외부 병합 정렬을 수행하며, 40712kB의 디스크를 사용했습니다.
        Worker 1:  Sort Method: external merge  Disk: 41112kB  -- 두 번째 워커가 외부 병합 정렬을 수행하며, 41112kB의 디스크를 사용했습니다.
        
        ->  Parallel Seq Scan on students  (cost=0.00..1265839.00 rows=2843750 width=8) (actual time=96.046..4756.037 rows=2332108 loops=3)
              Filter: ((g > 80) AND (g < 95))  -- 'g > 80 AND g < 95' 조건을 만족하는 행을 필터링합니다.
              Rows Removed by Filter: 14334559  -- 필터링된 행 중 14,334,559개의 행이 조건에 맞지 않아 제거되었습니다.
              
Planning Time: 2.968 ms  -- 쿼리 계획을 세우는 데 걸린 시간입니다.
JIT:  -- Just-In-Time (JIT) 컴파일링에 대한 정보입니다.
  Functions: 12  -- JIT 컴파일된 함수의 수입니다.
  Options: Inlining true, Optimization true, Expressions true, Deforming true  -- JIT 컴파일링의 최적화 옵션입니다.
  Timing: Generation 12.136 ms, Inlining 205.273 ms, Optimization 35.913 ms, Emission 45.493 ms, Total 298.816 ms  -- JIT 컴파일링에 소요된 시간입니다.
  
Execution Time: 5842.646 ms  -- 쿼리를 실행하는 데 걸린 총 시간입니다.
SQL
복사

Limit  (cost=0.56..2073.98 rows=1000 width=8) (actual time=0.018..1.120 rows=1000 loops=1)
  Buffers: shared hit=793
  -- Limit 노드는 쿼리 결과에서 상위 1000개의 행만 반환하도록 제한합니다.
  -- 실제 실행 시간은 0.018ms에서 1.120ms 사이이며, 1000개의 행이 반환되었습니다.
  -- 이 쿼리 동안 793개의 공유 버퍼 페이지가 캐시에서 사용되었습니다.

  ->  Index Scan Backward using g_idx on students  (cost=0.56..9489315.91 rows=4576667 width=8) (actual time=0.016..1.045 rows=1000 loops=1)
        -- g_idx 인덱스를 사용하여 students 테이블에서 조건에 맞는 데이터를 역방향으로 스캔합니다.
        -- 스캔 조건은 (g > 10 AND g < 20)입니다. 즉, g 값이 10보다 크고 20보다 작은 행들을 검색합니다.
        -- 인덱스에서 역순으로 검색하므로, 가장 큰 g 값을 가진 행부터 검색합니다.
        -- 이 인덱스 스캔의 예상 비용은 매우 낮으며 (0.56), 전체 예상 행 수는 4,576,667개로 추정되었습니다.
        -- 실제로는 1.045ms 동안 1000개의 행이 검색되었습니다.
        Index Cond: ((g > 10) AND (g < 20))
        Buffers: shared hit=793
        -- 이 단계에서도 793개의 공유 버퍼 페이지가 사용되었습니다.

Planning:
  Buffers: shared hit=20
  -- 쿼리 계획을 세우는 동안 20개의 공유 버퍼 페이지가 캐시에서 사용되었습니다.

Planning Time: 0.173 ms
-- 쿼리 계획을 세우는 데 걸린 시간은 0.173ms입니다.

Execution Time: 1.183 ms
-- 쿼리를 실행하는 데 걸린 총 시간은 1.183ms입니다.
SQL
복사

Gather Merge  (cost=1491835.39..1936820.29 rows=3813890 width=8) (actual time=4532.989..4898.234 rows=4499547 loops=1)
  Workers Planned: 2  -- 이 작업을 병렬로 수행하기 위해 2개의 워커 프로세스를 계획했습니다.
  Workers Launched: 2 -- 실제로 2개의 워커가 시작되었습니다.

  Buffers: shared hit=1981 read=951430, temp read=19837 written=19898
  -- 이 단계에서 1981개의 공유 버퍼 페이지가 캐시에서 사용되었고, 951430개의 페이지가 디스크에서 읽혔습니다.
  -- 또한, 정렬 작업에서 임시 디스크 공간을 사용했으며, 19837개의 페이지가 임시 디스크에서 읽히고, 19898개의 페이지가 임시 디스크에 쓰였습니다.

  ->  Sort  (cost=1490835.36..1495602.73 rows=1906945 width=8) (actual time=4476.295..4546.073 rows=1499849 loops=3)
        Sort Key: g DESC  -- 'g' 컬럼을 내림차순으로 정렬합니다.
        Sort Method: external merge  Disk: 26368kB  -- 정렬은 외부 병합 정렬(external merge sort)을 사용하며, 디스크에 26368kB를 사용했습니다.

        Buffers: shared hit=1981 read=951430, temp read=19837 written=19898
        -- 이 단계에서도 1981개의 공유 버퍼 페이지가 캐시에서 사용되었고, 951430개의 페이지가 디스크에서 읽혔습니다.
        -- 정렬 과정에서 19837개의 페이지가 임시 디스크에서 읽히고, 19898개의 페이지가 임시 디스크에 쓰였습니다.

        Worker 0:  Sort Method: external merge  Disk: 26144kB  -- 첫 번째 워커가 외부 병합 정렬을 수행하며, 26144kB의 디스크를 사용했습니다.
        Worker 1:  Sort Method: external merge  Disk: 26896kB  -- 두 번째 워커가 외부 병합 정렬을 수행하며, 26896kB의 디스크를 사용했습니다.

        ->  Parallel Seq Scan on students  (cost=0.00..1265839.00 rows=1906945 width=8) (actual time=58.726..4254.635 rows=1499849 loops=3)
              Filter: ((g > 10) AND (g < 20))  -- 'g > 10 AND g < 20' 조건을 만족하는 행을 필터링합니다.
              Rows Removed by Filter: 15166818  -- 필터링된 결과 중 15,166,818개의 행이 조건에 맞지 않아 제거되었습니다.
              Buffers: shared hit=1909 read=951430
              -- 이 단계에서는 1909개의 공유 버퍼 페이지가 캐시에서 사용되었고, 951430개의 페이지가 디스크에서 읽혔습니다.

Planning:
  Buffers: shared hit=20  -- 쿼리 계획을 수립하는 동안 20개의 공유 버퍼 페이지가 캐시에서 사용되었습니다.
Planning Time: 1.486 ms  -- 쿼리 계획을 수립하는 데 걸린 시간은 1.486ms입니다.

JIT:
  Functions: 12  -- JIT(Just-In-Time) 컴파일된 함수의 수입니다.
  Options: Inlining true, Optimization true, Expressions true, Deforming true  -- JIT 컴파일에 대한 최적화 옵션입니다.
  Timing: Generation 14.227 ms, Inlining 116.506 ms, Optimization 32.603 ms, Emission 24.407 ms, Total 187.743 ms  -- JIT 컴파일링에 소요된 시간입니다.
  
Execution Time: 5035.035 ms  -- 전체 쿼리 실행 시간입니다.
SQL
복사

1. 인덱스란 무엇인가?

•

인덱스는 데이터베이스에서 데이터를 빠르게 검색하기 위해 특정 열(또는 열들)에 대해 만들어진 데이터 구조입니다.

•

인덱스는 B-트리와 같은 자료 구조로 만들어지며, 검색 시에 데이터베이스는 인덱스를 사용해 해당 데이터를 빠르게 찾습니다.

2. 키 필드와 비키 필드

•

키 필드(index key column): 검색의 기준이 되는 열입니다. 예를 들어, 특정 학생들의 성적을 기준으로 검색하려면 "성적(grade)" 열을 키 필드로 설정할 수 있습니다.

•

비키 필드(non-key column): 검색에는 사용되지 않지만, 인덱스에 포함시켜서 검색 후 테이블을 다시 참조하지 않도록 할 수 있는 열입니다. 예를 들어, 성적을 기준으로 검색할 때 "학생 ID"를 비키 필드로 인덱스에 포함시킬 수 있습니다.

3. 기본 인덱스 사용의 문제점

•

기본적으로 인덱스는 특정 필드를 기준으로 검색을 빠르게 해줍니다. 예를 들어, 성적을 기준으로 학생을 검색하면, 해당 성적에 맞는 데이터를 인덱스에서 찾은 다음, 해당 데이터의 실제 값(예: 학생 ID 등)을 얻기 위해 테이블에서 다시 데이터를 가져와야 합니다.

•

이렇게 테이블을 다시 참조하는 과정이 추가적인 I/O를 발생시키며 성능을 저하시킬 수 있습니다.

4. 비키 필드를 포함한 인덱스의 장점

•

*비키 필드(non-key column)**를 인덱스에 포함시키면, 필요한 데이터가 모두 인덱스에 포함되어 있기 때문에, 테이블을 다시 참조할 필요가 없어집니다.

•

예를 들어, 성적과 학생 ID를 인덱스에 포함시키면, 성적을 기준으로 학생을 검색할 때, 학생 ID도 함께 가져올 수 있어 성능이 크게 향상됩니다.

7. 주의사항

•

비키 필드를 포함시키면 인덱스 크기가 커져 메모리에 모두 적재되지 않을 수 있습니다. 이 경우 인덱스 자체가 디스크에 저장되어 추가적인 I/O가 발생할 수 있습니다.

•

따라서, 인덱스 크기와 메모리 사용량을 고려하여 신중하게 인덱스를 설계해야 합니다.

8. 강의 요약

•

인덱스의 기본 개념과 키 필드와 비키 필드의 차이점을 이해하는 것이 중요합니다.

•

비키 필드를 적절히 활용하면 테이블에 다시 접근하는 비용을 줄여 성능을 크게 향상시킬 수 있습니다.

•

하지만 인덱스 크기와 메모리 사용량을 고려하여 적절하게 사용하는 것이 필요합니다.

인덱스 스캔 vs 인덱스 only 스캔

NOTE

CREATE TABLE test2 (
    a integer,
    b integer,
    c integer
);

INSERT INTO test2 (a, b, c)
SELECT
    trunc(random() * 1000)::int,
    trunc(random() * 1000)::int,
    trunc(random() * 1000)::int
FROM
    generate_series(1, 12000000);

create index on test2(a);
create index on test2(b);

EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 70;
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 70 limit 2;
EXPLAIN ANALYZE SELECT c FROM test2 WHERE b = 100;
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 100 AND b = 200;
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 100 OR b = 200;

drop index test2_a_idx, test2_b_idx;
create index on test2(a,b);
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 70; -- good
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 70 limit 2; -- good
EXPLAIN ANALYZE SELECT c FROM test2 WHERE b = 100; -- bad (not index)
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 100 AND b = 200; -- good
EXPLAIN ANALYZE SELECT c FROM test2 WHERE a = 100 OR b = 200; -- bad (not index)

create index on test2(b); -- 해당 인덱스 추가하면 쿼리 최적화가 된다!
SQL
복사

-------------------
| test2_a_idx      |   ->  Bitmap Index Scan -> [Matching rows for a = 100]
-------------------
                                |
                                V
-------------------
| test2_b_idx      |   ->  Bitmap Index Scan -> [Matching rows for b = 200]
-------------------
                                |
                                V
                           -------------
                           | BitmapAnd |  -> Combine results (find common rows)
                           -------------
                                |
                                V
                          -------------------
                          | Bitmap Heap Scan | -> Retrieve actual rows from heap
                          -------------------
SQL
복사
인덱스 테이블이 별개로 있는경우 과정

DB가 어떻게 인덱스를 선택하는가?

주요 내용 요약:

인덱스 사용 시나리오:

•

두 개의 인덱스를 모두 사용하는 경우: 데이터베이스 옵티마이저는 F1과 F2 인덱스를 각각 검색하여 일치하는 행(row) ID를 수집한 다음, 두 결과 집합을 결합하거나 교차(intersect)하여 최종 결과를 도출합니다. 이 방법은 검색 결과가 적당한 수의 행을 반환할 때 사용됩니다.

•

하나의 인덱스만 사용하는 경우: 옵티마이저가 F1 인덱스만 사용하여 검색 후, 필터링을 통해 F2 조건을 만족하는 행을 추출합니다. 이는 F1 인덱스가 적은 수의 행을 반환하고 F2 인덱스가 많은 행을 반환할 때 주로 사용됩니다.

•

테이블 스캔(Table Scan): 두 인덱스 모두 비효율적이라고 판단될 때, 옵티마이저는 전체 테이블을 스캔하여 조건에 맞는 행을 찾습니다. 이 경우, 인덱스를 사용하는 것보다 테이블 스캔이 더 효율적일 수 있습니다.

옵티마이저의 판단 기준:

•

통계(Statistics): 데이터베이스는 테이블에 대한 통계를 유지하여 인덱스의 효율성을 판단합니다. 예를 들어, 테이블에 있는 행의 수, 특정 값의 빈도 등을 바탕으로 어떤 인덱스를 사용할지 결정합니다.

•

통계 업데이트 필요성: 테이블에 대량의 데이터가 삽입되거나 삭제된 후 통계를 갱신하지 않으면, 옵티마이저가 잘못된 결정을 내릴 수 있습니다. 통계를 수동으로 업데이트하는 명령어로는 PostgreSQL의 ANALYZE, Oracle의 GATHER STATISTICS 등이 있습니다.

인덱스 힌트(Index Hint): 특정 상황에서 데이터베이스가 잘못된 인덱스를 사용할 수 있기 때문에, 개발자가 직접 인덱스 사용을 지시할 수 있는 힌트 기능을 사용할 수 있습니다.

결론:

데이터베이스에서 인덱스 사용은 매우 중요하며, 옵티마이저가 다양한 요소를 고려하여 최적의 인덱스를 선택합니다. 그러나 통계가 갱신되지 않거나 상황에 따라 옵티마이저가 최적의 결정을 내리지 못할 수 있으므로, 개발자가 인덱스 사용을 직접 제어할 수 있는 방법도 존재합니다. 이를 통해 쿼리 성능을 최적화할 수 있습니다.

SELECT
    indexname AS index_name,
    indexdef AS index_definition
FROM
    pg_indexes
WHERE
    tablename = 'grades';
SQL
복사

•

기존 인덱스 생성의 문제점:

◦

쓰기 작업 차단: 일반적인 인덱스 생성(CREATE INDEX)은 테이블에 대한 쓰기 작업을 차단합니다. 이로 인해 인덱스가 생성되는 동안 데이터베이스에 쓰기 작업(INSERT, UPDATE, DELETE)을 수행할 수 없습니다. 이는 특히 대규모 테이블에서 문제가 되며, 인덱스 생성에 시간이 오래 걸릴 수 있습니다.

◦

읽기 작업 허용: 반면, 읽기 작업(SELECT)은 인덱스 생성 중에도 허용됩니다. 그러나 쓰기 작업이 차단된다는 점은 운영 환경에서 큰 단점입니다.

•

CREATE INDEX CONCURRENTLY:

◦

PostgreSQL은 이러한 문제를 해결하기 위해 CREATE INDEX CONCURRENTLY라는 기능을 제공합니다.

◦

이 명령어는 인덱스를 생성하면서도 테이블에 대한 쓰기 작업을 허용합니다. 이는 인덱스 생성 중에도 데이터베이스가 계속해서 정상적으로 작동할 수 있도록 합니다.

◦

그러나 이 방식은 일반적인 인덱스 생성보다 시간이 더 오래 걸리고, CPU와 메모리 사용량이 더 많아질 수 있습니다.

◦

또한, 이 방법은 실패 가능성도 존재합니다. 예를 들어, 인덱스가 고유 인덱스(UNIQUE INDEX)인 경우, 중복된 값이 삽입되면 인덱스가 잘못된 상태가 될 수 있습니다.

•

미래 방향:

◦

PostgreSQL에서 CREATE INDEX CONCURRENTLY를 기본 옵션으로 만드는 것이 논의되고 있습니다. 이는 운영 환경에서 인덱스를 생성할 때 성능 저하나 서비스 중단을 최소화하기 위한 조치입니다.

Bloom Filters

NOTE

10억개의 데이터가 있는 db를 어떻게 디자인할것인가?, 방대한 양의 데이터를 처리하는 방법

•

브루트 포싱: 후세인은 맵리듀스(MapReduce)와 유사한 빅데이터 접근 방식으로 테이블을 여러 조각으로 나누어 멀티스레딩과 멀티프로세싱을 사용하여 병렬로 검색하는 방법을 설명합니다. 이 방법은 단순하지만 계산 비용이 많이 들고 인덱싱과 같은 최적화 없이는 비효율적입니다.

•

인덱싱 및 파티셔닝:

◦

인덱싱: B-트리와 같은 구조화된 인덱스를 생성하여 데이터 검색 속도를 높이는 방법입니다. 이는 전체 테이블을 스캔할 필요를 줄이고 검색 영역을 크게 좁혀 효율성을 높입니다.

◦

파티셔닝: 후세인은 수평 파티셔닝에 대해 자세히 설명합니다. 이 방법은 테이블을 다양한 위치에 저장되는 부분으로 나눕니다. 이 접근 방식은 데이터가 저장된 위치를 결정하는 파티션 키가 필요하며, 전체 테이블이 아닌 특정 세그먼트 내에서 더욱 집중적이고 빠른 검색을 가능하게 합니다.

•

샤딩: 데이터를 여러 서버에 분산시켜 각 서버가 테이블의 일부를 독립적으로 관리하는 방법입니다. 샤딩은 단일 서버에 대한 부하를 줄이고 성능을 향상시키는 데 도움이 되지만, 다른 샤드 간의 트랜잭션을 처리하는 복잡성을 증가시킵니다.

기사 - 장기 거래 비용

결국 Postgres(또는 다른 데이터베이스)에서 실패한 장기 업데이트 트랜잭션의 비용입니다.

Postgres에서 행을 건드리는 모든 DML 트랜잭션은 해당 행의 새 버전을 만듭니다. 행이 인덱스에서 참조되는 경우 해당 행도 새 튜플 ID로 업데이트해야 합니다. 인덱스를 업데이트할 필요가 없지만 행이 있는 페이지에 충분한 공간이 있는 경우에만 발생하는 힙 전용 튜플(HOT)과 같은 최적화의 예외가 있습니다(채우기 계수 < 100%).

수백만 개의 행을 업데이트한 긴 트랜잭션이 롤백되면 이 트랜잭션(내 경우 수백만 개)에서 생성된 새 행 버전은 이제 무효화되어 어떤 새 트랜잭션에서도 읽혀서는 안 됩니다. 이 문제를 해결하는 방법은 여러 가지가 있습니다. 트랜잭션 롤백 시 모든 죽은 행을 적극적으로 정리합니까? 아니면 사후 처리로 게으르게 합니까? 아니면 테이블을 잠그고 데이터베이스가 완전히 다시 시작될 때까지 정리합니까?

Postgres는 게으른 접근 방식, 즉 주기적으로 호출되는 vacuum이라는 명령을 수행합니다. Postgres는 죽은 행을 제거하고 페이지에서 공간을 확보하려고 시도합니다.

죽은 행을 그대로 두는 것에 무슨 해가 있을까요?실제로는 정확성 문제가 전혀 아닙니다.사실, 트랜잭션은 죽은 행을 만든 트랜잭션의 상태를 확인하여 죽은 행을 읽지 않도록 알고 있습니다.그러나 이것은 값비싼 확인이며, 이 행을 만든 트랜잭션이 커밋되었는지 롤백되었는지 확인하는 확인입니다.또한, 죽은 행이 활성 행이 있는 디스크 페이지에 있다는 사실은 데이터베이스가 죽은 행을 필터링해야 하므로 IO를 효율적이지 못하게 만듭니다.예를 들어, 페이지에 1000개의 행이 있지만 활성 행은 1개, 죽은 행은 999개만 있는 경우 데이터베이스는 해당 IO를 만들지만 단일 행만 가져옵니다.이를 반복하면 더 많은 IO를 만들게 됩니다.IO가 많을수록 성능이 느려집니다.

다른 데이터베이스는 열성적인 접근 방식을 취하고, 롤백이 성공적으로 완료되기 전에 데이터베이스를 시작하지 못하게 하며, 실행 취소 로그를 사용합니다. 어느 것이 옳고 어느 것이 그른가요? 여기 재미있는 부분이 있습니다! 아무것도 옳고 그름이 없습니다. 모두 엔지니어가 내리는 결정입니다. 모두 기본입니다. 이해하고 선택하는 것은 여러분에게 달려 있습니다. 무엇이든 작동할 수 있습니다. 무엇을 다루고 있는지 안다면 무엇이든 작동하게 만들 수 있습니다.

기사 - Microsoft SQL Server 클러스터형 인덱스 디자인

이것은 제가 읽은 가장 흥미로운 문서 페이지 중 하나이며, 여러분과 공유하고 싶었습니다. 이 링크 에서 전체 디자인 가이드를 읽을 수 있으며, 디자인의 pdf도 포함했습니다. 이 디자인 가이드에서 가장 흥미롭게 읽은 두 가지 중요한 부분을 발췌했습니다. 이미지와 클러스터형 인덱스가 B-트리 아키텍처에서 비클러스터형 인덱스와 비교하여 지속되는 방식에 주의하세요. 이것은 Microsoft에서 문제를 해결하는 방식이고 반드시 그렇게 해야 하는 것은 아니라는 점을 명심하세요. 이것이 어떻게 이루어지는지에 도전하고 다른 접근 방식을 생각해 보세요.

즐기다

•

후세인

클러스터형 인덱스 아키텍처

SQL Server에서 인덱스는 B-트리로 구성됩니다. 인덱스 B-트리의 각 페이지를 인덱스 노드라고 합니다. B-트리의 최상위 노드를 루트 노드라고 합니다. 인덱스의 최하위 노드를 리프 노드라고 합니다. 루트와 리프 노드 사이의 모든 인덱스 수준을 통틀어 중간 수준이라고 합니다. 클러스터형 인덱스에서 리프 노드는 기본 테이블의 데이터 페이지를 포함합니다. 루트 및 중간 수준 노드에는 인덱스 행을 포함하는 인덱스 페이지가 포함됩니다. 각 인덱스 행에는 키 값과 B-트리의 중간 수준 페이지 또는 인덱스의 리프 수준에 있는 데이터 행에 대한 포인터가 포함됩니다. 인덱스의 각 수준에 있는 페이지는 이중 연결 목록에서 연결됩니다.

클러스터형 인덱스는 sys.partitions 에 하나의 행을 가지며 , 인덱스에서 사용하는 각 파티션에 대해 index_id = 1입니다. 기본적으로 클러스터형 인덱스는 단일 파티션을 갖습니다. 클러스터형 인덱스에 여러 파티션이 있는 경우 각 파티션에는 해당 특정 파티션의 데이터가 포함된 B-트리 구조가 있습니다. 예를 들어, 클러스터형 인덱스에 4개의 파티션이 있는 경우 각 파티션에 하나씩 총 4개의 B-트리 구조가 있습니다.

클러스터형 인덱스의 데이터 유형에 따라 각 클러스터형 인덱스 구조에는 특정 파티션의 데이터를 저장하고 관리하는 하나 이상의 할당 단위가 있습니다. 최소한 각 클러스터형 인덱스에는 파티션당 하나의 IN_ROW_DATA 할당 단위가 있습니다. 클러스터형 인덱스에는 LOB (대형 개체) 열이 포함된 경우 파티션당 하나의 LOB_DATA 할당 단위도 있습니다. 8,060바이트 행 크기 제한을 초과하는 가변 길이 열이 포함된 경우 파티션당 하나의 ROW_OVERFLOW_DATA 할당 단위도 있습니다.

데이터 체인의 페이지와 그 안의 행은 클러스터형 인덱스 키의 값에 따라 정렬됩니다. 모든 삽입은 삽입된 행의 키 값이 기존 행 사이의 순서 순서에 맞는 지점에서 이루어집니다.

이 그림은 단일 파티션의 클러스터형 인덱스 구조를 보여줍니다.

비클러스터형 인덱스 아키텍처

비클러스터형 인덱스는 클러스터형 인덱스와 동일한 B-트리 구조를 갖지만 다음과 같은 중요한 차이점이 있습니다.

•

기본 테이블의 데이터 행은 비클러스터형 키를 기준으로 정렬 및 저장되지 않습니다.

•

비클러스터형 인덱스의 리프 수준은 데이터 페이지 대신 인덱스 페이지로 구성됩니다.

비클러스터형 인덱스 행의 행 로케이터는 행에 대한 포인터이거나 행의 클러스터형 인덱스 키입니다(다음에 설명됨).

•

테이블이 힙인 경우, 즉 클러스터형 인덱스가 없는 경우 행 로케이터는 행에 대한 포인터입니다. 포인터는 파일 식별자(ID), 페이지 번호, 페이지의 행 번호로 구성됩니다. 전체 포인터를 행 ID(RID)라고 합니다.

•

테이블에 클러스터형 인덱스가 있거나 인덱스가 인덱싱된 뷰에 있는 경우, 행 로케이터는 해당 행의 클러스터형 인덱스 키입니다.

비클러스터형 인덱스는 인덱스에서 사용하는 각 파티션에 대해 index_id > 1 인 sys.partitions 에 하나의 행을 갖습니다 . 기본적으로 비클러스터형 인덱스는 단일 파티션을 갖습니다. 비클러스터형 인덱스에 여러 파티션이 있는 경우 각 파티션에는 해당 특정 파티션에 대한 인덱스 행이 포함된 B-트리 구조가 있습니다. 예를 들어, 비클러스터형 인덱스에 4개의 파티션이 있는 경우 각 파티션에 하나씩 총 4개의 B-트리 구조가 있습니다.

비클러스터형 인덱스의 데이터 유형에 따라 각 비클러스터형 인덱스 구조에는 특정 파티션의 데이터를 저장하고 관리하는 하나 이상의 할당 단위가 있습니다. 최소한 각 비클러스터형 인덱스에는 인덱스 B-트리 페이지를 저장하는 파티션당 하나의 IN_ROW_DATA 할당 단위가 있습니다. 비클러스터형 인덱스에는 LOB(대형 개체) 열이 포함된 경우 파티션당 하나의 LOB_DATA 할당 단위도 있습니다. 또한 8,060바이트 행 크기 제한을 초과하는 가변 길이 열이 포함된 경우 파티션당 하나의 ROW_OVERFLOW_DATA 할당 단위가 있습니다 .

다음 그림은 단일 파티션의 비클러스터형 인덱스 구조를 보여줍니다.

B-Trees vs B+Trees

NOTE

full 테이블 스캔

•

페이지 단위 읽기: 데이터베이스 테이블은 디스크 상의 하나 또는 여러 데이터 파일로 구성됩니다. 이 데이터 파일들은 '페이지'라고 불리는 고정된 크기의 블록으로 나뉩니다. 예를 들어, 일부 데이터베이스는 기본적으로 8KB의 페이지 크기를 가지며, 이는 설정을 변경하지 않는 한 고정됩니다. MySQL의 경우에는 기본적으로 16KB의 페이지를 사용합니다.

•

디스크 읽기 작업: 데이터베이스가 특정 행을 찾기 위해 페이지를 순차적으로 읽습니다. 각 페이지 읽기 작업은 디스크의 섹터나 블록 단위로 처리되며, 하드 디스크 드라이브나 SSD의 경우 물리적인 페이지 크기가 다를 수 있습니다(예: SSD는 일반적으로 4KB).

•

비효율성: 전체 테이블을 스캔하면서 데이터베이스는 "이것이 내가 찾는 행인가?" 하고 각 행을 확인합니다. 이 과정은 많은 IO 작업을 필요로 하며, 데이터베이스는 마지막 페이지까지 도달할 때까지 이를 반복합니다. 만약 찾고자 하는 행이 테이블의 맨 마지막에 위치한다면, 이는 최악의 시나리오로 이어질 수 있습니다.

•

DBMS의 최적화: 대부분의 데이터베이스 관리 시스템(DBMS)은 전체 테이블 스캔을 수행할 때도 다양한 최적화 기술을 적용합니다. 예를 들어, 테이블을 여러 부분으로 나누고, 여러 작업자가 동시에 위에서 아래로 또는 아래에서 위로 작업을 진행하며 효율적으로 행을 찾을 수 있도록 합니다.

B- 트리

구성요소

•

노드(Nodes): B-트리는 여러 노드로 구성됩니다. 각 노드는 자식 노드를 가질 수 있으며, 노드 내부에는 요소들이 있습니다.

•

요소(Elements): 각 요소는 키(key)와 값(value)를 포함합니다. 키는 검색 대상이고, 값은 보통 데이터 포인터로, 특정 행을 가리키는 포인터입니다.

용어와 개념

•

도(degree, M): B-트리의 '도'는 노드가 가질 수 있는 자식 노드의 최대 수를 나타냅니다. 노드가 M개의 자식을 가질 수 있다면, 그 노드는 최대 M-1개의 요소를 갖습니다.

•

데이터 포인터(Data Pointer): 데이터 포인터는 값의 일부로서, 특정 행을 직접 가리키거나 기본 키를 통해 간접적으로 행을 가리킬 수 있습니다.

B-트리의 구조

•

루트 노드(Root Node): B-트리의 가장 상단에 위치한 첫 번째 노드입니다.

•

내부 노드(Internal Nodes): 루트 노드 아래에 위치하며, 자식 노드를 가질 수 있는 중간 단계의 노드입니다.

•

잎 노드(Leaf Nodes): B-트리의 가장 하단에 위치하며, 더 이상의 자식 노드가 없는 노드입니다.

실용적 고려사항

•

노드와 디스크 페이지: 실제 데이터베이스 시스템에서 노드는 디스크 페이지와 동일하게 취급됩니다. 각 페이지는 예를 들어 8KB와 같은 특정 크기를 가지며, 노드는 이 페이지 내에 적절히 맞도록 구성되어야 합니다.

1. 메모리 공간의 비효율적 사용

각 노드가 키(key)와 값(value) 모두를 저장하므로, 노드 하나에 저장할 수 있는 요소의 수가 제한됩니다. 검색 중 값은 사용되지 않는 경우가 많아 메모리 공간을 낭비할 수 있습니다. 예를 들어, 키만을 사용하여 검색을 할 때 값은 필요 없으나, 그 값이 노드에 저장되어 있어 공간을 차지하게 됩니다.

2. 범위 쿼리의 비효율성

B-트리는 키를 기준으로 데이터를 저장하므로, 특정 범위의 값을 빠르게 검색하는 데 비효율적일 수 있습니다. 예를 들어, 1부터 5까지의 키를 찾기 위해 여러 개의 노드를 거쳐야 하며, 각각의 노드에서 I/O 작업을 수행해야 하므로 처리 시간이 길어질 수 있습니다.

3. 내부 노드의 메모리 저장 문제

노드 내 모든 값이 저장되면 내부 노드를 메모리에 효과적으로 저장하는 것이 어려워질 수 있습니다. 특히 UUID나 문자열과 같은 크기가 큰 키를 사용하는 경우 더욱 그렇습니다. 이는 메모리 사용을 증가시키고, 인덱스 또는 B-트리의 메모리 저장 비용을 증가시킵니다.

B+트리의 개선점

B+트리는 B-트리의 몇 가지 한계를 해결하기 위해 개발되었습니다. B+트리는 모든 값들을 리프 노드(leaf node)에만 저장하고, 내부 노드는 키만을 저장하여 메모리 사용을 최적화합니다. 이 구조 덕분에 더 많은 키를 저장할 수 있고, 범위 쿼리의 효율성이 향상됩니다. 리프 노드들은 서로 연결 리스트로 연결되어 있어 범위 쿼리가 훨씬 빠르고 효율적으로 수행됩니다.

B+ 트리

B+ 트리의 구조

•

내부 노드: B+ 트리에서 내부 노드는 키만을 저장하고 값은 저장하지 않습니다. 이로 인해 노드 하나당 더 많은 키를 저장할 수 있으며, 이는 인덱스의 크기와 탐색 시간을 줄여줍니다.

•

리프 노드: 모든 데이터 값은 리프 노드에 저장됩니다. 리프 노드는 서로 연결되어 있어, 한 노드에서 다음 노드로의 접근이 용이하며, 이는 연속된 키들의 범위 쿼리를 매우 효율적으로 만듭니다.

범위 쿼리의 향상

B+ 트리는 리프 노드가 서로 연결된 덕분에 범위 쿼리가 훨씬 빠르고 효율적입니다. 예를 들어, 키 4부터 9까지의 범위를 찾는 경우, 한 번의 디스크 읽기 작업으로 연속된 여러 키를 빠르게 검색할 수 있습니다. 이는 리프 노드 간의 연결 리스트를 통해 이루어집니다.

메모리 및 저장 공간의 최적화

내부 노드에 키만 저장함으로써, B+ 트리는 메모리 사용을 최적화합니다. 값이 큰 데이터(예: UUID, 문자열)를 인덱스에 포함시킬 때, 내부 노드의 공간 절약은 더 많은 키를 저장할 수 있게 하여 전반적인 인덱스 크기를 줄이는 데 도움을 줍니다.

실제 데이터베이스 적용

실제 데이터베이스에서는 B+ 트리의 구조를 활용하여, 디스크 I/O를 줄이고 데이터 접근 속도를 높입니다. 특히, 대용량 데이터 처리와 빠른 검색이 필요한 환경에서 그 효과를 더욱 누릴 수 있습니다. 데이터베이스 시스템은 리프 노드에만 데이터 포인터를 저장하고, 내부 노드는 이 포인터들을 더욱 빠르게 탐색할 수 있는 경로만 제공함으로써 효율성을 극대화합니다.

B+ 트리는 B-트리에 비해 범위 쿼리 처리에 강점을 가지며, 대규모 데이터베이스 시스템에서 널리 사용되고 있는 이유를 잘 보여줍니다. 이러한 구조적 차이는 데이터베이스의 성능을 크게 향상시킬 수 있습니다.

B+ 트리의 특징과 DBMS 고려사항

•

리프 노드 포인터: B+ 트리에서 리프 노드들은 서로 연결되어 있어 범위 쿼리를 용이하게 합니다. 예를 들어, MySQL, PostgreSQL, SQL Server는 이러한 리프 노드 포인터를 구현하여, 연속된 데이터 노드를 효과적으로 접근할 수 있도록 합니다. MongoDB의 WiredTiger 엔진도 B+ 트리를 기반으로 하며, 특정 상황에서는 범위 쿼리를 지원하지 않는 설계 결정을 내릴 수도 있습니다.

•

메모리 최적화: B+ 트리의 내부 노드는 키만을 저장하기 때문에 메모리에 쉽게 맞출 수 있고, 이는 트리의 빠른 탐색을 가능하게 합니다. DBMS는 종종 내부 노드만 메모리에 저장하여, 디스크 I/O를 줄이고 접근 속도를 높이는 전략을 사용합니다.

•

저장 비용과 성능: 인덱스가 메모리에 완전히 로드될 때 가장 효과적입니다. 대부분의 경우 인덱스는 크기가 작으므로 메모리에 쉽게 맞출 수 있지만, 큰 인덱스의 경우 일부 DBMS는 내부 노드만 메모리에 저장할 선택을 합니다. 이로 인해 탐색 속도가 매우 빨라질 수 있습니다.

•

데이터 타입의 영향: 인덱싱되는 데이터의 타입(예: UUID, 문자열)에 따라 메모리에 맞추는 것이 더 어려울 수 있습니다. 데이터 타입에 따라 필요한 저장 공간이 크게 달라질 수 있으며, 이는 DBMS의 성능에 직접적인 영향을 미칩니다.

종합적인 고려

B+ 트리는 DBMS에서 매우 중요한 데이터 구조이며, 특히 대용량 데이터 처리와 빠른 데이터 검색이 필요한 애플리케이션에 적합합니다. 그러나 실제 성능은 사용하는 DBMS의 구현 방식, 데이터의 특성 및 인덱스 관리 전략에 따라 달라질 수 있습니다. 따라서 효과적인 데이터 관리를 위해서는 이러한 모든 요소를 종합적으로 고려하여 최적의 솔루션을 선택해야 합니다.

•

PostgreSQL과 MySQL의 보조 인덱스 차이:

PostgreSQL:

•

PostgreSQL에서는 보조 인덱스가 직접 튜플(tuple)을 가리키는 구조입니다. 이는 보조 인덱스가 실제 데이터 행의 위치를 직접 포인트하는 것을 의미하며, 이로 인해 데이터 검색 시 빠른 접근이 가능합니다. 그러나 이 방식은 튜플의 이동이나 변경이 발생할 경우 인덱스 업데이트가 필요하게 됩니다.

MySQL:

•

반면 MySQL에서는 보조 인덱스가 주 키(primary key)를 가리키는 방식을 사용합니다. 이는 보조 인덱스가 데이터 행의 실제 위치를 직접 포인트하는 대신, 주 키를 통해 간접적으로 데이터에 접근합니다. 이 방식은 주 키가 작고 관리하기 쉬운 경우에는 효율적이지만, UUID나 GUID와 같이 크고 복잡한 주 키를 사용할 경우 인덱스 크기가 커지고 성능이 저하될 수 있습니다.

성능에 미치는 영향:

•

UUID 사용의 문제점: UUID를 주 키로 사용하는 경우, 그 크기와 무작위성 때문에 삽입 연산에서 성능 저하가 발생할 수 있습니다. MySQL에서는 이러한 주 키를 가리키는 모든 보조 인덱스가 비효율적으로 커질 수 있으며, 이는 메모리 사용량 증가와 성능 저하를 초래합니다.

•

인덱스 조직화: MySQL의 경우, 인덱스가 클러스터형 인덱스로 구성되어 있어 전체 행을 인덱스에 저장합니다. 이 구조는 데이터 접근 시 빠른 성능을 제공하지만, 인덱스가 커지고 메모리 공간을 많이 차지할 수 있습니다.

실제 사례 – 우버(Uber)의 이동:

우버가 PostgreSQL에서 MySQL로 데이터베이스 시스템을 이전한 결정 중 하나는 바로 이러한 인덱스 관리와 관련된 성능 문제 때문이었습니다. PostgreSQL의 보조 인덱스가 튜플을 직접 가리키는 방식은 유연성은 높지만, 관리와 성능 최적화에 있어서는 MySQL의 접근 방식이 더 우수할 수 있습니다. 특히, 대규모 데이터와 고성능을 요구하는 환경에서 보조 인덱스의 효율성이 중요한 요소로 작용했습니다.

[PostgreSQL]
    보조 인덱스
         |
         v
    튜플 위치 포인터 (직접 접근)
         |
         v
    데이터 행 접근

[MySQL]
    보조 인덱스
         |
         v
    주 키 값 찾기
         |
         v
    주 키를 통한 데이터 행 위치 찾기
         |
         v
    데이터 행 접근
SQL
복사

ㅇㅇ

NOTE

•

노트 템플릿 시리즈

정리

목차

원자성(Atomicity)

격리성

Non-repeatable Reads

Phantom Reads

Isolation level

Consistency(일관성)

내구성

Serializable vs Non-repetable

1. Serializable 격리 수준

2. Repeatable Read 격리 수준

요약

Eventual Consistency

데이터베이스 내부 시스템

행 vs 열 기반 데이터베이스

Row-Oriented Database (행 기반 데이터베이스)

Column-Oriented Database (열 기반 데이터베이스)

1. Index-Organized Table (IOT) vs. Heap-Organized Table

2. Primary Index (Clustered Index)

3. Secondary Index

4. PostgreSQL의 인덱스 구조

Heap-Organized Table의 한계

목차

데이터베이스 페이지 - 심층 분석

페이지 풀

페이지 내용

작은 페이지 대 큰 페이지

페이지가 디스크에 저장되는 방식

Postgres 페이지 레이아웃

페이지 헤더 - 24바이트

ItemIds - 각각 4바이트

항목 - 가변 길이

특수 - 가변 길이

요약

목차

스캔 방식

seq tables scan

index scan

bitmap index scan

key vs non-key column

목차

1. 인덱스란 무엇인가?

2. 키 필드와 비키 필드

3. 기본 인덱스 사용의 문제점

4. 비키 필드를 포함한 인덱스의 장점

7. 주의사항

8. 강의 요약

인덱스 스캔 vs 인덱스 only 스캔

주요 내용 요약:

결론:

Bloom Filters

기사 - 장기 거래 비용

기사 - Microsoft SQL Server 클러스터형 인덱스 디자인

B-Trees vs B+Trees

full 테이블 스캔

B- 트리

구성요소

용어와 개념

B-트리의 구조

실용적 고려사항

1. 메모리 공간의 비효율적 사용

2. 범위 쿼리의 비효율성

3. 내부 노드의 메모리 저장 문제

B+트리의 개선점

B+ 트리

B+ 트리의 구조

범위 쿼리의 향상

메모리 및 저장 공간의 최적화

실제 데이터베이스 적용

B+ 트리의 특징과 DBMS 고려사항

종합적인 고려

PostgreSQL과 MySQL의 보조 인덱스 차이:

성능에 미치는 영향:

실제 사례 – 우버(Uber)의 이동:

ㅇㅇ