Optimizing Selections
Union Find
We used a union-find data structure to implement selection pushing. We use the visitor pattern to read the join condition and transitively invoke the equality and inequality conditions on attributes, which can be found here. Each attribute is mapped to a union-find element in the union-find data structure. This contains logic that performs interval arithmetic with conditions to make the selection filter our more unnecessary data. With this, we could write a new condition that makes selection much easier. This removed the need for a separate join visitor.
Selection Implementation
Based on the selectivity of the conditions and indexing costs, we chose to either use index or normal scanning. This means we no longer need to tell our DBMS through I/O which type of scan to use.
Optimizing Joins
Join Order
We used dynamic programming figure out the join costs for all possible subsets of tables, as well as the optimal join order for that given subset. For subsets that are 1 larger, we simply add the cost of the current subset and the cost of adding the current table. This information was populated into a table, where each entry contains the best join order, its associated cost, the size of the join (including the root), and the V-Values for each attribute in the join. Now, we leverage our union-find to extract sets of equal attributes.
Join Type
This was a relatively simple change. If the join condition was an equi-join, we used Sort-Merge Join. Otherwise, we used Block-Nested Loop Join. We removed in-memory sort, and we are exclusively using external sort. Also, we removed Tuple-Nested Loop Join.
Other
Printing Query Plans
We gave all operators a toString() function, so we could easily output which operations we are using for our query plan.
Removing Benchmarking
Because we are no longer comparing independent variables in this project milestone, we removed all benchmarking-related files. ad27f1b
Package Reorganization
We created a new package for our classes that handle optimizing the query plan. The old visitors package has been removed. ad27f1b