Comparing Join Algorithms
Review of cost formulae:
| Algorithm |
Cost |
| Nested Loops |
NR(1 + pR NS) |
| Nested Loops (improved) |
NR(1 + NS) |
| Block Nested Loops |
NR + ceil(NR / (B−2)) NS |
| Index Nested Loops |
NR(1 + 2 pR) |
| Sort Merge |
NR + NS |
- NR: Number of pages in R.
- NS: Number of pages in S.
- pR: Number of R rows per page.
- pS: Number of S rows per page.
- B: Number of pages (Blocks) in memory used for the join.
|