Manhattan life

Join methods

The optimizer can choose one of three basic join strategies when queries require tables to be joined.

• Nested-loop join
• Merge join
• Hash join

These methods are described in the following sections.

Nested-Loop Join

A nested-loop join is performed in one of the following two ways:

• Scanning the inner table for each accessed row of the outer table

  For example, consider that column A in tables T1 and T2 have the following values:

  Outer table T1: column A	Inner table T2: column A
  2	3
  3	2
  3	2
  	3
  	1

  To perform a nested-loop join, the database manager performs the following steps:

  1. Read the first row from T1. The value for A is "2"
  2. Scan T2 until a match ("2") is found, and then join the two rows
  3. Scan T2 until the next match ("2") is found, and then join the two rows
  4. Scan T2 to the end of the table
  5. Go back to T1 and read the next row ("3")
  6. Scan T2, starting at the first row, until a match ("3") is found, and then join the two rows
  7. Scan T2 until the next match ("3") is found, and then join the two rows
  8. Scan T2 to the end of the table
  9. Go back to T1 and read the next row ("3")
  10. Scan T2 as before, joining all rows which match ("3").
• Performing an index lookup on the inner table for each accessed row of the outer table

  This method can be used for the specified predicates if there is a predicate of the following form:

     expr(outer_table.column)  relop  inner_table.column 

  where relop is a relative operator (for example =, >, >=, <, or <=) and expr is a valid expression on the outer table. Consider the following examples:

     OUTER.C1 + OUTER.C2 <= INNER.C1 

     OUTER.C4 < INNER.C3 

  This method might significantly reduce the number of rows accessed in the inner table for each access of the outer table, although it depends on a number of factors, including the selectivity of the join predicate.

When it evaluates a nested loop join, the optimizer also decides whether to sort the outer table before performing the join. If it orders the outer table, based on the join columns, the number of read operations to access pages from disk for the inner table might be reduced, because they are more likely to be be in the buffer pool already. If the join uses a highly clustered index to access the inner table and if the outer table has been sorted, the number of index pages accessed might be minimized.

In addition, if the optimizer expects that the join will make a later sort more expensive, it might also choose to perform the sort before the join. A later sort might be required to support a GROUP BY, DISTINCT, ORDER BY or merge join.

Merge Join

Merge join, sometimes known as merge scan join or sort merge join, requires a predicate of the form table1.column = table2.column. This is called an equality join predicate. Merge join requires ordered input on the joining columns, either through index access or by sorting. A merge join cannot be used if the join column is a LONG field column or a large object (LOB) column.

In a merge join, the joined tables are scanned at the same time. The outer table of the merge join is scanned only once. The inner table is also scanned once unless repeated values occur in the outer table. If there are repeated values occur, a group of rows in the inner table might be scanned again. For example, if column A in tables T1 and T2 has the following values:

To perform a merge join, the database manager performs the following steps:

1. Read the first row from T1. The value for A is "2".
2. Scan T2 until a match is found, and then join the two rows.
3. Keep scanning T2 while the columns match, joining rows.
4. When the "3" in T2 is read, go back to T1 and read the next row.
5. The next value in T1 is "3", which matches T2, so join the rows.
6. Keep scanning T2 while the columns match, joining rows.
7. The end of T2 is reached.
8. Go back to T1 to get the next row -- note that the next value in T1 is the same as the previous value from T1, so T2 is scanned again starting at the first "3" in T2. The database manager remembers this position.

Hash Join

A hash join requires one or more predicates of the form table1.columnX = table2.columnY, for which the column types are the same. For columns of type CHAR, the length must be the same. For columns of type DECIMAL, the precision and scale must be the same. The column type cannot be a LONG field column, or a large object (LOB) column.

First, the designated INNER table is scanned and the rows copied into memory buffers drawn from the sort heap specified by the sortheap database configuration parameter. The memory buffers are divided into partitions based on a hash value that is computed on the columns of the join predicates. If the size of the INNER table exceeds the available sort heap space, buffers from selected partitions are written to temporary tables.

When the inner table has been processed, the second, or OUTER, table is scanned and its rows are matched to rows from the INNER table by first comparing the hash value computed for the columns of the join predicates. If the hash value for the OUTER row column matches the hash value of the INNER row column, the actual join predicate column values are compared.

