Optymalizacyjne pytanie dotyczące szybkości wyszukiwania dla dużej bazy danych MS SQL

Cześć dopiero od krótkiego czasu zajmuję się projektowaniem i tworzeniem baz danych w MS SQL. Mam już troszkę wprawy i nurtuje mnie pewne pytanie. Z tego co pamiętam to wyszukiwanie w bazie danych w tabeli po kluczu głównym zajmuje tyle co nic bo po kluczu głównym mamy dostęp automatyczny do danego wiersza. Jeżeli jestem w tym przekonaniu w błędzie to prosił bym o sprostowanie. Kontynuując załóżmy, że mamy tabele produktów z miliardem wierszy. Tabela jest tak zaprojektowana, że prawdopodobnie każdy użytkownik odnosi się jedynie do jednego z tych produktów. Jednak istnieje możliwość, że będą użytkownicy, którzy chcą być powiązani z kilkoma np max do 20 produktów. Od tego momentu zaczyna się mój dylemat.
Oto dwa rozwiązania miedzy którymi się zastanawiam.

1. Każdy produkt ma referencje do swojego użytkownika i po odpowiednim zapytaniu, baza przeszukuje tabelę miliarda wierszy wypisując listę produktów, z którymi dany użytkownik był powiązany.

Skoro takie zapytanie nie dotyczy już klucza głównego produktu, a zamiast tego dotyczy pola użytkownik w tabeli produktów. To wydaje mi się, że baza z takim zapytaniem musi przejść przez wszystkie miliard wierszy tabeli (co może być dość pracochłonne) i następnie wyświetla listę produktów.
To rozwiązanie jest pewnie dość standardowe dla małych baz

2. Drugim rozwiązaniem jest utworzenie tabeli użytkowników z referencją na ich pierwszy produkt. Tabela produktów będzie natomiast zawierać referencję do innego produktu. W takim przypadku zakładając, że znamy już klucz użytkownika to po tym kluczu automatycznie dostaniemy klucz główny pierwszego produktu. Jeżeli użytkownik będzie miał tylko jeden produkt to referencja z tego produktu będzie wskazywać na klucz produkt "0" i na tym działanie programu się skończy. Jeśli użytkownik ma kilka produktów to przechodzimy przez jego produkty jak przez listę za każdym razem otrzymując klucz główny następnego produktu.

Takie rozwiązanie sprawia, że jeśli miał bym tabelę z przynajmniej miliardem produktów przeszedł bym przez te jedynie kilka produktów użytkownika za każdym razem używając klucza głównego i nie musiał bym sprawdzać jak wcześniej całego miliarda wierszy.

Mam nadzieje, że dobrze opisałem problem.
Pamiętając więc o tym, że nasza tabela ma bardzo wiele rekordów, prawdopodobnie miliard jest tutaj zaniżoną liczbą.
Tak więc na jakie rozwiązanie powinienem się zdecydować?
z góry dzięki za odpowiedź

Proponuje zacząć od doczytania sobie: jak działają bazy danych, co to są indeksy (to obowiązkowo!), jakie są koszty wyszukiwania w hashmapach i drzewach binarnych.
W skrócie: wyszukiwanie po kluczu głownym jest szybkie nie ze względu na jakieś "automatyczne dostępy" a dlatego ze na klucz główny masz automatycznie indeks.
Rozwiązanie numer 1, o ile zalożysz indeks na pole idUżytkownika, jest wystarczające i nie ma sensu kombinować...

Wyliczyłem sobie ile może być rekordów tabeli produkty to +- 20 miliardów a jednak może być jeszcze więcej. W związku z tym że jest to sporo to przejście przed 20 miliardów rekordów może trochę potrwać. Chyba, że używanie referencji nie sprowadza się do zwykłego przechodzenia przez wszystkie wiersze a działa w inny sposób nachodzi mnie pytanie czy wyszukiwanie po kluczu obcym jest równie szybkie jak wyszukiwanie po kluczu głównym jeśli tak to faktycznie nie ma najmniejszego problemu w zastosowaniu pierwszego rozwiązania. Próbowałem przed chwilą znaleźć jakieś informacje na temat sposobów działania baz danych. Jednak w internecie jest pełno śmieci dotyczących podstaw i ciężko mi się przekopać do jakichś czysto optymalizacyjnych technologicznych informacji. Dodam również, że byłem pewien, że klucze są hashowane jednak nie znając dalszych informacji nie chciałem pisać głupot. Myślałem, że używa się tablic hashujacych. Jeżeli masz dostęp do jakiś artykułów, które mogły by się okazać mi przydatne to był bym wdzięczny. Jeśli nie to jutro przed świątecznymi zakupami :D wybiorę się do empiku i poszukam książki, która zawierała by takie informacje i przeczytam szybko rozdział. Jednak z tym też może się okazać problem. Bo większość książek jest biedna w takie informacje przynajmniej z przeczytanych przed chwilą 2 spisów treści wydawnictwa helion. Dzięki za pomoc i pozdro!

