Kiedy i dlaczego przyłączanie się do bazy danych jest drogie?

Robię badania baz danych i patrzę na pewne ograniczenia relacyjnych baz danych.

Rozumiem, że połączenia dużych tabel są bardzo drogie, ale nie jestem całkowicie pewien, dlaczego. Co DBMS musi zrobić, aby wykonać operację łączenia, gdzie jest wąskie gardło?
W jaki sposób denormalizacja może pomóc w pokonywaniu tego kosztu? W jaki sposób pomagają inne techniki optymalizacji (na przykład indeksowanie)?

Mile widziane osobiste doświadczenia! Jeśli zamierzasz publikować linki do zasobów, unikaj Wikipedii. Wiem już, gdzie to znaleźć.

W związku z tym zastanawiam się nad denormalizowanymi podejściami stosowanymi przez bazy danych usług w chmurze, takie jak BigTable i SimpleDB. Zobacz to pytanie .

Denormalizacja w celu poprawy wydajności? Brzmi przekonująco, ale nie zatrzymuje wody.

Chris Date, który w towarzystwie dr Teda Codda był oryginalnym zwolennikiem relacyjnego modelu danych, zabrakło mu cierpliwości z powodu niedoinformowanych argumentów przeciwko normalizacji i systematycznie demolował je metodą naukową: zdobył duże bazy danych i przetestował te twierdzenia.

Myślę, że pisał go w relacyjnych baz danych 1988-1991 Pism ale ta książka była później zwinięte w szóstej edycji Wprowadzenie do systemów baz danych , co jest ostateczny tekst na teorii baz danych i projektowania w swojej ósmej edycji jak piszę i prawdopodobnie pozostanie w druku przez dziesięciolecia. Chris Date był ekspertem w tej dziedzinie, kiedy większość z nas wciąż biegała boso.

Stwierdził, że:

• Niektóre z nich dotyczą szczególnych przypadków
• Wszystkie z nich nie zwracają się do ogólnego użytku
• Wszystkie są znacznie gorsze w przypadku innych szczególnych przypadków

Wszystko sprowadza się do zmniejszenia rozmiaru zestawu roboczego. Połączenia obejmujące odpowiednio wybrane klucze z poprawnie skonfigurowanymi indeksami są tanie, nie drogie, ponieważ umożliwiają znaczne przycinanie wyniku przed zmaterializowaniem wierszy.

Zmaterializowanie wyniku obejmuje masowe odczyty dysku, które są najdroższym aspektem ćwiczenia o rząd wielkości. Natomiast łączenie wymaga logicznie pobrania tylko kluczy . W praktyce nawet kluczowe wartości nie są pobierane: kluczowe wartości skrótu są używane do porównań połączeń, co zmniejsza koszty połączeń wielokolumnowych i radykalnie obniża koszty połączeń obejmujące porównania łańcuchów. Nie tylko znacznie zmieści się w pamięci podręcznej, ale jest znacznie mniej do odczytu.

Ponadto dobry optymalizator wybierze najbardziej restrykcyjny warunek i zastosuje go przed wykonaniem łączenia, bardzo skutecznie wykorzystując wysoką selektywność połączeń na indeksach o dużej liczności.

Wprawdzie ten typ optymalizacji można również zastosować do zdenormalizowanych baz danych, ale osoby, które chcą zdormormalizować schemat zazwyczaj nie myślą o kardynalności, gdy (jeśli) konfigurują indeksy.

Ważne jest, aby zrozumieć, że skany tabeli (badanie każdego wiersza w tabeli w trakcie tworzenia złączenia) są rzadkie w praktyce. Optymalizator zapytań wybierze skanowanie tabeli tylko wtedy, gdy zostanie zatrzymany co najmniej jeden z następujących elementów.