OUTER table rows that correspond to partitions not written to a temporary table are matched immediately with INNER table rows in memory. If the corresponding INNER table partition was written to a temporary table, the OUTER row is also written to a temporary table. Finally, matching pairs of partitions from temporary tables are read, and the hash values of their rows are matched, and the join predicates are checked.

For the full performance benefits of hash join, you might need to change the value of the sortheap database configuration parameter and the sheapthres database manager configuration parameter.

For the full performance benefits of hash joins, you might need to change the value of the sortheap database configuration parameter and the sheapthres database manager configuration parameter.

Hash-join performance is best if you can avoid hash loops and overflow to disk. To tune hash-join performance, estimate the maximum amount of memory available for sheapthres, then tune the sortheap parameter. Increase its setting until you avoid as many hash loops and disk overflows as possible, but do not reach the limit specified by the sheapthres parameter.

Increasing the sortheap value should also improve performance of queries that have multiple sorts.

The query optimizer cannot be accessed directly by users. Instead, once queries are submitted to database server, and parsed by the parser, they are then passed to the query optimizer where optimization occurs.

Implementation

Much work in database-systems has aimed at efficient implementation of joins, because relational systems commonly call for joins, yet face difficulties in optimising their efficient execution. The problem arises because (inner) joins operate both commutatively and associatively. In practice, this means that the user merely supplies the list of tables for joining and the join conditions to use, and the database system has the task of determining the most efficient way to perform the operation. A query optimizer determines how to execute a query containing joins. A query optimizer has two basic freedoms:

1. Join order: Because joins function commutatively, the order in which the system joins tables does not change the final result-set of the query. However, join-order does have an enormous impact on the cost of the join operation, so choosing the best join order becomes very important.
2. Join method: Given two tables and a join condition, multiple algorithms can produce the result-set of the join. Which algorithm runs most efficiently depends on the sizes of the input tables, the number of rows from each table that match the join condition, and the operations required by the rest of the query.

Many join-algorithms treat their inputs differently. One can refer to the inputs to a join as the "outer" and "inner" join operands, or "left" and "right", respectively. In the case of nested loops, for example, the database system will scan the entire inner relation for each row of the outer relation.

One can classify query-plans involving joins as follows:

left-deep 

using a base table (rather than another join) as the inner operand of each join in the plan

right-deep 

using a base table as the outer operand of each join in the plan

bushy 

neither left-deep nor right-deep; both inputs to a join may themselves result from joins

These names derive from the appearance of the query plan if drawn as a tree, with the outer join relation on the left and the inner relation on the right (as convention dictates).

Join algorithms

Three fundamental algorithms exist for performing a join operation.

Nested loops

Use of nested loops produces the simplest join-algorithm. For each tuple in the outer join relation, the system scans the entire inner-join relation and appends any tuples that match the join-condition to the result set. Naturally, this algorithm performs poorly with large join-relations: inner or outer or both. An index on columns in the inner relation in the join-predicate can enhance performance.

The "block nested loops" (BNL) approach offers a refinement to this technique: for every block in the outer relation, the system scans the entire inner relation. For each match between the current inner tuple and one of the tuples in the current block of the outer relation, the system adds a tuple to the join result-set. This variant means doing more computation for each tuple of the inner relation, but far fewer scans of the inner relation.

Merge join

If both join relations come in order, sorted by the join attribute(s), the system can perform the join trivially, thus:

1. Consider the current "group" of tuples from the inner relation; a group consists of a set of contiguous tuples in the inner relation with the same value in the join attribute.
2. For each matching tuple in the current inner group, add a tuple to the join result. Once the inner group has been exhausted, advance both the inner and outer scans to the next group.

Merge joins offer one reason why many optimizers keep track of the sort order produced by query plan operators—if one or both input relations to a merge join arrives already sorted on the join attribute, the system need not perform an additional sort. Otherwise, the DBMS will need to perform the sort, usually using an external sort to avoid consuming too much memory.

See also: Sort-Merge Join

Hash join

Main article: Hash join

A hash join algorithm can produce equi-joins. The database system pre-forms access to the tables concerned by building hash tables on the join-attributes. The lookup in hash tables operates much faster than through index trees. However, one can compare hashed values only for equality, not for other relationships.

Sample tables

All subsequent explanations on join types in this article make use of the following two tables. The rows in these tables serve to illustrate the effect of different types of joins and join-predicates. In the following tables, department.departmentID is the primary key, while employee.DepartmentID is a foreign key.

