kingsubin

PostgreSQL Index 관련 문서보고 너무 자세한 부분은 빼고 필요해 보이는 부분 정리했다.

잘못 이해해서 틀린 부분이 있을수도 있으니 정확한 정보는 문서에서 보는걸 추천..

내가 읽는 것도 어려웠어서 메모의 느낌이 아니라 알려주는 목적으로 읽기 쉽게 적는건 어려웠다. 다음 기회에 계속...

 

---

Index

• 빠른 검색을 위해 필요하다.
• 자료구조 선택
  • 이진트리의 경우 자식 노드의 최대 개수가 2개여서 데이터 양이 많을 경우 트리의 높이가 높아질 수 있고, 한쪽으로 편향된 트리의 모양을 가질 수 있다.
  • AVL Tree 나 Red-black Tree 와 같은 균형 잡힌 트리를 사용하면 안 되나요?
    • 한쪽으로 편향된 이진트리보다는 낫지만 여전히 자식노드의 수는 최대 2개이다.
  • B-Tree의 경우 편향되지 않고 이진트리에 비해 자식 노드를 많이 가질 수 있어 트리의 높이가 이진트리에 비해 낮아서 더 효율적이다.
  • B+Tree의 경우 leaf node를 제외하고는 데이터를 저장하지 않아 트리의 높이가 B-Tree 보다 더 낮아질 수 있다. 더 좋은 점은 left node 끼리 Linked List 로 연결되어 있어 range scan, full scan 에서 더 효율적이다.
  • 문서에서 B-Tree 라고 표기하지만 구현 설명을 보면 정확히는 B+Tree 를 사용한다.
• 그렇다고 무조건 Index 를 생성해서 사용하면 좋냐면 그건 또 아니다.
  • 추가 저장공간이 필요하다.
  • 조회가 아니라 insert, update, delete 시에는 인덱스를 정렬된 상태로 유지해야 해서 추가 시간이 걸린다.
• 그러면 언제 사용하는 게 좋은가?
  • sequential table scan 보다 효율적이라고 판단할 때 사용한다.
  • 데이터의 중복이 적고 insert, update, delete 가 자주 발생하지 않을 때 좋다.

---

11.1 Introduction

• query planner 가 검색에 내가 원하는 인덱스를 잘 사용하고 있는지 확인하려면 ANALYZE 명령어를 사용한다.
• 사이즈가 큰 테이블에서 인덱스를 생성할 때는 시간이 오래 걸린다.
• 인덱스 생성 시 병렬로 읽기는 허용하지만 쓰기는 인덱스가 빌드될 때까지 허용하지 않는다. 인덱스 생성과 쓰기를 병렬로 허용하려면 Building Indexes Concurrently 를 참조

---

11.2 Index Types

• B-tree, Hash, GiST, SP-GiST, GIN, BRIN 등 여러 인덱스 유형을 제공한다.
• 다른 인덱스 타입을 사용하겠다고 명시하지 않으면 기본적으로는 B-Tree 인덱스 타입을 생성한다.
• B-Tree
  • query planner 는 인덱싱 된 컬럼이 <, <=, =, >=, > 연산자를 사용하는 비교를 할 때 B-Tree 인덱스 사용을 고려한다.
  • 위 연산자의 조합에 해당하는 BETWEEN, IN 과 같은 비교도 B-Tree 인덱스 검색으로 구현할 수 있다.
  • IS NULL, IS NOT NULL 과 같은 키워드도 B-Tree 인덱스 검색으로 구현할 수 있다.
  • optimizer 는 LIKE 키워드 사용 시 문자열 시작 부분이 고정된 경우와 같은 패턴 매칭 연산자를 포함하는 쿼리에 B-Tree 인덱스를 사용할 수 있다. ex. col LIKE 'foo%'
  • 대/소문자 변환의 영향을 받지 않는 알파벳이 아닌 문자로 시작할 때 ILIKE 키워드 사용 시에도 B-Tree 인덱스를 사용할 수 있다.
• Hash Index
  • 해시 인덱스는 32비트 해시 코드를 저장한다.
  • 단순 동등성 비교만 처리할 수 있다.
  • query planner 는 동등 연산자를 포함할 때 해시 인덱스 사용을 고려한다.

---

11.3 Multicolumn Indexes

• B-Tree, GiST, GIN, BRIN 인덱스 타입만 multicolumn index를 지원한다.
• 인덱스는 INCLUDE 컬럼을 포함하여 최대 32개의 열을 가질 수 있다.
• 대부분의 상황에서 single column 인덱스는 충분하다. 3개 이상의 multiple column 인덱스는 테이블 사용이 extremely stylized 하지 않는 한 유용하지 않을 수 있다.

---

11.4. Indexes and ORDER BY