• W relacji jest mniej niż 200 wierszy (w tym przypadku skanowanie będzie tańsze)
• Nie ma odpowiednich indeksów w kolumnach łączenia (jeśli sensowne jest łączyć się w tych kolumnach, dlaczego nie są one indeksowane? Napraw to)
• Wymuszenie typu jest wymagane przed porównaniem kolumn (WTF ?! napraw to lub wróć do domu) ZOBACZ UWAGI KOŃCOWE DLA PROBLEMU ADO.NET
• Jednym z argumentów porównania jest wyrażenie (bez indeksu)

Wykonanie operacji jest droższe niż jej niewykonanie. Jednak wykonanie niewłaściwej operacji, zmuszenie do bezcelowego wejścia / wyjścia dysku, a następnie odrzucenie żużlu przed wykonaniem połączenia, którego naprawdę potrzebujesz, jest znacznie droższe. Nawet jeśli „niewłaściwa” operacja zostanie wstępnie obliczona, a indeksy zostały rozsądnie zastosowane, pozostaje znaczna kara. Denormalizacja w celu wstępnego obliczenia złączenia - niezależnie od związanych z tym anomalii aktualizacji - jest zobowiązaniem do konkretnego złączenia. Jeśli potrzebujesz innego przyłączenia, to zobowiązanie będzie Cię bardzo kosztować .

Jeśli ktoś chce mi przypomnieć, że to zmieniający się świat, myślę, że przekonasz się, że większe zbiory danych na bardziej cholernym sprzęcie przesadzają z rozpowszechnianiem odkryć Date.

Wszystkim z was, którzy pracują nad systemami rozliczeniowymi lub generatorami śmieci (wstydź się) i oburzają się na klawiaturze, aby powiedzieć mi, że wiesz, że denormalizacja jest szybsza, przepraszam, ale żyjesz w jednym ze specjalnych przypadki - w szczególności przypadek, w którym wszystkie dane przetwarzane są po kolei. To nie jest przypadek ogólny, a są uzasadnione w swojej strategii.

Jesteś nie usprawiedliwione fałszywie uogólniając je. Więcej informacji na temat odpowiedniego wykorzystania denormalizacji w scenariuszach hurtowni danych znajduje się na końcu sekcji notatek.

Chciałbym też odpowiedzieć

Połączenia to tylko kartezjańskie produkty z pewnym połyskiem

Co za ładunek byczków. Ograniczenia są stosowane tak wcześnie, jak to możliwe, najpierw najbardziej restrykcyjne. Przeczytałeś teorię, ale jej nie zrozumiałeś. Połączenia są traktowane jako „produkty kartezjańskie, do których mają zastosowanie predykaty” tylko przez optymalizator zapytania. Jest to symboliczna reprezentacja (w rzeczywistości normalizacja) w celu ułatwienia symbolicznego rozkładu, dzięki czemu optymalizator może wykonać wszystkie równoważne transformacje i uszeregować je według kosztów i selektywności, aby mógł wybrać najlepszy plan zapytań.

Jedynym sposobem uzyskania optymalizatora do wytworzenia produktu kartezjańskiego jest niedostarczenie predykatu: SELECT * FROM A,B

Notatki

David Aldridge zapewnia kilka ważnych dodatkowych informacji.

Rzeczywiście istnieje wiele innych strategii oprócz indeksów i skanów tabel, a nowoczesny optymalizator kosztuje je wszystkie przed opracowaniem planu wykonania.

Praktyczna rada: jeśli można go użyć jako klucza obcego, należy go zindeksować, tak aby strategia optymalizacji była dostępna dla optymalizatora.

Byłem mądrzejszy niż optymalizator MSSQL. To zmieniło się dwie wersje temu. Teraz ogólnie mnie uczy . W bardzo realnym sensie jest to system ekspercki, kodyfikujący całą mądrość wielu bardzo mądrych ludzi w dziedzinie wystarczająco zamkniętej, aby system oparty na regułach był skuteczny.