Myśle że warto zacząć od tego

Jeśli masz indeks na jakiś atrybut to wybranie z bazy rekordu szukając po tym atrybucie nie odbywa się przez przeglądanie tych 20 miliardów rekordów, tylko odbywa się w czasie nieporównywalnie krótszym z wykorzystaniem indeksu. Sama szybkość zależy tu od tego jak te indeksy są zrobione (hashowanie, drzewo binarne, B-drzewo).
Załóżmy że byłoby to zwykłe drzewo AVL. Wyszukanie w takim drzewie elementu odbywa się w czasie log2(n), czyli dla 20 miliardów elementów w drzewie jesteś w stanie wyszukać element po maksymalnie 35 porównaniach. Jest różnica? ;)

Myślę, że rozumiem już ideologię. Jak jutro coś znajdę w empiku to ewentualnie jeszcze doczytam głębiej. Na dziś te informacje jednak mi wystarczą, żeby kontynuować projekt.
Bardzo mi pomogłeś. Dzieki!

Ostatnie pytanie. Jak dobrze zrozumiałem to tego typu wyszukiwanie obowiązuje niezależnie od tego czy wyszukujemy po kluczu głównym czy obcym tak?
jeszcze raz dzieki i pozdro ;)

tu nie chodzi o klucz główny/obcy tylko o to czy na danym polu(polach) jest założony indeks! Koniec, kropka. Odczep się od kluczy :).
Jako iż klucz główny musi być unikalny to baza automatycznie na polu (polach), które ma być PK zakłada indeks unikalny (co oznacza, że wartości nie mogą się powtarzać). Przy zakładaniu FK indeks nie jest nigdzie automatycznie zakładany. Jedynie większość baz wymaga aby był założony indeks w tabeli na kolumnie do której odwołuje się FK.

Inna sprawa, że jeśli będziesz miał 20 000 000 000 rekordów i pole w którym będzie 1000 różnych wartości to indeks na takim polu nic nie da bo średnio dana wartość będzie występować w 20 000 000 000 / 1 000 = 20 000 000 rekordach.

Mówiąc obrazowo indeks działa jak skorowidz w książce - możesz albo przeszukać całą książkę strona po stronie w poszukiwaniu jakiejś frazy albo zajrzeć do skorowidza (skorowidzu - jak się to odmienia?) i tam mając ALFABETYCZNY spis fraz zobaczyć na której stronie się ona znajduje

mhm :)
W moim przypadku wykorzystanie indexów bedzie jednak przydatne bo na te przykładowe 20 000 000 000 rekordów przypadnie minimalnie ponizej 1 000 000 000 różnych kluczy obcych wiec powiązań kluczy obcych z rekordami będzie ponad 20 może do 30 :) co w konsekwencji da pewnie świetny wynik. Przedstawiłeś jednak dobry obraz całej sprawy.

Chciał bym się jeszcze upewnić bo jak rozumiem indeksowanie jest zakładane dla kluczy konkretnej tabeli tzn jeżeli mam dwie tabele użytkownicy i produkty a w produktach mam klucz obcy do użytkowników. To zakładane są indeksy na kluczach głównych obu tabel jednak jeżeli chcę przyspieszyć wyszukiwanie na tabeli produktów z wykorzystaniem klucza obcego to dodatkowo muszę założyć oddzielnie dla tabeli produkty indeksowanie na klucz obcy. Mam nadzieję że koncepcja jest zrozumiała 2 tabele, 2 indeksowania, dodatkowo trzecie indeksowanie dla jednej z tabel. Pytanie brzmiało czy sam muszę zakładać trzecie indeksowanie. Tak/Nie moim zdaniem tak ;P i to chyba tyle.

Nie potrzebnie jeszcze męczyłem właśnie wyczytałem, że index zakłada się na kolumnę lub kilka kolumn.
To chyba będzie wszystko.
Jeszcze raz dzięki za pomoc ;) pozdrawiam

Moja (i pewnie nie tylko) filozofia relacyjnych baz danych to klucz główny i klucz biznesowy na każdej tabeli bez wyjątku. Klucz główny to PK, który jest automatycznie indeksem. Klucz biznesowy to unikalny indeks nieklastrowany czyli zestaw kolumn, który jest unikalny w całej tabeli. Jeżeli tabele w bazie są znormalizowane i masz klucz biznesowy to automatycznie unikasz 95% typowych problemów wydajnościowych i możesz skupić się na tych 5%, których rozwiązanie jest mniej trywialne.