Join (⋈) is the primary means of combining information.

Join is important and potentially expensive

Most common join condition: equijoin, e.g. (R.pk = S.fk)

Join varieties (natural, inner, outer, semi, anti) all behave similarly.

We consider three strategies for implementing join

• nested loop ... simple, widely applicable, inefficient without buffering
• sort-merge ... works best if tables are soted on join attributes
• hash-based ... requires good hash function and sufficient buffering