Koji je algoritam za upit podataka iz dve tabele i kakva je njegova složenost?

Upit za podatke iz dve tabele obično se vrši pomoću operacije JOIN u SQL-u. Algoritam zavisi od tipa spoja (INNER JOIN, LEFT JOIN itd.) i načina izvršenja (ugneždene petlje, hash join, merge join).

Primer upita:

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

Algoritam:

1. Za svaki zapis iz prve tabele traže se odgovarajući zapisi u drugoj prema uslovu spoja.
2. Rezultati se kombinuju u jedan red.

Složenost zavisi od implementacije:

• Nested loops join — O(N*M), gde su N i M veličine tabela.
• Hash join — O(N + M), ako podaci stanu u memoriju i hashiranje je efikasno.
• Merge join — O(N log N + M log M), ako su tabele sortirane.

Optimizacija upita i izbor algoritma zavise od indeksa, obima podataka i statistika baze.