features-implemented
Functions:
pub fn from_str(type_str: &str) -> Result<Self, String> // Parse type
pub fn validate_value(&self, value: &str) -> Result<(), String> // Validate value
pub fn serialize_value(&self, value: &str) -> Result<Vec<u8>, String> // Convert to bytes
pub fn deserialize_value(&self, bytes: &[u8]) -> Result<String, String> // Convert from bytes
2. Error Handling Module (src/backend/error_handler.rs)
- Custom Error Types: Handled natively mapping explicit contexts.
- Graceful Fault Reporting: Friendly guidance over panics/crashes.
- Path Checking Validation: Safety wrappers over filesystem operations, directory paths, and file availability checks.
Error Types:
FileNotFound: File or path doesn't existInvalidPath: Directory provided instead of fileInvalidDataType: Unsupported data type encounteredValidationError: Data doesn't match schemaDiskFull: Disk space or permission issues
Functions:
pub fn validate_file_path(path: &str) -> RookResult<()>
pub fn verify_csv_path(csv_path: &str) -> RookResult<()>
pub fn print_error_with_guidance(error: &RookDBError)
pub fn safe_read_file(path: &str) -> RookResult<String>
pub fn safe_write_file(path: &str, content: &str) -> RookResult<()>
3. Page API Abstraction Layer (src/backend/page_api.rs)
- Safe Page Operands:
get_lower,get_upper,set_lower,set_upper. - Page Meta Information Check:
get_tuple_count,get_free_space,can_fit_tuple. - Integrity Validation: Header validation checking layout overlapping or unbounded data frames recursively.
Functions:
pub fn get_lower(page: &Page) -> io::Result<u32> // Get lower pointer
pub fn get_upper(page: &Page) -> io::Result<u32> // Get upper pointer
pub fn set_lower(page: &mut Page, value: u32) -> io::Result<()> // Set lower safely
pub fn set_upper(page: &mut Page, value: u32) -> io::Result<()> // Set upper safely
pub fn get_tuple_count(page: &Page) -> io::Result<u32> // Count tuples
pub fn get_free_space(page: &Page) -> io::Result<u32> // Available space
pub fn can_fit_tuple(page: &Page, tuple_size: u32) -> io::Result<bool>
pub fn validate_page_header(page: &Page) -> io::Result<()> // Verify integrity
pub fn get_page_stats(page: &Page) -> io::Result<String> // Formatted stats
pub fn reset_page(page: &mut Page) -> io::Result<()> // Empty page
4. Enhanced CSV Loading (src/backend/executor/load_csv.rs)
- Pre-Load Data Profiling: Header/schema compatibility test BEFORE mass operations begin, not aborting halfway.
- Per-Tuple Row Injection Validation: Validation triggers inline. Rejects malformed strings but preserves valid insertions indicating line limits.
- String Dimension Handiling: Handles length 10 padding natively, raises inline truncate warnings.
Functions:
pub fn load_csv(
catalog: &Catalog,
db_name: &str,
table_name: &str,
file: &mut File,
csv_path: &str,
) -> io::Result<u32> // Returns count of inserted rows
pub fn insert_single_tuple(
catalog: &Catalog,
db_name: &str,
table_name: &str,
file: &mut File,
values: &[&str],
) -> io::Result<bool> // Returns success/failure
Validation Process:
- Schema Validation: Check all column types exist and are supported
- File Validation: Ensure CSV file is readable
- Column Count Validation: Check each row has correct column count
- Value Validation: Validate each value against its data type
- Serialization: Convert values to bytes safely
- Insertion: Insert into heap using insert_tuple
5. Improved Catalog Persistence (src/backend/catalog/catalog.rs)
- Safe State Syncs:
save_catalogyieldsstd::io::Result<()>and recovers gracefully. - Fault-Tolerant Reloads: Corrupt
.jsonor deleted state files construct cleanly upon reload viaload_catalog()rather than crashing execution.
6. Layout Abstractions & Table Display (src/backend/executor/seq_scan.rs)
Features:
- Professional Table Format: Box drawing characters (┌─┬─┐)
- Single Header Row: Column names shown once, not repeated
- ID Column: Sequential tuple numbering
- Data Type Info: Shows type in header
- Error Handling: Graceful handling of deserialization errors
Output Format:
╔════════════════════════════════════════════╗
║ Tuples in 'mydb.users' ║
║ Total pages: 2 ║
╚════════════════════════════════════════════╝
[TABLE DISPLAY] Columns:
1: id (INT)
2: name (TEXT)
┌─────┬──────────────────────────────────────────────────┐
│ ID │ id: INT │ name: TEXT │
├─────┼──────────────────────────────────────────────────┤
│ 1 │ 1 │ Alice │
│ 2 │ 2 │ Bob │
│ 3 │ 3 │ Charlie │
└─────┴──────────────────────────────────────────────────┘
Total tuples displayed: 3
7. Frontend & REPL Operations (src/frontend/data_cmd.rs & src/frontend/menu.rs)
- Manual single-tuple ingestion feature mapping commands securely into native layout layers (
insert_tuple_cmd). - Upgraded nested boxes UI for operations categorizations visually dividing Menu selections over operations boundaries.
8. Heap File Management (HM) (src/backend/heap/heap_manager.rs)
- FSM-Backed Tuple Insertion:
insert_tupleintelligently maps new data directly to pages with free space by consulting the FSM tree instead of blindly appending. - Dynamic Growth:
allocate_new_pagesafely expands table boundaries horizontally and notifies FSM mappings only when capacity is exhausted. - Header Metadata Integrity:
HeaderMetadatapersists schema state (total tuples securely updated natively,page_count,fsm_page_count) ensuring state integrity preventing sequential misalignment. - Coordinate Lookups: Added
get_tuple(page_id, slot_id)for O(1) constant-time direct tuple coordinate fetching bypassing global scans natively. - Lazy Evaluation Iterator Scans: Implemented
HeapScanIteratoryielding page/slot structures lazily preventing memory faults when scanning multi-GB files.
9. Free Space Management (FSM) (src/backend/fsm/fsm.rs)
- 3-Level Binary Max-Tree: Tree-based structure replacing O(N) scan layouts. Stored safely inside a
.fsmpersistence sidecar fork avoiding main file cluster intrusion. - Constant-Time I/O Space Discovery (
fsm_search_avail): Rapid lookup resolving exact target heap pages fitting arbitrary payloads. Requires exactly 3 bounded page reads (O(1) I/O) while leveraging O(log N) binary max-tree cpu-checks internally, completely avoiding raw header sequence scanning. - Auto-Bubble Capacity Resolvers (
fsm_set_avail): Updating a leaf slot capacity recursively updates max parent nodes, notifying the tree roots exactly how much space is left across subsets. - Compaction Readiness (
fsm_vacuum_update): Integration hooking natively into vacuuming modules marking pages as refreshed effortlessly. - Fault-Tolerant Native Reconstruction (
build_from_heap): If a.fsmsidecar drops out of scope or is deleted, FSM rebuilds the layout completely seamlessly from the primary heap data without logging exceptions.
10. Diagnostics and Tracing Debug Statements
- Pervasive output streams mapping operation traces recursively
[TYPE_VALIDATOR],[ERROR_HANDLER],[CATALOG],[CSV_LOADER],[FSM_ALLOCATOR].
Technical Outcomes
- Robustness: Hardened IO interfaces over raw allocations/deallocations.
- Usability: Interactive feedback loop provides user prompts matching logical behaviors instead of memory leaks or generic panic tracebacks.
- Maintainability: Layered boundary patterns simplify future test assertions mapping and debugging safely.
11. Core Bug Fixes & Refactoring
read_all_pagesAPI Implementation: Added a new function indisk_manager.rsto read all pages (header + data) from a file on disk into memory.- Refactoring
load_table_from_disk: ModifiedBufferManager::load_table_from_diskinbuffer_manager.rsto utilize the newread_all_pagesAPI, significantly simplifying the reading logic. - Cleaned Up Legacy Code: Removed
load_csv_into_pagesandload_csv_to_bufferfrom the buffer manager. The active bulk loading logic now relies appropriately onload_csv.rsthrough the frontend commands. load_catalogData Sync Issue: Standardized CSV/Bulk loader to strictly useinsert_tupleper valid row insertion rather than trying to construct un-validated tuples blindly.- Catalog Failure Problem: Critical issue is when a accidentally deleted catalog file caused the DB to create a blank slate catalog. Thus data loss of the existing data.
- Removed
create_pageFunction: Eliminated problematiccreate_pagethat randomly appended zeroed blocks and corrupted the 20-byte HeaderMetadata. All page allocation now uses properly initialized Page structures with explicit HeaderMetadata instantiation and statefulupdate_header_page()synchronization.
Recent Fixes & Robustness Improvements
- Phantom Yields for Deleted Tuples: Solved by ignoring
offset == 0 && length == 0during scans (HeapScanIterator::next()) and failing gracefully inside targeted retrieval (HeapManager::get_tuple()). - Slot Directory Exhaustion (Dead Tuple Leak) Optimization: Prevented unbounded expansion of
lowerpointer by inspecting and reusing dead tuple slots (0..tuple_count). Now only expands when no dead slots exist, optimizing continuous data space accurately. - Tail Pointer Rollback Optimization in
delete_tuple(): When deleting the tuple perfectly bounded toupperor the slot strictly bounded tolower, boundaries dynamically rollback. Reclaims sequential space continuously exactly as PostgreSQL abort rollbacks behave. - Improved Table Statistics: The diagnostic tool exposes exact fragmentation limits (largest contiguous block), specific tuple allocations, slot contents, and dead counts across active blocks per page constraints.
12.Optimization :
- Early Exit: If the insert does not changes the category (e.g., from 15 to 15), we can skip the bubble-up entirely, This means for 95% of small inserts, fsm_set_avail will gracefully short-circuit, sparing you an unnecessary disk rewrite and bubble-up traversal.
13. Summary of Implemented Features
Core Database Operations
✓ FSM-Backed Tuple Insertion
- Intelligent page selection using 3-level binary max-tree
- 3-attempt retry strategy handles fragmentation gracefully
- O(log N) search time
✓ Tuple Fetching by Coordinates
- Direct O(1) lookup:
get_tuple(page_id, slot_id) -> Vec<u8> - No full-table scans required
- Safe slot entry parsing and validation
✓ Sequential Table Scans
- Lazy iterator implementation (
HeapScanIterator) - Memory-efficient: 1 page cached at a time
- Graceful handling of invalid/deleted slots
✓ Data Type Support
- INT: 32-bit signed integers (4 bytes)
- TEXT: Variable-length strings (10 bytes, padded/truncated)
- Case-insensitive type checking
- Comprehensive value validation
✓ CSV Bulk Loading
- Pre-load schema validation (fail-fast)
- Per-tuple validation inline (preserve successes, reject invalids)
- Smart string handling with length 10 padding
- Returns count of successfully inserted rows
✓ Persistent Catalog Management
- Graceful recovery from corrupted/missing catalog.json
- Automatic reconstruction by scanning data directory
- Atomic state synchronization on updates
Free Space Management (FSM)
✓ 3-Level Binary Max-Tree Structure
- Covers up to 64 billion heap pages with constant 3-level depth
- Sidecar
.fsmfile (separate from heap data) - Quantization to 0-255 categories (1 byte per page)
✓ Efficient Page Selection
fsm_search_avail(min_category): 3 bounded I/O reads, O(log N) CPUfp_next_slot: Reserved for future load spreading- Fallback: allocate new page if all existing pages fragmented
✓ Automatic Category Updates
fsm_set_avail(page_id, free_bytes): Bubble-up propagation- Leaf updates cascade to parents and root
- Self-correcting on quantization errors
✓ Fragmentation Handling
- Tracks contiguous free space only (current phase)
- Future support for total-space tracking with on-fly compaction
✓ Fault Tolerance
build_from_heap(): Automatic FSM reconstruction if.fsmcorrupted/deleted- No WAL logging needed; FSM is a hint layer
Heap File Management
✓ 20-Byte HeaderMetadata
page_count: Total heap pages (u32)fsm_page_count: Total FSM pages (u32)total_tuples: 64-bit tuple counter (u64, enables O(1) COUNT(*))last_vacuum: Reserved for future VACUUM tracking
✓ Slotted Page Layout
lowerpointer: slot directory (growing downward)upperpointer: tuple data (growing upward)- Safe slot entry parsing: (offset, length)
- Page stats API: tuple count, free space, integrity checks
✓ Dynamic Table Growth
allocate_new_page(): Append empty page, update header, register with FSM- Automatic FSM fork extension when needed
- Atomic header updates prevent state corruption
13. CHECK_HEAP Command (Diagnostics & Metrics)
The CHECK_HEAP CLI command provides comprehensive diagnostics and performance metrics for FSM and heap operations.
Command Usage
# Access from database REPL after selecting a table
> CHECK_HEAP
Output Format
The command displays a formatted metrics table showing operation counters:
╔══════════════════════════════════════════════════════════════╗
║ OPERATION METRICS ║
╠══════════════════════════════════════════════════════════════╣
║ FSM Operations: ║
║ - fsm_search_avail: 1 calls ║
║ - fsm_search_tree: 1 calls ║
║ - fsm_read_page: 1 calls ║
║ - fsm_write_page: 1 calls ║
║ - fsm_serialize_page: 1 calls ║
║ - fsm_deserialize_page: 1 calls ║
║ - fsm_set_avail: 1 calls ║
║ - fsm_vacuum_update: 0 calls ║
╠══════════════════════════════════════════════════════════════╣
║ Heap Operations: ║
║ - insert_tuple: 1 calls ║
║ - get_tuple: 0 calls ║
║ - allocate_page: 0 calls ║
║ - write_page: 1 calls ║
║ - read_page: 1 calls ║
║ - page_free_space: 0 calls ║
╚══════════════════════════════════════════════════════════════╝
Implementation Details
Location: src/backend/instrumentation.rs
Counters are atomic and thread-safe:
pub struct FSMMetrics {
pub fsm_search_avail_calls: AtomicU64,
pub fsm_search_tree_calls: AtomicU64,
pub fsm_read_page_calls: AtomicU64,
pub fsm_write_page_calls: AtomicU64,
pub fsm_set_avail_calls: AtomicU64,
pub serialize_fsm_page_calls: AtomicU64,
pub deserialize_fsm_page_calls: AtomicU64,
}
pub struct HeapMetrics {
pub insert_tuple_calls: AtomicU64,
pub delete_tuple_calls: AtomicU64,
pub get_tuple_calls: AtomicU64,
pub scan_table_calls: AtomicU64,
pub page_free_space_calls: AtomicU64,
pub allocate_new_page_calls: AtomicU64,
}
Zero Overhead: Metrics use relaxed atomic operations (no synchronization cost). Can be safely queried at any time via:
let stats = StatsSnapshot::capture();
stats.print_table();
14. Logging & Execution Guide
RUST_LOG Environment Variable
RookDB uses Rust's log crate with env_logger for conditional, hierarchical logging. The RUST_LOG environment variable controls output detail without modifying code.
Logging Hierarchy
Rust's logging follows a waterfall model: setting a level shows that level and all more critical levels:
LEAST DETAILED ────────────────────────────── MOST DETAILED
↓ ↓
off → error → warn → info → debug → trace
↑ ↑
Silence Only critical Everything
Running with Different Log Levels
1. Default: No Logs (Clean UI Only)
cargo run
# or explicitly:
RUST_LOG=off cargo run
Output: Only UI (ASCII tables, menus). Zero backend logs.
Best for: Production, demos, clean user experience.
2. Error Level: Critical Failures Only
RUST_LOG=error cargo run
Output:
[ERROR] Failed to open heap file: No such file or directory
[ERROR] Invalid page header detected at offset 8192
Best for: Troubleshooting severe issues, minimal noise.
3. Warning Level: Errors + Warnings
RUST_LOG=warn cargo run
Output:
[WARN] Page 5 detected with 94 bytes free (quantization mismatch)
[WARN] FSM rebuild needed; sidecar file corrupted
[ERROR] Failed to load table: Invalid schema
Best for: Production debugging, alerting on anomalies.
4. Info Level: Standard High-Level Operations
RUST_LOG=info cargo run
Output:
[INFO] Connected to database: 'mydb'
[INFO] Created table: 'users' (columns: id:INT, name:TEXT)
[INFO] Loaded 50000 rows from CSV
[INFO] Sequential scan on table 'users': 3 tuples found
[INFO] FSM rebuild completed (23000 heap pages scanned)
Best for: Development, understanding app flow, high-level milestones.
5. Debug Level: Developer Diagnostics
RUST_LOG=debug cargo run
Output:
[DEBUG] Catalog loaded from: /home/atharva/database/global/catalog.json
[DEBUG] Opening heap file: /home/atharva/database/base/users/users.dat
[DEBUG] Page 1: lower=8, upper=8192, free_space=8184
[DEBUG] Validating tuple size: 50 bytes ≤ 8184 available? YES
[DEBUG] FSM search: looking for category ≥ 2
[DEBUG] FSM root value: 5 (sufficient capacity)
[DEBUG] Traverse Level 2 → Level 1 → Level 0
[DEBUG] Found page 47 (category 5)
[DEBUG] Insert successful: (page_id=47, slot_id=3)
[DEBUG] Updating FSM: page 47 now has 26 bytes free (category 1)
Best for: Development, understanding file operations, debugging normal behavior.
6. Trace Level: Byte-Level Details (Extreme)
RUST_LOG=trace cargo run
Output:
[TRACE] serialize_page: encoding header (lower=8, upper=8192)
[TRACE] page_offset: 8192 (page_id=1, PAGE_SIZE=8192)
[TRACE] writing bytes [0..8]: [0x08, 0x00, 0x00, 0x00, 0x00, 0x20, ...]
[TRACE] slot_entry_offset: 8
[TRACE] slot_entry_value: (offset=8134, length=58)
[TRACE] writing bytes [8..16]: [0x96, 0x1F, 0x00, 0x00, 0x3A, 0x00, ...]
[TRACE] page_write_complete: 8192 bytes written to disk
[TRACE] fsm_leaf_index: 47 (heap_page_id=47, FSM_SLOTS_PER_PAGE=4000)
[TRACE] category_value: floor(26 * 255 / 8192) = 0
[TRACE] fsm_tree[node_47] = 0x00
[TRACE] parent_node_88: max(tree[88], tree[89]) = 3
[TRACE] bubble_up_complete: reached FSM root
Best for: Debugging FSM tree issues, corruption investigation, byte-level analysis.
15. Compaction Team Integration APIs
The Compaction Team (Project 10) has 3 high-level facade functions to safely integrate tuple reorganization and VACUUM operations without modifying core heap manager logic.
1. insert_raw_tuple - Tuple Relocation
pub fn insert_raw_tuple(
db_name: &str,
table_name: &str,
tuple_data: &[u8]
) -> io::Result<(u32, u32)>
Purpose: Insert a tuple without going through the normal 3-attempt FSM search
Use Case: Relocating a tuple from one page to another during page compaction
Example:
// Compaction reads a fragmented tuple
let tuple_bytes = hm.get_tuple(page_5, slot_2)?;
// Relocate it to a better location via FSM search
let (new_page_id, new_slot_id) = insert_raw_tuple(
"mydb",
"users",
&tuple_bytes
)?;
### 2. `update_page_free_space` - In-Place Compaction
```rust
pub fn update_page_free_space(
db_name: &str,
table_name: &str,
page_id: u32,
absolute_free_bytes: u32
) -> io::Result<()>
Purpose: Notify FSM that a page gained free space after in-place compaction
Use Case: Consolidating fragmented dead space by shifting tuples, then informing FSM
Example:
// Before: Page 7 has 76 bytes contiguous + 50 bytes dead
// After compaction: Page 7 has 126 bytes contiguous (merged)
update_page_free_space("mydb", "users", 7, 126)?;
// FSM recalculates:
// category_old = floor(76 × 255 / 8192) = 2
// category_new = floor(126 × 255 / 8192) = 4
// Page becomes more searchable for future inserts
3. rebuild_table_fsm - Full FSM Rebuild
pub fn rebuild_table_fsm(
db_name: &str,
table_name: &str
) -> io::Result<()>
Purpose: Rebuild entire FSM from scratch after extensive table reorganization
Use Case: After compacting thousands of pages, ensure FSM accuracy
Example:
// After full-table compaction of 10000 pages
rebuild_table_fsm("mydb", "users")?;
// FSM rebuilds by:
// 1. Scanning all 10000 heap pages
// 2. Computing free-space category for each page
// 3. Rebuilding 3-level tree from scratch
// 4. Writing `.fsm` sidecar file
16. Frontend & CLI Changes
New Commands
CHECK_HEAP - Diagnostics Command
Usage: SELECT * FROM <table>; CHECK_HEAP
Displays operation metrics and FSM statistics (see Section 13).
Enhanced INSERT Command
Now uses FSM-backed page selection:
> INSERT INTO users VALUES (1, 'Alice');
[INFO] FSM search for category ≥ 2
[INFO] Found page 47 with sufficient free space
[INFO] Inserted: (page_id=47, slot_id=3)
Logging Control
Integrated with RUST_LOG:
# Clean UI
RUST_LOG=off cargo run
# With diagnostics
RUST_LOG=debug cargo run
# Deep debugging
RUST_LOG=trace cargo run
Menu System Updates
- Restructured nested menus for clarity
- Added operation categorization (Database, Table, Data)
- Integrated logging feedback into operation output
- Error messages now provide actionable guidance
---
## 18. Known Limitations & Future Work
### Current Phase (Project 6)
✓ FSM tracks contiguous free space only (fragmentation acceptable)
✓ Single-threaded operations
✓ Page-oriented storage (8 KB fixed)
✓ INT and TEXT types only
### Future Phase
→ Total space tracking with on-the-fly compaction
→ Multi-threaded concurrent inserts
→ Dynamic data type support
→ Advanced indexing (B-tree, hash)
→ Query optimization (cost-based planning)
→ Distributed replication
---