V-최적 히스토그램

히스토그램은 데이터의 시각적 표현으로 가장 일반적으로 사용된다.그러나 데이터베이스 시스템은 히스토그램을 사용하여 내부적으로 데이터를 요약하고 쿼리의 크기 추정치를 제공한다.이러한 히스토그램은 사용자에게 제공되거나 시각적으로 표시되지 않으므로 이들의 구성에 더 광범위한 옵션을 사용할 수 있다.단순하거나 이국적인 히스토그램은 정렬 값, 소스 값, 파티션 클래스 및 파티션 규칙의 네 가지 매개변수로 정의된다.가장 기본적인 히스토그램은 등폭 히스토그램이며, 여기서 각 버킷은 동일한 범위의 값을 나타낸다.이 히스토그램은 "Sort Value of Value"인 "Source Value of Frequency"가 시리얼 파티션 클래스에 있고 모든 버킷의 범위가 동일하다는 파티션 규칙을 갖는 것으로 정의된다.

V-최적 히스토그램은 보다 "이항적" 히스토그램의 예다.V-최적성은 버킷의 누적 가중 분산을 최소화하기 위해 버킷 경계를 배치한다는 파티션 규칙이다.이 규칙의 시행은 복잡한 문제이며 이러한 히스토그램의 구성도 복잡한 과정이다.

정의

v-최적 히스토그램은 이러한 맥락에서 가중 분산이라고 하는 양을 최소화하는 개념을 기반으로 한다.^[1]이것은 다음과 같이 정의된다.

${\displaystyle W=\sum _{j=1}^{J}n_{j}V_{j}\...}$

여기서 히스토그램은 J 빈 또는 버킷으로 구성되며, n은_j j번째 빈에 포함된 항목의 수이고, 여기서 V는_j j번째 빈의 항목과 관련된 값 사이의 분산이다.

예

다음 예제는 값 정렬 값, 주파수 소스 값 및 직렬 파티션 클래스를 포함하는 V-최적 히스토그램을 구성한다.실제로 연구나 상용 제품에 사용되는 거의 모든 히스토그램은 직렬 등급으로, 순차 정렬 값이 동일한 버킷 또는 순차 버킷에 배치된다는 것을 의미한다.예를 들어 값 1, 2, 3, 4는 버킷 1과 2 또는 버킷 1, 2와 3으로 표시되지만 버킷 1과 3에는 표시하지 않는다.그것은 그 이상의 논의에서 가정으로 받아들여질 것이다.

예를 들어, 정수 목록과 같은 간단한 데이터 집합을 취하십시오.

1, 3, 4, 7, 2, 8, 3, 6, 3, 6, 8, 2, 1, 6, 3, 5, 3, 4, 7, 2, 6, 7, 2

값 및 주파수 쌍(1, 2), (2, 4), (3, 5), (4, 2), (5, 1), (6, 4), (7, 3), (8, 2)를 계산한다.

우리의 V-최적 히스토그램은 두 개의 버킷을 가질 것이다.한 버킷은 8시 데이터 지점에서 끝나야 하기 때문에, 우리는 다른 버킷 경계를 어디에 둘지 결정해야 한다.V-최적성 규칙은 버킷의 누적 가중 분산을 최소화해야 한다고 명시한다.우리는 두 가지 옵션을 살펴보고 그 옵션의 누적 분산을 계산할 것이다.

옵션 1: 버킷 1에는 1~4의 값이 포함되어 있다.버킷 2는 5에서 8까지의 값을 포함한다.

버킷 1:
평균 주파수 3.25
가중분산 2.28

버킷 2:
평균 주파수 2.5
가중분산 2.19

가중 분산 합계 4.47

옵션 2: 버킷 1에는 값 1 ~ 2가 포함되어 있다.버킷 2는 3에서 8까지의 값을 포함한다.

버킷 1:
평균 주파수 3
가중분산 1.41

버킷 2:
평균 주파수 2.83
가중분산 3.29

가중 분산 합계 4.70

첫 번째 선택이 더 낫기 때문에 히스토그램이 저장되는 것은 다음과 같다.
버킷 1: 범위(1–4), 평균 주파수 3.25
버킷 2: 범위(5–8), 평균 주파수 2.5

V-최적성과 등거리 또는 등거리의 장점

V-최적 히스토그램은 버킷 내용을 더 잘 추정한다.히스토그램은 기준 데이터의 추정치로서 모든 히스토그램에 오류가 있을 것이다.VOptimal 히스토그램에 사용되는 파티션 규칙은 버킷 간에 가능한 가장 작은 분산을 시도하며, 이는 더 작은 오류를 제공한다.Poosala와 Ioannidis 1의 연구는 데이터의 가장 정확한 추정이 VOptimal 히스토그램으로 이루어지며, 값을 정렬 파라미터로, 주파수를 소스 파라미터로 사용한다는 것을 보여주었다.

V-최적성 대 등폭 또는 등깊이의 단점

V-최적 히스토그램이 더 정확하지만 단점이 있다.그것은 갱신하기 어려운 구조다.소스 매개변수를 변경하면 기존 히스토그램을 업데이트하는 대신 히스토그램을 완전히 다시 작성해야 할 수 있다.등폭 히스토그램에는 이 문제가 없다.에퀴 깊이 히스토그램은 이 문제를 어느 정도 겪게 되겠지만, 에퀴 깊이 구조가 단순하기 때문에 유지 비용이 더 저렴하다.VOptimal 히스토그램 업데이트의 어려움은 이러한 히스토그램을 구성하는 데 수반되는 어려움의 결과물이다.

