Seminarium: Systemy Rozproszone
14 maja 2015, godzina 12:15,
sala
Operacja JOIN jest niewątpliwie jedną z najważniejszych i najprzydatniejszych spośród operacji bazodanowych. Niestety jest ona także chyba najkosztowniejszą i najtrudniejszą do zoptymalizowania, szczególnie gdy potrzebne jest złączenie wielu bardzo dużych tabel. Co więcej koszt operacji zależy w dużej mierze od rozmiaru wyniku, który często trudno jest ocenić na podstawie wejściowych danych.
Od wielu lat trwają badania zarówno nad szacowaniem wielkości JOINa jak i znalezieniem optymalnego algorytmu obliczającego go. Obecnie wszystkie systemy bazodanowe mają oczywiście wbudowane pewne mechanizmy estymacji i optymalizacji. Jednak tradycyjne podejście (zaimplementowane w niemal wszystkich nierozproszonych systemach bazodanowych) przy liczeniu złączenia wielu tabel zakłada liczenie go w sposób sekwencyjny co często jest nieoptymalne i czasami powoduję powstawanie dużych (w stosunku do końcowego wyniku) wyników pośrednich.
W swojej prezentacji opowiem jak realizowane są JOINy w tradycyjnych systemach bazodanowych i jak wyglądają próby optymalizacji tej operacji. Następnie przedstawię alternatywę do sekwencyjnego liczenia złączenia wielu tabel i opiszę algorytm nazwany przez jego autorów Hyper Cube Algorithm. Pozwala on na efektywne liczenie złączenia wielu tabel na rozproszonym systemie. Na zakończenie opowiem na przykładzie systemów PIG i HIVE jak istniejące systemy rozproszone implementują i optymalizują operację JOIN.
Zapraszam serdecznie!
Marta Drozdek
Bibliografia: