비트 맵 인덱스를 "가짜"로 만드는 것이 합리적입니까?

Question

나는 계량 된 데이터를 분석하는 데 도움이되는 OLAP 응용 프로그램을 계획하고 있으며 저장된 값이 다른 각도 (시간, 소스)에서 보일 것이므로 데이터베이스에 대해 일종의 스타 스키마를 갖게 될 것입니다. , 유형 등) 요청은 이러한 차원을 따라 집계 된 데이터를 요청할 것입니다. 쿼리는 많은 행을 전달하는 경향이 있습니다 (최대 약 100,000 개).

이 주제에 대한 연구 (my question here 참조)는 비트 맵 색인이 내가 계획하고있는 방식으로 데이터를 검색하는 좋은 방법임을 나타냅니다. 그러나, 나는 복수의 db 엔진을 지원하고자하는데, 그 중 일부는 테이블 (특히 MySQL)에 비트 맵 인덱스를 제공하지 않습니다.

이제 필자 만의 비트 맵 인덱스를 만들고 유지 관리하여 팩트 테이블을 가리키는 행 ID를 찾을 수 있습니다. 그러나 데이터베이스가 여전히 B-Tree에서 행 ID를 검색 할 것이기 때문에 이것이 인덱스의 모든 목적을 무력화시킬 것으로 생각됩니다. 더 심오한 이론적 배경이나 더 많은 경험을 가진 누군가가 치수 표에서 느린 결합을 할 필요가없는 것과 같이 여전히 무엇인가 얻으면 알려 줄 수 있습니까?

답이 간단하지 않은 경우 평가해야 할 사항에 대한 힌트를 주시면 감사하겠습니다.

Answer 1

비트 맵 인덱스를 직접 지원하지 않는 일부 DB 엔진은 사실 테이블을 치지 않고도 이러한 유형의 쿼리를 수행 할 수있는 별 최적화 기능을 제공합니다. 예를 들어, SQL Server에는 해상도를 수행하기 위해 즉석에서 비트 맵을 구성하여 비슷한 작업을 수행하는 Index Intersection이라는 기능이 있습니다. Microsoft 은으로,이 성능은 비트 맵 인덱스와 유사합니다. 이 주제에 대한 약간의 팬 아웃은 This posting을 참조하십시오.

MySQL이 이것을 수행한다면 내 머리 꼭대기에서 잘 모르겠지만 PostgreSQL은 분명히 그렇습니다. IIRC (Greenplum, 나는 생각한다)의 일부는 비트 맵 인덱스를 직접적으로 지원하며,이를 메인 DB 엔진에 통합하는 것에 대한 이야기가있다. 이것이 아직 끝나지 않았다면 나는 기억하지 못한다.

나는 현대의 DBMS 플랫폼이 스타 쿼리 최적화를 제공한다는 것을 알게 될 것이므로 휠을 다시 발명 할 필요는 없을 것입니다. 이 작업을 수행 할 수없는 하나 또는 두 가지를 찾을 수 있지만 항상 지원하지 않는 옵션이 있습니다.

Answer 2

사용자 정의 데이터 구조를 사용하여 메모리에서 많은 양의 데이터를 조작 할 때 비트 맵 인덱스를 사용하여 좋은 행운을 얻었지만 좋은 (타사 데이터베이스를 사용하지 않는 타사 데이터베이스를 구현하는 것은 다소 어색합니다. like) API를 사용하여 색인 구조를 확장합니다.

일반적으로 B- 트리 색인을 통해 검색 할 것이므로 내 경험이 어떤 가이드 일지라도 아무 것도 얻을 수 없습니다.

아니요.

응용 프로그램이 본래 OLAP이고 순서가 지정된 범위로 자연스럽게 그룹화되는 소수의 수가 있고 실제로 문제의 점근 적 변경이 필요한 경우 구조와 같은 '합계 테이블'을 작성하는 것을 고려할 수 있습니다 그러면 2^d 연산을 사용하는 계층 적 응답을 쿼리 할 수 ​​있으며 많은 관련 쿼리를 수행하는 경우이를 상환 할 수 있습니다.

(x1, y1)에서 (x2, y2) 범위의 합계에 관심이있는 좌표 x 및 y를 가진 2d의 예입니다.

별도로 저장하면 면적에 비례하여 여러 항목을 합산해야합니다.

sumtable을 사용하여 각 위치 (x, y)에 해당 위치의 값을 저장하지 말고 (0,0)에서 (x, y)까지의 영역 합계를 저장하십시오. - 합 (X1, Y2) - 합 (X2, Y1) + 합계 (X1, Y1)

을

합 (X2, Y2) :

은 그럼 당신은 요청에 의해 모든 범위의 쿼리에 응답 할 수 있습니다 상수 금액 (x, y에 대한 인덱스가 있고 SQL에 저장되어 있다고 가정하면 데이터 세트 크기의 로그, 로그)

복잡한 속성이있는 경우 범위이지만 간단한 사전 식 색인, 날짜 등을 처리 할 수 ​​있습니다.