Indeks mapy bitowej - Bitmap index

Indeks bitmap jest szczególnym rodzajem wskaźnika bazy danych , który wykorzystuje bitmapy .

Tradycyjnie uważano, że indeksy bitmapowe dobrze sprawdzają się w przypadku kolumn o niskiej liczności , które mają niewielką liczbę odrębnych wartości, absolutnie lub w stosunku do liczby rekordów zawierających dane. Skrajnym przypadkiem niskiej kardynalności są dane logiczne (np. Czy mieszkaniec miasta ma dostęp do internetu?), Które mają dwie wartości: Prawda i Fałsz. Indeksy bitmapowe używają tablic bitowych (powszechnie nazywanych bitmapami) i odpowiadają na zapytania, wykonując bitowe operacje logiczne na tych mapach bitowych. Indeksy bitmapowe mają znaczną przewagę pod względem przestrzeni i wydajności w porównaniu z innymi strukturami do wykonywania zapytań dotyczących takich danych. Ich wadą jest to, że są mniej wydajne niż tradycyjne indeksy B-drzewa dla kolumn, których dane są często aktualizowane: w konsekwencji są częściej stosowane w systemach tylko do odczytu, które specjalizują się w szybkich zapytaniach - np. Hurtownie danych i generalnie nie nadają się do aplikacje do przetwarzania transakcji online .

Niektórzy badacze twierdzą, że indeksy bitmap są również przydatne w przypadku danych o umiarkowanej lub nawet wysokiej kardynalności (np. Danych o unikatowej wartości), do których dostęp jest możliwy tylko do odczytu, a zapytania uzyskują dostęp do wielu kolumn indeksowanych bitmapą za pomocą AND , OR lub XOR operatorów.

Indeksy bitmapowe są również przydatne w aplikacjach hurtowni danych do łączenia dużej tabeli faktów z mniejszymi tabelami wymiarów, takimi jak te ułożone w schemacie gwiaździstym .

Przykład

Kontynuując przykład z dostępem do Internetu, indeks mapy bitowej można logicznie rozpatrywać w następujący sposób:

Identyfikator HasInternet Mapy bitowe
Y N
1 tak 1 0
2 Nie 0 1
3 Nie 0 1
4 Nieokreślony 0 0
5 tak 1 0

Po lewej stronie Identyfikator odnosi się do unikalnego numeru przypisanego każdemu mieszkańcowi, HasInternet to dane do indeksowania, zawartość indeksu mapy bitowej jest pokazana jako dwie kolumny pod nagłówkiem mapy bitowe . Każda kolumna na lewej ilustracji jest mapą bitową w indeksie mapy bitowej. W tym przypadku istnieją dwie takie mapy bitowe, jedna dla „ma internet” Tak, a druga dla „ma internet” Nie . Łatwo zauważyć, że każdy bit w mapie bitowej Y pokazuje, czy dany wiersz odnosi się do osoby, która ma dostęp do Internetu. To najprostsza forma indeksu bitmapy. Większość kolumn będzie miała bardziej wyraźne wartości. Na przykład kwota sprzedaży prawdopodobnie będzie miała znacznie większą liczbę odrębnych wartości. Odmiany indeksu bitmapy mogą również skutecznie indeksować te dane. Omówimy pokrótce trzy takie odmiany.

Uwaga: Przegląd wielu cytowanych tu odniesień znajduje się w ( John Wu (2007) ). Dla tych, którzy mogą być zainteresowani eksperymentowaniem z niektórymi z wymienionych tutaj pomysłów, wiele z nich jest zaimplementowanych w oprogramowaniu open source, takim jak FastBit, biblioteka Lemur Bitmap Index C ++, biblioteka Roaring Bitmap Java i system Apache Hive Data Warehouse.

Kompresja

Ze względów historycznych kompresja bitmapy i odwrócona kompresja list zostały opracowane jako osobne kierunki badań i dopiero później uznano, że rozwiązują zasadniczo ten sam problem.