• 인덱스는 별도의 정렬 단계 없이 ORDER BY 를 사용하면 정렬 순서로 제공할 수 있다.
• 현재 B-Tree 인덱스만 정렬을 제공하며, 다른 인덱스 유형은 unspecified, implementation-dependent order 하는 행을 리턴한다.
• planner 는 ORDER BY 사양과 일치하는 인덱스, 물리적 순서로 테이블을 스캔하고 명시적 정렬을 사용하여 사양을 만족시키는 것 중에서 고려한다.
• 테이블의 많은 부분을 스캔해야 하는 쿼리일 때, sequential access pattern 을 따르는 명시적 정렬은 disk I/O 가 덜 필요해서 인덱스보다 더 빠를 수 있다.
• ORDER BY 와 LIMIT n 을 조합하는 경우: 명시적 정렬은 n 개의 rows 를 식별하기 위해 모든 데이터에 접근해야 하지만, ORDER BY와 매칭되는 인덱스가 있으면 나머지 스캔하지 않고 첫 번째 행을 찾을 수 있다.
• 기본적으로, B-Tree 인덱스는 마지막에 null이 있는 오름차순으로 정렬한다.
• 인덱스를 정방향으로 스캔하면 만족스러운 결과를 출력한다.
• B-Tree 인덱스 생성 시 ASC, DESC, NULLS FIRST, NULLS LAST 를 사용하여 순서를 조정할 수 있다.

 

ex. index (x, y):

• Good
  • ORDER BY x, y
  • ORDER BY x DESC, y DESC
• Bad
  • ORDER BY x ASC, y DESC
  • x ASC, y DESC) or (x DESC, y ASC)

기본 정렬 순서가 아니라 특수한 정렬 순서를 가지는 인덱스는 엄청난 속도 향상을 가져올 수 있다. 특수한 정렬 순서가 필요한 쿼리를 얼마나 사용하느냐에 따라 다르다.

---

11.5. Combining Multiple Indexes

• 단일 인덱스 스캔은 해당 연산자 클래스의 연산자와 함께 인덱스의 열을 사용하고 AND로 결합된 쿼리절만 사용할 수 있다.
  • Index (a, b) 가 있을 때, WHERE a = 5 AND b = 6 는 인덱스를 사용하지만, WHERE a = 5 OR b = 6 은 인덱스를 직접 사용할 수 없다.
• pg 에는 단일 인덱스 스캔으로 구현할 수 없는 경우를 처리하기 위해 multiple indexes(동일 인덱스의 여러 사용을 포함하는) 를 결합하는 기능이 있다.
  • WHERE x = 42 OR x = 47 OR x = 53 OR x = 99 와 같은 쿼리는 4개의 개별 스캔으로 분류될 수 있다.
  • x 와 y 에 별도의 인덱스가 있을 때, WHERE x = 5 AND y = 6 과 같은 쿼리의 경우 적절한 쿼리절과 함께 각 인덱스를 사용하고 인덱스 결과를 함께 AND 하여 식별한다.
• multicolumn 인덱스가 가장 좋은 경우도 있지만 별도의 인덱스를 만들고 인덱스 조합 기능에 의존하는 것이 더 나은 경우도 있다.

 

ex. 작업에 column x 또는 y 만 사용하거나 x, y 모두 포함하여 사용하는 경우

• 별도의 인덱스 x, y 를 생성하고 조합하여 사용
  • x, y 모두 포함하는 경우 multicolumn index 보다는 아니지만 잘 작동함.
  • x, y 따로 포함하는 경우도 잘 작동함.
• 인덱스 (x, y) 를 만들어 사용
  • x, y 모두 포함하는 경우 index combination 보다 효율적임.
  • y 만 포함하는 경우 거의 쓸모가 없음.
  • x 만 포함하는 경우 사용은 가능하지만 단일 인덱스 x 보다 크기가 크고 속도가 느림.
• x, y, (x, y) 모두 생성하여 사용
  • 테이블이 업데이트되는 것보다 훨씬 더 자주 검색되고, 세 가지 유형의 쿼리가 모두 사용되는 경우에만 유용함.

---

11.6. Unique Indexes

• 현재 B-Tree 인덱스만 Unique 선언할 수 있다.
• Null 값은 같은 것으로 간주하지 않는다.
• multicolumn unique index 는 모든 인덱싱 된 열이 동일한 경우에만 거부한다.
• PostgreSQL은 unique constraint, primary key 가 테이블에 정의될 때 자동으로 unique index 를 생성한다.
• unique column 에 명시적으로 인덱스 생성할 필요 없고 그렇게 하면 자동으로 생성된 인덱스가 복제된다.

---

11.7. Indexes on Expressions

• 인덱스는 하나 이상의 열에서 계산된 function 또는 scalar expression 일 수 있다.
• 계산 결과를 기반으로 테이블에 빠르게 액세스 하는데 유용하다.

 

