Algorytm merge w praktyce

Podstawy teoretyczne algorytmu

Algorytmów jest mnóstwo. Nie dlatego, że się masowo rozmnażają, ale dlatego, że są potrzebne i każdy z nich ma swoje zastosowanie. Jednym z ważniejszych jest algorytm merge. Jest on różnie tłumaczony i występuje pod szyldami algorytmu scalania i algorytmu złączenia. Dlaczego obie nazwy? Po przeczytaniu wszystko się wyjani. Algorytm jest bardzo szybki, stąd też jego szerokie zastosowanie.

Zanim przejdę do konkretów, przyjrzyjmy się podstawowej zasadzie działania w pseudokodzie:

Koniec algorytmu. Najważniejszym założeniem algorytmu jest określona kolejność elementów - muszą być posortowane! Jeżeli są, najmniejsze elementy są na początku, a dostęp do coraz większych elementów odbywa się sekwencyjnie. Sprawia to, że algorytm działa w czasie liniowym, co dla większości zastosowań jest wynikiem rewelacyjnym.

Przyjrzyjmy się przykładowej implementacji algorytmu Merge w C#.

Algorytm scalania w C#

Wspomniałem wcześniej o dwóch polskojęzycznych nazwach i o ich współistnieniu. Pierwszy przykład pokaże, że lepiej pasuje do niego określenie scalania. Zadaniem będzie scalenie dwóch list, czyli zrobienie z dwóch posortowanych jednej, również posortowanej.

Implementacja nie wymaga chyba wyjaśnień. Jedyne miejsce, które może być niejasne zostało opatrzone komentarzem. Przyjrzyjmy się jeszcze na procedurę testową:

Oraz wynik działania programu:

Dopisałem sobie metodę Write, która wyświetli wyniki operacji scalania i złączeń. Ciało metody nie będzie więcej powielane, bo będzie ona taka sama dla wszystkich pokazywanych przypadków. Ponadto, każda z pokazywanych metod jest na tyle ogólna, że będzie działała z każdym typem, który da się porównać.

Pokazana powyżej metoda Merge jest typowym algorytmem scalania, stosowanym między innymi w algorytmie sortowania przez scalanie. Dla ekspertów bazodanowych algorytm Merge znaczy jednak coś zupełnie innego.

Algorytm złączenia elementów unikalnych

Znane z języka SQL złączenie działa bardzo podobnie i różni się tylko sposobem traktowania elementów zbioru. O ile w przypadku scalania wszystkie elementy lądowały w zbiorze wynikowym, o tyle w przypadku złączenia w zbiorze wynikowym lądują tylko elementy wspólne dla obu zbiorów. Jest to typowe złączenie klucz podstawowy-klucz obcy relacyjnej algebry w bazach danych. Przyjrzyjmy się zatem kolejnemu przykładowi:

Żeby niepotrzebnie nie mnożyć tekstu, procedura testowa i wynik zostaną pokazane na jednym listingu.

W metodzie złączenia MergeDistinctJoin widać niewielkie modyfikacje. Po pierwsze, nie da się określić rozmiaru zbioru wynikowego, więc pojawia się lista. Nie ma takiej potrzeby, bo znany jest maksymalny rozmiar tablicy, a to ogranicza nam obszar pamięci, którą trzeba zarezerwować. Najczęściej nie ma potrzeby szukania takich drobnostek optymalizacyjnych ale zdarza się, że i one będą potrzebne. W bazach danych kilkuprocentowy wzrost wydajności to może być bardzo dużo i decydować o wyborze produktu przez konkretnego klienta. Reasumując - trzeba pamiętać, że algorytm może być jeszcze zoptymalizowany.

Napisałem w komentarzu, że metoda MergeDistinctJoin zakłada, że:

• elemenrty są posortowane,
• elementy w każdej z list są unikalne

Takie założenie sprawia, że złożoność całego algorytmu jest liniowa - O(n). Co się dzieje, gdy nie można założyć unikalności? Problem trochę się komplikuje, ale nie jest beznadziejny.

Algorytm złączenia dla elementów powtarzających się