Oprogramowanie może kompresować każdą bitmapę w indeksie bitmapy, aby zaoszczędzić miejsce. Na ten temat wykonano wiele pracy. Chociaż istnieją wyjątki, takie jak roaringowe mapy bitowe, algorytmy kompresji bitmap zwykle wykorzystują kodowanie run-length , takie jak kod bitmapowy wyrównany do bajtów, kod hybrydowy wyrównany do słów, kompresja hybrydowa z wyrównaniem do słów podzielona na partycje (PWAH), słowo listy pozycji Wyrównana hybryda, skompresowany indeks adaptacyjny (COMPAX), ulepszona hybryda wyrównana względem słów (EWAH) i skompresowana kombinowana liczba całkowita „N” SEt. Te metody kompresji wymagają niewielkiego wysiłku, aby skompresować i zdekompresować. Co ważniejsze, mapy bitowe skompresowane za pomocą BBC, WAH, COMPAX, PLWAH, EWAH i CONCISE mogą bezpośrednio uczestniczyć w operacjach bitowych bez dekompresji. Daje im to znaczną przewagę nad ogólnymi technikami kompresji, takimi jak LZ77 . Kompresja BBC i jej pochodne są wykorzystywane w komercyjnym systemie zarządzania bazami danych . BBC skutecznie zmniejsza rozmiary indeksów i utrzymuje wydajność zapytań . BBC koduje mapy bitowe w bajtach , podczas gdy WAH koduje słowami, lepiej dopasowując obecne procesory . „Zarówno w przypadku danych syntetycznych, jak i rzeczywistych danych aplikacji, nowe schematy wyrównane do słów zajmują tylko 50% więcej miejsca, ale wykonują operacje logiczne na skompresowanych danych 12 razy szybciej niż BBC”. Zgłoszono, że mapy bitowe PLWAH zajmują 50% miejsca zajmowanego przez mapy bitowe WAH i oferują do 20% szybszą wydajność operacji logicznych . Podobne rozważania można zrobić dla CONCISE i Enhanced Word-Aligned Hybrid.

Wydajność schematów takich jak BBC, WAH, PLWAH, EWAH, COMPAX i CONCISE zależy od kolejności rzędów. Proste sortowanie leksykograficzne może podzielić rozmiar indeksu przez 9 i przyspieszyć indeksy kilka razy. Im większa tabela, tym ważniejsze jest sortowanie wierszy. Zaproponowano również techniki przetasowania, aby osiągnąć te same wyniki sortowania podczas indeksowania danych przesyłanych strumieniowo.

Kodowanie

Podstawowe indeksy bitmap używają jednej mapy bitowej dla każdej odrębnej wartości. Istnieje możliwość zmniejszenia liczby używanych map bitowych przy użyciu innej metody kodowania . Na przykład możliwe jest kodowanie wartości odrębnych w języku C przy użyciu map bitowych dziennika (C) z kodowaniem binarnym .

Zmniejsza to liczbę map bitowych, dodatkowo oszczędzając miejsce, ale aby odpowiedzieć na każde zapytanie, należy uzyskać dostęp do większości map bitowych. To sprawia, że ​​potencjalnie nie jest tak skuteczny, jak skanowanie odwzorowania pionowego danych podstawowych, zwanego również widokiem zmaterializowanym lub indeksem odwzorowania. Znalezienie optymalnej metody kodowania, która równoważy (dowolną) wydajność zapytań, rozmiar indeksu i konserwację indeksu, pozostaje wyzwaniem.

Nie biorąc pod uwagę kompresji, Chan i Ioannidis przeanalizowali klasę metod kodowania wieloskładnikowego i doszli do wniosku, że kodowanie dwuskładnikowe znajduje się na skraju krzywej wydajności w stosunku do rozmiaru indeksu i dlatego stanowi najlepszy kompromis między rozmiarem indeksu a wydajność zapytań.

Binning

W przypadku kolumn o dużej liczności przydatne jest kategoryzowanie wartości, przy czym każdy przedział obejmuje wiele wartości i budowanie map bitowych, które będą reprezentowały wartości w każdym przedziale. Takie podejście zmniejsza liczbę używanych bitmap niezależnie od metody kodowania. Jednak indeksy dzielone mogą odpowiadać tylko na niektóre zapytania bez sprawdzania danych podstawowych. Na przykład, jeśli przedział obejmuje zakres od 0,1 do 0,2, to gdy użytkownik zapyta o wszystkie wartości mniejsze niż 0,15, wszystkie wiersze, które mieszczą się w przedziale, są możliwymi trafieniami i należy je sprawdzić, aby zweryfikować, czy faktycznie są mniejsze niż 0,15 . Proces sprawdzania danych podstawowych jest nazywany sprawdzaniem kandydata. W większości przypadków czas potrzebny na sprawdzenie kandydata jest znacznie dłuższy niż czas potrzebny do pracy z indeksem bitmapy. W związku z tym indeksy dzielone na kategorie wykazują nieregularną wydajność. W przypadku niektórych zapytań mogą być bardzo szybkie, ale znacznie wolniejsze, jeśli zapytanie nie pasuje dokładnie do kosza.

