Skip to main content

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 exist
  • InvalidPath: Directory provided instead of file
  • InvalidDataType: Unsupported data type encountered
  • ValidationError: Data doesn't match schema
  • DiskFull: 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:

  1. Schema Validation: Check all column types exist and are supported
  2. File Validation: Ensure CSV file is readable
  3. Column Count Validation: Check each row has correct column count
  4. Value Validation: Validate each value against its data type
  5. Serialization: Convert values to bytes safely
  6. Insertion: Insert into heap using insert_tuple

5. Improved Catalog Persistence (src/backend/catalog/catalog.rs)

  • Safe State Syncs: save_catalog yields std::io::Result<()> and recovers gracefully.
  • Fault-Tolerant Reloads: Corrupt .json or deleted state files construct cleanly upon reload via load_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_tuple intelligently maps new data directly to pages with free space by consulting the FSM tree instead of blindly appending.
  • Dynamic Growth: allocate_new_page safely expands table boundaries horizontally and notifies FSM mappings only when capacity is exhausted.
  • Header Metadata Integrity: HeaderMetadata persists 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 HeapScanIterator yielding 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 .fsm persistence 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 .fsm sidecar 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_pages API Implementation: Added a new function in disk_manager.rs to read all pages (header + data) from a file on disk into memory.
  • Refactoring load_table_from_disk: Modified BufferManager::load_table_from_disk in buffer_manager.rs to utilize the new read_all_pages API, significantly simplifying the reading logic.
  • Cleaned Up Legacy Code: Removed load_csv_into_pages and load_csv_to_buffer from the buffer manager. The active bulk loading logic now relies appropriately on load_csv.rs through the frontend commands.
  • load_catalog Data Sync Issue: Standardized CSV/Bulk loader to strictly use insert_tuple per 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_page Function: Eliminated problematic create_page that randomly appended zeroed blocks and corrupted the 20-byte HeaderMetadata. All page allocation now uses properly initialized Page structures with explicit HeaderMetadata instantiation and stateful update_header_page() synchronization.

Recent Fixes & Robustness Improvements

  1. Phantom Yields for Deleted Tuples: Solved by ignoring offset == 0 && length == 0 during scans (HeapScanIterator::next()) and failing gracefully inside targeted retrieval (HeapManager::get_tuple()).
  2. Slot Directory Exhaustion (Dead Tuple Leak) Optimization: Prevented unbounded expansion of lower pointer by inspecting and reusing dead tuple slots (0..tuple_count). Now only expands when no dead slots exist, optimizing continuous data space accurately.
  3. Tail Pointer Rollback Optimization in delete_tuple(): When deleting the tuple perfectly bounded to upper or the slot strictly bounded to lower, boundaries dynamically rollback. Reclaims sequential space continuously exactly as PostgreSQL abort rollbacks behave.
  4. 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 .fsm file (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) CPU
  • fp_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 .fsm corrupted/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

  • lower pointer: slot directory (growing downward)
  • upper pointer: 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
  • 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

---