Pi Hydrae: Difference between revisions
en>Bibcode Bot m Adding 3 arxiv eprint(s), 0 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot |
en>Monkbot |
||
| Line 1: | Line 1: | ||
{{multiple issues| | |||
{{no footnotes|date=October 2012}} | |||
{{refimprove|date=November 2006}} | |||
}} | |||
A '''block-nested loop''' ('''BNL''') is an [[algorithm]] used to [[join (SQL)|join]] two relations in a [[relational database]]. | |||
This algorithm is a variation on the simple [[nested loop join]] used to join two relations <math>R</math> and <math>S</math> (the "outer" and "inner" join operands, respectively). Suppose <math>|R| < |S|</math>. In a traditional nested loop join, <math>S</math> will be scanned once for every tuple of <math>R</math>. If there are many qualifying <math>R</math> tuples, and particularly if there is no applicable index for the join key on <math>S</math>, this operation will be very expensive. | |||
The block nested loop join algorithm improves on the simple nested loop join by only scanning <math>S</math> once for every ''group'' of <math>R</math> tuples. For example, one variant of the block nested loop join reads an entire [[page (computing)|page]] of <math>R</math> tuples into memory and loads them into a [[hash table]]. It then scans <math>S</math>, and probes the hash table to find <math>S</math> tuples that match any of the tuples in the current page of <math>R</math>. This reduces the number of scans of <math>S</math> that are necessary. | |||
A more aggressive variant of this algorithm loads as many pages of <math>R</math> as can be fit in the available memory, loading all such tuples into a hash table, and then repeatedly scans <math>S</math>. This further reduces the number of scans of <math>S</math> that are necessary. In fact, this algorithm is essentially a special-case of the classic [[hash join]] algorithm. | |||
The block nested loop runs in <math>O(P_r P_s/M)</math> I/Os where <math>M</math> is the number of available pages of internal memory and <math>P_r</math> and <math>P_s</math> is size of <math>R</math> and <math>S</math> respectively in pages. Note | |||
that block nested loop runs in <math>O(P_r+P_s)</math> I/Os if <math>R</math> fits in the available internal memory. | |||
==References== | |||
{{Reflist}} | |||
* [http://dev.mysql.com/doc/refman/5.6/en/bnl-bka-optimization.html Block Nested-Loop Joins] in the MySQL 5.6 Reference Manual. | |||
{{DEFAULTSORT:Block Nested Loop}} | |||
[[Category:Join algorithms]] | |||
Revision as of 15:50, 28 January 2014
Template:Multiple issues A block-nested loop (BNL) is an algorithm used to join two relations in a relational database.
This algorithm is a variation on the simple nested loop join used to join two relations and (the "outer" and "inner" join operands, respectively). Suppose . In a traditional nested loop join, will be scanned once for every tuple of . If there are many qualifying tuples, and particularly if there is no applicable index for the join key on , this operation will be very expensive.
The block nested loop join algorithm improves on the simple nested loop join by only scanning once for every group of tuples. For example, one variant of the block nested loop join reads an entire page of tuples into memory and loads them into a hash table. It then scans , and probes the hash table to find tuples that match any of the tuples in the current page of . This reduces the number of scans of that are necessary.
A more aggressive variant of this algorithm loads as many pages of as can be fit in the available memory, loading all such tuples into a hash table, and then repeatedly scans . This further reduces the number of scans of that are necessary. In fact, this algorithm is essentially a special-case of the classic hash join algorithm.
The block nested loop runs in I/Os where is the number of available pages of internal memory and and is size of and respectively in pages. Note that block nested loop runs in I/Os if fits in the available internal memory.
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- Block Nested-Loop Joins in the MySQL 5.6 Reference Manual.