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

[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.