This is a database gradually developed by a team of three in the course CS 4321 Practicum in Database Systems. The database here is able to build B+ indexes, evaluate SELECT SQL queries, read in tables, and output matching tuples.
The top level class, i.e., the interpreter/harness that reads the input and produces output, is /src/database/DatabaseCatalog.java. It first collects table statistics including schemas, and minimum and maximum values of each column, and builds static B+ tree indices based on the index configuration file. Then, for each query, it parses the query using JSqlParser, and writes out the logical plan, the physical plans, and the actual matching tuples. The difference between a logical plan and a physical plan is that only physical plan knows which specific operator to use. Take the Join operator as an example, we only know that we need perform a join (Logical Join) when building the logical operator tree. The specific choice of join, i.e., either a tuple nested loop join, a block nested loop join, or a sort merge join, will be decided when building the physical operator tree.
Building two operator trees allow us to optimize query evaluations. After building the logical operator tree using /src/logicalOperator/LogicalPlanBuilder.java, the /src/physicalOperator/PhysicalPlanBuilder.java will recursively visit each tree node and build the specific physical plan tree. For LogicalSelectOperator, the plan builder will choose to use IndexScanOperator or Full Table ScanOperator based on indexes. For LogicalJoinOperator, the plan builder will choose to use TNLJ, BNLJ or SMJ, and the order of joins, based on the cost of each join method/order. Union-Find data structure is implemented here to group table columns with the same numeric constraints, including equality, minimum and maximum and to push the constraints up to the plan tree.
####Known bug We didn’t fully implement visit(LogicalJoin), i.e., the part where chooses specific join operators and table join orders.