잘지내자, 우리 잘지내자, 우리

이번 장에서는 쿼리 실행에 대한 원칙에 대해 배워보자. 쿼리에 답하기 위한 cost(비용)은 다음 두 가지에 영향을 받는다. 파티셔닝 원칙(Partitioning principle) 쿼리 실행 알고리즘(Query execution algorithm) 파티셔닝 원칙은 지난 블로그에서 다뤘으니, 이번에는 쿼리 실행 알고리즘에 대하여 다뤄보겠다. 알고리즘들을 보기 앞서, Hypothetical Index Organiztion에 대해 알아볼 필요가 있다. Hypothetical의 사전적 의미는 '가상의'라는 뜻으로, 직역하자면 '가상의 인덱스 구성'이라고 볼 수 있겠다. 일반적인 Array를 생각해보면, 각 배열에는 한개의 object가 존재한다. 하지만 위계질서(hierarchy)를 가진 entries로 노드..

이번 장에서는 기본적인 partitioning 원칙에 대해 다뤄보자. 거리 공간 M=(D,d)에 대하여 총 세 가지의 기본 분류 방법을 다뤄볼것이다. 1. Ball Partitioning 아주 기본적이고 간단한 방법이이다. 반지름 dm을 기준으로 안/ 밖에 속하는 object로 구분한 것이다. 좀 더 발전한 방법으로 Multi - way ball partitioning도 있다. 안과 밖의 두 집합으로 나누는 것이 아니라, 안/중간/밖 이렇게 세 부분으로 분류를 한다. 2. Generalized Hper-plane Partitioning Ball Partitioning이 원을 기준으로 구역이 나뉘었다면, Generalized hyper-plane Partitioning은 직선을 기준으로 로 구역이 나뉜다...