Sorted File Organization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/*
 * Sorted File Layout
 * 
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                        FILE HEADER                               │
 * │  - Sort key attribute                                            │
 * │  - Sort order (ASC/DESC)                                         │
 * │  - Page count, record count                                      │
 * │  - Pointer to overflow area (if used)                            │
 * └─────────────────────────────────────────────────────────────────┘
 *
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                        PAGE 1                                    │
 * │  Records with keys: 1, 5, 12, 23, 45, 67                        │
 * │  Min key: 1, Max key: 67                                        │
 * └─────────────────────────────────────────────────────────────────┘
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                        PAGE 2                                    │
 * │  Records with keys: 89, 101, 134, 156, 178, 199                 │
 * │  Min key: 89, Max key: 199                                      │
 * └─────────────────────────────────────────────────────────────────┘
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                        PAGE 3                                    │
 * │  Records with keys: 234, 267, 289, 312, 345, 378                │
 * │  Min key: 234, Max key: 378                                     │
 * └─────────────────────────────────────────────────────────────────┘
 *
 * └─── ... more pages ... ───┘
 *
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                    OVERFLOW AREA (Optional)                      │
 * │  Records inserted after initial load, waiting for reorganization │
 * └─────────────────────────────────────────────────────────────────┘
 */
 
struct SortedFileHeader {
    int32   magic_number;        // File type identifier
    int32   version;             // File format version
    int64   num_pages;           // Total pages in main area
    int64   num_records;         // Total records
    int64   overflow_pages;      // Pages in overflow area
    int32   sort_key_offset;     // Offset of sort key in record
    int32   sort_key_length;     // Length of sort key
    int16   sort_key_type;       // Type (INT, VARCHAR, etc.)
    int16   sort_order;          // ASC = 1, DESC = 2
    int64   last_reorganization; // Timestamp of last reorg
    byte    reserved[200];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

function search_sorted_file(SortedFile file, Key target) -> Record? {
    // Phase 1: Binary search to find the correct page
    PageID page_id = binary_search_pages(file, target);
    
    if (page_id == NOT_FOUND) {
        return null;  // Key is outside file's key range
    }
    
    // Phase 2: Load the page and search within it
    Page page = buffer_pool.get_page(file.file_id, page_id);
    Record record = binary_search_within_page(page, target);
    
    return record;  // null if not found within page
}
 
function binary_search_pages(SortedFile file, Key target) -> PageID {
    int low = 0;
    int high = file.header.num_pages - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        
        // Read page header to get key boundaries
        PageBoundary bounds = get_page_boundaries(file, mid);
        
        if (target < bounds.min_key) {
            high = mid - 1;  // Target is in earlier page
        } else if (target > bounds.max_key) {
            low = mid + 1;   // Target is in later page
        } else {
            return mid;      // Target is within this page's range
        }
    }
    
    return NOT_FOUND;  // Key doesn't exist in file
}
 
function binary_search_within_page(Page page, Key target) -> Record? {
    int low = 0;
    int high = page.header.num_records - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        Record record = page.get_record(mid);
        Key record_key = extract_key(record);
        
        if (record_key == target) {
            return record;   // Found!
        } else if (record_key < target) {
            low = mid + 1;   // Search upper half
        } else {
            high = mid - 1;  // Search lower half
        }
    }
    
    return null;  // Key not found in this page
}
 
