też czytam z przyjemnością tą dyskusję, wiele można się nauczyć. proszę dalej 
Tak z ciekawości stworzyłem 10 mln rekordów Item, 10 mln rekordów listings. Każdemu listingowi przypisałem losowo 1-10 itemów, co dało 55 007 226 rekordów ListingItem. Indeks założony na listing_items(listing_id). Baza mysql, cache zapytań wyłączony (query_cache_size=0).
[code]>> l = Listing.find(rand(10_000_000))
Listing Load (28.7ms) SELECT * FROM listings WHERE (listings.id = 7546480)
±--------±------------------------±------------------------+
| id | created_at | updated_at |
±--------±------------------------±------------------------+
| 7546480 | 2009-10-18 19:23:01 UTC | 2009-10-18 19:23:01 UTC |
±--------±------------------------±------------------------+
1 row in set
l.items(true)
Item Load (137.5ms) SELECTitems.* FROMitemsINNER JOINlisting_itemsONitems.id =listing_items.item_id WHERE ((listing_items.listing_id = 7546480)) ORDER BY position
±---------±------------------------±------------------------+
| id | created_at | updated_at |
±---------±------------------------±------------------------+
| 2420041 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 8146028 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 4895215 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 1894403 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 1745660 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 10098376 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 6350939 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
±---------±------------------------±------------------------+
7 rows in setl.items(true)
Item Load (0.7ms) SELECTitems.* FROMitemsINNER JOINlisting_itemsONitems.id =listing_items.item_id WHERE ((listing_items.listing_id = 7546480)) ORDER BY position
±---------±------------------------±------------------------+
| id | created_at | updated_at |
±---------±------------------------±------------------------+
| 2420041 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 8146028 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 4895215 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 1894403 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 1745660 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 10098376 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
| 6350939 | 2009-10-18 18:33:02 UTC | 2009-10-18 18:33:02 UTC |
±---------±------------------------±------------------------+[/code]
Jak widać czasy za 1 razem nie są powalające (28.7m i 137.5ms), ale należy za poprawkę wziąć fakt, że prawd. tylko część danych będzie używana na bieżąco, zatem szybko zostaną zbuforowane często używane strony, stąd drugie wywołanie l.items(true) zajmuje już < 1ms. Przy odpowiedniej konfiguracji (tu zwykła developerksa) i sprzęcie powinno śmigać.
I jeszcze explain:
mysql> explain SELECT `items`.* FROM `items` INNER JOIN `listing_items` ON `items`.id = `listing_items`.item_id WHERE ((`listing_items`.listing_id = 7546480)) ORDER BY position\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: listing_items
type: ref
possible_keys: index_listing_items_on_listing_id
key: index_listing_items_on_listing_id
key_len: 5
ref: const
rows: 7
Extra: Using where; Using filesort
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: items
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: test_development.listing_items.item_id
rows: 1
Extra:
2 rows in set (0.00 sec)
Nic dodać, nic ująć.
Panowie, 10 mln rekordów na tabelę?
Rozmawialiśmy o technikach optymalizacji dla serwisów o skali friendfeeda, grona, facebooka (ugh!) i innych takich, gdzie milion(y) to jest userów – a każdy z nich generuje tyle contentu (oraz istnieje “friendships”, powodujący czasem podwójne złącznenie), że inne tabele mają rekordów miliardy.
Milion rekordów to ja mam w bazie developerskiej na laptopie żeby zobaczyć gdzie opłaca się położyć indeksy i co będzie wymagało optymalizacji w pierwszej kolejności 
[quote=Tomash]Panowie, 10 mln rekordów na tabelę?
Rozmawialiśmy o technikach optymalizacji dla serwisów o skali friendfeeda, grona, facebooka (ugh!) i innych takich, gdzie milion(y) to jest userów – a każdy z nich generuje tyle contentu (oraz istnieje “friendships”, powodujący czasem podwójne złącznenie), że inne tabele mają rekordów miliardy.
Milion rekordów to ja mam w bazie developerskiej na laptopie żeby zobaczyć gdzie opłaca się położyć indeksy i co będzie wymagało optymalizacji w pierwszej kolejności ;)[/quote]
A gdzie jest napisane, że ktokolwiek mówił o tej wielkości serwisów, był wyciągnięty problem joina, a tu kolega nagle wymyśla, że rozmawiamy o czymś innym.
Btw, u mnie na bazie testowej join 10mln x 10 mln robi się w okolicach od 2ms do 800ms, bo nie chciało mi się zmieniać ustawień bazy, więc naprawdę mówienie o tym, że joiny są jakieś koszmarne to jakiś dowcip.
Natomiast przy serwisach skali facebooka problemem jest raczej coś innego. Danych jest tyle, że taniej wychodzi zrobić to na wielu serwerach niż na jednym, bo jeden będzie o wiele droższy niż wiele badziewnych maszyn. Przez takie rozproszenie joiny stają się tak koszmarnie niewydajne, że praktycznie i tak nikt ich nie robi (nawet nie ma odpowiednich mechanizmów do tego). Bazy takie jak Hadoop czy BigTable nie mają joinów z definicji bo taka architektura, a nie dlatego, że joiny w bazach są wolne (bo nie są). Trzeba też powiedzieć, że Hadoop nie robi tego za darmo, brak joinów wymusza porządną denormalizację bazy i przechowywanie tych samych danych w wielu miejscach przez co updaty robią się o wiele droższe i często może to prowadzić to tego, że dane się rozjeżdżają, no ale coś za coś.
800 ms?
W 2-3 sekundy trzeba mieć już wygenerowaną i wyrenderowaną odpowiedź – co będzie ciężkie do osiągnięcia, jeśli w samej bazie spędzimy 800ms.
Panowie, sorry – nie jestem ekspertem od baz SQL, przyznaję się bez bicia i od początku. I póki nie będę, bardziej wierzę kolesiom znanym mi z nazwiska, twarzy i dużych serwisów które utworzyli, rozwijają i utrzymują – że JOIN to operacja kosztowna i jej eliminacja (przez denormalizację) jest kolejnym, po położeniu indeksów, niezbędnym krokiem do utrzymania akceptowalnej wydajności w miarę rozrostu serwisu (i bazy).
[quote=Tomash]Panowie, 10 mln rekordów na tabelę?
Rozmawialiśmy o technikach optymalizacji dla serwisów o skali friendfeeda, grona, facebooka (ugh!) i innych takich, gdzie milion(y) to jest userów – a każdy z nich generuje tyle contentu (oraz istnieje “friendships”, powodujący czasem podwójne złącznenie), że inne tabele mają rekordów miliardy.
Milion rekordów to ja mam w bazie developerskiej na laptopie żeby zobaczyć gdzie opłaca się położyć indeksy i co będzie wymagało optymalizacji w pierwszej kolejności ;)[/quote]
Uważam, że 50 mln rekordów to o wiele więcej niż posiada statystyczna baza. Przy takiej skali wielkości o jakiej piszesz to już nie jest kwestia “kosztownych” joinów, ale prawie każdego zapytania. Ponadto pojedyncze, tak ogromne tabele są niewygodne w użyciu, backupowaniu, utrzymaniu.
Tylko życzyć każdemu z nas by miał takie problemy.
800 ms?
W 2-3 sekundy trzeba mieć już wygenerowaną i wyrenderowaną odpowiedź – co będzie ciężkie do osiągnięcia, jeśli w samej bazie spędzimy 800ms.
Panowie, sorry – nie jestem ekspertem od baz SQL, przyznaję się bez bicia i od początku. I póki nie będę, bardziej wierzę kolesiom znanym mi z nazwiska, twarzy i dużych serwisów które utworzyli, rozwijają i utrzymują – że JOIN to operacja kosztowna i jej eliminacja (przez denormalizację) jest kolejnym, po położeniu indeksów, niezbędnym krokiem do utrzymania akceptowalnej wydajności w miarę rozrostu serwisu (i bazy).[/quote]
Twoim błędem jest zbyt dosłowne traktowanie tego co oni mówią. Po pierwsze dotyczy to skali, z którą podejrzewam żaden z nas nie miał do czynienia (przynajmniej mogę mówić za siebie). Po drugie to nie join jest kosztowną operacją. Join to tylko skutek rozproszenia danych po różnych tabelach. Przecież niektóre joiny możesz zastąpić 2 prostymi selectami (co robią przecież railsy bodajże od wersji 2.0), ale nie zmieni to faktu, że złożoność będzie taka sama. Należy pamiętać, że zawsze istnieje pewna skala, przy której powszechnie stosowane rozwiązania stają się nieużywalne.
Nie ma oczywiście dyskusji z faktem, że denormalizacja to kolejny krok w optymalizacji. Tak samo jak i sharding, partycjonowanie, klastrowanie. Czy w takim układzie powiemy, że przechowywanie danych w 1 tabelce jest niewydajne, bo lepiej użyć partycjonowania? Kluczem do tej dyskusji jest zdefiniowanie skali problemu. Bez tego pisanie, że joiny są niewydajne, tylko sieje zamęt w głowach ludzi, którzy nie rozumieją do końca problemu.
OK, masz rację, trochę za bardzo zmierzamy w kierunku “railsy są wolne i zasobożerne”.
A co byście poprawili w takim zapytaniu?
select distinct * from streets where
id in(select distinct street_id from letters_streets where letter_id = 27) and
id in(select distinct street_id from letters_streets where letter_id = 11) and
id in(select distinct street_id from letters_streets where letter_id = 18) and
id in(select distinct street_id from letters_streets where letter_id = 26) and
id in(select distinct street_id from letters_streets where letter_id = 8) and
id in(select distinct street_id from letters_streets where letter_id = 6);
Wykonanie tego przy 60 tys ulic zajmuje kilka na MySQLu kilka sekund. Jest to próba zasymulowania GPSowego wprowadzania liter, o którym pisałem wcześniej, przy czym w tym przykładzie id’ki są losowe, ale przyjmując za podstawę zwykłe ASCII, letter_id w zakresie 0-127 oznacza pierwszy znak, 128-255 drugi itp. Struktura analogiczna do wcześniejszej, czyli trzy tabele: streets, letters i letters_streets. Wiem, że tekstowe wyszukiwanie na bazie mogłoby być szybsze, ale jest to tylko przykład.
EDIT: poprawiłem item_id na street_id.
Spróbuj rozbić to na 2 zapytania:
ids = select item_id from letters_streets where letter_id in (27, 11, 18, 26, 8, 6)
select distinct * from streets where id in (ids)
Po pierwsze sorry za drobną pomyłkę, wyedytowałem poprzedniego posta. Po drugie to niestety nie będzie to, bo letter_id IN () daje sumę, a ja potrzebuję iloczyn z poszczególnych WHERE’ów, a to nie wychodzi na to samo.
Ja bym przed denormalizacją wolał uskutecznic cachowanie jeśli byłoby to możliwe.
[quote=ohaleck]A co byście poprawili w takim zapytaniu?
select distinct * from streets where
id in(select distinct street_id from letters_streets where letter_id = 27) and
cut…[/quote]
Ja bym zainstalował sphinx.
Jak ktoś ma tylko młotek to wszystko wygląda dla niego jak gwóźdź. Relacyjna baza danych nie rozwiązuje wszystkich problemów. Jeśli chcesz obsłużyć taki use case to potrzebujesz serwera, który obsługuje full text search.
Nie potrzebuję text search. Tak jak napisałem, podpowiadanie (czy raczej ukrywanie) znaków jest to tylko najprostszy przykład tej aplikacji. Mógłbym zrobić np. n-wymiarowy tag cloud, wtedy zamiast liter miałbym tagi, a zamiast nazw ulic adresy (albo id) stron.
A jeśli przeczytasz kilka postów wyżej, to właśnie sam napisałem, że relacyjna baza danych nie rozwiązuje wszystkich problemów i ten problem jest na to dowodem. Chodzi mi tylko o to, czy tego SQLa można jeszcze jakoś zoptymalizować.
Dokładnie tak
[quote=ohaleck]A co byście poprawili w takim zapytaniu?
select distinct * from streets where
id in(select distinct street_id from letters_streets where letter_id = 27) and
id in(select distinct street_id from letters_streets where letter_id = 11) and
id in(select distinct street_id from letters_streets where letter_id = 18) and
id in(select distinct street_id from letters_streets where letter_id = 26) and
id in(select distinct street_id from letters_streets where letter_id = 8) and
id in(select distinct street_id from letters_streets where letter_id = 6);
Wykonanie tego przy 60 tys ulic zajmuje kilka na MySQLu kilka sekund. Jest to próba zasymulowania GPSowego wprowadzania liter, o którym pisałem wcześniej, przy czym w tym przykładzie id’ki są losowe, ale przyjmując za podstawę zwykłe ASCII, letter_id w zakresie 0-127 oznacza pierwszy znak, 128-255 drugi itp. Struktura analogiczna do wcześniejszej, czyli trzy tabele: streets, letters i letters_streets. Wiem, że tekstowe wyszukiwanie na bazie mogłoby być szybsze, ale jest to tylko przykład.
EDIT: poprawiłem item_id na street_id.[/quote]
Czegoś nie łapię, mógłbyś pokazaż co masz w tabeli letters_streets?
To zapewne nic Ci nie da:
mysql> select * from letters_streets limit 10;
+-------------+---------+
| letter_id | street_id |
+-------------+---------+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 5 | 3 |
| 5 | 4 |
| 5 | 5 |
| 5 | 5 |
| 6 | 5 |
+-------------+---------+
10 rows in set (0.00 sec)
Generalnie jest tak: ulica o nazwie ABC ma przypisane odpowiednio rekordy, które można nazwać A1, B2, C3 czyli A na pierwszej pozycji, B na drugiej itp. Tworząc bazę czytam listę ulic i dla każdej ulicy: 1) tworzę nowy rekord street, 2) używając find_or_create dodaję kolejne rekordy dla liter do letters i asocjacje do letters_streets.
Aplikacja znając pierwszą literę odnajduje wszystkie ulice zaczynające się na tę literę (co jest proste i szybkie), a następnie szuka wszystkich liter występujących na drugiej pozycji (lub w uproszczeniu: w ogóle wszystkich liter) w nazwach tych ulic. Mając je, może wyszarzyć niektóre przyciski, a inne nie.
ohaleck, czy mógłbyś opisać jaki problem dokładnie próbujesz rozwiązać? (nie do końca rozumiem kwestię tych liter). Wydaje mi się, że nie do końca dobrze się do tego zabrałeś (na ostateczne osądy poczekam aż dokładnie opiszesz problem, który musisz rozwiązać).
OK. Zostawmy ulice i literki żeby nikogo nie ciągnęło do wyszukiwania tekstowego. Sformułuję problem inaczej:
N artykułów, każdy ma M(N) tagów w relacji has_and_belongs_to_many albo has_many :through. Chcę umożliwić wyszukiwanie po tagach (dowolnej ich ilości), przy czym wybranie jednego taga spowoduje odświeżenie listy tagów tak, że widoczne będą tylko inne tagi występujące wraz z tymi już zaznaczonymi (wszystkimi). W ten sposób mogę uściślać kryteria wyszukiwania mając gwarancję dostania na końcu niezerowego wyniku w postaci artykułu lub artykułów.
Taka metoda określana jest jako faceted search albo faceted navigation i nie znam polskiego tłumaczenia tego terminu.
Rzuciłem ten problem jako kontynuacja wątku dotyczącego optymalizacji. Próbowałem to zaimplementować na SQLu i poległem ze względu na tragiczną wydajność, a moim celem, jeśli w ogóle dojdzie do działającej implementacji jest tylko i wyłącznie udowodnienie (lub ewentualnie obalenie) tezy, że takiego problemu na relacyjnej bazie nie da się bez denormalizacji zaimplementować z zachowaniem przyzwoitem wydajności. W przeciwnym razie, byłaby powszechnie stosowana np. w sklepach internetowych czy Allegro w celu redukcji rozbudowanych hierarchii kategorii produktów. Do 40" TV Sony wiedzie jedna ścieżka (najpierw muszę wybrać przekątną, a następnie markę), a mogłoby ich być wiele.
Temat stanowi dla mnie bardziej ciekawostkę niż rzeczywisty problem i przedstawiam go raczej jako zagadkę, a nie poważne zagadnienie.