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

class IOCostModel:
    """
    I/O cost model for database operations.
    All times in milliseconds, sizes in bytes.
    """
    
    def __init__(self, storage_type='ssd_nvme'):
        if storage_type == 'hdd':
            self.seek_time = 8.0        # ms
            self.rotation_latency = 4.0  # ms (7200 RPM)
            self.transfer_rate = 150     # MB/s
        elif storage_type == 'ssd_sata':
            self.seek_time = 0.1        # ms
            self.rotation_latency = 0   # N/A
            self.transfer_rate = 500    # MB/s
        else:  # ssd_nvme
            self.seek_time = 0.03       # ms
            self.rotation_latency = 0   # N/A
            self.transfer_rate = 3000   # MB/s
        
        self.page_size = 8192  # 8 KB default
    
    def random_read_time(self, pages=1):
        """Time for random page reads."""
        per_page = (
            self.seek_time + 
            self.rotation_latency + 
            (self.page_size / 1024 / 1024) / self.transfer_rate * 1000
        )
        return pages * per_page
    
    def sequential_read_time(self, pages):
        """Time for sequential page reads (amortized seek)."""
        # First page: full seek + transfer
        # Subsequent pages: mostly transfer
        first_page = self.random_read_time(1)
        if pages <= 1:
            return first_page
        
        # Subsequent pages: minimal seek, just transfer
        transfer_time = (pages - 1) * (self.page_size / 1024 / 1024) / self.transfer_rate * 1000
        return first_page + transfer_time
    
    def iops_capacity(self):
        """Maximum random I/O operations per second."""
        single_io = self.random_read_time(1)
        return 1000 / single_io  # Convert ms to seconds
 
# Compare storage types
for storage in ['hdd', 'ssd_sata', 'ssd_nvme']:
    model = IOCostModel(storage)
    print(f"\n{storage.upper()}:")
    print(f"  Random 1 page: {model.random_read_time(1):.3f} ms")
    print(f"  Random 10 pages: {model.random_read_time(10):.3f} ms")
    print(f"  Sequential 10 pages: {model.sequential_read_time(10):.3f} ms")
    print(f"  Max IOPS: {model.iops_capacity():.0f}")

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

import math
 
def analyze_point_lookup_cost(
    record_count: int,
    fanout: int,
    page_size_kb: int = 8,
    storage_type: str = 'ssd_nvme',
    cached_levels: int = 2
):
    """
    Analyze the cost of a point lookup in a B+-tree.
    """
    # Calculate tree height
    if record_count <= fanout - 1:
        height = 1
    else:
        height = math.ceil(math.log(record_count / (fanout - 1), fanout)) + 1
    
    # I/O times by storage type (ms)
    io_times = {
        'hdd': 10.0,
        'ssd_sata': 0.15,
        'ssd_nvme': 0.05
    }
    single_read_ms = io_times.get(storage_type, 0.05)
    
    # Actual I/O (accounting for caching)
    uncached_levels = max(0, height - cached_levels)
    total_io_ms = uncached_levels * single_read_ms
    
    # CPU cost (binary search within pages)
    # log2(fanout) comparisons per level, ~0.0001 ms each
    comparisons_per_level = math.log2(fanout)
    cpu_ms = height * comparisons_per_level * 0.0001
    
    return {
        'height': height,
        'cached_levels': min(cached_levels, height),
        'disk_ios': uncached_levels,
        'io_time_ms': total_io_ms,
        'cpu_time_ms': cpu_ms,
        'total_time_ms': total_io_ms + cpu_ms
    }
 
# Analyze various scenarios
scenarios = [
    (1_000_000, 500, 'ssd_nvme', 2),      # 1M records, fast SSD, 2 levels cached
    (1_000_000_000, 500, 'ssd_nvme', 2),  # 1B records, fast SSD, 2 levels cached
    (1_000_000_000, 500, 'hdd', 2),       # 1B records, HDD, 2 levels cached
    (1_000_000_000, 500, 'ssd_nvme', 3),  # 1B records, NVMe, 3 levels cached
]
 
print("Point Lookup Cost Analysis")
print("=" * 75)
for records, fanout, storage, cached in scenarios:
    result = analyze_point_lookup_cost(records, fanout, 8, storage, cached)
    print(f"\n{records:,} records, {storage}, {cached} cached levels:")
    print(f"  Height: {result['height']}, Disk I/Os: {result['disk_ios']}")
    print(f"  I/O Time: {result['io_time_ms']:.3f} ms, CPU: {result['cpu_time_ms']:.4f} ms")
    print(f"  Total: {result['total_time_ms']:.3f} ms")

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
75
76
77
78
79
80
81

