Real MySQL 1권 (p.247 ~ 265)
B-Tree 인덱스
가용성과 효율성
작업 범위 결정 조건 : 인덱스 스캔 범위를 결정하는 조건
필터링 조건 : 스캔 범위를 줄이지 못하고 필터 역할만 하는 조건
INDEX ix_test ( column_1, column_2, column_3, ..., column_n )과 같은 인덱스가 존재할 때 작업 범위 조건으로 인덱스를 사용할 수 있는 조건
column_1~column_(i - 1)칼럼까지동등 비교 형태('=' 또는 'IN')로 비교column_i칼럼에 대해 동등 비교, 부등호 비교,LIKE좌측 일치 패턴 비교
R-Tree 인덱스
MySQL의 공간 인덱스
구조 및 특성
지원하는 데이터 타입은 point, line, polygon, geometry
핵심은 MBR(Minimum Bounding Rectangle)로, 해당 도형을 감싸는 최소 크기의 사각형을 의미
인덱스는 MBR의 포함 관계를 기반으로 B-Tree 형태로 생성됨
용도
ST_Contains(), ST_Within() 등의 포함 관계 비교 함수로 검색할 때 사용
SELECT * FROM tb_location WHERE ST_Contains(사각 상자, px);전문 검색 인덱스
B-Tree 인덱스의 한계
InnoDB의 경우 3072바이트까지만 잘라서 인덱스 키로 사용
전체 일치 또는 좌측 일부 일치 같은 검색만 가능
전문 검색에는 사용 불가
전문 검색 인덱스란
문서 전체에 대한 분석과 검색을 위한 인덱싱 기능
어근 분석 알고리즘
불용어 처리 -> 어근 분석 과정을 거쳐 이루어짐
불용어 처리 : 검색에서 별 의미 없는 단어를 필터링하는 작업
어근 분석 : 단어의 원형을 찾는 작업
한글의 경우 어근 분석보다는 형태소를 분석함 (형태소 분석 프로그램인 MeCab을 사용 가능)
형태소 분석이 제대로 수행되려면 분석 모델을 언어 샘플을 사용해 학습시켜야 하는데, 이 과정에 많은 노력이 필요함
n-gram 알고리즘
본문을 n 글자씩 잘라서 인덱싱하는 방법, 보통 2-gram(Bi-gram)이 많이 사용됨
단순해서 어근 분석 알고리즘보다 범용적으로 적용 가능하지만 인덱스의 크기가 상당히 큰 편
불용어와 일치하거나 불용어를 포함하는 경우 필터링하고 최종 인덱스 등록
가용성
다음 두 조건을 갖춰야 전문 검색 인덱스를 사용 가능
- 쿼리 문장이 전문 검색을 위한 문법
(MATCH ... AGAINST ...)을 사용 - 테이블이 전문 검색 대상 칼럼에 대해서 전문 검색 인덱스 보유
CSAPP (p.577 ~ 583)
5.9.2 Reassociation Transformation
k * 1a loop unrolling
CPE를 Latency Bound 아래로 낮추는 또 하나의 방법
하나의 mul 연산만이 loop register 사이의 data dependency를 이루므로 critical path를 구성하는 연산의 수가 절반이 되고, minimum possible CPE도 절반이 됨
k * 1a loop unrolling도 k * k unrolling과 비슷한 성능 향상을 만들어 냄
k가 충분히 크면 throughput bound에 가까운 성능 도달
한계
reassociation을 통해 연산 순서를 바꾸므로 associative하지 않은 floating-point addition, multiplication에 대해서는 동일한 결과가 나오리라는 보장이 없음 -> 컴파일러는 최적화를 수행하지 않음
GCC는 정수 연산에 대해 reassociation을 수행하지만, 효과가 항상 좋은 것은 아님
일반적으로 k * k loop unrolling이 더욱 신뢰성 있는 프로그램 성능 향상을 위한 방법임
SIMD
SIMD : Single Instruction, Multiple Data
SSE : Streaming SIMD Extensions
AVX : Advanced Vector eXtensions
SIMD execution model은 하나의 명령어로 전체 벡터에 대한 연산을 수행
벡터는 vector register에 저장되는데, 현대의 AVX 벡터 레지스터는 32바이트 길이를 가짐 (8개의 32비트 숫자, 4개의 64비트 숫자를 저장할 수 있음)
//Multiply Packed Single-Precision Floating-Point Values
vmulps (%rcx), %ymm0, %ymm1