Strona korzysta z plików cookies w celu realizacji usług i zgodnie z Polityką Plików Cookies.



14.05.2019

Bezpłatna konferencja OSEC...

Jako patron medialny serdecznie zapraszamy na bezpłatną konferencję OSEC Forum 2019, któa...
23.04.2019

Optymalizacja zużycia chmury

HPE GreenLake Hybrid Cloud
23.04.2019

Zarządzanie wydajnością

VMware vRealize Operations 7.5
19.04.2019

Technologie open source

SUSECON 2019
19.04.2019

Wyjątkowo małe

OKI seria C800
19.04.2019

Łatwy montaż

Rittal AX i KX
18.04.2019

Technologie wideo

Avaya IX Collaboration Unit
18.04.2019

Krótki rzut

Optoma W318STe i X318STe
18.04.2019

Do mobilnej pracy

Jabra Evolve 65e

Indeksy kolumnowe – budowa i działanie

Data publikacji: 29-08-2018 Autor: Marcin Szeliga
Oprócz wysokiego...

Indeksy kolumnowe pozwalają wydajnie przechowywać bardzo duże, liczące nawet miliardy wierszy, zbiory danych. W artykule przyglądamy się ich budowie i działaniu w wersji zaimplementowanej w serwerze SQL Server 2014 i nowszych.

Jak wydajnie analizować (filtrować, grupować i sumować) coraz większe, liczące miliony i miliardy wierszy zbiory danych? Można te dane wstępnie pogrupować i wyliczyć różne sumy, np. sprzedaż w poszczególnych miastach towarów z różnych kategorii w ciągu miesiąca, roku i dekady – w ten sposób działa m.in. SQL Server Analysis Services Multidimensional. Można też skompresować szczegółowe dane i przetwarzać je wektorowo, np. za pomocą technologii xVelocity zaimplementowanej w SQL Server Analysis Services Tabular i Power BI pod nazwą Vertipaq oraz w SQL Server jako ColumnStore.

> Technologia xVelocity

SQL Server, tak jak wiele serwerów baz danych, przechowuje dane w postaci wierszy – jeden lub więcej wierszy tabeli zapisywanych jest w 8-kilobajtowych blokach nazywanych stronami. Takie rozwiązanie sprawdza się w bazach operacyjnych, których użytkownicy na bieżąco wstawiają, modyfikują, usuwają lub odczytują pojedyncze wiersze. Jednak w bazach analitycznych, w których użytkownicy odczytują całe tabele, a następnie grupują odczytane dane i łączą je z danymi z innych tabel, rozwiązanie to jest mało wydajne.


> Indeks kolumnowy


Sposobem na skrócenie czasu odczytania całej tabeli nie jest jej poindeksowanie, ale skompresowanie – jeżeli dane zajmują mniej miejsca (są zapisane na mniejszej liczbie stron), ich odczytanie wymagać będzie mniej operacji wejścia/wyjścia i będzie trwać krócej. Żeby zmaksymalizować ten zysk, współczynnik kompresji danych musi być jak największy.

W algorytmach kompresji bezstratnej współczynnik kompresji zależy przede wszystkim od kompresowanych danych – im bardziej są one różnorodne, tym jest on niższy. Innymi słowy, im więcej jest powtarzających się wartości, tym wyższy współczynnik kompresji danych. Ponieważ dane w kolumnach powtarzają się częściej niż w wierszach (np. w kolumnie Państwo we wszystkich wierszach może występować wartość Polska, ale szansa, że w kilku kolumnach tego samego wiersza, takich jak Nazwisko, Imię czy Kraj, wystąpią te same wartości, jest bliska zeru), przechowując na stronach kolumny, a nie wiersze, zwiększamy współczynnik kompresji.

Ponadto użytkownicy systemów analitycznych bardzo rzadko odczytują wszystkie kolumny tabeli – znacznie częściej interesuje ich tylko kilka albo nawet jedna kolumna (np. z ceną). Ponieważ jednostką odczytu danych w serwerze SQL Server jest strona (odczytywane i zapisywane są strony, a nie wiersze, kolumny czy tabele), podzielenie kolumn pomiędzy różne strony pozwala odczytać tylko te, na których znajdują się potrzebne dane, a nie wszystkie strony tabeli.

Zanim przedstawimy kolejne zalety przechowywania na stronach kolumn, a nie wierszy tabeli, warto wyjaśnić omówione tematy na przykładzie. Weźmy kilka wierszy przykładowej tabeli faktów (tabeli, w której przechowywane są miary, np. ilość i wartość sprzedaży) oraz klucze wiążące ją z tabelami wymiarów (np. z kalendarzem, tabelą zawierającą dane o produktach, sklepach i regionach). Dane te przedstawiono w tabeli 1.

W pierwszej kolejności dane są dzielone poziomo, na bloki liczące maksymalnie milion wierszy każdy. Te bloki nazywane są grupami wierszy. Następnie każda grupa wierszy dzielona jest pionowo, na wartości poszczególnych kolumn. W rezultacie powstają segmenty zawierające do miliona wartości każdy (tabela 2).

Każdy segment zostaje osobno skompresowany. Kompresja przebiega w kilku etapach, a to, które operacje zostaną przeprowadzone dla danego segmentu, zależy głównie od typu kompresowanych danych:

1. Wartości liczbowe zostają przeskalowane tak, aby można je było zapisać na jak najmniejszej liczbie bitów. Na przykład jeżeli najmniejszą wartością w segmencie było 10 000, od wszystkich wartości odjęte zostanie 10 000;
2. Wartości tekstowe mogą zostać zakodowane metodą jeden do wielu. Powoduje ona zastąpienie jednej zmiennej tyloma zmiennymi binarnymi, ile różnych wartości występowało w oryginalnej kolumnie. Na przykład przyjmującą cztery wartości kolumnę kolor należałoby zastąpić czterema kolumnami: czarny, czerwony, srebrny i biały, w których każdy element przyjmowałby wartość 1 lub 0;
3. Na etapie kodowania długości serii poszczególne wartości zostają zastąpione wartością serii uzupełnioną o liczbę jej powtórzeń (tabela 3);
4. Kolejnym etapem jest kodowanie słownikowe. Polega ono na zastąpieniu oryginalnej wartości (np. imienia Marcin) identyfikatorem (np. liczbą 1). Dane mogą też zostać skompresowane kodowaniem Huffmana;
5. Na końcu następuje kodowanie binarne za pomocą opatentowanego przez Microsoft, niejawnego algorytmu. W jego efekcie dane są konwertowane do postaci binarnej i zapisywane na stronach;
6. Opcjonalnie użytkownik może dodatkowo skompresować wybrane dane za pomocą algorytmu XPress8 będącego nieco zmodyfikowaną wersją algorytmu LZ77, tego samego, który jest używany do kompresji ZIP.

[...]

Pracownik naukowy Wyższej Szkoły Bankowej w Poznaniu Wydział Zamiejscowy w Chorzowie, jest autorem książek poświęconych analizie danych i posiada tytuł Microsoft Most Valuable Professional.

Pełna treść artykułu jest dostępna w papierowym wydaniu pisma.

.

Transmisje online zapewnia: StreamOnline

All rights reserved © 2019 Presscom / Miesięcznik "IT Professional"