Historia

Pojęcie indeksu bitmapowego zostało po raz pierwszy wprowadzone przez profesora Israela Spieglera i Rafiego Maayana w ich badaniu pt. „Storage and Retrieval Considerations of Binary Data Bases”, opublikowanym w 1985 r. Pierwszym komercyjnym produktem bazodanowym, w którym zaimplementowano indeks bitmapowy, była firma Computer Corporation of America's Model 204 . Patrick O'Neil opublikował artykuł na temat tej implementacji w 1987 roku. Ta implementacja jest hybrydą pomiędzy podstawowym indeksem bitmapy (bez kompresji) a listą identyfikatorów wierszy (lista RID). Ogólnie indeks jest zorganizowany jako drzewo B + . Gdy liczność kolumn jest niska, każdy węzeł liścia B-drzewa zawierałby długą listę identyfikatorów RID. W tym przypadku wymaga mniej miejsca, aby przedstawić listy RID jako mapy bitowe. Ponieważ każda mapa bitowa reprezentuje jedną odrębną wartość, jest to podstawowy indeks mapy bitowej. Wraz ze wzrostem liczności kolumn każda mapa bitowa staje się rzadka i przechowywanie map bitowych może wymagać więcej miejsca na dysku niż przechowywanie tej samej zawartości co listy RID. W tym przypadku przełącza się na używanie list RID, co czyni go indeksem drzewa B + .

Mapy bitowe w pamięci

Jednym z najmocniejszych powodów używania indeksów bitmap jest to, że otrzymane z nich wyniki pośrednie są również mapami bitowymi i mogą być efektywnie ponownie wykorzystywane w dalszych operacjach, aby odpowiedzieć na bardziej złożone zapytania. Wiele języków programowania obsługuje to jako strukturę danych z tablicą bitową. Na przykład Java ma BitSet klasę.

Niektóre systemy baz danych, które nie oferują trwałych indeksów bitmap, używają bitmap wewnętrznie w celu przyspieszenia przetwarzania zapytań. Na przykład PostgreSQL w wersji 8.1 i nowszych implementuje optymalizację „skanowania indeksu mapy bitowej”, aby przyspieszyć dowolnie złożone operacje logiczne między dostępnymi indeksami w jednej tabeli.

W przypadku tabel z wieloma kolumnami łączna liczba odrębnych indeksów spełniających wszystkie możliwe zapytania (z warunkami filtrowania równości w każdym z pól) rośnie bardzo szybko i jest definiowana przez następującą formułę:

.

Skanowanie indeksów bitmap łączy wyrażenia w różnych indeksach, dlatego wymaga tylko jednego indeksu na kolumnę do obsługi wszystkich możliwych zapytań w tabeli.

Zastosowanie tej strategii dostępu do indeksów B-drzewa może również łączyć zapytania o zakres w wielu kolumnach. W tym podejściu tymczasowa mapa bitowa w pamięci jest tworzona z jednym bitem dla każdego wiersza w tabeli (w ten sposób 1  MB może przechowywać ponad 8 milionów wpisów). Następnie wyniki z każdego indeksu są łączone w mapę bitową przy użyciu operacji bitowych . Po sprawdzeniu wszystkich warunków mapa bitowa zawiera „1” dla wierszy pasujących do wyrażenia. Na koniec mapa bitowa jest przeszukiwana i pobierane są pasujące wiersze. Oprócz wydajnego łączenia indeksów, poprawia to również lokalność odwołań do dostępu do tabeli, ponieważ wszystkie wiersze są pobierane sekwencyjnie z głównej tabeli. Wewnętrzna mapa bitowa jest odrzucana po zapytaniu. Jeśli w tabeli jest zbyt wiele wierszy, aby użyć 1 bitu na wiersz, zamiast tego tworzona jest „stratna” mapa bitowa z jednym bitem na stronę dysku. W tym przypadku mapa bitowa służy po prostu do określenia, które strony mają zostać pobrane; kryteria filtru są następnie stosowane do wszystkich wierszy na pasujących stronach.

Bibliografia

Uwagi
Bibliografia