„Bollocks” mogły być nietaktowne. Zostałem poproszony o bycie mniej wyniosłym i przypomniano mi, że matematyka nie kłamie. To prawda, ale nie wszystkie implikacje modeli matematycznych należy koniecznie brać dosłownie. Pierwiastki kwadratowe liczb ujemnych są bardzo przydatne, jeśli ostrożnie unikniesz zbadania ich absurdu (gra słów tam) i do cholery upewnij się, że je wszystkie skasujesz, zanim spróbujesz zinterpretować swoje równanie.

Powodem, dla którego odpowiedziałem tak brutalnie, było to, że sformułowane oświadczenie tak mówi

Połączenia są produktami kartezjańskimi ...

To nie może być to, co miał, ale to , co zostało napisane, a to kategorycznie nieprawdziwe. Produkt kartezjański to relacja. Łączenie jest funkcją. Mówiąc dokładniej, sprzężenie jest funkcją o wartości relacyjnej. Przy pustym predykacie wytworzy produkt kartezjański, a sprawdzenie, czy to robi, jest jednym sprawdzeniem poprawności dla silnika zapytań do bazy danych, ale w praktyce nikt nie pisze nieograniczonych połączeń, ponieważ nie mają one praktycznej wartości poza klasą.

Wywołałem to, ponieważ nie chcę, aby czytelnicy wpadli w starożytną pułapkę mylenia modelu z modelowaną rzeczą. Model jest przybliżeniem, celowo uproszczonym dla wygodnej manipulacji.

Wartość graniczna dla wyboru strategii łączenia skanowania tabeli może się różnić w zależności od silnika bazy danych. Ma na to wpływ szereg decyzji implementacyjnych, takich jak współczynnik wypełnienia węzłów drzewa, rozmiar klucz-wartość i subtelności algorytmu, ale ogólnie mówiąc, indeksowanie o wysokiej wydajności ma czas wykonania k log n + c . C termin jest stałym narzutem składającym się głównie z czasu konfiguracji, a kształt krzywej oznacza, że ​​nie otrzymasz wypłaty (w porównaniu do wyszukiwania liniowego), dopóki n nie będzie setek.

Czasami denormalizacja jest dobrym pomysłem

Denormalizacja to zobowiązanie do konkretnej strategii łączenia. Jak wspomniano wcześniej, koliduje to z innymi strategiami łączenia. Ale jeśli masz wiadra miejsca na dysku, przewidywalne wzorce dostępu i tendencję do przetwarzania dużej części lub całości, to wstępne obliczenie sprzężenia może być bardzo opłacalne.

Możesz także dowiedzieć się, jakie ścieżki dostępu zwykle wykorzystuje Twoja operacja, i wstępnie obliczyć wszystkie sprzężenia dla tych ścieżek dostępu. Jest to przesłanka stojąca za hurtowniami danych, a przynajmniej wtedy, gdy budują je ludzie, którzy wiedzą, dlaczego robią to, co robią, i to nie tylko ze względu na zgodność z modnymi słowami.

Prawidłowo zaprojektowana hurtownia danych jest wytwarzana okresowo przez masową transformację ze znormalizowanego systemu przetwarzania transakcji. Takie rozdzielenie operacji i baz danych raportowania ma bardzo pożądany efekt eliminacji konfliktu między OLTP a OLAP (przetwarzanie transakcji online, tj. Wprowadzanie danych, i przetwarzanie analityczne online, tj. Raportowanie).

Ważną kwestią jest to, że oprócz okresowych aktualizacji hurtownia danych jest tylko do odczytu . To sprawia, że ​​sporne jest pytanie o anomalie aktualizacji.

Nie popełniaj błędu denormalizacji bazy danych OLTP (bazy danych, na której odbywa się wprowadzanie danych). Może to być szybsze w przypadku rozliczeń, ale jeśli to zrobisz, otrzymasz anomalie aktualizacji. Czy kiedykolwiek próbowałeś nakłonić Reader's Digest do zaprzestania wysyłania Ci rzeczy?

