Block nested loop

Article summary

A block-nested loop (BNL) is an algorithm used to join two relations in a relational database. This algorithm is a variation of the simple nested loop join and joins two relations R and S (the "outer" and "inner" join operands, respectively). Suppose |R| . In a traditional nested loop join, S will be scanned once for every tuple of R . If there are many qualifying R tuples, and particularly if there is no applicable index for the join key on S , this operation will be very expensive. The block nested loop join algorithm improves on the simple nested loop join by only scanning S once for every group of R tuples. Here groups are disjoint sets of tuples in R and the union of all groups has the same tuples as R . For example, one variant of the block nested loop join reads an entire page of R tuples into memory and loads them into a hash table. It then scans S , and probes the hash table to find S tuples that match any of the tuples in the current page of R . This reduces the number of scans of S that are necessary.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.