import math
 
def analyze_range_scan_cost(
    total_records: int,
    matching_records: int,
    fanout: int,
    storage_type: str = 'ssd_nvme',
    cached_levels: int = 2,
    is_clustered: bool = True
):
    """
    Analyze cost of a range scan in a B+-tree.
    
    Parameters:
    - is_clustered: True if index is clustered (data in leaf pages)
                   False if secondary index (requires heap lookup)
    """
    # Records per leaf page
    records_per_leaf = fanout - 1
    
    # Leaf pages to scan
    leaf_pages = math.ceil(matching_records / records_per_leaf)
    
    # Tree traversal cost (point lookup to first leaf)
    height = math.ceil(math.log(total_records / records_per_leaf, fanout)) + 1
    traversal_ios = max(0, height - cached_levels)
    
    # I/O characteristics
    io_times = {'hdd': 10.0, 'ssd_sata': 0.15, 'ssd_nvme': 0.05}
    random_io = io_times[storage_type]
    
    # Sequential read benefit (leaves are linked)
    # First leaf: random access, subsequent: ~10% of random cost
    sequential_multiplier = 0.1 if storage_type == 'hdd' else 0.8
    
    if leaf_pages <= 1:
        leaf_scan_ios = leaf_pages
    else:
        # First leaf random, rest sequential
        effective_ios = 1 + (leaf_pages - 1) * sequential_multiplier
        leaf_scan_ios = effective_ios
    
    # For non-clustered: add heap lookups (random I/O per record)
    if not is_clustered:
        # Worst case: each record on different page
        # Best case: all records fit in few pages
        # Estimate: unique pages = matching_records / records_per_data_page
        records_per_data_page = 50  # Estimate for heap pages
        heap_pages = math.ceil(matching_records / records_per_data_page)
        # Some pages will be cached; estimate 50% hit rate
        heap_ios = heap_pages * 0.5
    else:
        heap_ios = 0
    
    total_ios = traversal_ios + leaf_scan_ios + heap_ios
    total_time_ms = random_io * total_ios
    
    return {
        'height': height,
        'traversal_ios': traversal_ios,
        'leaf_pages': leaf_pages,
        'leaf_scan_ios': leaf_scan_ios,
        'heap_ios': heap_ios,
        'total_ios': total_ios,
        'time_ms': total_time_ms,
        'selectivity': matching_records / total_records * 100
    }
 
# Analyze range scan scenarios
print("Range Scan Cost Analysis (1 Billion records, NVMe SSD)")
print("=" * 70)
 
for match_pct in [0.001, 0.01, 0.1, 1.0, 10.0]:
    matching = int(1_000_000_000 * match_pct / 100)
    result = analyze_range_scan_cost(
        1_000_000_000, matching, 500, 'ssd_nvme', 2, True
    )
    print(f"\nSelectivity {match_pct}% ({matching:,} records):")
    print(f"  Leaf pages: {result['leaf_pages']:,}")
    print(f"  Total I/Os: {result['total_ios']:.1f}")
    print(f"  Time: {result['time_ms']:.2f} ms")

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88

import math
import random
 
def analyze_insert_cost(
    current_records: int,
    fanout: int,
    fill_factor: float = 0.7,
    storage_type: str = 'ssd_nvme',
    cached_levels: int = 2
):
    """
    Analyze the cost of inserting a record into a B+-tree.
    """
    # Calculate tree structure
    records_per_leaf = fanout - 1
    avg_records_per_leaf = records_per_leaf * fill_factor
    
    height = max(1, math.ceil(math.log(current_records / avg_records_per_leaf, fanout)) + 1)
    
    # I/O times
    io_times = {'hdd': 10.0, 'ssd_sata': 0.15, 'ssd_nvme': 0.05}
    io_ms = io_times[storage_type]
    
    # Lookup cost (reads)
    read_ios = max(0, height - cached_levels)
    
    # Write cost depends on split probability
    # Probability of leaf split = 1 - fill_factor (simplified)
    # Actually depends on how full the target leaf is
    leaf_split_prob = 1 - fill_factor
    
    # Internal node split much rarer (propagates up)
    internal_split_prob = leaf_split_prob ** 2  # Approximation
    
    # Expected write I/Os:
    # - Always write 1 leaf
    # - If split: write 2 leaves + 1 internal update
    # - If internal split: additional propagation
    expected_write_ios = 1 + leaf_split_prob * 2 + internal_split_prob * 2
    
    # Total cost
    total_ios = read_ios + expected_write_ios
    
    return {
        'height': height,
        'read_ios': read_ios,
        'expected_write_ios': expected_write_ios,
        'leaf_split_prob': leaf_split_prob,
        'total_ios': total_ios,
        'time_ms': total_ios * io_ms
    }
 
