비트맵 색인

Bitmap index

비트맵 색인은 비트맵을 사용하는 특별한 종류의 데이터베이스 색인이다.null

비트맵 인덱스는 전통적으로 저 카디널리티 열에 대해 잘 작동하는 것으로 간주되어 왔으며, 이 열에는 데이터가 포함된 레코드 수에 따라 절대적으로 또는 상대적으로 적은 수의 구별되는 값이 있다.카디널리티가 낮은 극단적인 경우는 부울 데이터(예: 도시에 거주하는 사람이 인터넷에 접속할 수 있는가?)로, 참과 거짓이라는 두 가지 가치를 가진다.비트맵 인덱스는 비트 어레이(일반적으로 비트맵이라고 함)를 사용하고 이러한 비트맵에서 비트 논리 연산을 수행하여 쿼리에 응답한다.비트맵 인덱스는 그러한 데이터의 조회를 위해 다른 구조에 비해 상당한 공간과 성능상의 이점을 가지고 있다.그들의 단점은 데이터가 자주 업데이트되는 열의 기존 B-트리 지표보다 효율성이 낮다는 것이다. 따라서 빠른 질의에 특화된 읽기 전용 시스템(예: 데이터 웨어하우스, 일반적으로 온라인 트랜잭션 처리 애플리케이션에 적합하지 않은 시스템)에 더 많이 채택된다.null

일부 연구자들은 비트맵 인덱스가 읽기 전용 방식으로 액세스되는 중간 또는 심지어 높은 카디널리티 데이터(예: 고유값 데이터)에도 유용하다고 주장하고, 쿼리는 AND, OR 또는 XOR 연산자를 사용하여 다중 비트맵 인덱싱된 열에 광범위하게 액세스한다.[1]null

비트맵 인덱스는 또한 스타 스키마에 배열된 것과 같은 작은 차원 테이블에 큰 팩트 테이블을 결합하는 데이터 웨어하우징 애플리케이션에도 유용하다.null

예

인터넷 액세스 예를 계속하면 비트맵 색인을 다음과 같이 논리적으로 볼 수 있다.

식별자 하스 인터넷 비트맵스
Y N
1 네 1 0
2 아니요. 0 1
3 아니요. 0 1
4 지정되지 않음 0 0
5 네 1 0

왼쪽에서 식별자는 각 거주자에게 할당된 고유 번호를 가리키며, HasInternet은 인덱싱할 데이터, 비트맵 인덱스의 내용은 제목 비트맵 아래에 두 개의 열로 표시된다.왼쪽 그림의 각 열은 비트맵 색인에서 비트맵이다.이 경우 '인터넷이 있다'는 비트맵과 '인터넷이 있다'는 비트맵이 두 개 있다.비트맵 Y의 각 비트는 특정 행이 인터넷 접속을 하는 사람을 지칭하는지 여부를 보여주는 것을 쉽게 볼 수 있다.이것은 가장 간단한 형태의 비트맵 색인이다.대부분의 열은 더 뚜렷한 값을 가질 것이다.예를 들어 판매금액은 구별되는 값의 수가 훨씬 많을 가능성이 높다.비트맵 인덱스의 변동은 이 데이터도 효과적으로 인덱싱할 수 있다.우리는 그러한 세가지 변형을 간략히 검토한다.null