Miejsce na dysku jest obecnie tanie, więc powal się. Ale denormalizacja jest tylko częścią historii hurtowni danych. Znacznie większy wzrost wydajności wynika z wcześniej obliczonych zrolowanych wartości: sum miesięcznych, tego rodzaju rzeczy. To zawsze o zmniejszenie zestaw roboczy.

Problem ADO.NET z niedopasowaniem typów

Załóżmy, że masz tabelę SQL Server zawierającą indeksowaną kolumnę typu varchar i używasz AddWithValue, aby przekazać parametr ograniczający zapytanie do tej kolumny. Ciągi w języku C # są Unicode, więc domyślnym typem parametru będzie NVARCHAR, który nie pasuje do VARCHAR.

VARCHAR na NVARCHAR jest rozszerzającą konwersją, więc dzieje się to niejawnie - ale pożegnaj się z indeksowaniem i powodzenia w ustaleniu przyczyny.

„Policz uderzenia dysku” (Rick James)

Jeśli wszystko jest buforowane w pamięci RAM, JOINssą raczej tanie. Oznacza to, że normalizacja nie ma znacznego ograniczenia wydajności .

Jeśli schemat „znormalizowany” powoduje JOINsduże uderzenie w dysk, ale równoważny schemat „znormalizowany” nie musiałby uderzać w dysk, to denormalizacja wygrywa rywalizację o wydajność.

Komentarz oryginalnego autora: Nowoczesne silniki baz danych bardzo dobrze organizują sekwencjonowanie dostępu, aby zminimalizować straty pamięci podręcznej podczas operacji łączenia. Powyższe, choć prawdziwe, może być błędnie interpretowane jako sugerujące, że przyłączenia są z konieczności problematycznie drogie w przypadku dużych danych. Doprowadziłoby to do niewłaściwego podejmowania decyzji przez niedoświadczonych programistów.

To, czego większość komentujących nie zauważa, to szeroki zakres metod łączenia dostępnych w złożonym RDBMS, a denormalizatory niezmiennie odzwierciedlają wyższy koszt utrzymania zdormalizowanych danych. Nie każde sprzężenie opiera się na indeksach, a bazy danych mają wiele zoptymalizowanych algorytmów i metod łączenia, które mają na celu zmniejszenie kosztów łączenia.

W każdym razie koszt połączenia zależy od jego rodzaju i kilku innych czynników. To wcale nie musi być drogie - kilka przykładów.

• Sprzężenie mieszające, w którym łączone są dane zbiorcze, jest w rzeczywistości bardzo tanie, a koszt staje się znaczny tylko wtedy, gdy tabeli skrótów nie można buforować w pamięci. Nie wymaga indeksu. Równe partycjonowanie między połączonymi zestawami danych może być bardzo pomocne.
• Koszt połączenia sortowania-scalania zależy raczej od kosztu sortowania niż scalania - metoda dostępu oparta na indeksie może praktycznie wyeliminować koszt sortowania.
• Koszt połączenia zagnieżdżonej pętli w indeksie zależy od wysokości indeksu b-drzewa i dostępu do samego bloku tabeli. Jest szybki, ale nie nadaje się do połączeń luzem.
• Sprzężenie zagnieżdżonej pętli oparte na klastrze jest znacznie tańsze, z mniejszą liczbą logicznych operacji we / wy na wiersz łączenia - jeśli połączone tabele znajdują się w tym samym klastrze, wówczas połączenie staje się bardzo tanie dzięki kolokacji połączonych wierszy.

Bazy danych są zaprojektowane do łączenia i są bardzo elastyczne w tym, jak to robią i ogólnie bardzo wydajne, chyba że źle zrozumieją mechanizm łączenia.

