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

Question

저장된 값은 다른 각도 (시간, 소스, 유형에서 볼 수 있기 때문에 데이터베이스에 대한 일종의 Star 스키마를 가질 것입니다. 등) 및 요청은 이러한 차원에 따라 집계 된 데이터를 요구합니다. 쿼리는 많은 행을 전달하는 경향이 있습니다 (최대 약 100,000).

이 주제에 대한 나의 연구 (또한 참조 여기 내 질문) 비트 맵 지수는 내가 계획하는 방식으로 데이터를 검색하는 좋은 방법임을 나타냅니다. 그러나 여러 DB 엔진을 지원하고 싶습니다. 그 중 일부는 테이블 (특히 MySQL)에 비트 맵 지수를 제공하지 않습니다.

이제, 나는 확실히 내 자신의 비트 맵 색인을 빌드하고 유지 관리하고 그것을 사용하여 사실 테이블을 가리키는 행 ID를 찾을 수 있습니다. 그러나 데이터베이스가 여전히 B- 트리에서 행 ID를 검색 할 것이기 때문에 이것이 색인의 전체 목적을 물리 칠 것으로 생각됩니다. 더 심오한 이론적 배경이나 더 많은 경험을 가진 사람이 차원 테이블에서 느리게 조인 할 필요가없는 것처럼 여전히 아무것도 얻을 수 있는지 말해 줄 수 있습니까?

또한 대답이 간단하지 않은지 평가해야 할 것에 대한 힌트에 감사드립니다.

Answer 1

비트 맵 인덱스를 직접 지원하지 않는 일부 DB 엔진에는 여전히 팩트 테이블에 도달하지 않고도 이러한 유형의 쿼리를 수행 할 수있는 스타 최적화가 여전히 있습니다. 예를 들어 SQL Server에는 해상도를 수행하기 위해 비트 맵을 즉석에 구축하여 유사한 작업을 수행하는 인덱스 교차로라는 기능이 있습니다. 마이크로 소프트 주장 이것의 성능은 비트 맵 인덱스와 비슷합니다. 보다 이 게시물 이 주제에 대한 약간의 팬 아웃.

MySQL 이이 작업을 수행하면 내 머리 꼭대기를 확신하지 못하지만 Postgresql은 확실히 그렇습니다. IIRC 중 일부 (GreenPlum, 내 생각)는 비트 맵 인덱스를 직접 지원하며 메인 DB 엔진에 통합하는 이야기가있었습니다. 이것이 아직 끝났는지 기억이 나지 않습니다.

대부분의 최신 DBMS 플랫폼은 한 종류의 스타 쿼리 최적화를 제공하므로 휠을 다시 발명 할 필요가 없을 것입니다. 당신은 이것을 할 수없는 한두 가지를 찾을 수 있지만, 항상 그들을 지원하지 않는 옵션이 있습니다.

Answer 2

사용자 정의 데이터 구조를 사용하여 메모리에서 많은 데이터를 조작 할 때 비트 맵 지수로 행운을 빕니다. 인덱스 구조를 확장합니다.

일반적으로 B-Tree 지수를 통해 검색 할 예정이므로 어쨌든 내 경험이 가이드라면 아무것도 얻지 못할 것입니다.

그래서 안돼.

신청서가 본질적으로 OLAP에 있고 자연스럽게 주문한 범위로 그룹화하는 적은 수의 차원이있는 경우 문제의 점근을 변경 해야하는 경우 '합계 테이블'과 같은 구조를 구축하는 것을 고려할 수 있습니다. 2^D 연산에 대한 계층 적 답변에 대해서는 여러 관련 쿼리를 수행하는 경우 상각 할 수 있습니다.

좌표 x 및 y가있는 2D의 예는 (x1, y1)에서 (x2, y2)에서 (x2, y2) 범위에 걸쳐 관심이 있습니다.

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

각 위치 (x, y)에 대해 합계를 사용하면 해당 위치의 값을 저장하지 않고 대신 (0,0)에서 (x, y)까지 영역을 저장합니다.

그런 다음 다음과 같이 질문하여 모든 범위 쿼리에 응답 할 수 있습니다.

Sum (x2, y2) -Sum (x1, y2) -Sum (x2, y1) + sum (x1, y1)

일정한 양의 오버 헤드 (X와 Y에 인덱스가 있고 SQL에 저장하고 있다고 가정하면 데이터 세트 크기의 로그가 있습니다).

물론 이것은 범위로 분해되지는 않지만 간단한 사전 사전 색인, 날짜 등을 처리 할 수있는 복잡한 속성이 있다면 분류됩니다.