참고: 여기서 인용한 많은 참고문헌은 (John Wu(2007)에서 검토한다.[2]여기서 언급된 아이디어들 중 몇 가지를 실험하는 데 관심이 있을 수 있는 사람들을 위해,[3] 그들 중 많은 것들이 FastBit, Lemur 비트맵 지수 C++ Library,[4] Couring Bitmap Java 라이브러리[5], Apache Hive Data Warehouse 시스템과 같은 오픈 소스 소프트웨어에서 구현된다.null

압축

역사적 이유로 비트맵 압축과 반전 목록 압축은 별도의 연구 라인으로 개발되었고, 후에야 본질적으로 동일한 문제를 해결하는 것으로 인식되었다.[6]null

소프트웨어는 비트맵 인덱스의 각 비트맵을 압축하여 공간을 절약할 수 있다.이 문제에 관해서는 상당한 양의 연구가 있었다.[7][8]비록 로링 bitmaps,[9]비트 맵 같은 Byte-aligned 비트 맵 Code,[10]은 Word-Aligned 하이브리드 같은 압축 알고리즘이 일반적으로 실행 길이의 인코딩을 고용하고 있는 예외가 있code,[11]은 분할 Word-Aligned 하이브리드(PWAH)지휘 리스트 워드 Aligned Hybrid,[13]은 압축 적응 지수(COMPAX)[14]Enh compression,[12].Word-Aligned Hyb ancedread (EWAH) 및 COMPressed 'N' Compositeable 정수 SET.[16][17]이러한 압축 방법은 압축과 압축을 푸는 데 거의 노력이 필요하지 않다.더 중요한 것은 BBC, WAH, COMPAX, PLWAH, EWAH, SNAPE로 압축된 비트맵이 압축 해제 없이 비트 와이즈 연산에 직접 참여할 수 있다는 점이다.이것은 그들에게 LZ77과 같은 일반적인 압축 기술에 비해 상당한 이점을 준다. BBC 압축과 그 파생상품은 상업적 데이터베이스 관리 시스템에서 사용된다.BBC는 인덱스 크기를 줄이고 쿼리 성능을 유지하는 데 효과적이다.반면 WAH 말로, 더 나은 현재 CPUs과 일치하는 인코딩 BBC를."둘 다 합성 데이터와 실제 응용 프로그램 데이터에는 새 단어시켰습니다 제도지만, 압축된 데이터에 12배나 빠른 BBC보다 논리적 작업을 수행할 뿐 50%더 많은 공간을 사용하는 비트 맵 부호화합니다."[18]PLWAH 비트 맵 이 저장 공간 WA에서 소비의 50%으로 전해졌다.H 비트맵을 제공하고 논리적 운영에서 최대 20% 더 빠른 성능을 제공하십시오.[13]SNAPE 및 Enhanced Word-Alignment Hybrid에 대해서도 유사한 고려사항을 적용할 수 있다.[15]null

BBC, WAH, PLWAH, EWAH, COMPAX, COMPAX와 같은 계획의 수행은 행의 순서에 따라 달라진다.간단한 사전 분류는 인덱스 크기를 9로 나누고 인덱스를 몇 배 더 빠르게 만들 수 있다.[19]테이블이 클수록 행을 정렬하는 것이 중요하다.스트리밍 데이터를 인덱싱할 때 동일한 정렬 결과를 얻기 위한 개편 기법도 제시됐다.[14]null

인코딩

기본 비트맵 인덱스는 각각의 개별 값에 대해 하나의 비트맵을 사용한다.다른 인코딩 방식을 사용하면 비트맵을 줄일 수 있다.[20][21]예를 들어, 이진 인코딩이 있는 로그(C) 비트맵을 사용하여 C 고유 값을 인코딩할 수 있다.[22]null

이것은 비트맵의 수를 줄여 공간을 더 절약하지만, 어떤 질의에 답하기 위해서는 대부분의 비트맵에 접속해야 한다.이것은 잠재적으로 구체화된 뷰 또는 투영 지수라고도 알려진 베이스 데이터의 수직 투영을 스캔하는 것만큼 효과적이지 않다.쿼리 성능, 인덱스 크기, 인덱스 유지보수의 균형을 맞추는 최적의 인코딩 방법을 찾는 것은 과제로 남는다.null

Chan과 Ioannidis는 압축을 고려하지 않고 여러 개의 구성 요소 인코딩 방법을 분석하여 2개의 구성 요소 인코딩이 성능 대 인덱스 크기 곡선의 꼬임에 있으므로 인덱스 크기와 쿼리 성능 사이의 최상의 트레이드오프를 나타낸다는 결론을 내렸다.[20]null

비닝

높은 카디널리티 열의 경우 값을 bin으로 하는 것이 유용하며, 여기서 각 bin은 여러 값을 포괄하고 각 bin의 값을 나타내는 비트맵을 빌드한다.이 접근방식은 인코딩 방법과 관계없이 사용되는 비트맵의 수를 줄인다.[23]그러나 빈 인덱스는 기본 데이터를 검사하지 않고 일부 쿼리에만 응답할 수 있다.예를 들어, 빈이 0.1에서 0.2까지의 범위를 포함하는 경우, 사용자가 0.15 미만의 모든 값을 요구할 때, 빈에 있는 모든 행은 가능한 적중이며 실제로 0.15 미만인지 확인하기 위해 확인해야 한다.기초자료를 확인하는 과정을 후보확인이라고 한다.대부분의 경우 후보 체크가 사용하는 시간이 비트맵 지수와 작업하는 데 필요한 시간보다 상당히 길다.따라서 빈 인덱스는 불규칙한 성능을 보인다.일부 쿼리의 경우 속도가 매우 빠를 수 있지만 쿼리가 정확히 빈과 일치하지 않을 경우 훨씬 느릴 수 있다.null

역사

비트맵 지수의 개념은 1985년 발표된 이스라엘 스피글러 교수와 라피 마얀 교수가 연구한 '이진 데이터 베이스의 저장 및 검색 고려사항'에서 처음 소개됐다.[24]비트맵 지수를 구현한 첫 번째 상업용 데이터베이스 제품은 미국의 모델 204의 Computer Corporation이었다.패트릭 오닐은 1987년에 이 구현에 관한 논문을 발표했다.[25]이 구현은 기본 비트맵 색인(압축 없음)과 Row Identifier 목록(RID-list) 사이의 하이브리드다.전체적으로 지수를 B+나무로 구성한다.칼럼 카디널리티가 낮을 때, B 트리의 각 리프 노드는 긴 RID 목록을 포함할 것이다.이 경우 RID 목록을 비트맵으로 나타내는 데 더 적은 공간이 필요하다.각각의 비트맵은 하나의 고유한 값을 나타내기 때문에 이것이 기본 비트맵 색인이다.칼럼 카디널리티가 증가하면 각 비트맵은 희박해지고 RID 목록과 동일한 콘텐츠를 저장하는 것보다 비트맵을 저장하는 데 더 많은 디스크 공간이 필요할 수 있다.이 경우 RID 목록을 사용하도록 전환하여 B+트리 인덱스로 만든다.[26][27]null

인메모리 비트맵

비트맵 인덱스를 사용하는 가장 강력한 이유 중 하나는 비트맵에서 생성된 중간 결과도 비트맵이며 더 복잡한 쿼리에 응답하기 위해 후속 작업에 효율적으로 재사용될 수 있기 때문이다.많은 프로그래밍 언어가 이것을 비트 배열 데이터 구조로 지원한다.예를 들어, Java는BitSet계급의

영구 비트맵 인덱스를 제공하지 않는 일부 데이터베이스 시스템은 쿼리 처리 속도를 높이기 위해 내부적으로 비트맵을 사용한다.예를 들어, Postgre.SQL 버전 8.1 이상에서는 "비트맵 인덱스 스캔" 최적화를 구현하여 단일 테이블에서 사용 가능한 인덱스 간에 임의로 복잡한 논리적 작업을 가속화한다.null

열이 많은 테이블의 경우 가능한 모든 쿼리(두 필드의 동일 필터링 조건 포함)를 충족하기 위한 고유 인덱스 총 수가 매우 빠르게 증가하며, 이 공식에 의해 정의된다.

.[28][29]

비트맵 인덱스 스캔은 서로 다른 인덱스에 대한 식을 결합하므로 테이블에서 가능한 모든 쿼리를 지원하기 위해 열당 하나의 인덱스만 필요로 한다.null

B-트리 인덱스에 이 액세스 전략을 적용하면 여러 열의 범위 쿼리를 결합할 수도 있다.이 접근법에서는 테이블의 각 행에 대해 1비트를 사용하여 임시 메모리 내 비트맵을 생성한다(1MB는 따라서 800만 개 이상의 항목을 저장할 수 있음).다음으로 각 인덱스의 결과를 비트맵으로 조합하여 비트 연산한다.모든 조건을 평가한 후 비트맵에는 표현식과 일치하는 행에 대한 "1"이 포함된다.마지막으로 비트맵을 통과하고 일치하는 행을 검색한다.인덱스를 효율적으로 결합하는 것 외에도, 이것은 모든 행이 메인 테이블에서 순차적으로 가져오기 때문에 테이블 액세스의 참조 위치도 개선한다.[30]내부 비트맵은 쿼리 후 폐기된다.표에 행이 너무 많아 행당 1비트를 사용할 수 없는 경우 디스크 페이지당 1비트로 대신 "손실" 비트맵이 생성된다.이 경우 비트맵은 가져올 페이지를 결정하는 데만 사용되며 필터 기준은 일치하는 페이지의 모든 행에 적용된다.null

참조

메모들
  1. ^ 비트맵 색인 대 B-트리 색인: 어떤 때와 언제, Vivek Sharma, Oracle Technical Network.
  2. ^ John Wu (2007). "Annotated References on Bitmap Index". Archived from the original on 2012-06-30.
  3. ^ 패스트비트
  4. ^ Lemur 비트맵 색인 C++ 라이브러리
  5. ^ 포효하는 비트맵
  6. ^ 장궈왕, 천빈린, 야니스 파파콘스탄티누, 스티븐 스완슨."비트맵 압축 vs에 대한 실험적 연구 반전 목록 압축" 2017. doi: 10.1145/3035918.3064007
  7. ^ T. Johnson (1999). "Performance Measurements of Compressed Bitmap Indices" (PDF). In Malcolm P. Atkinson; Maria E. Orlowska; Patrick Valduriez; Stanley B. Zdonik; Michael L. Brodie (eds.). VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7–10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann. pp. 278–89. ISBN 978-1-55860-615-9.
  8. ^ Wu K, Otoo E, Shoshani A (March 5, 2004). "On the performance of bitmap indices for high cardinality attributes" (PDF).
  9. ^ Chambi, S.; Lemire, D.; Kaser, O.; Godin, R. (2016). "Better bitmap performance with Roaring bitmaps". Software: Practice and Experience. 46 (5): 709–719. arXiv:1402.6407. doi:10.1002/spe.2325. S2CID 1139669.
  10. ^ 바이트 정렬 데이터 압축
  11. ^ 워드 정렬 비트맵 압축 방법, 데이터 구조 및 장치
  12. ^ van Schaik, Sebastiaan; de Moor, Oege (2011). "A memory efficient reachability data structure through bit vector compression". Proceedings of the 2011 international conference on Management of data. SIGMOD '11. Athens, Greece: ACM. pp. 913–924. doi:10.1145/1989323.1989419. ISBN 978-1-4503-0661-4.
  13. ^ a b Deliège F, Pedersen TB (2010). "Position list word aligned hybrid: optimizing space and performance for compressed bitmaps" (PDF). In Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Leger, Felix Naumann, Anastasia Ailamaki, Fatma Ozcan (eds.). EDBT '10, Proceedings of the 13th International Conference on Extending Database Technology. New York, NY, USA: ACM. pp. 228–39. doi:10.1145/1739041.1739071. ISBN 978-1-60558-945-9. S2CID 12234453.
  14. ^ a b F. Fusco; M. Stoecklin; M. Vlachos (September 2010). "NET-FLi: on-the-fly compression, archiving and indexing of streaming network traffic" (PDF). Proc. VLDB Endow. 3 (1–2): 1382–93. doi:10.14778/1920841.1921011. S2CID 787443.
  15. ^ a b Lemire, D.; Kaser, O.; Aouiche, K. (2010). "Sorting improves word-aligned bitmap indexes". Data & Knowledge Engineering. 69: 3–28. arXiv:0901.3751. doi:10.1016/j.datak.2009.08.006. S2CID 6297890.
  16. ^ 간결함: 2011년 5월 28일 웨이백 기계에 보관된 압축 'n' 복합 정수 세트
  17. ^ a b Colantonio A, Di Pietro R (31 July 2010). "Concise: Compressed 'n' Composable Integer Set" (PDF). Information Processing Letters. 110 (16): 644–50. arXiv:1004.0403. doi:10.1016/j.ipl.2010.05.018. S2CID 8092695. Archived from the original (PDF) on 22 July 2011. Retrieved 2 February 2011.
  18. ^ Wu K, Otoo EJ, Shoshani A (2001). "A Performance comparison of bitmap indexes" (PDF). In Henrique Paques, Ling Liu, David Grossman (eds.). CIKM '01 Proceedings of the tenth international conference on Information and knowledge management. New York, NY, USA: ACM. pp. 559–61. doi:10.1145/502585.502689. ISBN 978-1-58113-436-0. S2CID 10974671.
  19. ^ D. Lemire; O. Kaser; K. Aouiche (January 2010). "Sorting improves word-aligned bitmap indexes". Data & Knowledge Engineering. 69 (1): 3–28. arXiv:0901.3751. doi:10.1016/j.datak.2009.08.006. S2CID 6297890.
  20. ^ a b C.-Y. Chan; Y. E. Ioannidis (1998). "Bitmap index design and evaluation" (PDF). In Ashutosh Tiwary; Michael Franklin (eds.). Proceedings of the 1998 ACM SIGMOD international conference on Management of data (SIGMOD '98). New York, NY, USA: ACM. pp. 355–6. doi:10.1145/276304.276336.
  21. ^ C.-Y. Chan; Y. E. Ioannidis (1999). "An efficient bitmap encoding scheme for selection queries" (PDF). Proceedings of the 1999 ACM SIGMOD international conference on Management of data (SIGMOD '99). New York, NY, USA: ACM. pp. 215–26. doi:10.1145/304182.304201.
  22. ^ P. E. O'Neil; D. Quass (1997). "Improved Query Performance with Variant Indexes". In Joan M. Peckman; Sudha Ram; Michael Franklin (eds.). Proceedings of the 1997 ACM SIGMOD international conference on Management of data (SIGMOD '97). New York, NY, USA: ACM. pp. 38–49. doi:10.1145/253260.253268.
  23. ^ N. Koudas (2000). "Space efficient bitmap indexing". Proceedings of the ninth international conference on Information and knowledge management (CIKM '00). New York, NY, USA: ACM. pp. 194–201. doi:10.1145/354756.354819. ISBN 978-1581133202. S2CID 7504216.
  24. ^ Spiegler I; Maayan R (1985). "Storage and retrieval considerations of binary data bases". Information Processing and Management. 21 (3): 233–54. doi:10.1016/0306-4573(85)90108-6.
  25. ^ O'Neil, Patrick (1987). "Model 204 Architecture and Performance". In Dieter Gawlick; Mark N. Haynie; Andreas Reuter (eds.). Proceedings of the 2nd International Workshop on High Performance Transaction Systems. London, UK: Springer-Verlag. pp. 40–59.
  26. ^ D. Rinfret; P. O'Neil; E. O'Neil (2001). "Bit-sliced index arithmetic". In Timos Sellis (ed.). Proceedings of the 2001 ACM SIGMOD international conference on Management of data (SIGMOD '01). New York, NY, USA: ACM. pp. 47–57. doi:10.1145/375663.375669.
  27. ^ E. O'Neil; P. O'Neil; K. Wu (2007). "Bitmap Index Design Choices and Their Performance Implications" (PDF). 11th International Database Engineering and Applications Symposium (IDEAS 2007). pp. 72–84. doi:10.1109/IDEAS.2007.19. ISBN 978-0-7695-2947-9.
  28. ^ Alex Bolenok (2009-05-09). "Creating indexes".
  29. ^ Egor Timoshenko. "On minimal collections of indexes" (PDF).
  30. ^ Tom Lane (2005-12-26). "Re: Bitmap indexes etc". PostgreSQL mailing lists. Retrieved 2007-04-06.
참고 문헌 목록