Myślę, że całe pytanie opiera się na fałszywym założeniu. Dołącza na dużych tabel są nie koniecznie drogie. W rzeczywistości efektywne wykonywanie połączeń jest jednym z głównych powodów, dla których w ogóle istnieją relacyjne bazy danych . Połączenia na dużych zestawach często są drogie, ale bardzo rzadko chcesz połączyć całą zawartość dużej tabeli A z całą zawartością dużej tabeli B. Zamiast tego piszesz zapytanie w taki sposób, że używane są tylko ważne wiersze każdej tabeli i rzeczywisty zestaw zachowany przez złączenie pozostaje mniejszy.

Dodatkowo, masz wydajności wymienione przez Petera Wone'a, tak że tylko ważne części każdego rekordu muszą być w pamięci, dopóki nie pojawi się ostateczny zestaw wyników. Ponadto w dużych zapytaniach z wieloma sprzężeniami zwykle chcesz zacząć od mniejszych zestawów tabel i pracować aż do dużych, aby zestaw przechowywany w pamięci pozostawał tak mały, jak to tylko możliwe.

Po prawidłowym wykonaniu sprzężenia są zazwyczaj najlepszym sposobem porównywania, łączenia lub filtrowania dużych ilości danych.

Wąskie gardło jest prawie zawsze dyskowe we / wy, a dokładniej - losowe dyskowe we / wy (dla porównania, sekwencyjne odczyty są dość szybkie i mogą być buforowane za pomocą strategii odczytu z wyprzedzeniem).

Dołącza może zwiększać liczbę losowych wyszukiwań - jeśli przeskakujesz czytając małe fragmenty dużego stołu. Ale optymalizatorzy zapytań szukają tego i zamieniają go w sekwencyjny skan tabeli (odrzucając niepotrzebne wiersze), jeśli uzna, że ​​tak będzie lepiej.

Pojedyncza tabela zdenormalizowana ma podobny problem - wiersze są duże, a więc mniej pasują do pojedynczej strony danych. Jeśli potrzebujesz wierszy, które znajdują się daleko od siebie (a duży rozmiar wiersza czyni je dalej od siebie oddalonymi), będziesz mieć więcej losowych operacji we / wy. Ponownie, skanowanie tabeli może być zmuszone, aby tego uniknąć. Ale tym razem skan tabeli musi odczytać więcej danych ze względu na duży rozmiar wiersza. Dodaj do tego fakt, że kopiujesz dane z jednej lokalizacji do wielu lokalizacji, a RDBMS ma o wiele więcej do odczytania (i buforowania).

Z 2 tabelami otrzymujesz również 2 indeksy klastrowe - i ogólnie możesz indeksować więcej (z powodu mniejszego obciążenia związanego z wstawianiem / aktualizacją), co może znacznie zwiększyć wydajność (głównie znowu, ponieważ indeksy są (względnie) małe, szybkie do odczytania z dysku (lub tanie w buforowaniu) i zmniejsz liczbę wierszy tabeli, które musisz odczytać z dysku).

Jedyny narzut z łączeniem pochodzi z rozpracowania pasujących rzędów. Serwer Sql używa 3 różnych rodzajów sprzężeń, głównie w oparciu o rozmiary zestawu danych, aby znaleźć pasujące wiersze. Jeśli optymalizator wybierze niewłaściwy typ łączenia (z powodu niedokładnych statystyk, nieodpowiednich indeksów lub po prostu błędu optymalizatora lub wielkości krawędzi), może to drastycznie wpłynąć na czasy zapytań.

• Łączenie w pętli jest zdecydowanie tanie dla (co najmniej 1) małego zestawu danych.
• Łączenie scalające wymaga najpierw pewnego rodzaju obu zestawów danych. Jeśli jednak dołączysz do indeksowanej kolumny, indeks jest już posortowany i nie trzeba wykonywać żadnych dalszych prac. W przeciwnym razie podczas sortowania występuje pewien narzut procesora i pamięci.
• Łączenie skrótów wymaga zarówno pamięci (do przechowywania tablicy skrótów), jak i procesora (do budowy skrótu). Ponownie jest to dość szybkie w stosunku do dyskowych operacji we / wy. Jeśli jednak nie ma wystarczającej ilości pamięci RAM do przechowywania tablicy hashtable, Sql Server użyje tempdb do przechowywania części tablicy hashtable i znalezionych wierszy, a następnie przetworzy tylko części tablicy hashtable na raz. Podobnie jak w przypadku wszystkich rzeczy na dysku, jest to dość powolne.

