oceanbase/miniob

Features

• Relational Data Storage - Manages on-disk relational data storage using pages, buffers, and file organization.
• Educational Database Systems - An open-source relational database kernel designed for learning database internals.
• Concurrent Read-Write Transactions - Coordinates concurrent read and write operations to maintain ACID properties.
• Atomic Transaction Coordinators - Coordinates concurrent transactions with isolation and atomicity guarantees using a transactional storage layer.
• Data Persistence and Storage - Manages persistent data storage and retrieval through a dedicated storage engine.
• Record-Level Indexes - Build and maintain index structures to accelerate record retrieval by key values.
• Transactional Row Storages - Persists rows to disk and reads them back while preserving atomicity and isolation for each operation.
• Commit Order Dependencies - Coordinate transaction commit order by tracking which transactions must commit before others to prevent deadlocks.
• Relational Database Metadata Inspectors - Stores and retrieves metadata about databases, tables, fields, and indexes for schema operations.
• Page-Based Storage - Organizes index data into fixed-size pages stored in external files for B+ tree nodes.
• Scan Method Selections - Pick between full table scan and index scan based on relation size, selectivity, and available indexes to minimize data access cost.
• Grouped Aggregations - Group rows by specified columns and compute aggregate functions per group using a hash-based approach.
• Hash Join Implementations - Combine rows from two tables by building a hash table on one table and probing it with rows from the other.
• Join Operator Selection - Select the lowest-cost join algorithm by comparing estimated costs of Nested Loop Join and Hash Join.
• Join Order Selections - Evaluate alternative join sequences using cost estimates or heuristic rules to select the most efficient plan.
• Level-Based Compaction Strategies - Implements level-based compaction to merge overlapping sorted runs and bound read amplification.
• Multi-Version Concurrency Control - Controls transaction commit, rollback, and isolation using multi-version concurrency control.
• MySQL Wire Protocol Servers - Communicates with clients using the standard MySQL wire protocol.
• Fixed-Size Page Organizations - Divides database files into fixed-size pages and tracks which pages store data, free space, and contents.
• Buffer Pool Page Evictions - Manages disk page loading into a fixed-size memory pool with eviction for efficient access.
• Predicate Pushdown - Move filter conditions from the WHERE clause closer to the table scan to reduce rows processed early.
• Query Aggregates - Compute aggregate functions like sum over all rows without grouping and process data in chunks for efficiency.
• Query Plan Optimizations - Rewrites query syntax trees using rules and statistics to produce faster execution plans.
• Query Plan Execution Engines - Parse SQL statements into a query plan and run it through a custom execution engine to produce results.
• Result Sorting - Order the result set by specified columns in ascending or descending order using the ORDER BY clause.
• Identifier Semantic Resolution - Translate table and field names in the syntax tree into pointers that point to actual in-memory metadata objects.
• Arithmetic Expression Parsers - Parse arithmetic expressions with operator precedence, parentheses, and unary negation from SQL text into an abstract syntax tree.
• SQL Query Optimizations - Rewrite and adjust the query syntax tree using rules and statistics to improve execution efficiency.
• SQL Statement Parsing - Parse SQL statements into an internal representation for further processing and execution.
• Per-Table File Group Storages - Persists each table as a set of files for metadata, data records, and indexes inside a database folder.
• B+ Tree Indexing - Implements B+ tree index entry insertion with node splitting and upward propagation.
• B+ Tree Index Entry Deletions - Removes key-value pairs from a B+ tree and borrows from or merges with sibling nodes when underfull.
• Dual Storage Engines - Stores relational data using either a balanced B+ Tree for indexed lookups or a log-structured merge-tree for write-optimized batch operations.
• Node Locking Mechanisms - Acquire read or write locks on tree nodes during traversal and release parent locks when child nodes are safe.
• Range Scans - Walks leaf nodes of a B+ tree to retrieve all records whose keys fall within a specified interval.
• Dual-Engine Storage Systems - Implements a dual-engine storage architecture combining B+ Tree and LSM-Tree.
• LSM-Tree Key-Value Stores - A write-optimized storage engine organizing data in sorted runs with leveled compaction.
• Subquery Flattenings - Rewrite nested subqueries as equivalent multi-table join operations to eliminate repeated execution and enable better access paths.
• Isolation Level Management - Supports serializable, repeatable read, snapshot isolation, and read committed levels for transaction visibility.
• Checkpoint-Based Recovery Logs - Creates periodic checkpoints to bound the log range needed for crash recovery.
• Vector Storage - Stores high-dimensional vectors as a native column type with configurable dimensionality.
• Write-Ahead Logging - Records before and after images of modifications to a log before flushing data pages to disk.
• Checkpoint-Based Recovery Systems - Combines write-ahead logging with periodic checkpoints for crash recovery.
• Interactive Command Line Interfaces - Read commands from standard input, send them to the server, and display the returned results.
• Database Crash Recovery - Restores database consistency after failure using write-ahead logging and checkpoints.
• Text SQL Executions - Accept plain-text SQL statements from authenticated clients and return results as OK, error, or result-set packets.
• Relational Database Tutorials - A hands-on project for learning relational database internals by building a SQL engine.
• Operation Logs - Records operation logs to support database recovery and durability.
• Database Connection Acceptances - Accept TCP or Unix socket connections and dispatch requests to a thread model for processing.
• Database Page Caching - Keep frequently accessed disk pages in a memory region using a page table with dirty flags and reference counts.
• Slotted Page Storage Layouts - Arranges variable-length records inside pages using a slot array that grows from the front while data grows from the back.
• Expression Type Hierarchies - Model SQL expressions as a class hierarchy covering fields, constants, comparisons, functions, and subqueries.
• Concurrency Locking - Implements shared and exclusive locks on data items to coordinate concurrent transaction access.
• Transaction Deadlock Resolution - Detects circular wait conditions in transaction lock graphs and aborts transactions to resolve deadlocks.
• Volcano Query Processors - Processes SQL queries by pulling tuples one at a time through a tree of physical operators, enabling modular plan execution.
• Buffer Pool Frame Managers - Manages disk page loading into memory frames with pin counting and lock tracking.
• Database Test Case Executors - Execute a suite of SQL test cases against the database kernel and report pass or fail results for each case.
• Corrupted Page Recovery Mechanisms - Restores partially written database pages from saved copies during crash recovery.
• Database Internals - Shares internal technical notes and paper reviews to help developers understand database internals.
• Fixed-Length Record Storage - Structures fixed-length records within pages using bitmaps for slot tracking.
• Shared Table Scans - Attach multiple queries to a single table scan cursor so they reuse data already read from disk.
• Static Hashing - Maps keys to buckets via hash functions for record retrieval from pages.
• Heap Storage Engines - Stores records in unordered page collections with linked lists or page directories.
• In-Memory Block Caches - Store frequently accessed data blocks in memory to accelerate lookups from sorted string table files.
• Top-K Vector Similarity Retrievals - Retrieve the top-K most similar vectors by combining a distance function with ORDER BY and LIMIT clauses.
• Output Comparison Validators - Run the same SQL statements on both MiniOB and MySQL and compare their outputs to detect discrepancies.
• PAX Storage Layouts - Implements PAX hybrid storage layout that partitions attributes vertically within each database page.
• Page Prefetching - Load pages into the buffer pool ahead of query execution to reduce wait time during sequential scans.
• Aggregate Push-Ups - Move aggregate computation from a subquery into the outer query so the aggregation is calculated only once.
• IVF-Flat Indexes - Accelerates nearest-neighbor search by clustering high-dimensional vectors and probing only the most relevant clusters during query time.
• Custom SQL Statement Extensions - Adds new SQL statement types by defining lexer tokens, parser rules, AST nodes, and execution operators.
• Concurrent Tree Mutations - Run multi-threaded insert, delete, query, and scan workloads under Google Benchmark to verify concurrency correctness.
• Subquery Merging Optimizations - Combine several semantically equivalent subqueries into a single one to reduce redundant table scans and join operations.
• Vector Database Extensions - Extends the relational database with vector storage, distance functions, and nearest neighbor search.
• Vector Arithmetic - Supports element-wise vector addition, subtraction, and multiplication in SQL queries.
• SIMD-Accelerated Arithmetic - Uses single-instruction-multiple-data instructions to speed up arithmetic, aggregation, and hash-table operations on vectorized data chunks.
• Batch Processing Accelerators - Use single-instruction-multiple-data instructions to speed up arithmetic, aggregation, and hash-table lookups on vectorized data.
• Relational Algebra Rewritings - Transform a relational algebra expression into an equivalent form that reduces intermediate result sizes and improves efficiency.
• SQL Vector Distance Functions - Calculate L2, cosine, or inner-product distance between two vectors using built-in SQL functions.
• Sequential Scan Buffer Pool Bypasses - Read large sequential page runs directly into local query memory instead of the shared buffer pool.
• Dedicated Connection Threads - Assign each client connection its own thread that listens for messages, processes SQL, and sends responses.
• Server Thread Pools - Selects between one-thread-per-connection and a shared thread pool at startup via a command-line argument.
• Shared Connection Thread Pools - Route all client connections through a single thread pool that listens for messages and dispatches tasks to worker threads.
• Custom - Define new test scenarios by writing Python code that groups DDL, DML, and DQL instructions with dependency ordering.
• Databases and Analytics - Compact database for learning database internals.
• C Plus Plus - Listed in the “C Plus Plus” section of the Awesome For Beginners awesome list.

Star history