V-최적 히스토그램 계산은 다른 유형의 히스토그램에 비해 계산 비용이 많이 든다.^[2]

건설현안

위의 예는 간단한 것이다.버킷 경계선 선택은 7개뿐이다.7가지 옵션 모두에 대한 누적 분산을 쉽게 계산할 수 있고 절대 최적 배치를 선택할 수 있다.그러나 값의 범위가 커지고 버킷의 수가 커질수록 가능한 히스토그램의 집합은 기하급수적으로 증가하며, 순진한 접근법을 사용하여 절대 최소 분산을 제공하는 경계 집합을 찾는 것은 위압적으로 복잡한 문제가 된다.동적 프로그래밍을 사용하여 V-최적 히스토그램을 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle O(N^{2}B)}$에서 계산할 수 있으며, 여기서$$ N은 데이터 포인트 수, B는 버킷 수입니다.^[3]

최적 히스토그램을 찾는 것은 이차적이므로 대신 V-최적 히스토그램에 근사치를 적용하는 것이 일반적이다.무작위 솔루션을 만들고, 이를 출발점으로 삼아 개선함으로써, "최고의" 솔루션의 공정한 근사치인 솔루션을 찾을 수 있다.이 문제를 해결하는 데 사용되는 한 가지 방법은 반복 개선 알고리즘이다.또 다른 것은 시뮬레이션된 어닐링이다.이 두 가지를 2상 최적화 또는 2PO로 결합할 수 있다.이러한 알고리즘은 "임의의 알고리즘"에 제시되어 있다.쿼리를 최적화하는 방법으로 " (아래 참조) 그러나 일반적인 아이디어는 V-최적 히스토그램의 구축에 적용될 수 있다.

반복 개선

반복 개선(II)은 상당히 순진한 탐욕스러운 알고리즘이다.무작위 상태에서 시작하여 여러 방향으로 반복적인 단계를 고려한다.비용을 가장 잘 개선할 수 있는 단계(이 경우 총 분산)를 취한다.이 과정은 더 이상의 개선이 불가능한 국소적 최소치에서 정착될 때까지 반복된다.V-최적 히스토그램의 구성에 적용되는 초기 무작위 상태는 버킷 경계 배치를 나타내는 값의 집합일 것이다.반복적인 개선 단계는 각 경계를 국부적 최소값까지 이동한 후 다음 경계로 이동하고 그에 따라 조정하는 것을 포함한다.

시뮬레이션 어닐링

시뮬레이션 아닐링의 기본적인 설명은 그것이 II와 많이 비슷하다는 것이다. 단지 매번 탐욕스러운 단계를 취하는 대신, 때때로 비용이 증가하는 단계를 받아들일 것이다.이론적으로, SA는 국지적인 최소치에서 멈출 가능성이 낮을 것이고, 더 세계적인 것을 찾을 가능성이 더 높을 것이다.유용한 이미지 조각은 "M" 모양의 그래프로 Y축의 전체 비용을 나타낸다.초기 상태가 "M"의 "V"자형 부분일 경우 II는 국소 최소값인 높은 계곡에 정착하게 된다.SA는 오르막길을 받아들이기 때문에 'V'의 비탈을 올라 글로벌 최소치인 'M'의 기슭에 서게 될 가능성이 높다.

2상 최적화

2상 최적화, 즉 2PO는 II와 SA 방법을 결합한다.II는 로컬 최소치에 도달할 때까지 실행되며, 그 후 SA는 덜 분명한 개선을 찾기 위한 시도로 해당 솔루션에 대해 실행된다.

변형

V-최적 히스토그램의 이면에 있는 아이디어는 각 버킷 내부의 분산을 최소화하는 것이다.이를 고려할 때, 멤버 1명과의 세트의 분산이 0이라는 생각이 든다.이것은 "End-Biased" V-최적 히스토그램 뒤에 숨겨진 생각이다.주파수가 가장 높은 값은 항상 자체 버킷에 배치된다.이렇게 하면 해당 값(가장 빈번한 값이기 때문에 가장 자주 요청되는 추정치일 가능성이 높은 값)에 대한 추정치가 항상 정확하고 데이터 집합에서 높은 분산을 일으킬 가능성이 가장 높은 값도 제거된다.

또 다른 생각으로는 가치 대신 빈도로 분류하면 분산이 줄어든다는 것이다.이것은 자연스럽게 같은 가치를 서로 옆에 두는 경향이 있을 것이다.그러한 히스토그램은 주파수 정렬 값과 주파수 소스 값을 사용하여 구성할 수 있다.그러나 이때 버킷에는 버킷에 어떤 데이터 값이 있는지 나타내는 추가 정보가 있어야 한다.이러한 히스토그램은 추가적으로 요구되는 추정 계층 때문에 정확도가 떨어지는 것으로 나타났다.

참조

인용된 작품

• Poosala, V.; Haas, P. J.; Ioannidis, Y. E.; Shekita, E. J. (1996). "Improved histograms for selectivity estimation of range predicates". Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96. p. 294. doi:10.1145/233269.233342. ISBN 978-0897917940. S2CID 2948277. PDF 다운로드
• Ioannidis, Y. E.; Poosala, V. (1995). "Balancing histogram optimality and practicality for query result size estimation". Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95. p. 233. doi:10.1145/223784.223841. ISBN 978-0897917315. S2CID 15298037. PDF 다운로드
• Ioannidis, Y. E.; Kang, Y. (1990). "Randomized algorithms for optimizing large join queries". ACM SIGMOD Record. 19 (2): 312. doi:10.1145/93605.98740. PDF 다운로드