Aký je algoritmus pre dopytovanie údajov z dvoch tabuliek a aká je jeho zložitosť?

Dopyt po dátach z dvoch tabuliek sa zvyčajne vykonáva pomocou operácie JOIN v SQL. Algoritmus závisí od typu spojenia (INNER JOIN, LEFT JOIN atď.) a spôsobu vykonania (vnorené slučky, hash join, merge join).

Príklad dopytu:

SELECT a.*, b.*
FROM tableA a
JOIN tableB b ON a.key = b.key;

Algoritmus:

1. Pre každý záznam z prvej tabuľky sa hľadajú zodpovedajúce záznamy v druhej podľa podmienky spojenia.
2. Výsledky sa skombinujú do jedného riadku.

Zložitosť závisí od implementácie:

• Nested loops join — O(N*M), kde N a M sú veľkosti tabuliek.
• Hash join — O(N + M), ak sa dáta zmestia do pamäti a hashovanie je efektívne.
• Merge join — O(N log N + M log M), ak sú tabuľky zoradené.

Optimalizácia dopytu a výber algoritmu závisí od indexov, objemu dát a štatistík databázy.