PERFORMING EFFICIENT JOIN OPERATIONS ON LARGE TABLES

摘要

A technique for efficiently joining multiple large tables in a database system with a processor using a small main memory. The technique utilizes a join index (103 and 303) and minimizes the number of Input/Output operations while maximizing the use of the small main memory through a buffer allocation process (111 and 901). Three embodiments are described which all use a parallel-merge operation. The first technique, a slam-join, joins two tables without a pre-allocation of buffers as buffers (111 and 112) are used latter in the process. The second technique, multi-slam-join, joins three or more tables adding a merge technique which prepartitions memory. The third technique, parallel-join, processes each input table completely independently. The parallel-merge technique identifies the lowest value from multiple files and orders all values from lowest to highest. This enables sequential reading of the input files saving I/O operations.