Note: The "Marketing" Department currently has no listed employees. On the other hand, the employee "Jasper" has no link to any currently valid Department in the Department Table.

Inner join

An inner join does require each record in the two joined tables to have a matching record. An inner join essentially combines the records from two tables (A and B) based on a given join-predicate. The SQL-engine computes the Cartesian product of all records in the tables. Thus, processing combines each record in table A with every record in table B. Only those records in the joined table that satisfy the join predicate remain. This type of join occurs most commonly in applications, and represents the default join-type.

SQL:2003 specifies two different syntactical ways to express joins. The first, called "explicit join notation", uses the keyword JOIN, whereas the second uses the "implicit join notation". The implicit join notation lists the tables for joining in the FROM clause of a SELECT statement, using commas to separate them. Thus, it always computes a cross-join, and the WHERE clause may apply additional filter-predicates. Those filter-predicates function comparably to join-predicates in the explicit notation.

One can further classify inner joins as equi-joins, as natural joins, or as cross-joins.

Programmers should take special care when joining tables on columns that can contain NULL values, since NULL will never match any other value (or even NULL itself), unless the join condition explicitly uses the IS NULL or IS NOT NULL predicates.

As an example, the following query takes all the records from the Employee table and finds the matching record(s) in the Department table, based on the join predicate. The join predicate compares the values in the DepartmentID column in both tables. If it finds no match (i.e., the department-id of an employee does not match the current department-id from the Department table), then the joined record remains outside the joined table, i.e., outside the (intermediate) result of the join.

Example of an explicit inner join:

SELECT *
FROM   employee 
       INNER JOIN department 
          ON employee.DepartmentID = department.DepartmentID

Example of an implicit inner join:

SELECT *  
FROM   employee, department 
WHERE  employee.DepartmentID = department.DepartmentID

Explicit Inner join result:

Types of inner joins

Equi-join

An equi-join, also known as an equijoin, is a specific type of comparator-based join, or theta join, that uses only equality comparisons in the join-predicate. Using other comparison operators (such as <) disqualifies a join as an equi-join. The query shown above has already provided an example of an equi-join:

SELECT *
FROM   employee 
       INNER JOIN department 
          ON employee.DepartmentID = department.DepartmentID

The resulting joined table contains two columns named DepartmentID, one from table Employee and one from table Department

SQL:2003 does not have a specific syntax to express equi-joins, but some database engines provide a shorthand syntax: for example, MySQL and PostgreSQL support USING(DepartmentID) in addition to the ON ... syntax.

A natural join offers a further specialization of equi-joins. The join predicate arises implicitly by comparing all columns in both tables that have the same column-name in the joined tables. The resulting joined table contains only one column for each pair of equally-named columns.

The above sample query for inner joins can be expressed as a natural join in the following way:

SELECT *
FROM   employee NATURAL JOIN department

The result appears slightly different, however, because only one DepartmentID column occurs in the joined table.

Using the NATURAL JOIN keyword to express joins can suffer from ambiguity at best, and leaves systems open to problems if schema changes occur in the database. For example, the removal, addition, or renaming of columns changes the semantics of a natural join. Thus, the safer approach involves explicitly coding the join-condition using a regular inner join.

The Oracle database implementation of SQL selects the appropriate column in the naturally-joined table from which to gather data. An error-message such as "ORA-25155: column used in NATURAL join cannot have qualifier" may encourage checking and precisely specifying the columns named in the query.

Cross join

A cross join, cartesian join or product provides the foundation upon which all types of inner joins operate. A cross join returns the cartesian product of the sets of records from the two joined tables. Thus, it equates to an inner join where the join-condition always evaluates to True or join-condition is absent in statement.

If A and B are two sets, then cross join = A × B.

The SQL code for a cross join lists the tables for joining (FROM), but does not include any filtering join-predicate.

Example of an explicit cross join:

SELECT *
FROM   employee CROSS JOIN department

Example of an implicit cross join:

SELECT *
FROM   employee, department;

The cross join does not apply any predicate to filter records from the joined table. Programmers can further filter the results of a cross join by using a WHERE clause.

[Quote]:http://72.14.235.104/search?q=cache:0TSYT7pUFioJ:en.wikipedia.org/wiki/Join_(SQL)+inner+join&hl=ja&ct=clnk&cd=6&gl=jp&client=firefox-a