W optymalnym przypadku nie powodują one dyskowych operacji we / wy, a zatem są nieistotne z punktu widzenia wydajności.

Podsumowując, w najgorszym przypadku - powinno być w rzeczywistości szybsze odczytanie takiej samej ilości danych logicznych z x połączonych tabel, jak w przypadku pojedynczej tabeli znormalizowanej z powodu mniejszych odczytów z dysku. Aby odczytać tę samą ilość danych fizycznych , może wystąpić niewielki narzut.

Ponieważ czas kwerendy jest zwykle zdominowany przez koszty we / wy, a rozmiar danych nie zmienia się (minus niektóre bardzo małe narzuty wiersza) z denormalizacją, nie ma ogromnej korzyści, którą można uzyskać, łącząc ze sobą tabele. Typem denormalizacji, który ma tendencję do zwiększania wydajności, IME, jest buforowanie obliczonych wartości zamiast odczytywania 10 000 wierszy wymaganych do ich obliczenia.

Kolejność dołączania do tabel jest niezwykle ważna. Jeśli masz dwa zestawy danych, spróbuj zbudować kwerendę w taki sposób, aby najmniejsza została wykorzystana jako pierwsza w celu zmniejszenia ilości danych, na których kwerenda musi pracować.

W przypadku niektórych baz danych nie ma to znaczenia, na przykład MS SQL przez większość czasu zna prawidłową kolejność łączenia. W przypadku niektórych (takich jak IBM Informix) kolejność robi różnicę.

Decyzja o tym, czy denormalizować, czy normalizować, jest dość prostym procesem, biorąc pod uwagę klasę złożoności złączenia. Na przykład, mam tendencję do projektowania moich baz danych z normalizacją, gdy zapytania są O (k log n), gdzie k jest względne do pożądanej wielkości wyjściowej.

Prostym sposobem na denormalizację i optymalizację wydajności jest zastanowienie się, w jaki sposób zmiany w normalizowanej strukturze wpływają na zdenormalizowaną strukturę. Może to być jednak problematyczne, ponieważ może wymagać logiki transakcyjnej do pracy ze zdenormalizowaną strukturą.

Debata na temat normalizacji i denormalizacji nie zakończy się, ponieważ problemy są ogromne. Istnieje wiele problemów, w których naturalne rozwiązanie wymaga obu podejść.

Zasadniczo zawsze zapisywałem znormalizowaną strukturę i zdenormalizowane pamięci podręczne, które można odtworzyć. Ostatecznie te pamięci podręczne ratują mój tyłek, aby rozwiązać przyszłe problemy z normalizacją.

Opracowanie tego, co powiedzieli inni,

Połączenia to tylko kartezjańskie produkty z pewnym połyskiem. {1,2,3,4} X {1,2,3} dałoby nam 12 kombinacji (nXn = n ^ 2). Ten zestaw obliczeniowy działa jako odniesienie do warunków, które są stosowane. DBMS stosuje warunki (jak tam, gdzie zarówno lewa, jak i prawa to 2 lub 3), aby dać nam pasujące warunki. W rzeczywistości jest bardziej zoptymalizowany, ale problem jest taki sam. Zmiany wielkości zestawów gwałtownie zwiększałyby rozmiar wyniku. Ilość zużytej pamięci i cykli procesora odbywa się w sposób wykładniczy.

Kiedy denormalizujemy, całkowicie unikamy tego obliczenia, myślimy o przyklejonym kolorowym, przyczepionym do każdej strony książki. Możesz wywnioskować informacje bez użycia odniesienia. Karą, którą płacimy, jest to, że naruszamy istotę DBMS (optymalna organizacja danych)