Browse Prior Art Database

Algorithm for Optimal Buffer Partitioning in Nested Block Joins

IP.com Disclosure Number: IPCOM000120048D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 2 page(s) / 64K

Publishing Venue

IBM

Related People

Iyer, BR: AUTHOR [+2]

Abstract

Disclosed is an algorithm for optimally partitioning the buffer in a multiple relation nested block join. Nested block join (1) is a generalization (to blocks) of the traditional nested loop algorithm. The speed of a nested block join depends heavily upon the way in which the buffer is partitioned among the various relations participating in the join.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Algorithm for Optimal Buffer Partitioning in Nested Block Joins

      Disclosed is an algorithm for optimally partitioning the
buffer in a multiple relation nested block join.  Nested block join
(1) is a generalization (to blocks) of the traditional nested loop
algorithm.  The speed of a nested block join depends heavily upon the
way in which the buffer is partitioned among the various relations
participating in the join.

      Suppose there are R relations, and a total buffer size of B + 1
pages.  Suppose relation i consists of pi pages. Let xi denote the
number of buffer pages allocated to relation i.  Relation 1 will be
the outermost relation, and so on, through relation R, the innermost
relation.  Assign xR = 1, which can easily be shown to be the optimal
choice. This leaves B buffer pages to be allocated among R-1
relations.  The total number of I/Os is given by the formula

                            (Image Omitted)

(Here,  a denotes the ceiling function evaluated at a.) The goal is
to minimize this objective function subject to the constraint that

      Nominally, one ought to decide first on the ordering of the
relations, i.e., which relation is best to be innermost, and so on,
through to outermost.  However, note that for any fixed set {xi} of
decision variables, the value of the objective function is minimal
when p1&...&pR .  Thus assume, without loss of generality, that the
relations are arranged in order of increasing size.

      To solve this optimization problem (P), start with an exact
solution to an approxim...