ex. SELECT * FROM test1 WHERE lower(col1) = 'value'

• CREATE INDEX test1_lower_col1_idx ON test1 (lower(col1)) 로 생성한 인덱스를 사용할 수 있다.
• 이때 인덱스를 UNIQUE 로 선언하면, col1 값이 대/소문자가 달라도 UNIQUE 제약조건이 걸려 생성을 방지한다.

ex. SELECT * FROM people WHERE (first_name || ' ' || last_name) = 'John Smith'

• 위 쿼리를 자주 사용한다면 CREATE INDEX people_names ON people ((first_name || ' ' || last_name)) 로 인덱스를 생성할 가치가 있다.

 

• Index expressions 은 삽입이나 삭제에 상대적으로 유지 비용이 많이 든다.
• 그러나 Index expressions 은 이미 저장되어 있으므로 검색 중에 다시 계산되지 않는다.
• 위 두 예시의 경우 시스템은 쿼리를 WHERE indexcolum = 'constant' 와 같이 인식하므로 검색 속도는 다른 인덱스 쿼리와 동일하다.
• 따라서 Index expressions 은 검색 속도가 insert, update 보다 더 중요할 때 유용하다.

---

11.8. Partial Indexes

• partial index 는 테이블의 하위 집합에 구축된 인덱스이다.
• 부분 인덱스를 사용하는 주요 이유 중 하나는 공통 값을 인덱싱 하지 않기 위해서이다.

 

Setting up a Partial Index to Exclude Common Values
ex. web server access logs 저장한다고 가정, 대부분의 IP 주소는 조직의 IP 주소 범위에서 발생, IP 를 검색하는 것이 주로 외부 액세스를 위한 것이라면 조직의 서브넷에 해당하는 IP 범위는 인덱싱 할 필요가 없을 것

• CREATE INDEX access_log_client_ip_ix ON access_log (client_ip) WHERE NOT (client_ip > inet '192.168.100.0' AND client_ip < inet '192.168.100.255') 와 같이 partial index 를 생성할 수 있음.
• SELECT * FROM access_log WHERE url = '/index.html' AND client_ip = inet '212.78.10.32' 해당 쿼리는 partial index 를 사용할 수 있음.
• SELECT * FROM access_log WHERE url = '/index.html' AND client_ip = inet '192.168.100.23' 해당 쿼리는 partial index 를 사용할 수 없음.
• 이러한 종류의 partial index 는 공통 값이 미리 결정되어 있어야 하므로 변경되지 않는 데이터 분포에 적합하다.

 

Setting up a Partial Index to Exclude Uninteresting Values
ex. unbilled orders, billed orders 가 있는 orders 테이블이 존재함. unbilled orders 는 전체 테이블의 작은 부분을 차지하지만 가장 많이 액세스 되는 경우 unbilled orders 에 대해서만 index 를 생성하여 성능을 향상할 수 있다.

• CREATE INDEX orders_unbilled_index ON orders (order_nr) WHERE billed is not true 와 같이 partial index 를 생성할 수 있다.
• SELECT * FROM orders WHERE billed is not true AND order_nr < 10000 해당 쿼리는 partial index 를 사용할 수 있음. order_nr 없이도 가능하다.
• 해당 partial index 는 전체 인덱스를 스캔해야 하므로 다른 인덱스만큼 효율적이지 않다. 그러나 위 조건과 같이 unbilled orders가 상대적으로 적을 때는 인덱스를 생성하여 사용하는 것이 더 유리할 수 있다.

 

Setting up a Partial Unique Index
ex. subject, target, success 컬럼이 있고 successful: (subject, target) 이 테이블에 하나의 entry 만 존재함. 그러나 unsuccessful은 은 여러 entries 가능

• CREATE UNIQUE INDEX tests_success_constraint ON tests (subject, target) WHERE success
• 해당 partial index 는 조건과 같이 successful 이 거의 없고 unsuccessful이 많을 때 효율적이다.

 

Do Not Use Partial Indexes as a Substitute for Partitioning

# 1번
CREATE INDEX mytable_cat_1 ON mytable (data) WHERE category = 1;
CREATE INDEX mytable_cat_2 ON mytable (data) WHERE category = 2;
CREATE INDEX mytable_cat_3 ON mytable (data) WHERE category = 3;
...
CREATE INDEX mytable_cat__`N`_ ON mytable (data) WHERE category = _`N`_;

# 2번
CREATE INDEX mytable_cat_data ON mytable (category, data);

