Wydajność zapytani sub select Opcje

[kris2]

Mam taki zestaw tabel:

użytkownik (z uzytkownikami systemu)

grupy (grupy do ktorych moze zapisac sie uzytkownik) (np A, B, C , D , E ...)

uzytkownicy_grupa (relacjz zawierająca informacje o grupac do ktorych jest zapisany użytkownik)

załóżmy że użytkowników jest milion a grup 10-20 więc wydajność ma znaczenie.

schamt jest taki

użytkownik 1 - N użytkownicy_grupa N <- 1 grupy

Jak najwydajniej zapytać się o użytkowników należących do grupy A, B i C:
Przychodzą mi do głowy 3 rozwiązania

po 1: - totalnie lame
- umieścic w tabeli użytkownicy spis grup po przecinku i użyć LIKE

po 2: - wykorzystanie zmiennej typu array
- to też nie wygląda na idealne rozwiązanie ponieważ jest ograniczenie przy przeszukiwaniu zmiennych array, można jedynie użyć any lub all
(+ na PostgreSQL napisano
Tip: Arrays are not sets; searching for specific array elements may be a sign of database misdesign. Consider using a separate table with a row for each item that would be an array element. This will be easier to search, and is likely to scale up better to large numbers of elements.
)

po 3: - używanie subselecta na zasadzie

[SQL] pobierz, plaintext 
SELECT * FROM użytkownik u WHERE (SELECT * FROM grupa g WHERE u.użytkownik_id=g.użytkownik_id AND (g.grupa=A or g.grupa=B or g.grupa=C))=3
[SQL] pobierz, plaintext 

Ma ktoś jakieś lepsze rozwiązania lub umie uzasadnić które wybrać i dlaczego?

Ten post edytował kris2 21.08.2007, 19:40:38

[Zbłąkany]

Rozwiązanie 1 odpada, 2 zda egzamin pod warunkiem, że nikt nie będzie grzebać w tych tablicach ręcznie (wszystkie aktualizacje itd najlepiej, aby robiły triggery). Co do 3 rozwiązania to będzie świetne pod warunkiem, że powprowadzasz klucze główne (PK) dla każdej tabeli i pozakładasz odpowiednie indeksy oraz potworzysz relacje, wtedy zapytania typu JOIN w połączeniu z podzapytaniami są bardzo wydajne.

[osiris]

Wydaje mi sie ze to zapytanie nie jest zbyt optymalne, a to dlatego ze podzapytanie bedzie wykonywane dla kazdego uzytkownika.Chyba najprosciej:

[SQL] pobierz, plaintext 
SELECT * FROM uzytkownicy WHERE id IN (
SELECT uzytkownik_id
FROM uzytkownicy_grupy WHERE grupa_id IN (A,B,C,D)
GROUP BY uzytkownik_id
HAVING COUNT(grupa_id) = 4)
[SQL] pobierz, plaintext 

W tym wypadku podzapytanie powinno wykonac sie tylko raz, gdyz nie ma w nim odwolania do tabeli zewnetrznej

Jesli chodzi o indeksy, to niewazne ktoro rozwiazanie zastosujesz, zawsze powinienes z nich korzystac.

A zeby sie w latwy sposob przekonac ktoro rozwiazanie bedzie najszybsze, stworz te tabele, wypelnij je przykladowymi danymi i uruchom kilka razy te zapytania, ale wylacz dla nich cacheowanie (SQL_NO_CACHE).

Teraz przyszedl mi do glowy jeszcze jeden pomysl. Ma on jedno wazne ograniczenie, ale mysle ze byloby najbardziej wydajne.
Ograniczeniem jest tu liczba wszystkich mozliwych grup, nie moze byc wieksza niz 32 (bo typu int ma 32bity).

Dla pelnego zrozumienia wymagana jest podstawowa wiedza nt operacji logicznych.

Oto co moznaby zrobic:
- tabela uzytkownicy_grupa niepotrzebna
- kazdej grupie przypisujesz numer bedacy potega dwojki (1,2,4,8,16,32... az do 2^31)
- do tabeli uzytkownikow dodajesz jedno pole grupy - typu unsigned int
- teraz chcesz dodac kogos do danej grupy:

[SQL] pobierz, plaintext 
UPDATE uzytkownicy SET grupy = (grupy | $nr_grupy) WHERE id = $id_uzytkownika
[SQL] pobierz, plaintext 

- usunac kogos z danej grupy:

