simpledb.materialize
Class MergeJoinPlan

java.lang.Object
  simpledb.materialize.MergeJoinPlan

All Implemented Interfaces:

Plan

public class MergeJoinPlan
extends java.lang.Object
implements Plan

The Plan class for the mergejoin operator.

Author:

Edward Sciore

Constructor Summary

MergeJoinPlan(Plan p1, Plan p2, java.lang.String fldname1, java.lang.String fldname2, Transaction tx)
Creates a mergejoin plan for the two specified queries.

Method Summary

int	blocksAccessed() Returns the number of block acceses required to mergejoin the sorted tables.
int	distinctValues(java.lang.String fldname) Estimates the distinct number of field values in the join.
Scan	open() The method first sorts its two underlying scans on their join field.
int	recordsOutput() Returns the number of records in the join.
Schema	schema() Returns the schema of the join, which is the union of the schemas of the underlying queries.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MergeJoinPlan

public MergeJoinPlan(Plan p1,
                     Plan p2,
                     java.lang.String fldname1,
                     java.lang.String fldname2,
                     Transaction tx)

Creates a mergejoin plan for the two specified queries. The RHS must be materialized after it is sorted, in order to deal with possible duplicates.

Parameters:

p1 - the LHS query plan

p2 - the RHS query plan

fldname1 - the LHS join field

fldname2 - the RHS join field

tx - the calling transaction

Method Detail

open

public Scan open()

The method first sorts its two underlying scans on their join field. It then returns a mergejoin scan of the two sorted table scans.

Specified by:

open in interface Plan

Returns:

a scan

See Also:

Plan.open()

blocksAccessed

public int blocksAccessed()

Returns the number of block acceses required to mergejoin the sorted tables. Since a mergejoin can be preformed with a single pass through each table, the method returns the sum of the block accesses of the materialized sorted tables. It does not include the one-time cost of materializing and sorting the records.

Specified by:

blocksAccessed in interface Plan

Returns:

the estimated number of block accesses

See Also:

Plan.blocksAccessed()

recordsOutput

public int recordsOutput()

Returns the number of records in the join. Assuming uniform distribution, the formula is:

 R(join(p1,p2)) = R(p1)*R(p2)/max{V(p1,F1),V(p2,F2)}

Specified by:

recordsOutput in interface Plan

Returns:

the estimated number of output records

See Also:

Plan.recordsOutput()

distinctValues

public int distinctValues(java.lang.String fldname)

Estimates the distinct number of field values in the join. Since the join does not increase or decrease field values, the estimate is the same as in the appropriate underlying query.

Specified by:

distinctValues in interface Plan

Parameters:

fldname - the name of a field

Returns:

the estimated number of distinct field values in the output

See Also:

Plan.distinctValues(java.lang.String)

schema

public Schema schema()

Returns the schema of the join, which is the union of the schemas of the underlying queries.

Specified by:

schema in interface Plan

Returns:

the query's schema

See Also:

Plan.schema()