/*
 * I/O Cost Analysis:
 * 
 * Without page boundary cache:
 *   - Each step of page binary search: 1 I/O to read page header
 *   - Total page search: O(log B) I/Os
 *   - Final page read: 1 I/O
 *   - Total: O(log B) I/Os
 * 
 * With sparse page directory in memory:
 *   - Page binary search: 0 I/Os (all in memory)
 *   - Final page read: 1 I/O
 *   - Total: O(1) I/Os for equality search!
 * 
 * This is why maintaining a sparse directory is critical.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

function range_query(SortedFile file, Key low, Key high) -> List<Record> {
    List<Record> results = new List();
    
    // Step 1: Binary search for starting page
    PageID start_page = find_first_page_geq(file, low);
    
    if (start_page == NOT_FOUND) {
        return results;  // No records >= low exist
    }
    
    // Step 2: Sequential scan through pages until we exceed high
    PageID current_page = start_page;
    
    while (current_page < file.header.num_pages) {
        Page page = buffer_pool.get_page(file.file_id, current_page);
        
        // Check if this page could contain any matching records
        if (page.min_key > high) {
            break;  // All remaining pages have keys > high
        }
        
        // Scan records in this page
        for (int i = 0; i < page.header.num_records; i++) {
            Record record = page.get_record(i);
            Key key = extract_key(record);
            
            if (key > high) {
                // Records are sorted, so no more matches in this page
                break;
            }
            
            if (key >= low) {
                results.add(record);
            }
        }
        
        current_page++;
    }
    
    return results;
}
 
/*
 * Example: Range query for orders with dates in [2024-01-01, 2024-01-31]
 * 
 * File: 10 million orders, 40 per page = 250,000 pages
 * Selectivity: 1 month out of 10 years ≈ 0.83%
 * Matching records: ~83,000 records over ~2,100 pages
 * 
 * Heap file: 250,000 page reads (full scan)
 * Sorted file: 1 (find start) + 2,100 (scan range) = 2,101 page reads
 * 
 * Improvement: 119x fewer I/Os
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

function insert_with_shift(SortedFile file, Record new_record) -> RID {
    Key key = extract_key(new_record);
    
    // Find target page
    PageID target_page = find_page_for_key(file, key);
    Page page = buffer_pool.get_page(file.file_id, target_page);
    
    if (page.has_space_for(new_record)) {
        // Simple case: room in the target page
        return insert_into_page_sorted(page, new_record);
    }
    
    // Complex case: page is full, need to shift
    
    // Find last record in last page that needs to shift
    // Create new page at end of file
    PageID new_page_id = file.allocate_new_page();
    Page new_page = buffer_pool.get_page(file.file_id, new_page_id);
    
    // Shift last record from each full page to the next page
    // Working backwards from end of file to target page
    for (PageID p = file.header.num_pages - 2; p >= target_page; p--) {
        Page current = buffer_pool.get_page(file.file_id, p);
        Page next = buffer_pool.get_page(file.file_id, p + 1);
        
        // Move last record from current to first position of next
        Record last = current.remove_last_record();
        next.insert_at_beginning(last);
        
        buffer_pool.mark_dirty(current);
        buffer_pool.mark_dirty(next);
    }
    
    // Now target page has room
    return insert_into_page_sorted(page, new_record);
}
 
/*
 * Cost Analysis:
 * 
 * For a file with B pages, inserting into the first page:
 * - Read B pages
 * - Write B pages
 * - Total: 2B I/O operations
 * 
 * For 10 million records (250,000 pages) at 10ms per I/O:
 * - 500,000 I/O operations
 * - 5,000 seconds ≈ 1.4 hours per insert!
 * 
 * This is clearly unacceptable for transactional workloads.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/*
 * Sorted File with Overflow Area
 * 
 * Main File (Sorted):
 * ┌────────────────┐
 * │ Page 1         │──────┐
 * │ Keys: 1-100    │      │ Overflow pointer
 * └────────────────┘      ▼
 *                    ┌────────────────┐
 *                    │ Overflow Block │
 *                    │ Key: 47, 83    │
 *                    └────────────────┘
 * 
 * ┌────────────────┐
 * │ Page 2         │──────┐
 * │ Keys: 101-200  │      │
 * └────────────────┘      ▼
 *                    ┌────────────────┐
 *                    │ Overflow Block │
 *                    │ Key: 156       │
 *                    └────────────────┘
 */
 
function insert_with_overflow(SortedFile file, Record new_record) -> RID {
    Key key = extract_key(new_record);
    
    // Find target page
    PageID target_page = find_page_for_key(file, key);
    Page page = buffer_pool.get_page(file.file_id, target_page);
    
    if (page.has_space_for(new_record)) {
        return insert_into_page_sorted(page, new_record);
    }
    
    // Insert into overflow area
    OverflowBlock overflow = get_or_create_overflow(page);
    int slot = overflow.append(new_record);
    
    // Update statistics
    file.header.overflow_record_count++;
    
    // Check if reorganization is needed
    if (should_reorganize(file)) {
        schedule_background_reorganization(file);
    }
    
    return RID(target_page, slot, IS_OVERFLOW);
}
 
function search_with_overflow(SortedFile file, Key target) -> Record? {
    // First, binary search in main file
    PageID page_id = binary_search_pages(file, target);
    Page page = buffer_pool.get_page(file.file_id, page_id);
    
    // Search within page
    Record record = binary_search_within_page(page, target);
    if (record != null) {
        return record;
    }
    
    // Not in main page - check overflow chain
    OverflowBlock overflow = page.overflow_pointer;
    while (overflow != null) {
        record = linear_search(overflow, target);
        if (record != null) {
            return record;
        }
        overflow = overflow.next;
    }
    
    return null;  // Not found anywhere
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

function delete_sorted(SortedFile file, Key key) -> bool {
    // Binary search to find the record
    PageID page_id = binary_search_pages(file, key);
    Page page = buffer_pool.get_page(file.file_id, page_id);
    
    int slot = binary_search_slot(page, key);
    if (slot == NOT_FOUND) {
        // Check overflow chain
        OverflowBlock overflow = page.overflow_pointer;
        while (overflow != null) {
            slot = linear_search_slot(overflow, key);
            if (slot != NOT_FOUND) {
                overflow.mark_deleted(slot);
                file.header.deleted_count++;
                return true;
            }
            overflow = overflow.next;
        }
        return false;  // Key not found
    }
    
    // Option A: Mark as deleted (fast)
    page.mark_deleted(slot);
    file.header.deleted_count++;
    
    // Option B: Shift records to fill gap (maintains density)
    // page.shift_records_after(slot);
    // file.adjust_subsequent_pages_if_needed();
    
    buffer_pool.mark_dirty(page);
    return true;
}
 
/*
 * Fragmentation Impact:
 * 
 * After many deletions, pages may have significant unused space:
 * 
 * Page before deletions: [R1][R2][R3][R4][R5][R6] - 0% fragmentation
 * Page after deletions:  [R1][XX][R3][XX][R5][XX] - 50% fragmentation
 * 
 * Effects:
 * - Range queries read more pages for same result count
 * - Memory usage increases (caching partially empty pages)
 * - Binary search may need to skip tombstones
 */