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



19.10.2018

4K, HDR i USB-C

Philips 328P6VUBREB
16.10.2018

Pełna optymalizacja

Quest Foglight for Virtualization Enterprise 8.8 (FVE)
12.10.2018

Linux w chmurze Azure

SUSE Linux Enterprise 15 / Microsoft Azure
09.10.2018

Nowe antywirusy

Bitdefender 2019
03.10.2018

Niezawodny tandem

Veeam Hyper-Availability Platform i Cisco HyperFlex
26.09.2018

Zarządzane z chmury

NETGEAR GC752X(P)
21.09.2018

Kolor razy 6

Kyocera ECOSYS i TASKalfa
18.09.2018

Na ataki piątej generacji

Check Point 23900
14.09.2018

UHD dla pro

Samsung UJ59

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 © 2013 Presscom / Miesięcznik "IT Professional"