Zastanówmy się, co się dzieje, gdy elementy się powtarzają. Co się stanie, gdy w jednej z list napotkamy na dwie takie same wartości? Jeżeli w drugiej liście takiego elementu nie będzie, nic się nie stanie. Jeżeli będzie, wynik powinien zawierać dwa złączenia. W metodzie MergeDistinctJoin, jeżeli wykryto złączenie, pomijane są elementy obu list. Jasne jest, że w ten sposób zgubimy jeden rezultat. Dla przypadku {1,1}x{1,2} odnaleziona zostanie jedna para jedynek, wskaźniki zostaną zwiększone, a porównanie 1 z 2 da nam wynik negatywny. Można kombinować i zwiększać wskaźnik z tej strony, z której kolejny element jest taki sam, ale po pierwsze, zmusimy algorytm do wielu dodatkowych porównań (chyba, że znamy strukturę i rozkład danych w listach, a dokładniej założenie o unikalności - baza danych może mieć taką informację!Baza danych posiada klucze główne, których wartości z założenia są unikalne oraz indeksy, które mogą nakładać wymóg unikalności. Każde takie drobne założenie może mieć wpływ na wybór sposobu złączenia i złożoności użytego algorytmu.), a po drugie, nie rozwiąże to innego problemu. Co się stanie, gdy i w drugiej liście znajdują się powtarzające elementy? Przyjrzyjmy się kolejnemu przykładowi:

Co robi algorytm? Jeżeli napotka identyczne wartości w obu listach, przeszukuje obie w przód. Liczba złączeń będzie równa NxM, gdzie N to liczba powtarzających się elementów w pierwszej liście, a M to liczba powtarzających się elementów w drugiej liście. Jeżeli nie ma powtórzeń, to wynikiem będzie 1, jeżeli w pierwszej liście są dwa takie same elementy a w drugiej 1 to wynikiem będzie dwa, jeżeli natomiast w obu listach są po dwa takie same, wynikiem będzie 2x2=4. W przypadku serwera SQL algorytm musi być bardziej skomplikowany, bo do wyników złączeń dołączane są najczęściej inne kolumny, które muszą pochodzić z dwóch zbiorów i być odpowiednio skrzyżowane. Modyfikacja nie będzie duża, jednak rozwiązanie pozostawiam do samodzielnego opracowania. Przyjrzyjmy się jeszcze przykładowi i wynikowi działania:

Złożoność algorytmu jest znacznie trudniejsza do oszacowania i waha się: od złożoności liniowej O(n), gdy nie ma powtarzających się elementów, do złożoności kwadratowej O(n^2), gdy wszystkie elementy są takie same.

Oba pokazane algorytmy złączenia wymagają posortowanych zbiorów. Pozwala to na sekwencyjne przetwarzanie danych oraz, można tak uznać, liniową złożoność algorytmów. Pojawia się pytanie: a jeżeli wartości nie są posortowane?

Tradycyjne złączenie zbiorów

Jeżeli nie można założyć, że elementy w obu zbiorach występują we wskazanej kolejności, można postąpić różnie. Jeżeli jeden ze zbiorów jest posortowany, można rozważyć użycie algorytmu sortowania na drugim i wykonać operację złączenia, ale można też skorzystać z bardzo prostego, choć niezbyt wydajnego algorytmuTak prawdę mówiąc metod postępowania jest więcej. Z ciekawszych warto zwrócić uwagę na tablice haszujące, które również wykorzystywne są w bazach danych.. Przyjrzyjmy się jeszcze jednemu algorytmowi:

Popatrzmy jeszcze na wyniki - nie powinno być zaskoczenia:

Złożoność jest kwadratowa, ale nie to jest cały problem. Problem polega na tym, że pętla wewnętrzna wykonywana jest tyle razy, ile jest elementów w pętli zewnętrznej. Dla operacji w pamięci operacyjnej nie ma to znaczenia, ale dla baz danych może być problemem. Skanowanie danych zapisanych w pamięci masowej (dyskach twardych) jest zwykle najkosztowniejszą operacją i serwery bazodanowe starają sie tego unikać. Co więcej, największa wydajność odczytu pojawia się wtedy, gdy dane są czytane sekwencyjnie, kolejnymi stronami, bo głowica dysku nie musi wykonywać chaotycznych skoków. Ponadto, SQL Server może zastosować technikę wyprzedzonego odczytu, czyli pobrać kolejne strony z nadzieją, że i tak je będzie musiał zaraz pobrać. Jeżeli kolejność stron pamięci jest prawidłowa, zapytanie zostanie przetworzone szybciej. Jeżeli nie - trudno, pomyłki się zdarzają. Analizator zapytań, znając problemy z wydajnością, rozważa wstępne sortowanie danych oraz inne techniki optymalizacji, które nie dopuszczają do klasycznego złączenia.

Algorytmy złączenia w SQL Server