def simulate_bulk_insert_cost(
    initial_records: int,
    insert_count: int,
    fanout: int,
    storage_type: str = 'ssd_nvme'
):
    """
    Simulate the total cost of bulk random insertions.
    """
    total_time_ms = 0
    splits = 0
    
    for i in range(insert_count):
        current = initial_records + i
        result = analyze_insert_cost(current, fanout, 0.7, storage_type, 2)
        total_time_ms += result['time_ms']
        if random.random() < result['leaf_split_prob']:
            splits += 1
    
    return {
        'total_time_ms': total_time_ms,
        'avg_time_ms': total_time_ms / insert_count,
        'split_count': splits,
        'split_rate': splits / insert_count * 100
    }
 
# Analyze single insert
print("Single Insert Cost Analysis")
print("=" * 50)
for records in [1_000_000, 100_000_000, 1_000_000_000]:
    result = analyze_insert_cost(records, 500, 0.7, 'ssd_nvme', 2)
    print(f"\n{records:,} existing records:")
    print(f"  Height: {result['height']}")
    print(f"  Read I/Os: {result['read_ios']}, Write I/Os: {result['expected_write_ios']:.2f}")
    print(f"  Split probability: {result['leaf_split_prob']*100:.1f}%")
    print(f"  Expected time: {result['time_ms']:.3f} ms")

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

def analyze_delete_cost(
    current_records: int,
    fanout: int,
    deletion_pattern: str = 'random',  # 'random', 'sequential', 'targeted'
    storage_type: str = 'ssd_nvme',
    cached_levels: int = 2
):
    """
    Analyze the cost of deleting a record from a B+-tree.
    """
    import math
    
    records_per_leaf = fanout - 1
    min_fill = (fanout - 1) // 2
    
    height = max(1, math.ceil(math.log(current_records / records_per_leaf, fanout)) + 1)
    
    io_times = {'hdd': 10.0, 'ssd_sata': 0.15, 'ssd_nvme': 0.05}
    io_ms = io_times[storage_type]
    
    # Lookup cost
    read_ios = max(0, height - cached_levels)
    
    # Merge probability depends on deletion pattern
    if deletion_pattern == 'random':
        # Random deletions spread across pages; merge rare
        underflow_prob = 0.05  # Low probability of any page hitting minimum
    elif deletion_pattern == 'sequential':
        # Sequential deletions concentrate on few pages; merge likely
        underflow_prob = 0.30
    else:  # targeted (deleting known sparse regions)
        underflow_prob = 0.50
    
    # Expected write I/Os
    # - Always write 1 leaf (remove entry)
    # - If underflow: read sibling, possibly merge (write 1-2)
    # - If merge: update parent (write 1)
    read_sibling_prob = underflow_prob
    merge_prob = underflow_prob * 0.5  # Half of underflows result in merge
    
    expected_extra_reads = read_sibling_prob * 1  # Read sibling
    expected_write_ios = 1 + merge_prob * 2  # Leaf + possible merge
    
    total_read_ios = read_ios + expected_extra_reads
    total_ios = total_read_ios + expected_write_ios
    
    return {
        'height': height,
        'read_ios': total_read_ios,
        'write_ios': expected_write_ios,
        'underflow_prob': underflow_prob,
        'merge_prob': merge_prob,
        'total_ios': total_ios,
        'time_ms': total_ios * io_ms
    }
 
# Compare deletion patterns
print("Delete Cost Analysis (1B records, f=500, NVMe)")
print("=" * 60)
 
for pattern in ['random', 'sequential', 'targeted']:
    result = analyze_delete_cost(1_000_000_000, 500, pattern, 'ssd_nvme', 2)
    print(f"\n{pattern.capitalize()} deletions:")
    print(f"  Underflow probability: {result['underflow_prob']*100:.0f}%")
    print(f"  Merge probability: {result['merge_prob']*100:.1f}%")
    print(f"  Read I/Os: {result['read_ios']:.2f}, Write I/Os: {result['write_ios']:.2f}")
    print(f"  Total time: {result['time_ms']:.3f} ms")

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
75
76
77
78
79
80
81

import math
 
