„N + 1 wybiera problem” jest ogólnie określany jako problem w dyskusjach ORM (Object-Relational Mapation) i rozumiem, że ma to coś wspólnego z koniecznością wykonywania dużej liczby zapytań do bazy danych dla czegoś, co wydaje się proste w obiekcie świat.
Czy ktoś ma bardziej szczegółowe wyjaśnienie problemu?
orm
select-n-plus-1
Lars A. Brekken
źródło
źródło
Odpowiedzi:
Załóżmy, że masz kolekcję
Car
obiektów (wiersze bazy danych), a każdy z nichCar
ma kolekcjęWheel
obiektów (także wierszy). Innymi słowy,Car
→Wheel
jest relacją jeden do wielu.Powiedzmy, że musisz iterować przez wszystkie samochody i dla każdego wydrukować listę kół. Naiwna implementacja operacji byłaby następująca:
A następnie dla każdego
Car
:Innymi słowy, masz jeden wybór dla samochodów, a następnie N dodatkowych wyborów, gdzie N jest całkowitą liczbą samochodów.
Alternatywnie można uzyskać wszystkie koła i wykonać wyszukiwanie w pamięci:
Zmniejsza to liczbę podróży w obie strony do bazy danych z N + 1 do 2. Większość narzędzi ORM oferuje kilka sposobów zapobiegania wybieraniu N + 1.
Odniesienia: Java Persistence with Hibernate , rozdział 13.
źródło
SELECT * from Wheel;
), zamiast N + 1. Przy dużej wartości N wydajność może być bardzo znacząca.Otrzymasz zestaw wyników, w którym wiersze podrzędne w tabeli 2 powodują duplikację, zwracając wyniki tabeli 1 dla każdego wiersza podrzędnego w tabeli 2. Mapujący O / R powinien rozróżnić instancje table1 na podstawie unikalnego pola klucza, a następnie użyć wszystkich kolumn table2, aby zapełnić instancje potomne.
N + 1 to miejsce, w którym pierwsze zapytanie wypełnia główny obiekt, a drugie zapytanie wypełnia wszystkie obiekty potomne dla każdego zwróconego unikalnego obiektu podstawowego.
Rozważać:
oraz tabele o podobnej strukturze. Jedno zapytanie dotyczące adresu „22 Valley St” może zwrócić:
O / RM powinien wypełnić instancję Dom o ID = 1, Adres = „22 Valley St”, a następnie wypełnić tablicę Inhabitants instancjami People dla Dave'a, Johna i Mike'a za pomocą tylko jednego zapytania.
Zapytanie N + 1 dla tego samego adresu użytego powyżej spowoduje:
z osobnym zapytaniem jak
i w wyniku czego powstaje osobny zestaw danych, np
a wynik końcowy jest taki sam jak powyżej dla pojedynczego zapytania.
Zaletą pojedynczego wyboru jest to, że masz wszystkie dane z góry, które mogą być tym, czego ostatecznie pragniesz. Zaletą N + 1 jest to, że złożoność zapytań jest zmniejszona i można użyć leniwego ładowania, w którym potomne zestawy wyników są ładowane tylko na pierwsze żądanie.
źródło
Dostawca z relacją jeden do wielu z Produktem. Jeden dostawca ma (dostarcza) wiele produktów.
Czynniki:
Tryb leniwy dla dostawcy ustawiony na „prawda” (domyślnie)
Tryb pobierania używany do wysyłania zapytań o Produkt to Wybierz
Tryb pobierania (domyślnie): Dostęp do informacji o dostawcy
Buforowanie nie odgrywa roli po raz pierwszy
Dostęp do dostawcy
Tryb pobierania to Wybierz pobieranie (domyślnie)
Wynik:
To jest problem wyboru N + 1!
źródło
Nie mogę komentować bezpośrednio innych odpowiedzi, ponieważ nie mam wystarczającej reputacji. Warto jednak zauważyć, że problem zasadniczo pojawia się tylko dlatego, że historycznie wiele dbms było dość słabych, jeśli chodzi o obsługę sprzężeń (MySQL jest szczególnie godnym uwagi przykładem). Tak więc n + 1 często było zauważalnie szybsze niż złączenie. Są też sposoby na poprawienie n + 1, ale nadal bez konieczności łączenia, z czym wiąże się pierwotny problem.
Jednak MySQL jest teraz o wiele lepszy niż kiedyś, jeśli chodzi o dołączenia. Kiedy po raz pierwszy nauczyłem się MySQL, często używałem łączenia. Potem odkryłem, jak wolne są i zamiast tego przełączyłem na n + 1 w kodzie. Ale ostatnio wróciłem do przyłączeń, ponieważ MySQL jest teraz o wiele lepszy w obsłudze niż wtedy, gdy zacząłem go używać.
Obecnie proste sprzężenie na odpowiednio zindeksowanym zestawie tabel rzadko stanowi problem pod względem wydajności. A jeśli daje to hit wydajności, to użycie wskazówek indeksu często rozwiązuje je.
Jest to omówione tutaj przez jeden z zespołów programistów MySQL:
http://jorgenloland.blogspot.co.uk/2013/02/dbt-3-q3-6-x-performance-in-mysql-5610.html
Podsumowując, jeśli w przeszłości unikałeś złączeń z powodu fatalnej wydajności MySQL, spróbuj ponownie w najnowszych wersjach. Prawdopodobnie będziesz mile zaskoczony.
źródło
JOIN
algorytmów używanych w RDBMS nazywa się pętlami zagnieżdżonymi. Zasadniczo jest to wybór N + 1 pod maską. Jedyną różnicą jest to, że DB dokonał inteligentnego wyboru, aby użyć go na podstawie statystyk i indeksów, a nie kodu klienta, zmuszając go kategorycznie.Z powodu tego problemu odeszliśmy od ORM w Django. Zasadniczo, jeśli spróbujesz
ORM z przyjemnością zwróci wszystkie osoby (zwykle jako instancje obiektu Person), ale wtedy będzie musiał zapytać o tablicę samochodową dla każdej Osoby.
Proste i bardzo skuteczne podejście do tego nazywam „ rozkładaniem wachlarzy ”, co pozwala uniknąć nonsensownego pomysłu, że wyniki zapytania z relacyjnej bazy danych powinny być odwzorowane z powrotem na oryginalne tabele, z których składa się zapytanie.
Krok 1: Szeroki wybór
To zwróci coś w rodzaju
Krok 2: Objectify
Ssaj wyniki do ogólnego twórcy obiektów z argumentem do podzielenia po trzecim elemencie. Oznacza to, że obiekt „jones” nie zostanie wykonany więcej niż raz.
Krok 3: Renderuj
Zobacz tę stronę internetową dla implementacji Fanfolding dla Pythona.
źródło
select_related
, co ma rozwiązać ten problem - w rzeczywistości jego dokumenty zaczynają się od przykładu podobnego do twojegop.car.colour
przykładu.select_related()
iprefetch_related()
się teraz Django.select_related()
przyjaciel nie wydaje się robić żadnej z oczywistych użytecznych ekstrapolacji połączenia, takich jakLEFT OUTER JOIN
. Problem nie jest problemem interfejsu, ale problemem związanym z dziwnym pomysłem, że obiekty i dane relacyjne są możliwe do zmapowania .... moim zdaniem.Na czym polega problem zapytania N + 1
Problem zapytania N + 1 występuje, gdy struktura dostępu do danych wykonała N dodatkowych instrukcji SQL w celu pobrania tych samych danych, które mogły zostać pobrane podczas wykonywania podstawowego zapytania SQL.
Im większa wartość N, tym więcej zapytań zostanie wykonanych, tym większy wpływ na wydajność. I w przeciwieństwie do dziennika powolnych zapytań, które mogą pomóc Ci znaleźć wolno działające zapytania, problem N + 1 nie zostanie wykryty, ponieważ każde dodatkowe zapytanie działa wystarczająco szybko, aby nie wyzwalać dziennika wolnych zapytań.
Problem polega na wykonywaniu dużej liczby dodatkowych zapytań, które ogólnie wymagają wystarczającej ilości czasu, aby spowolnić czas odpowiedzi.
Rozważmy, że mamy następujące tabele bazy danych post i post_comments, które tworzą relację jeden do wielu :
Utworzymy następujące 4
post
rzędy:Stworzymy również 4
post_comment
rekordy potomne:Problem zapytania N + 1 ze zwykłym SQL
Jeśli wybierzesz
post_comments
użycie tego zapytania SQL:A później decydujesz się pobrać powiązane
post
title
dla każdegopost_comment
:Wywołujesz problem zapytania N + 1, ponieważ zamiast jednego zapytania SQL wykonałeś 5 (1 + 4):
Naprawienie problemu zapytania N + 1 jest bardzo łatwe. Wszystko, co musisz zrobić, to wyodrębnić wszystkie dane, których potrzebujesz w oryginalnym zapytaniu SQL:
Tym razem wykonywane jest tylko jedno zapytanie SQL, aby pobrać wszystkie dane, których jesteśmy dalej zainteresowani.
Problem zapytania N + 1 z JPA i Hibernacją
Podczas korzystania z JPA i Hibernacji istnieje kilka sposobów na wywołanie problemu zapytania N + 1, dlatego bardzo ważne jest, aby wiedzieć, jak można uniknąć takich sytuacji.
W kolejnych przykładach rozważmy, że mapujemy tabele
post
ipost_comments
na następujące elementy:Odwzorowania JPA wyglądają tak:
FetchType.EAGER
Używanie
FetchType.EAGER
niejawnie lub jawnie dla stowarzyszeń JPA jest złym pomysłem, ponieważ masz zamiar pobrać znacznie więcej potrzebnych danych. Więcej,FetchType.EAGER
strategia jest również podatna na problemy z zapytaniami N + 1.Niestety, skojarzenia
@ManyToOne
i@OneToOne
używająFetchType.EAGER
domyślnie, więc jeśli twoje odwzorowania wyglądają tak:Używasz
FetchType.EAGER
strategii i za każdym razem, gdy zapomnisz użyć jejJOIN FETCH
podczas ładowania niektórychPostComment
encji za pomocą zapytania JPQL lub Criteria API:Wywołujesz problem zapytania N + 1:
Zwróć uwagę na dodatkowe SELECT, które są wykonywane, ponieważ
post
stowarzyszenie musi być pobrana przed zwróceniemList
odPostComment
podmiotów.W przeciwieństwie do domyślnego planu pobierania, którego używasz podczas wywoływania
find
metodyEnrityManager
zapytania, JPQL lub Criteria API definiuje jawny plan, którego Hibernacja nie może zmienić, automatycznie wstrzykuj JOIN FETCH. Musisz to zrobić ręcznie.Jeśli w ogóle nie potrzebujesz
post
skojarzenia, nie masz szczęścia,FetchType.EAGER
ponieważ nie ma sposobu, aby go nie pobrać. Dlatego lepiej jest używaćFetchType.LAZY
domyślnie.Ale jeśli chcesz użyć
post
powiązania, możesz użyć,JOIN FETCH
aby uniknąć problemu z zapytaniem N + 1:Tym razem Hibernacja wykona jedną instrukcję SQL:
FetchType.LAZY
Nawet jeśli przejdziesz na używanie
FetchType.LAZY
jawnie dla wszystkich skojarzeń, nadal możesz natknąć się na problem N + 1.Tym razem
post
powiązanie jest mapowane w następujący sposób:Teraz, gdy pobierasz
PostComment
podmioty:Hibernacja wykona jedną instrukcję SQL:
Ale jeśli później odniesiesz się do leniwie załadowanego
post
skojarzenia:Otrzymasz problem z zapytaniem N + 1:
Ponieważ
post
skojarzenie jest pobierane leniwie, podczas uzyskiwania dostępu do leniwego skojarzenia zostanie wykonana dodatkowa instrukcja SQL w celu zbudowania komunikatu dziennika.Ponownie, poprawka polega na dodaniu
JOIN FETCH
klauzuli do zapytania JPQL:I podobnie jak w
FetchType.EAGER
przykładzie, to zapytanie JPQL wygeneruje pojedynczą instrukcję SQL.Jak automatycznie wykryć problem zapytania N + 1
Jeśli chcesz automatycznie wykryć problem zapytania N + 1 w warstwie dostępu do danych, w tym artykule wyjaśniono, jak to zrobić za pomocą projektu typu
db-util
open source.Najpierw musisz dodać następującą zależność Maven:
Następnie wystarczy użyć
SQLStatementCountValidator
narzędzia do potwierdzenia wygenerowanych instrukcji SQL:Jeśli używasz
FetchType.EAGER
i uruchamiasz powyższy przypadek testowy, otrzymasz następujący błąd przypadku testowego:źródło
SELECT cars, wheels FROM cars JOIN wheels LIMIT 0, 5
. Ale dostajesz 2 samochody z 5 kołami (pierwszy samochód ze wszystkimi 4 kołami i drugi samochód tylko z 1 kołem), ponieważ LIMIT ograniczy cały zestaw wyników, nie tylko klauzulę root.Załóżmy, że masz SPÓŁKĘ i PRACOWNIKA. FIRMA ma wielu PRACOWNIKÓW (tj. PRACOWNIK ma pole COMPANY_ID).
W niektórych konfiguracjach O / R, gdy masz zmapowany obiekt Firmy i masz dostęp do jego obiektów Pracownika, narzędzie O / R dokona jednego wyboru dla każdego pracownika, a jeśli robisz tylko proste SQL, możesz to zrobić
select * from employees where company_id = XX
. Zatem N (liczba pracowników) plus 1 (firma)Tak działały początkowe wersje EJB Entity Beans. Wierzę, że takie rzeczy jak Hibernacja zniosły to, ale nie jestem zbyt pewien. Większość narzędzi zwykle zawiera informacje dotyczące ich strategii mapowania.
źródło
Oto dobry opis problemu
Teraz, gdy rozumiesz problem, zwykle można go uniknąć, wykonując połączenie dołączenia w zapytaniu. To zasadniczo wymusza pobranie leniwie załadowanego obiektu, więc dane są pobierane w jednym zapytaniu zamiast n + 1 zapytań. Mam nadzieję że to pomoże.
źródło
Sprawdź post Ayende na ten temat: Zwalczanie problemu wyboru N + 1 w NHibernate .
Zasadniczo, jeśli używasz ORM, takiego jak NHibernate lub EntityFramework, jeśli masz relację jeden do wielu (główny-szczegółowy) i chcesz wyświetlić wszystkie szczegóły dla każdego rekordu głównego, musisz wykonać wywołania zapytania N + 1 do baza danych, gdzie „N” oznacza liczbę rekordów głównych: 1 zapytanie, aby uzyskać wszystkie rekordy główne, i N zapytań, po jednym na rekord główny, aby uzyskać wszystkie szczegóły na rekord główny.
Więcej wywołań zapytań do bazy danych → dłuższy czas oczekiwania → zmniejszona wydajność aplikacji / bazy danych.
Jednak ORM mają opcje pozwalające uniknąć tego problemu, głównie za pomocą JOIN.
źródło
O wiele szybciej jest wydać 1 zapytanie, które zwraca 100 wyników, niż wydać 100 zapytań, z których każde zwraca 1 wynik.
źródło
Moim zdaniem artykuł napisany w Hibernacji Pitfall: Dlaczego relacje powinny być leniwe jest dokładnie odwrotny do prawdziwego problemu N + 1.
Jeśli potrzebujesz poprawnego wyjaśnienia, zapoznaj się z Hibernacją - Rozdział 19: Poprawa wydajności - Pobieranie strategii
źródło
Podany link zawiera bardzo prosty przykład problemu n + 1. Jeśli zastosujesz go do Hibernacji, to w zasadzie mówi o tym samym. Podczas zapytania o obiekt jednostka jest ładowana, ale wszelkie skojarzenia (o ile nie skonfigurowano inaczej) będą ładowane z opóźnieniem. Stąd jedno zapytanie dotyczące obiektów głównych i drugie zapytanie w celu załadowania powiązań dla każdego z nich. Zwrócone 100 obiektów oznacza jedno zapytanie początkowe, a następnie 100 dodatkowych zapytań, aby uzyskać skojarzenie dla każdego, n + 1.
http://pramatr.com/2009/02/05/sql-n-1-selects-explained/
źródło
Jeden milioner ma N samochodów. Chcesz zdobyć wszystkie (4) koła.
Jedno (1) zapytanie ładuje wszystkie samochody, ale dla każdego (N) samochodu przesyłane jest osobne zapytanie dotyczące ładowania kół.
Koszty:
Załóżmy, że indeksy pasują do pamięci RAM.
Analiza składni i planowania 1 + N + wyszukiwanie indeksu ORAZ 1 + N + (N * 4) dostęp do płyty w celu załadowania ładunku.
Załóżmy, że indeksy nie pasują do pamięci RAM.
Dodatkowe koszty w najgorszym przypadku dostęp do płyt 1 + N dla indeksu obciążenia.
Podsumowanie
Szyjka butelki ma dostęp do płyty (około 70 razy na sekundę dostępu losowego na dysku twardym). Chętny wybór połączenia również uzyskałby dostęp do płyty 1 + N + (N * 4) razy dla ładunku. Jeśli więc indeksy mieszczą się w pamięci RAM - nie ma problemu, jest wystarczająco szybki, ponieważ dotyczą tylko operacji pamięci RAM.
źródło
Problem wyboru N + 1 to ból i sensowne jest wykrywanie takich przypadków w testach jednostkowych. Opracowałem małą bibliotekę do weryfikacji liczby zapytań wykonanych za pomocą danej metody testowej lub po prostu dowolnego bloku kodu - JDBC Sniffer
Po prostu dodaj specjalną regułę JUnit do swojej klasy testowej i umieść adnotację z oczekiwaną liczbą zapytań w metodach testowych:
źródło
Problem, jak inni stwierdzili bardziej elegancko, polega na tym, że albo masz kartezjański produkt z kolumn OneToMany, albo robisz selekcje N + 1. Możliwie gigantyczny zestaw wyników lub odpowiednio rozmowa z bazą danych.
Dziwię się, że nie wspomniano o tym, ale poradziłem sobie z tym problemem ... Tworzę pół-tymczasową tabelę identyfikatorów . Robię to również, gdy masz
IN ()
ograniczenie klauzuli .Nie działa to we wszystkich przypadkach (prawdopodobnie nawet nie w większości), ale działa szczególnie dobrze, jeśli masz wiele obiektów potomnych, tak że produkt kartezjański wymknie się spod kontroli (tj. Wiele
OneToMany
kolumn, liczba wyników będzie pomnożenie kolumn) i jest to bardziej zadanie wsadowe.Najpierw wstawiasz identyfikatory obiektów nadrzędnych jako partię do tabeli identyfikatorów. Ten batch_id to coś, co generujemy w naszej aplikacji i którego trzymamy.
Teraz dla każdego
OneToMany
kolumny po prostu wykonaj aSELECT
na tabeli ids, porównując tabelęINNER JOIN
podrzędną za pomocąWHERE batch_id=
(lub odwrotnie). Musisz tylko upewnić się, że sortujesz według kolumny id, ponieważ ułatwi to scalanie kolumn wyników (w przeciwnym razie będziesz potrzebować HashMap / Table dla całego zestawu wyników, co może nie być takie złe).Następnie okresowo czyścisz tabelę identyfikatorów.
Działa to również szczególnie dobrze, jeśli użytkownik wybierze powiedzmy 100 lub więcej różnych elementów do pewnego rodzaju przetwarzania masowego. Umieść 100 różnych identyfikatorów w tabeli tymczasowej.
Teraz liczba zapytań zależy od liczby kolumn OneToMany.
źródło
Weźmy na przykład Matta Solnita, wyobraź sobie, że definiujesz powiązanie między samochodem a kołami jako LAZY i potrzebujesz niektórych pól Wheels. Oznacza to, że po pierwszym wybraniu hibernacja wykona „Wybierz * z kół, gdzie car_id =: id” DLA KAŻDEGO samochodu.
To sprawia, że pierwszy wybór i więcej 1 wybór dla każdego samochodu N, dlatego nazywa się to problemem n + 1.
Aby tego uniknąć, spraw, aby skojarzenie było pobierane tak chętnie, aby hibernacja ładowała dane z łączeniem.
Ale uwaga, jeśli wiele razy nie uzyskujesz dostępu do powiązanych Kół, lepiej jest pozostawać ODPORNY lub zmienić typ pobierania za pomocą kryteriów.
źródło