[SQL] pobierz, plaintext 
UPDATE uzytkownicy SET grupy = (grupy & ~$nr_grupy) WHERE id = $id_uzytkownika
[SQL] pobierz, plaintext 

- chcesz wyszukac wg danej grupu:

[SQL] pobierz, plaintext 
SELECT * FROM uzytkownicy WHERE (grupy & $nr_grupy) > 0
[SQL] pobierz, plaintext 

Wszysktkie te operacje mozna wykonac dla kilku grup naraz, zastepujac $nr_grupy czyms takim ($grupa_1 | $grupa_2 | $grupa_3 .... $grupa_n)czyli dla przykladu:

[SQL] pobierz, plaintext 
SELECT * FROM uzytkownicy WHERE (grupy & ($g1 | $g2 | $g3 | $g5)) > 0
[SQL] pobierz, plaintext 

operatory:
& - iloczyn logiczny bit po bicie
| - suma logiczna bit po bicie
~ - inwersja wszystkich bitow

Uwaga, nie mylic tych operatorow z &&, || i !

Ten post edytował osiris 22.08.2007, 10:53:33

[kris2]

osiris jesteś dla mnie mistrzem świata
to naprawde świetne rozwiązania i sprawdzone bo używałem go wiele lat temu kodując w pascalu gdy wielkość zasobów miala kosmiczne znaczenie.
Ide sobie posprawdzać czy to będzie tak wydajne jak myśle.

Wielkie dzięki!

[osiris]

Nie ma sprawy. Kiedys postawisz mi piwo

Tez kiedys uzywalem takiego rozwiazania jak programowalem w C/C++. Jak widac wiedza programistyczna moze sie przydac w roznych dziedzinach informatyki.

Daj znac jakie wyniki otrzymales przy testach, bo sam jestem ciekawy, jak bardzo wydajne jest takie rozwiazanie.

[kris2]

Po wstępnych testach moge powiedzieć że wygląda na to że liczenie wszystkiego na bitach jest kilka razy szybsze niż używanie subselectów i dodatkowej tabeli. Nie wiem jak bedzie z updatami, bo tego nie sprawdzalem ale one maja dla mnie akurat mniejsze znaczenie. Jedyny minus jest taki że zapytanie na bitach nie wykorzystuje indexów.
Tylko ja mam na tyle specyficzny przypadek że ograniczenia zasięgu będą na obu tabelach więc to nie ma znaczenia.
Testy robiłem na tabeli 1,5mln rekordów na bazie PostgreSQL. Niestety nie zdążyłem przetestować wszystkoego co chciałem ale jak mi się uda to to tutaj opisze.

[SongoQ]

Rozwiazanie jest dobra, jeszcze minusem jest to ze nie wymuszamy relacji (mozna dodac grupe ktora nie istnieje). Ale to jak zawsze cos kosztem czegos. Mozna np triggera zalozyc i weryfikowac.

[osiris]

Jedna uwaga. Do moich zapytan podanych we wczesniejszym poscie wkradl sie blad. Ponizsze zapytanie jest zle:

[SQL] pobierz, plaintext 
SELECT * FROM uzytkownicy WHERE (grupy & $grupy) > 0
[SQL] pobierz, plaintext 

powinno byc:

[SQL] pobierz, plaintext 
SELECT * FROM uzytkownicy WHERE (grupy & $grupy) = $grupy
[SQL] pobierz, plaintext 

W pierwszym przypadku zostana znalezieni wszyscy uzytkownicy ktorzy naleza do przynajmniej jednej z grup (a nie wszystkich)!

Ciekaw bylem wydajnosci takiego rozwiazania i sam zrobilem troche testow.

Stworzylem przykladowa tabele:

