Database Management Systems

Storage Hierarchy:
                    Speed      Capacity
CPU Registers       ~1 ns      ~KB
L1/L2/L3 Cache     ~10 ns     ~MB
Main Memory (RAM)   ~100 ns    ~GB
SSD                 ~100 μs    ~TB
HDD                 ~10 ms     ~TB

Database files live on disk → Minimize disk I/O!

# Heap File Organization
# + Fast inserts (append anywhere)
# + Good for small tables
# - Slow search O(n) - must scan all

# Sequential File Organization
# + Fast range queries (sorted)
# + Binary search O(log n)
# - Slow inserts (must maintain order)

# Hash File Organization
# + O(1) average for equality lookup
# - No range queries
# - May need rehashing as data grows

Without Index:
┌──────────────────────────────────────┐
│  Full Table Scan: O(n)               │
│  Check every row to find matches     │
└──────────────────────────────────────┘

With Index:
┌──────────────────────────────────────┐
│  Index Lookup: O(log n)              │
│  Go directly to matching rows        │
└──────────────────────────────────────┘

DENSE INDEX:
Entry for EVERY search key value
┌───────────┐     ┌───────────────────┐
│ 10 → #1   │     │ #1: {10, Alice}   │
│ 20 → #2   │ ──→ │ #2: {20, Bob}     │
│ 30 → #3   │     │ #3: {30, Charlie} │
│ 40 → #4   │     │ #4: {40, Diana}   │
└───────────┘     └───────────────────┘
  Index              Data File

SPARSE INDEX:
Entry for FIRST key in each block (requires sorted data)
┌───────────┐     ┌───────────────────┐
│ 10 → Block1│     │ Block1: 10,11,12  │
│ 40 → Block2│ ──→ │ Block2: 40,41,42  │
│ 70 → Block3│     │ Block3: 70,71,72  │
└───────────┘     └───────────────────┘

PRIMARY INDEX:
• On ordering key (data file sorted by this key)
• Usually sparse
• One per table

SECONDARY INDEX:
• On non-ordering field
• Always dense (data not sorted by this key)
• Multiple allowed per table

Example:
Employee table sorted by emp_id
• Primary index on emp_id (sparse OK)
• Secondary index on dept_id (must be dense)

B+ Tree Properties:
• Self-balancing tree
• All data in leaf nodes (internal = navigation only)
• Leaf nodes linked (for range queries)
• High fanout → short height → few disk I/Os

Order = m (max children per node)
• Each node: ceil(m/2) to m children
• Root: 2 to m children
• Leaf: ceil((m-1)/2) to (m-1) keys

                    [30 | 70]                 ← Internal (root)
                   /    |    \ 
                 /      |      \
          [10|20]    [40|50|60]   [80|90]     ← Internal
          /  |  \      / | | \      / | \
         /   |   \    /  | |  \    /  |  \
        ↓    ↓    ↓  ↓   ↓ ↓   ↓  ↓   ↓   ↓
       [Leaf nodes with actual data, linked together]
       
       Leaf: [5|10] ↔ [15|20|25] ↔ [30|35] ↔ ... 

# SEARCH (key = 45):
# 1. Start at root [30|70]
# 2. 30 < 45 < 70, go middle child [40|50|60]
# 3. 40 < 45 < 50, go second child
# 4. Reach leaf, search for 45
# Time: O(log_m n) where m = fanout

# INSERT (key = 55):
# 1. Find correct leaf
# 2. If space: insert in sorted order
# 3. If full: SPLIT leaf
#    - Move half keys to new leaf
#    - Insert separator key to parent
#    - If parent full: split propagates up

# DELETE (key = 45):
# 1. Find and remove from leaf
# 2. If node underflows (< ceil((m-1)/2) keys):
#    - Try to borrow from sibling
#    - Or merge with sibling
# 3. Merge may propagate to parent

-- Creating B+ Tree index
CREATE INDEX idx_salary ON Employee(salary);

