[DB] Key (Index) 는 어떻게 동작하나?

 

 

쿼리에서 Key를 타면 시간 복잡도?

예상 O(1) or O(log N) ✅

복합키면 시간 복잡도?

위와 그대로

 

결국 DB도 해시테이블 구조라 해싱 컴퓨팅 비용만 들이고

미리 키만 저장하면 O(1)이 들거라 생각.

복합키면 해싱 비용이 더 들어갈 뿐이지 시간복잡도의 오르내림은 없을것.

 

 

틀렸다.
해시 테이블이 아니라
B-Tree의 O(Log N)

 

Example table

 

Full Table Scan

테이블의 전체 row 를 확인하는 것.

-- name is not indexed column
EXPLAIN ANALYZE SELECT id
FROM test.public.users
WHERE name='kkk';

실행 결과 `Seq Scan` 이 이뤄짐을 알 수있다. postgresql 에서의 `Seq Scan` 은 Full Scan과 같다.

Seq Scan on users  (cost=0.00..1.26 rows=1 width=36) (actual time=0.013..0.014 rows=0 loops=1)
  Filter: ((name)::text = 'kkk'::text)
  Rows Removed by Filter: 23

 

Index Scan

-- Index table scan
-- since `id` is indexed column (Primary Key)
EXPLAIN ANALYZE SELECT id
FROM user
WHERE id=2

PK인 `id`를 태워 보냈는데도 `Seq Scan` 이 일어났다.

같은 쿼리에 PK 인 `id` (index column) 조건을 걸었는데도 왜 `Seq Scan` 이 일어나는가?

 

-- index scan 강제하기
SET enable_seqscan = OFF;

Index scan 성공.

 

 

 

 

해시테이블이 아닌 B-Tree

DB의 모든 인덱스는 보통 B-Tree로 정렬 및 저장된다.

B-Tree 의 연산 (Insert, Delete, Search)의
시간 복잡도는 O(Log N) 이다.

 

Index 는 포인터를 함께 저장한다

특정 컬럼에 Index 를 걸면, 해당 컬럼이 자신이 속한 row (다른 attributes) 를 통째로 가리킨다.

즉, 포인터를 저장한다.

여기서 바로 Hash-Table 구조를 엿볼 수 있다.

모든 컬럼의 Key 값 (B-Tree에 정렬, 저장되는) 이 키가 되고, 해당 키는 row라는 값을 갖는 것이다.

 

Key (Indexed)	Value
Sorted & Stored in B-Tree value about specific column	row data pointed by key

 

A pointer is a reference to a place in memory where the relevant row data is stored on disk.

 

 

DB는 쿼리하는 순간, 일단 키부터 찾는다.

쿼리내에 indexed column 이 존재하는지 우선 찾고, 없으면 Full Scan 때린다.

👉🏻 속도 구데기.

 

 

인덱싱의 단점은 없는가?

컴퓨팅 비용 : 모든 operation ( Search & Insert & Delete )등 에서 O(log N) 의 시간이 발생.

 

⚠️ 이론과 달리 index scan이 무조건 seq scan (full scan) 보다 빠른건 아니다.

index scan 시 '포인터'를 타야하기 때문이다.

테이블의 크기와 예상 반환 row 의 수에 따라 쿼리 optimizer 가 스캔 방식을 달리하는 메커니즘이 내장되어있다는 뜻이다.

 

위 예제에선 전체 row 가 23개밖에 되지 않아서 굳이 index scan을 통해 키를 찾고 포인터 간접참조를 하기보다, 전체 데이터를 스캔(Seq Scan) 하여 필터링 하는 것이 더 짧게 걸린다고 optimizer 가 판단한 것이다.

 

📝 Conclusion

1. 쿼리 짤 때 인덱스 타도록해라. 
   허나 인덱스를 포함시킨 쿼리를 날려도 optimizer 에 의해 다르게 동작할 수 있다.
   `enable_seqscan` 같은 옵션을 조절하자.
2. 인덱스는 B-Tree 구조로 정렬 & 저장된다.
   모든 동작은 O(Log N) 이다.
3. 자주 index query 를 할 가능성이 있는 컬럼에만 인덱스를 걸어야한다.
   == 자주 사용되는 쿼리를 고려하여 테이블 스키마를 설계해야한다.