Nested Loop Join

Description

A nested loop join is the simplest join method, which is implemented in all relational database systems. It compares the data in two tables to check whether the join conditions are met.

In GaussDB, a nested loop join scans the inner table for each row in the outer table searching for rows that meet the join conditions. This is similar to two nested loops. The outer loop traverses the outer table, and the inner loop traverses the inner table.

The time complexity of a nested loop join is O(n x m), where n and m indicate the numbers of rows in the two tables. If the inner table can be scanned by using indexes, the time complexity can be reduced to O(n log m).

Typical Scenarios

• Any of the inner or outer table is very small.
• An inner table quickly locates the row that meets the condition (for example, an index has been created for the join column of the inner table) based on the join condition.
• A nested loop join can be executed under any join conditions if it has no restrictions.

Examples

Example: Join two small tables.

-- Prepare data.
gaussdb=# CREATE TABLE employee(id int, deptid int); 
CREATE TABLE 
gaussdb=# INSERT INTO employee VALUES(1, 1), (2,1),(3,2),(4, 1), (5,2); 
INSERT 0 5 
gaussdb=# CREATE TABLE manager(id int, deptid int); 
CREATE TABLE 
gaussdb=# INSERT INTO manager VALUES(1,1), (2,2),(3,1),(4,2); 
INSERT 0 4

-- Execution result.
gaussdb=# EXPLAIN SELECT * FROM employee e JOIN manager m ON e.deptid < m.deptid; 
                               QUERY PLAN                                 
------------------------------------------------------------------------- 
 Nested Loop  (cost=0.00..69341.37 rows=1539400 width=16) 
   Join Filter: (e.deptid < m.deptid) 
   ->  Seq Scan on employee e  (cost=0.00..31.49 rows=2149 width=8) 
   ->  Materialize  (cost=0.00..42.23 rows=2149 width=8) 
         ->  Seq Scan on manager m  (cost=0.00..31.49 rows=2149 width=8) 
(5 rows)

-- Drop.
gaussdb=# DROP TABLE employee,manager;

In the preceding example, the output of nested loop join is as follows.