-- Query using index
SELECT * FROM Employee WHERE salary = 50000;
-- Uses index: O(log n) instead of O(n)

-- Range query (uses linked leaves)
SELECT * FROM Employee WHERE salary BETWEEN 40000 AND 60000;
-- Find 40000 in tree, then scan linked leaves until 60000

hash(key) = key mod num_buckets

Example: 5 buckets
hash(12) = 12 mod 5 = 2  → Bucket 2
hash(47) = 47 mod 5 = 2  → Bucket 2 (collision!)
hash(35) = 35 mod 5 = 0  → Bucket 0

Bucket 0: [35, ...]
Bucket 1: []
Bucket 2: [12, 47, ...]  ← Overflow chain
Bucket 3: []
Bucket 4: []

Problem: Fixed buckets don't scale well!

Dynamic hashing - grows/shrinks as needed

Components:
• Global Depth (d): Bits used from hash to index
• Local Depth: Bits used by each bucket
• Directory: Points to buckets (size = 2^d)

Example: Global depth = 2 (4 directory entries)
Hash(key) → Binary → Use last 2 bits

Directory:        Buckets:
  00 ──────→ [A, B]  local depth = 2
  01 ──────→ [C, D]  local depth = 2  
  10 ─┐
  11 ─┴────→ [E, F]  local depth = 1

When bucket overflows:
1. If local depth < global depth: Just split bucket
2. If local depth = global depth: Double directory first

Grows one bucket at a time (no directory)

• Split pointer (p) indicates next bucket to split
• Two hash functions: h0 and h1
• When p reaches end, increment level

Growth: Triggered by overflow or load factor
Advantage: No directory, gradual growth

SQL Query
    ↓
Parser (Syntax check)
    ↓
Optimizer (Generate plan)
    ↓
Execution Engine
    ↓
Results

Optimizer considers:
• Available indexes
• Table statistics
• Join order
• Algorithm choices

Cost = # of disk I/Os (primary factor)

Key Statistics:
• n(R) = Number of tuples in R
• b(R) = Number of blocks/pages
• V(A,R) = Number of distinct values of A in R

Selection Selectivity:
σ_{A=v}(R) ≈ n(R) / V(A,R) tuples

Example:
Employee has 10,000 rows, 100 departments
SELECT * WHERE dept_id = 5
Estimated: 10,000/100 = 100 rows

# 1. NESTED LOOP JOIN
# For each tuple r in R:
#     For each tuple s in S:
#         if r.A = s.A: output (r, s)
# Cost: O(n * m) comparisons
# Disk I/O: b(R) + n(R) * b(S)

# 2. BLOCK NESTED LOOP
# For each BLOCK of R:
#     For each BLOCK of S:
#         For each tuple r in R-block:
#             For each tuple s in S-block:
#                 ...
# Cost: b(R) + b(R) * b(S) (better!)

# 3. INDEX NESTED LOOP
# For each tuple r in R:
#     Use index to find matching s in S
# Cost: b(R) + n(R) * (index lookup cost)

# 4. SORT-MERGE JOIN
# Sort both R and S on join attribute
# Merge sorted relations
# Cost: Sort + Merge = O(n log n + m log m)

# 5. HASH JOIN
# Build hash table on smaller relation
# Probe with tuples from larger relation
# Cost: O(n + m) if fits in memory

-- Query: SELECT * FROM A, B, C WHERE A.x = B.x AND B.y = C.y

-- Possible join orders:
-- (A ⋈ B) ⋈ C
-- (B ⋈ C) ⋈ A  
-- (A ⋈ C) ⋈ B
-- A ⋈ (B ⋈ C)
-- ... and more!

-- Optimizer picks order with lowest estimated cost
-- Uses dynamic programming or heuristics
-- Principle: Do selective operations first

EXPLAIN ANALYZE SELECT * FROM Employee WHERE salary > 50000;

-- Output shows:
-- - Access method (index scan vs sequential scan)
-- - Estimated rows
-- - Actual time
-- - Join methods used