• 1번 같이 a large set of non-overlapping partial indexes 를 생성할 수 있으나 이것은 나쁜 생각이고 2번과 같이 single non-partial index 를 사용하는 것이 더 나을 것이다.
• 2번 인덱스의 경우 1번 인덱스보다 더 크기 때문에 더 많은 트리 수준을 내려가야 하지만 planner가 1번의 partial index 중 적절한 하나를 선택하는데 드는 비용보다는 확실히 적을 것이다.
• 테이블이 너무 커서 단일 인덱스의 성능이 좋지 않은 경우 파티셔닝을 고려해야 함. 파티셔닝의 경우 시스템이 테이블과 인덱스가 겹치지 않는 것을 이해하므로 훨씬 더 나은 성능이 가능하다.

---

11.9. Index-Only Scans and Covering Indexes

• 모든 인덱스는 테이블의 기본 데이터 영역(table's heap) 과 별도로 저장된다.
• 즉, 일반적인 인덱스 스캔에서의 검색에는 인덱스와 힙 모두에서 데이터를 가져와야 한다.
• 성능 문제를 위해 힙 액세스 없이 인덱스에서만 쿼리에 응답하는 index-only scan을 지원한다.

 

index-only scan 의 조건

• index-only scan 을 지원하는 인덱스 타입이어야 한다.
• GiST, SP-GiST 인덱스는 일부 연산자 클래스에 대해서만 지원하고, B-Tree 인덱스는 항상 index-only scan 을 지원한다.
• 쿼리는 인덱스에 저장된 열만 참조해야 한다.

ex. 인덱스 (x, y), z 가 있을 때

• SELECT x, y FROM tab WHERE x = 'key', SELECT x FROM tab WHERE x = 'key' AND y < 42 는 index-only scan 을 지원함.
• SELECT x, z FROM tab WHERE x = 'key', SELECT x FROM tab WHERE x = 'key' AND z < 42 는 index-only scan 을 지원하지 않음.

 

covering index

• index-only scan 을 효과적으로 사용하기 위해 covering index (자주 실행하는 특정 유형의 쿼리에 필요한 열을 포함하도록 특별히 설계된 인덱스) 를 생성할 수 있다.
• SELECT y FROM tab WHERE x = 'key' 과 같은 쿼리를 실행할 때 일반적으로는 x 에 대한 인덱스를 만든다.
• CREATE INDEX tab_x_y ON tab(x) INCLUDE (y) 와 같이 covering index 를 만들면 y에 대하여 힙을 방문하지 않고 인덱스에서 얻을 수 있기에 index-only scan 으로 처리할 수 있다.
• 이때 column y 는 인덱스 검색 키의 일부가 아니므로 인덱스가 처리할 수 있는 데이터 유형이 아니어도 상관없다.
• CREATE UNIQUE INDEX tab_x_y ON tab(x) INCLUDE (y) 와 같이 unique 인덱스를 생성할 수 도 있는데 마찬가지로 uniqueness 조건은 x 컬럼에만 적용된다.
• key 가 아닌 payload column 을 인덱스에 추가할 때는 보수적인 태도를 취하는 것이 좋다.
  • 인덱스 튜플이 인덱스 유형에 허용된 최대 크기를 초과하면 데이터 삽입이 실패한다.
  • 키가 아닌 열은 인덱스 테이블의 데이터를 복제하고 인덱스 크기를 팽창시켜 잠재적으로 속도 저하시킨다.

---

11.11. Indexes and Collations

• 인덱스는 인덱스 컬럼당 하나의 collation 만 지원합니다.
• 여러 collations 가 필요한 경우, 여러 인덱스가 필요합니다.
• 인덱스는 열의 collation 을 자동으로 사용합니다.

CREATE TABLE test1c (
    id integer,
    content varchar COLLATE "x"
);

# 1
CREATE INDEX test1c_content_index ON test1c (content);

# 2
CREATE INDEX test1c_content_y_index ON test1c (content COLLATE "y");

• SELECT * FROM test1c WHERE content > constant 해당 쿼리는 1번 인덱스를 사용할 수 있다.
• SELECT * FROM test1c WHERE content > constant COLLATE "y" 해당 쿼리는 1번 인덱스를 사용할 수 없고 collation "y" 를 지원하는 2번 인덱스를 추가해서 사용해야 한다.

---

11.12. Examining Index Usage

• 어떤 인덱스를 생성할지 결정하는 것은 어렵고 많은 테스트가 필요하다.
• 실험을 위해 실제 데이터를 사용하세요.
  • 적은 data sets 이나 production 의 data 와 다른 임의의 값은 통계를 왜곡합니다.
• 항상 ANALYZE 를 먼저 실행하세요.
  • 쿼리에서 실제로 사용되고 있는 인덱스는 어떤 것인지, 내가 의도한 인덱스를 사용하고 있는지 확인해야 한다.

 

---

• https://www.postgresql.org/docs/current/indexes.html
• https://www.postgresql.org/docs/current/btree.html
• https://www.postgresql.org/docs/current/storage-page-layout.html