DOCSEARCHbyAlgolia
Submit Docs

MIT 6.830/6.814 SimpleDB Labs

repository·master·Indexed 43 days ago

https://github.com/mit-db-class/simple-db-hw-2021

Distribution point and documentation for the MIT 6.830/6.814 SimpleDB labs. Includes instructions for environment setup using Git, building and testing with Apache Ant, and implementation guidelines for Lab 1, covering the BufferPool, Catalog, HeapFile, and SeqScan operator.

Tokens
12.8K
Snippets
33
Records
72
Agent score
56%

What's inside SimpleDB

  1. Overview of Lab 5: B+ Tree Index

    master

    In this lab, you are tasked with implementing a B+ tree index to enable efficient lookups and range scans. The project provides low-level infrastructure for the tree structure, while you are responsible for implementing the core logic:

    • Searching: Locating keys within the tree.
    • Splitting Pages: Handling node overflows during insertion.
    • Redistributing Tuples: Moving data between pages to maintain balance.
    • Merging Pages: Handling underflows during deletion.

    B+ Tree Structure Details

    • Internal Nodes: Contain multiple entries consisting of a key value and left/right child pointers. An internal node with m keys will have m+1 child pointers.
    • Leaf Nodes: In this implementation, leaf pages contain the actual data entries.
    • Sibling Pointers: Adjacent leaf pages are linked via left and right sibling pointers, allowing range scans to proceed by following these pointers after the initial search finds the starting leaf.

  2. How the SimpleDB Optimizer works

    master

    The SimpleDB optimizer follows a specific control flow to transform queries into executable plans:

    1. Initialization: Parser.java constructs table statistics and stores them in a statsMap.
    2. Parsing: When a query is input, Parser.java calls parseQuery.
    3. Logical Planning: parseQuery constructs a LogicalPlan representing the query.
    4. Physical Planning: parseQuery then calls physicalPlan on the LogicalPlan instance. This method returns a DBIterator object used to execute the query.

    As a developer, you are responsible for implementing the logic within physicalPlan to devise an optimal plan based on the statistics provided.

  3. Implementation guidelines for Lab 1

    master

    When implementing Lab 1, follow these guidelines:

    1. Completing Code: You must fill in all unimplemented code. You may add private methods or helper classes. You may change APIs, but ensure grading tests still run and explain your decisions in your writeup.
    2. Unimplemented Methods: Many methods in the provided interfaces are not required for Lab 1 (e.g., Insert.dbIterator() or certain deleteTuple logic). The code you submit must compile even if these methods are left as stubs.
    3. Transactions and Locking: While you do not need to implement transactions, locking, or recovery in this lab, you must preserve the transaction ID parameters in the interfaces. Pass the fake transaction ID provided by the test code through your operators and into the buffer pool.

  4. Estimate Plan Cost using Scans and Joins

    master

    In this implementation, costs are focused on sequences of joins and base table accesses using left-deep plans.

    Overall Plan Cost

    For a left-deep join plan p = t1 join t2 join ... tn, the cost is calculated as the sum of scan costs and join costs: scancost(t1) + scancost(t2) + joincost(t1 join t2) + scancost(t3) + joincost((t1 join t2) join t3) + ...

    Note: scancost(t1) is defined as number of pages in t1 * SCALING_FACTOR (assuming no caching).

    Join Cost (Nested Loops)

    The cost of joining t1 (outer) to t2 (inner) is: joincost(t1 join t2) = scancost(t1) + (ntups(t1) * scancost(t2)) + (ntups(t1) * ntups(t2))

    Where ntups(t) is the number of tuples in table t.

  5. Understand the SimpleDB Architecture

    master

    SimpleDB is a database system composed of several key components that you will implement or interact with:

    • Fields and Tuples: Field is an interface for data types (e.g., integer, string). Tuple objects contain a collection of Field objects and are described by a TupleDesc (tuple descriptor) which contains a collection of Type objects.
    • Catalog: The Catalog class maintains a list of all tables and their schemas (TupleDesc) currently in the database.
    • BufferPool: The BufferPool caches database pages in memory. It manages a fixed number of pages defined by numPages.
    • Access Methods (HeapFile): These provide a way to read/write data from disk. A HeapFile organizes tuples into pages, where each page has a header (a bitmap indicating which slots are valid) and a set of slots for tuples.
    • Operators: These implement relational algebra (e.g., SeqScan, select, join) by implementing the DbIterator interface. Operators are chained together to form a query plan.
    • Database Class: Provides global access to the Catalog, BufferPool, and log file via static methods.

  6. Implement BufferPool management

    master

    In Lab 2, you must extend the BufferPool to handle memory constraints and data persistence. You are required to implement:

    1. Tuple Insertion and Deletion: Methods to modify pages on disk.
    2. Page Eviction: A policy to flush stale pages from the buffer pool when the number of referenced pages exceeds the available memory.

    Note: You do not need to implement transactions or locking for this lab.

  7. Understand B+ Tree page types in BTreeFile

    master

    The BTreeFile implementation relies on several specialized page types. You will primarily interact with these classes to implement the B+ Tree logic:

    • BTreePage.java: An abstract class containing common code for both leaf and internal pages.
    • BTreeInternalPage.java: Implements internal nodes of the tree.
    • BTreeLeafPage.java: Implements leaf nodes of the tree.
    • BTreeHeaderPage.java: Tracks which pages in the file are currently in use.
    • BTreeRootPtrPage.java: A singleton page at the start of the file that points to the root page and the first header page.

  8. Detect and handle deadlocks

    master

    Deadlocks can occur when transactions are waiting for locks held by each other. You must implement a mechanism to detect or prevent deadlocks and respond by throwing a TransactionAbortedException.

    Implementation Options:

    • Cycle Detection (Recommended): Maintain a 'wait-for' dependency graph. Periodically or whenever a lock request is made, check for cycles in the graph. If a cycle is detected, abort a transaction to break the cycle.
    • Timeout Policy: A simpler (but less sophisticated) approach where a transaction is aborted if it has been waiting for a lock for too long.
    • Global Ordering (Prevention): Use schemes like WAIT-DIE or WOUND-WAIT to prevent cycles from forming based on transaction timestamps.

    Requirement: When a deadlock is detected, you must throw TransactionAbortedException. This allows the higher-level code to catch the error and call transactionComplete() for cleanup.

  9. B+ Tree invariants for debugging

    master

    When implementing the B+ Tree, ensure your code maintains these properties. You can use BTreeChecker.java to verify these invariants:

    1. Parent-Child Linkage: If a parent points to a child, the child must point back to that parent.
    2. Sibling Linkage: Leaf nodes must have bidirectional sibling pointers (left/right). The first and last leaves must point to null for their respective outer siblings.
    3. Record Integrity: Record IDs must match the page they reside in.
    4. Key Ordering (Internal): A key in an internal node must be larger than any key in the left child and smaller than any key in the right child.
    5. Key Ordering (Leaf): A key in an internal node must be $\ge$ any key in the left child and $\le$ any key in the right child.
    6. Homogeneity: A node must contain either all non-leaf children or all leaf children.
    7. Occupancy: A non-root node cannot be less than half full.

  10. Implement NO STEAL/FORCE buffer management policy

    master

    To simplify recovery and ensure ACID properties without log-based recovery, implement a NO STEAL/FORCE policy in the BufferPool:

    1. NO STEAL: Do not evict dirty (updated) pages from the buffer pool if they are locked by an uncommitted transaction.
      • Task: Modify evictPage in BufferPool. If the eviction policy selects a dirty page, you must find an alternative clean page to evict. If all pages in the buffer pool are dirty, throw a DbException.
    2. FORCE: On transaction commit, force all dirty pages associated with that transaction to disk (e.g., write them out).

    This policy ensures that you never need to undo work (because dirty pages are never stolen) or redo work (because updates are forced on commit).

  11. Implement Query Optimization components

    master

    The goal of this lab is to implement a query optimizer on top of SimpleDB, specifically focusing on selectivity estimation and cost-based optimization (e.g., a Selinger-style optimizer).

    A recommended implementation workflow includes:

    1. Statistics Estimation: Implement methods in the TableStats class to estimate filter selectivities and scan costs. You can use histograms (a skeleton for IntHistogram is provided) or other statistical methods.
    2. Join Estimation: Implement methods in the JoinOptimizer class to estimate the cost and selectivities of joins.
    3. Join Ordering: Implement the orderJoins method in the JoinOptimizer class. This method should use the computed statistics to produce an optimal ordering for a series of joins (e.g., using the Selinger algorithm).

    Grading is based on passing the Ant targets test and systemtest.