To, że zająłem się algorytmami złączenia w kontekscie SQL Server nie jest przypadkowe. Optymalizator zapytań, analizując struktury danych w tabelach oraz wyniki zapytań podrzędnych, widoków i funkcji tablicowych może stwierdzić, że dane, bez cienia wątpliwości, będą unikatowe. To pozwoli mu wybrać najwydajniejszy z algorytmów złączenia. Pamiętajmy, że SQL Server może gromadzić statystyki na temat rozkładu poszczególnych kolumn biorących udział w złączeniu i określić, jakie jest prawdopodobieństwo wystąpienia powtarzających się wartości. Także rozmiary tabel uczestniczących w złączeniu mają kolosalne znaczenie. Jeżeli jedna z tablic jest mała, można ją wczytać w całości do pamięci operacyjnej, a tam nawet wielokrotne skanowanie nie stanowi wielkiego narzutu. Na koniec pamiętajmy, że te wszystkie rozważania, przemyślenia, analizy, które SQL Server musi przeprowadzić, też wymagają czasu i wysiłku. Gdy obie tabele uczestniczące w złączeniu są małe może się okazać, że teoretycznie najwolniejszy algorytm okaże się najszybszy. Taki już urok złożoności, która nie bierze pod uwagę czasu trwania jednego kroku. Zwykłe zagnieżdzone pętle wykonają 100 operacji, podczas gdy złożony algorytm złączenia - 1. Oznacza to, że dopiero powyżej 100 rekordów czasy się zrównają, a dopiero powyżej zaczniemy obserwować rosnącą przewagę algorytmów o lepszej złożoności. Skąd takie różnice? Ze specyfiki procesora, który, mimo całej swojej złożoności, źle radzi sobie z instrukcjami wyboru. Źle przewidziane skoki (instrukcje IF) niszczą cały wysiłek przetwarzania potokowego. To przetwarzanie potokowe w ogólnym rozrachunku daje nam bardzo dużo, ale ma też swoje ciemne, warunkowe strony... algorytmy to w dużej mierze warunki i pętle, czyli też warunki, zakończenia pętli.

Czy SQL Server stosuje podobne algorytmy? Co do zasady tak, jeżeli natomiast chodzi o implementację, sprawa nie jest tak prosta. Pokazane algorytmy działają na jednej kolumnie, która nie ma żadnych innych kolumn przy sobie. Złączenie może być równościowe (gdy wartości są równe) lub dowolne inne, to jest nierównościowe, funkcyjne. Złączenie może być na wielu kolumnach, z warunkami logicznymi. Trzeba sobie zdać sprawę, że w bazie danych jest jeszcze NULL, który sprawia problemy początkującym (czy NULL=NULL?). To wszystko sprawia, że praktyczna implementacja jest nie lada wyzwaniem, znacznie przekraczającym pokazane przykłady.

Zakończenie

Na koniec taka ciekawostka, z algorytmów, żeby jeszcze trochę zmusić do wysiłku intelektualnego. Jak się zmieni kod metody, jeżeli na końcu każdej z tablic wejściowych umieścimy maksymalny element, symboliczną nieskończoność? Popatrzmy na pseudokod i zwróćmy uwagę na jego prostotę:

Liczba warunków upraszcza się, bo nie trzeba sprawdzać warunku końca tabeli. Wartości w nieprzetworzonej jeszcze do końca tabeli zawsze będą mniejsze od wartości maksymalnej w drugiej, skończonej. To taka technika strażnika, tym strażnikiem jest nieskończoność.

To, że przedstawiłem temat algorytmu złączenia, nie jest przypadkowe. W wielu systemach, w tym również w systemach baz danych, algorytmy stanowią o sile rozwiązań. Pisząc zapytania SQL warto wiedzieć, że tam pod spodem, tam, gdzie wzrok nie sięga, wykorzystywane są powszechnie nam znane algorytmy. Tam nie ma żadnej magii, dane nie biorą się same z siebie, złączenia też muszą być jakoś wykonane. Wiedza na temat tych algorytmów (w tym wspomnianego algorytmu złączenia merge) pozwala tworzyć lepsze rozwiązania, lepiej dopasować strukturę tabel, lepiej zaplanować zapytania. Znajomość algorytmu złączenia podkreśla wagę kluczy głównych i indeksów, które, a jakże, przechowują dane posortowane rosnąco lub malejąco, ale posortowane. Indeksy wcale nie muszą zawierać unikalnych wartości, bo już samo to, że wartości są posortowane, dużo nam daje.

Na koniec - znajomość algorytmu złączenia pozwala nam wyczuć potencjalne problemy dużo wcześniej, wykryć miejsca, w których w przyszłości mogą się pojawić problemy z wydajnością. Dobrze wszyscy wiemy, że im wcześniej, tym lepiej.

Kategoria:AlgorytmyC#SQL Server