Indeks zakresu bloku
Indeks zakresu bloków lub BRIN to technika indeksowania bazy danych . Mają one na celu poprawę wydajności przy bardzo dużych stołach.
Indeksy BRIN zapewniają podobne korzyści jak partycjonowanie poziome lub sharding , ale bez konieczności jawnego deklarowania partycji.
BRIN ma zastosowanie do indeksu w tabeli, która jest duża i gdzie wartość klucza indeksu można łatwo posortować i ocenić za pomocą funkcji MinMax.
BRIN zostały pierwotnie zaproponowane przez Alvaro Herrerę z 2. Kwadrantu w 2013 r. jako „wskaźniki Minmax”. Dotychczasowe implementacje są ściśle powiązane z wewnętrznymi technikami implementacji i przechowywania tabel bazy danych. To czyni je wydajnymi, ale ogranicza je do określonych dostawców. Jak dotąd PostgreSQL jest jedynym dostawcą, który ogłosił produkt na żywo z tą specyficzną funkcją, w PostgreSQL 9.5. Inni dostawcy opisali kilka podobnych funkcji, w tym Oracle , „mapy stref” Netezzy , „pakiety danych” Infobright , MonetDB i Apache Hive z ORC/Parquet.
Projekt
BRIN działa poprzez „podsumowanie” dużych bloków danych w zwartej formie, którą można skutecznie przetestować, aby wcześnie wykluczyć wiele z nich z zapytania do bazy danych. Testy te wykluczają duży blok danych dla każdego porównania. Zmniejszając objętość danych na tak wczesnym etapie, zarówno poprzez reprezentowanie dużych bloków jako małych krotek, jak i eliminację wielu bloków, BRIN znacznie zmniejsza ilość szczegółowych danych, które węzeł bazy danych musi analizować wiersz po wierszu.
Przechowywanie danych w dużych bazach danych jest warstwowe i fragmentaryczne, a przechowywanie tabel jest ułożone w „bloki”. Każdy blok zawiera około 1 MB w każdej porcji i są one pobierane przez żądanie określonych bloków z warstwy pamięci masowej opartej na dysku. BRIN to lekka warstwa podsumowania w pamięci powyżej: każda krotka w indeksie podsumowuje jeden blok pod względem zakresu zawartych w nim danych: jego wartości minimalne i maksymalne oraz jeśli blok zawiera jakiekolwiek dane inne niż null dla kolumny ( s) zainteresowania.
W przeciwieństwie do tradycyjnego indeksu, który lokalizuje obszary tabeli zawierające interesujące nas wartości, BRIN działa jak „indeksy ujemne”, pokazując bloki, które zdecydowanie nie są interesujące i tym samym nie wymagają dalszego przetwarzania.
Niektóre proste testy porównawcze sugerują pięciokrotną poprawę wydajności wyszukiwania przy skanowaniu indeksu w porównaniu z tabelą nieindeksowaną. W porównaniu z B-drzewami unikają kosztów związanych z utrzymaniem.
Ponieważ BRIN są tak lekkie, mogą być przechowywane w całości w pamięci, unikając w ten sposób obciążenia dysku podczas skanowania. To samo może nie dotyczyć B-drzewa: B-drzewo wymaga węzła drzewa dla każdego około N wierszy w tabeli, gdzie N to pojemność pojedynczego węzła, a zatem rozmiar indeksu jest duży. Ponieważ BRIN wymaga tylko krotki dla każdego bloku (z wielu wierszy), indeks staje się wystarczająco mały, aby odróżnić dysk od pamięci. W przypadku „wąskiej” tabeli objętość indeksu B-drzewa zbliża się do objętości samej tabeli; BRIN może stanowić tylko 5-15%.
Zalety
Wyszukiwanie i skanowanie indeksu
Duży indeks bazy danych zwykle używałby algorytmów B-drzewa . BRIN nie zawsze zastępuje B-drzewo, jest ulepszeniem sekwencyjnego skanowania indeksu, ze szczególnymi (i potencjalnie dużymi) zaletami, gdy indeks spełnia określone warunki do uporządkowania, a celem wyszukiwania jest wąski zestaw te wartości. W ogólnym przypadku, przy losowych danych, B-drzewo może nadal być lepsze.
Szczególną zaletą techniki BRIN, wspólną ze Smart Scanning Oracle Exadata, jest wykorzystanie tego typu indeksu z aplikacjami Big Data lub hurtowniami danych , gdzie wiadomo, że prawie cała tabela jest nieistotna dla zakresu zainteresowania. BRIN umożliwia przeszukiwanie tabeli w takich przypadkach, pobierając tylko bloki, które mogą zawierać interesujące dane i wykluczając te, które są wyraźnie poza zakresem lub nie zawierają danych dla tej kolumny.
Wstawić
Częstym problemem związanym z przetwarzaniem dużych tabel jest to, że pobieranie wymaga użycia indeksu, ale utrzymywanie tego indeksu spowalnia dodawanie nowych rekordów. Typową praktyką było grupowanie dodatków i dodawanie ich jako pojedynczej transakcji zbiorczej lub usuwanie indeksu, dodawanie partii nowych rekordów, a następnie ponowne tworzenie indeksu. Oba te czynniki zakłócają jednoczesne operacje odczytu/zapisu i mogą nie być możliwe w niektórych nieprzerwanie działających firmach.
W przypadku BRIN spowolnienie związane z utrzymaniem indeksu jest znacznie mniejsze w porównaniu z B-drzewem. Wong donosi, że B-tree spowolniło dodawanie do nieindeksowanej tabeli 10 GB o 85%, ale porównywalny BRIN miał tylko 11% kosztów ogólnych.
Tworzenie indeksu
BRIN można utworzyć dla bardzo dużych danych, w przypadku których B-drzewo wymagałoby partycjonowania poziomego.
Tworzenie BRIN jest również znacznie szybsze niż w przypadku B-drzewa, o 80%. Byłoby to przydatne ulepszenie refaktoryzacji istniejących aplikacji bazodanowych, które korzystają z podejścia upuść-dodaj-ponowne indeksowanie, bez konieczności wprowadzania zmian w kodzie.
Realizacja
Uzależnienie od porządku w tabeli
Można zdefiniować wiele BRIN dla różnych kolumn w jednej tabeli. Istnieją jednak ograniczenia.
BRIN są wydajne tylko wtedy, gdy kolejność kluczowych wartości jest zgodna z organizacją bloków w warstwie pamięci. W najprostszym przypadku może to wymagać fizycznego uporządkowania tabeli, co często jest kolejnością tworzenia znajdujących się w niej wierszy, w celu dopasowania do kolejności klucza. Tam, gdzie tym kluczem jest data utworzenia, może to być trywialny wymóg.
Jeśli dane są naprawdę losowe lub jeśli występuje duża zmiana kluczowych wartości w „gorącej” bazie danych, założenia leżące u podstaw BRIN mogą się załamać. Wszystkie bloki zawierają wpisy „interesujące”, więc niewiele z nich może zostać wcześnie wykluczonych przez filtr zakresu BRIN.
W większości przypadków BRIN jest ograniczony do jednego indeksu na tabelę. Można zdefiniować wiele BRIN, ale tylko jeden może mieć odpowiednią kolejność. Jeśli dwa (lub więcej) indeksy mają podobne zachowanie przy porządkowaniu, możliwe i przydatne może być zdefiniowanie wielu BRIN w tej samej tabeli. Oczywistym przykładem jest sytuacja, w której zarówno data utworzenia, jak i kolumna record_id rosną monotonicznie wraz z sekwencją tworzenia rekordu. W innych przypadkach wartość klucza może nie być monotoniczna, ale pod warunkiem, że w fizycznym porządku rekordu nadal istnieje silne zgrupowanie, BRIN jest skuteczny.
Indeksy pamięci masowej Exadata
BRIN ma pewne podobieństwa do Oracle Exadata „ Indeksy pamięci ”. Exadata ma silną koncepcję „warstwy pamięci” w swoim stosie architektury. Dane tabeli są przechowywane w blokach lub „komórkach pamięci” na serwerach pamięci masowej. Te komórki pamięci masowej są nieprzejrzyste dla serwera pamięci masowej i są zwracane na żądanie do mechanizmu bazy danych na podstawie ich identyfikatora. Wcześniej węzły bazy danych musiały zażądać wszystkich komórek pamięci, aby je przeskanować.
Indeksy magazynu zapewniają oczyszczanie danych w tej warstwie: skutecznie wskazując sekcje, które nie są już przedmiotem zainteresowania. Indeks pamięci jest ładowany do pamięci na serwerze pamięci, tak że gdy wysyłane jest żądanie dotyczące komórek, może ono zostać poprzedzone wartościami wyszukiwania. Są one porównywane z indeksem magazynu, a następnie tylko odpowiednie komórki muszą zostać zwrócone do węzła bazy danych.
Korzyści w zakresie wydajności z indeksem magazynu są najbardziej widoczne, gdy indeksowana kolumna zawiera wiele wartości null . Podczas skanowania rzadkich danych uzyskuje się ogromne korzyści w zakresie wydajności .
Rozwój
Siódmego Programu Ramowego Unii Europejskiej (FP7/2007-2013).
PostgreSQL
Implementacja dla PostgreSQL była po raz pierwszy widoczna w 2013 roku. BRIN pojawił się w wersji 9.5 PostgreSQL na początku 2016 roku.