def compare_bulk_load_strategies(
    record_count: int,
    fanout: int,
    storage_type: str = 'ssd_nvme',
    available_memory_mb: int = 1024
):
    """
    Compare individual inserts vs optimized bulk load.
    """
    records_per_leaf = fanout - 1
    leaf_pages = math.ceil(record_count / records_per_leaf)
    
    height = math.ceil(math.log(leaf_pages, fanout)) + 1
    
    # Calculate total nodes
    internal_pages = 0
    level_pages = leaf_pages
    while level_pages > 1:
        parent_pages = math.ceil(level_pages / fanout)
        internal_pages += parent_pages
        level_pages = parent_pages
    
    total_pages = leaf_pages + internal_pages
    
    io_times = {'hdd': 10.0, 'ssd_sata': 0.15, 'ssd_nvme': 0.05}
    io_ms = io_times[storage_type]
    
    # Strategy 1: Individual inserts
    # Each insert: ~2 reads (height with caching) + ~1.5 writes
    individual_ios = record_count * (2 + 1.5)
    individual_time_s = individual_ios * io_ms / 1000
    
    # Strategy 2: Optimized bulk load
    # Sort phase: external merge sort
    # Assuming 100 bytes per record
    record_size = 100
    data_size_mb = record_count * record_size / (1024 * 1024)
    sort_passes = math.ceil(math.log(data_size_mb / available_memory_mb, 
                                      available_memory_mb / record_size))
    sort_passes = max(1, sort_passes)
    
    # Sort I/Os: read all data per pass, write all data per pass
    pages_for_data = math.ceil(data_size_mb / 8 * 1024)  # 8KB pages
    sort_ios = pages_for_data * 2 * sort_passes
    
    # Build phase: sequential write of all index pages
    build_ios = total_pages
    
    # Total bulk load I/Os
    bulk_ios = sort_ios + build_ios
    bulk_time_s = bulk_ios * io_ms / 1000
    
    speedup = individual_time_s / bulk_time_s
    
    return {
        'record_count': record_count,
        'total_pages': total_pages,
        'individual_ios': individual_ios,
        'individual_time_s': individual_time_s,
        'individual_time_hours': individual_time_s / 3600,
        'bulk_ios': bulk_ios,
        'bulk_time_s': bulk_time_s,
        'bulk_time_hours': bulk_time_s / 3600,
        'speedup': speedup
    }
 
# Compare for various dataset sizes
print("Bulk Load Strategy Comparison")
print("=" * 70)
 
for records in [1_000_000, 100_000_000, 1_000_000_000]:
    result = compare_bulk_load_strategies(records, 500, 'ssd_nvme')
    print(f"\n{records:,} records:")
    print(f"  Total index pages: {result['total_pages']:,}")
    print(f"  Individual inserts: {result['individual_ios']:,.0f} I/Os = "
          f"{result['individual_time_hours']:.1f} hours")
    print(f"  Bulk load: {result['bulk_ios']:,.0f} I/Os = "
          f"{result['bulk_time_s']:.1f} seconds")
    print(f"  Speedup: {result['speedup']:.0f}x")

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

def calculate_wal_overhead(
    operations_per_second: int,
    avg_operation_size_bytes: int = 200,
    page_size: int = 8192,
    full_page_writes: bool = True,
    compression_ratio: float = 0.5
):
    """
    Calculate WAL overhead for B+-tree operations.
    """
    # Base log record per operation
    base_log_bytes = avg_operation_size_bytes
    
    # Full page image on first modification after checkpoint
    # (for crash recovery)
    # Assume 1/100 operations require full page write
    fpw_probability = 0.01 if full_page_writes else 0
    fpw_size = page_size * fpw_probability
    
    # Total log bytes per operation
    log_bytes_per_op = (base_log_bytes + fpw_size) * compression_ratio
    
    # Log bandwidth required
    log_bandwidth_mbps = (log_bytes_per_op * operations_per_second) / (1024 * 1024)
    
    # Sync overhead (fsync calls)
    # Assuming group commit: 1 sync per 10ms at high load
    syncs_per_second = min(100, operations_per_second / 10)
    
    return {
        'log_bytes_per_op': log_bytes_per_op,
        'log_bandwidth_mbps': log_bandwidth_mbps,
        'syncs_per_second': syncs_per_second,
        'additional_latency_ms': 1 / syncs_per_second * 1000 if syncs_per_second > 0 else 0
    }
 
# Analyze for high-throughput OLTP
result = calculate_wal_overhead(10000, 200)
print(f"WAL overhead at 10K TPS:")
print(f"  Log bytes per op: {result['log_bytes_per_op']:.0f}")
print(f"  Log bandwidth: {result['log_bandwidth_mbps']:.1f} MB/s")
print(f"  Syncs/second: {result['syncs_per_second']:.0f}")