Join Problem Generator Refresh for new problem

This page generates simple (in terms of setup and assumptions) 4-way join optimization problems. Given the statistics and tables below, compute the join plan based on Selinger as discussed in class, the result cardinality, as well as the cost in terms of the number of pages that must be read.

  1. The fanout is the same as the number of directory entries
  2. Restricted to the join options in the table on the right
  3. Joins are on the same attribute
  4. Join attr is a key in each table
  5. All tuples are the same size
  6. Indices are all on this attribute.
  7. Joins are not key-foreign key joins
  8. There's no cache, so each page must be accessed from disk.
Join Name Description
Hash-INL Index nested loops using Hash Index
Primary-BTree-INL Index nested loops using Primary BTree
Sec-BTree-INL Index nested loops using Secondary BTree
NL Nested loops
HashJoin Hash Join
Designed for the simplified query optimization lectures in Columbia's W4111 Introduction to Databases