[SQL] pobierz, plaintext 
CREATE TABLE `users` (
  `id` mediumint(10) UNSIGNED NOT NULL AUTO_INCREMENT,
  `name` varchar(20) collate utf8_polish_ci NOT NULL,
  `pass` varchar(40) collate utf8_polish_ci NOT NULL,
  `groups` int(10) UNSIGNED NOT NULL DEFAULT '0',
  `homedir` varchar(30) collate utf8_polish_ci NOT NULL,
  `active` tinyint(1) NOT NULL DEFAULT '0',
  PRIMARY KEY  (`id`),
  KEY `groups` (`groups`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 COLLATE=utf8_polish_ci
[SQL] pobierz, plaintext 

i wypelnilem je przypadkowymi danymi. Jesli chodzi o name, pass i homedir, dane te pobralem czytajac plik avi , groups byly losowo generowane, active co druga jest 1.

Wstawilem 1,5 mln rekordow. Tabela zajmuje:170MB, z indeksami prawie 200MB.

Co sie okazalo to to ze dlugosc wyszukiwania uzytkownikow nalezacych do wybranych grup zalezy od tego ile grup chcemy sprawdzic. Nie wiem czemu tak sie dzieje, moze ktos ma jakis pomysl.

Testy przeprowadzilem w nastepujacy sposob:
dla kazdej mozliwej liczby bitow(1-31) wykonywalem 10 zapytan:

[SQL] pobierz, plaintext 
SELECT SQL_NO_CACHE * FROM users WHERE groups & $liczba = $liczba LIMIT 30
[SQL] pobierz, plaintext 

gdzie $liczba to losowo wygenerowana liczba w ktorej n bitow jest zapalonych (to tak jakbysmy szukali user wsrod n losowo wybranych grup),

mierzylem czas wykonywania tych zapytan i potem obliczylem srednia.
Oto wyniki:

Kod

Ilosc bitow        Sredni czas(s)
---------------------------------
1               0.00074770450592
2               0.000751495361328
3               0.000946569442749
4               0.0039412021637
5               0.0040956735611
6               0.00505304336548
7               0.00831155776978
8               0.0105215072632
9               0.0200308084488
10              0.0367336988449
11              0.0835324525833
12              0.147039031982
13              0.276187181473
14              0.507218337059
15              1.06423690319
16              1.53951747417
17              1.59646685123
18              1.64317190647
19              1.67781071663
20              1.71348867416
21              1.56421909332
22              1.59005527496
23              1.62178874016
24              1.64297554493
25              1.67281501293
26              1.65174326897
27              1.57270855904
28              1.6054520607
29              1.62569227219
30              1.66454772949
31              1.6705922842

Jak widac czas wykonywania zapytania na poczatku rosnie wykladniczo. Pozniej najprawdopodobniej zaczely coraz lepiej dzialac mechanizmy cacheujace linux'a.

Testy przeprowadzalem na kompie:
AMD Sempron 2500+
pamiec 1GB RAM
dysk 160GB SATA 8MB Cache
OS: Kubuntu 7.04

W czasie wykonywania testu zajetosc czasu procesora byla maksymalna.

Komp sluzy do uzytku domowego, wiec w czasie testow bylo otwartych sporo innych aplikacji, ale staralem sie wtedy nic nie robic (nawet nie ruszalem myszka) wiec wyniki powinny byc w miare wiarygodne.

Nie wiem czy to jest optymalne rozwiazanie, warto by jeszcze sprawdzic jak sie sprawdzi moje wczesniejsze rozwiazanie (z grupowaniem) i jakie beda osiaga przy wykorzystaniu pola typu BITFIELD.

Ten post edytował osiris 23.08.2007, 15:09:16

[kris2]

według mnie obciążenie wzrasta ponieważ wykonujesz więcej operacji matematycznych przy każdej krotce.

u mnie na szczescie beda dwa dodatkowe założenia.
Po 1 wyciągam pierwsze 1000 rekordów a ponieważ nie używam order by to nie ma sortowania i zapytanie nie przeszuka całości
po 2 bede mial inne ograniczenia niż tylko na bitach.

Ale widać po tym że takie zapytanie może trwać nawet kilka ms co nie jest mało.

[osiris]

według mnie obciążenie wzrasta ponieważ wykonujesz więcej operacji matematycznych przy każdej krotce.

Ilość operacji matematycznych powinna być taka sama dla każdej liczby grup. Dla przykładu, jeśli szukamy osoby należącej do grup 1,2,3,4,5 to wykonywana będzie dla każdego rekordu operacja:
grupy & 31 (bo 31 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4)
natomiast jeśli szukamy dla grup 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 to wykonujemy operacje:
grupy & 4194303 (bo 4194303 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^21)

(operację sumy logicznej można zastąpić w tym przypadku operacją sumy arytmetycznej, gdyż na żadnym bicie nie dochodzi do przeniesienia).

Jak widać zawsze wykonywana jest tylko jedna operacja, zmienia się tylko drugi argument funkcji.

Jedyny powód, który potrafię sobie wyobrazić, dlaczego czas wykonywania rośnie wraz z ilością sprawdzanych bitów (grup) to taki, że być może MySQL optymalizuje w jakiś sposób zapytania, w których argument operatora & ma mało "zapalonych" bitów.