import json
from datetime import datetime, timedelta
# Load entire flight dataset to memory
with open('flights.json', 'r') as f:
all_flights = json.load(f) # 50,000 flights
# Check every single flight
tomorrow_lax_jfk = []
tomorrow = datetime.now().date() + timedelta(days=1)
for flight in all_flights:
if (flight['departure'] == 'LAX' and
flight['arrival'] == 'JFK' and
flight['date'] == tomorrow and
flight['available_seats'] > 0):
tomorrow_lax_jfk.append(flight)
# Examined 50,000 records to find 3Structured Storage and Query Systems
EE 547 - Unit 4
Optimization Requires Structure
Without structure, these optimizations are impossible:
File: Every query is a full scan - no way to skip irrelevant data
Database: Structure lets us jump directly to what we need
Concurrent Access: The Lost Update Problem
Two users book the same flight simultaneously:
Without coordination, concurrent updates lose data. This isn’t rare - it happens whenever two users access the same record.
Operating System File Locks: Correctness vs Performance
File locking mechanism prevents corruption through mutual exclusion:
- OS kernel enforces exclusive access to file descriptors
fcntl.flock()system call blocks concurrent processes- Only one process can hold lock at a time
- Creates serialized execution bottleneck
Adding locks prevents corruption but eliminates concurrency:
import threading
import time
flight_lock = threading.Lock()
def book_seat(user):
# Everyone waits here
flight_lock.acquire()
try:
# Now only one user at a time
with open('flight.json', 'r') as f:
flight = json.load(f)
flight['seats'] -= 1
with open('flight.json', 'w') as f:
json.dump(flight, f)
finally:
flight_lock.release()
# Next user can proceed
Files create an impossible trade-off: concurrent access for performance, but coordination for correctness.
Reads During Writes: Inconsistent Data
Without coordination, readers see partial updates:
Files offer no isolation between readers and writers. Partial updates create states that should never exist.
Structure Changes Everything
Relational model: Data organized as sets with defined relationships
Relations aren’t just “tables” - they’re mathematical sets that enable query optimization and coordination.
Declarative Queries: Say What, Not How
The breakthrough: Describe the result, let the system figure out how
Declarative queries let the database choose optimal execution based on data distribution, available indexes, and system resources.
Transactions: The Coordination Solution
Databases provide ACID guarantees to solve concurrency:
Transactions ensure each operation sees a consistent view of data, even with concurrent access.
The Relational Model: Mathematical Structure for Data
What is a relational database?
A relational database organizes data using mathematical relations - structured sets of data that follow specific rules:
Relation (Table) - A named collection of related data
- Like a spreadsheet, but with strict rules
- Each relation has a fixed structure (schema)
- Contains zero or more rows of data
Tuple (Row) - A single record in a relation
- Represents one instance of the entity
- Contains values for each attribute
- No duplicate rows allowed in a relation
Attribute (Column) - A named property of the relation
- Has a specific data type (INTEGER, VARCHAR, etc.)
- Domain defines valid values for the attribute
- Order of attributes doesn’t matter mathematically
Unlike files or spreadsheets, relations have mathematical properties that enable optimization and ensure data consistency.
Foreign Keys: Connecting Relations
Foreign Keys - References Between Relations
A foreign key is an attribute (or combination) that refers to the primary key of another relation:
Purpose:
- Establish relationships between tables
- Maintain referential integrity
- Enable join operations
Referential integrity rules:
- Foreign key value must match an existing primary key value
- OR foreign key value can be NULL (if allowed)
- Cannot delete a referenced primary key row
- Cannot insert invalid foreign key values
Example: bookings.flight_id → flights.flight_id
- Every booking must reference a valid flight
- Cannot delete a flight that has bookings
- Cannot create booking for non-existent flight
Database enforces these rules automatically - attempts to violate referential integrity are rejected with an error.
Mathematical Foundation: Set Operations
SQL is based on mathematical set theory
Unlike programming with arrays or lists, SQL treats data as mathematical sets:
- No inherent order (until you specify ORDER BY)
- No duplicate rows (unless you specify ALL)
- Operations follow set algebra rules
This mathematical foundation allows the database to:
- Rearrange operations for efficiency
- Apply optimization rules automatically
- Guarantee consistent results regardless of data size
Query Processing: Parse, Plan, Execute
Understanding how databases process your SQL
When you write a query, the database follows three phases:
1. Parse & Validate
- Check syntax and table/column names
- Verify you have permissions
- Build internal query tree
2. Plan Optimization
- Files cannot do this optimization
- Analyze multiple execution strategies
- Choose lowest-cost approach based on data statistics
- Consider available indexes and join algorithms
3. Execute
- Run the optimized plan
- Return results
The same SQL can execute differently as your data grows, always choosing the most efficient path.
JOIN Operations: Combining Data Sources
Moving beyond single-table queries
Real-world data is normalized across multiple tables to avoid redundancy and maintain consistency. JOINs recombine this data for analysis.
File processing limitations:
- Employee data in
employees.json
- Department data in
departments.json - To get “employee name with department”, you need custom code to link them
Database solution:
- Tables are linked by foreign key relationships
- JOIN operations combine tables based on these relationships
- Database optimizes the combination process
Mathematical foundation: JOINs implement relational algebra operations on sets, allowing precise control over how tables combine.
Our flight database has natural relationships that JOINs exploit.
Cartesian Product: The Foundation
Understanding the mathematical basis of JOINs
Every JOIN operation starts with the Cartesian product - every row from table A combined with every row from table B.
Example:
- Table A has 3 rows
- Table B has 4 rows
- Cartesian product has 3 × 4 = 12 rows
Cartesian product implications:
- This is computationally expensive
- Most combinations are meaningless
- JOINs add conditions to filter down to useful combinations
A JOIN is a Cartesian product followed by filtering. The database optimizer finds efficient ways to compute this without actually creating the full Cartesian product.
INNER JOIN: Meaningful Combinations Only
Filtering the Cartesian product to useful rows
INNER JOIN keeps only combinations where the join condition is TRUE.
Syntax:
Most common pattern - Foreign Key JOINs:
What happens:
- Database considers all flight-aircraft combinations
- Keeps only pairs where IDs match
- Returns combined information
Result: Only flights that have matching aircraft records. Orphaned records (flights without aircraft, aircraft without flights) are excluded.
Performance: Database uses indexes on join columns to avoid full Cartesian product computation.
query = """
SELECT
f.flight_number,
f.departure_airport,
a.model,
a.capacity
FROM flights f
INNER JOIN aircraft a ON f.aircraft_id = a.aircraft_id
LIMIT 5
"""
print(run_sql(query))| flight_number | departure_airport | model | capacity |
|:----------------|:--------------------|:-----------------|-----------:|
| UA101 | JFK | Airbus A320 | 180 |
| UA102 | JFK | Boeing 777-300ER | 396 |
| UA103 | JFK | Airbus A350-900 | 325 |
| UA104 | JFK | Boeing 787-9 | 296 |
| UA105 | JFK | Airbus A321 | 220 |
5 rows | 3.5 msLEFT OUTER JOIN: Preserving Left Table
Keeping all rows from the left table
LEFT JOIN returns all rows from the left table, plus matching rows from the right table. When no match exists, NULL values fill the right table columns.
Use case: “Show all flights, and aircraft info when available”
- Maybe some flights don’t have aircraft assigned yet
- You still want to see those flights in results
- Aircraft columns will be NULL for unmatched flights
Syntax pattern:
Mental model:
- Start with complete left table
- Add right table data where possible
- Fill gaps with NULL
When to use: Analysis requiring complete left table data, even when relationships are incomplete.
query = """
SELECT
f.flight_number,
f.departure_airport,
a.model,
CASE WHEN a.aircraft_id IS NULL
THEN 'No aircraft assigned'
ELSE a.model
END as aircraft_status
FROM flights f
LEFT JOIN aircraft a ON f.aircraft_id = a.aircraft_id
WHERE a.aircraft_id IS NULL
LIMIT 3
"""
print("### Flights without aircraft")
print(run_sql(query))### Flights without aircraft
No results returned | 4.2 msRIGHT and FULL OUTER JOINs
Complete outer join patterns
RIGHT JOIN: Mirror of LEFT JOIN
- Preserves all rows from right table
- Adds left table data where matches exist
- Less commonly used (can rewrite as LEFT JOIN)
FULL OUTER JOIN: Union of LEFT and RIGHT
- Preserves all rows from both tables
- NULL fills gaps in either direction
- Useful for complete relationship analysis
Practical example:
- All aircraft and all flights
- See which aircraft have no flights scheduled
- See which flights have no aircraft assigned
- Complete operational picture
FULL OUTER JOINs are expensive - they process both tables completely.
query = """
SELECT
COALESCE(f.flight_number, 'No flights') as flight_info,
COALESCE(a.model, 'No aircraft') as aircraft_info,
CASE
WHEN f.flight_id IS NULL THEN 'Unused aircraft'
WHEN a.aircraft_id IS NULL THEN 'Unassigned flight'
ELSE 'Matched'
END as relationship_status
FROM flights f
FULL OUTER JOIN aircraft a ON f.aircraft_id = a.aircraft_id
WHERE f.flight_id IS NULL OR a.aircraft_id IS NULL
LIMIT 5
"""
print("### Unmatched records")
print(run_sql(query))### Unmatched records
No results returned | 4.6 msMultiple Table JOINs
Building complex queries with multiple relationships
Real analysis often requires data from 3+ tables. JOINs can be chained to follow relationship paths.
Pattern:
Execution process:
- Database joins first two tables
- Result becomes input to next join
- Process continues left-to-right
Join order optimization: Database may reorder joins for efficiency based on:
- Table sizes
- Available indexes
- Selectivity of conditions
Example scenario: “Show passenger names, flight details, and aircraft type for bookings”
- Requires: bookings → flights → aircraft
- Also needs: bookings → passengers
query = """
SELECT
p.first_name || ' ' || p.last_name as passenger,
f.flight_number,
f.departure_airport || '→' || f.arrival_airport as route,
a.model,
b.seat
FROM bookings b
JOIN passengers p ON b.passenger_id = p.passenger_id
JOIN flights f ON b.flight_id = f.flight_id
JOIN aircraft a ON f.aircraft_id = a.aircraft_id
LIMIT 5
"""
print(run_sql(query))| passenger | flight_number | route | model | seat |
|:-------------------|:----------------|:--------|:-----------------|:-------|
| First_456 Last_456 | UA101 | JFK→DFW | Airbus A320 | A12 |
| First_413 Last_413 | UA129 | JFK→DFW | Airbus A321 | C23 |
| First_297 Last_297 | UA142 | JFK→DFW | Boeing 777-300ER | C30 |
| First_86 Last_86 | UA101 | JFK→DFW | Airbus A320 | A1 |
| First_459 Last_459 | UA101 | JFK→DFW | Airbus A320 | A14 |
5 rows | 6.6 msJOIN Performance and Optimization
How databases make JOINs efficient
Naive approach: Actually compute Cartesian product, then filter
- 1000 flights × 50 aircraft = 50,000 combinations to check
- Completely impractical for large tables
Optimized approaches:
- Nested Loop Join - For each row in left table, scan right table
- Hash Join - Build hash table on smaller table, probe with larger
- Merge Join - Sort both tables, merge in order
Database chooses based on:
- Table sizes and available memory
- Whether indexes exist on join columns
- Estimated selectivity of join conditions
Index importance: Foreign key columns should always be indexed. This transforms O(n×m) operations into O(n log m).
Query planning: EXPLAIN shows chosen join strategy and estimated costs.
query = """
EXPLAIN (COSTS OFF, BUFFERS OFF)
SELECT f.flight_number, a.model
FROM flights f
JOIN aircraft a ON f.aircraft_id = a.aircraft_id
WHERE f.departure_airport = 'LAX'
LIMIT 3
"""
result, _ = execute_query(query)
print("### Query execution plan:")
for row in result['QUERY PLAN'].head(4):
print(f" {row}")### Query execution plan:
Limit
-> Nested Loop
Join Filter: (a.aircraft_id = f.aircraft_id)
-> Seq Scan on flights fCommon JOIN Pitfalls
Avoiding expensive mistakes
1. Missing JOIN conditions
Results in flights × aircraft combinations - extremely expensive.
2. Wrong JOIN type
- Using INNER JOIN when you need LEFT JOIN loses data
- Using LEFT JOIN when you need INNER JOIN includes NULLs
3. Joining on wrong columns
- Join conditions must make logical sense
- Usually primary key to foreign key relationships
4. Multiple conditions in ON vs WHERE
- Conditions in ON clause: applied during join
- Conditions in WHERE clause: applied after join
- Different results with OUTER JOINs
Performance impact: These mistakes can turn millisecond queries into minute-long disasters.
Row count verification:
query = """
SELECT
COUNT(*) as total_rows,
COUNT(DISTINCT f.flight_id) as unique_flights,
COUNT(DISTINCT a.aircraft_id) as unique_aircraft
FROM flights f
JOIN aircraft a ON f.aircraft_id = a.aircraft_id
"""
print("### Sanity check JOIN results")
print(run_sql(query))### Sanity check JOIN results
| total_rows | unique_flights | unique_aircraft |
|-------------:|-----------------:|------------------:|
| 200 | 200 | 8 |
1 rows | 4.1 msScalar Subqueries: Single Value Results
Subqueries that return exactly one value
Scalar subqueries can appear anywhere a single value is expected:
- WHERE clauses for comparisons
- SELECT clauses for computed columns
- HAVING clauses for aggregate comparisons
Execution model:
- Database executes subquery first
- Uses returned value in outer query
- If subquery returns multiple rows → error
- If subquery returns no rows → NULL
Performance consideration: Scalar subqueries in SELECT are executed once per output row. Use JOINs when possible for better performance.
# Subquery in SELECT clause
query = """
SELECT
departure_airport,
COUNT(*) as flights,
(SELECT COUNT(*) FROM flights) as total_flights,
ROUND(COUNT(*)::decimal / (SELECT COUNT(*) FROM flights) * 100, 1) as percentage
FROM flights
GROUP BY departure_airport
ORDER BY flights DESC
LIMIT 4
"""
print("### Airport market share")
print(run_sql(query))### Airport market share
| departure_airport | flights | total_flights | percentage |
|:--------------------|----------:|----------------:|-------------:|
| JFK | 200 | 200 | 100 |
1 rows | 4.8 msIN and EXISTS: Set Membership Testing
Two approaches for “find records that relate to others”
IN subqueries:
# Find passengers who have bookings
query = """
SELECT
first_name,
last_name,
email
FROM passengers
WHERE passenger_id IN (
SELECT DISTINCT passenger_id
FROM bookings
)
LIMIT 5
"""
print("### Passengers with bookings (IN)")
print(run_sql(query))### Passengers with bookings (IN)
| first_name | last_name | email |
|:-------------|:------------|:---------------------|
| First_1 | Last_1 | passenger1@email.com |
| First_2 | Last_2 | passenger2@email.com |
| First_3 | Last_3 | passenger3@email.com |
| First_4 | Last_4 | passenger4@email.com |
| First_5 | Last_5 | passenger5@email.com |
5 rows | 4.2 msEXISTS subqueries:
# Same result using EXISTS
query = """
SELECT
first_name,
last_name,
email
FROM passengers p
WHERE EXISTS (
SELECT 1
FROM bookings b
WHERE b.passenger_id = p.passenger_id
)
LIMIT 5
"""
print("### Passengers with bookings (EXISTS)")
print(run_sql(query))### Passengers with bookings (EXISTS)
| first_name | last_name | email |
|:-------------|:------------|:---------------------|
| First_1 | Last_1 | passenger1@email.com |
| First_2 | Last_2 | passenger2@email.com |
| First_3 | Last_3 | passenger3@email.com |
| First_4 | Last_4 | passenger4@email.com |
| First_5 | Last_5 | passenger5@email.com |
5 rows | 4.4 msPerformance difference: EXISTS stops at first match; IN builds complete list. EXISTS is often faster for large subquery results.
Window Functions: Row-by-Row Analysis
Analytical functions that operate over sets of related rows
Traditional aggregation collapses multiple rows into single results. Window functions perform calculations across row sets while preserving individual rows.
Window functions add analytical context to each row without losing the original data structure.
Analytical Functions: Running Calculations
Cumulative sums, moving averages, and lead/lag comparisons
# Running totals and comparisons
query = """
SELECT
departure_airport,
scheduled_departure::date as flight_date,
passenger_count,
SUM(passenger_count) OVER (
PARTITION BY departure_airport
ORDER BY scheduled_departure
ROWS UNBOUNDED PRECEDING
) as running_total,
AVG(passenger_count) OVER (
PARTITION BY departure_airport
ORDER BY scheduled_departure
ROWS 2 PRECEDING
)::int as three_day_avg,
LAG(passenger_count, 1) OVER (
PARTITION BY departure_airport
ORDER BY scheduled_departure
) as prev_flight_passengers
FROM flights
WHERE departure_airport = 'LAX'
AND scheduled_departure >= '2024-01-15'
AND scheduled_departure < '2024-01-18'
ORDER BY scheduled_departure
LIMIT 8
"""
print("### Time-series analysis with window functions")
print(run_sql(query))### Time-series analysis with window functions
Error: Execution failed on sql '
SELECT
departure_airport,
scheduled_departure::date as flight_date,
passenger_count,
SUM(passenger_count) OVER (
PARTITION BY departure_airport
ORDER BY scheduled_departure
ROWS UNBOUNDED PRECEDING
) as running_total,
AVG(passenger_count) OVER (
PARTITION BY departure_airport
ORDER BY scheduled_departure
ROWS 2 PRECEDING
)::int as three_day_avg,
LAG(passenger_count, 1) OVER (
PARTITION BY departure_airport
ORDER BY scheduled_departure
) as prev_flight_passengers
FROM flights
WHERE departure_airport = 'LAX'
AND scheduled_departure >= '2024-01-15'
AND scheduled_departure < '2024-01-18'
ORDER BY scheduled_departure
LIMIT 8
': column "passenger_count" does not exist
LINE 5: passenger_count,
^
Frame specifications control the calculation window:
ROWS UNBOUNDED PRECEDING- from start to current rowROWS 2 PRECEDING- previous 2 rows plus current
ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING- centered 3-row window
LAG/LEAD functions access neighboring rows:
LAG(column, 1)- value from previous rowLEAD(column, 2)- value from 2 rows ahead- Perfect for period-over-period comparisons
SQL vs File Processing: The Complete Picture
File-based approach limitations:
SQL database advantages:
Performance comparison for complex analysis:
- File processing: 100+ lines of code, 5+ seconds execution, high error potential
- SQL: 30 lines, < 100ms execution, database-guaranteed correctness
SQL provides the same abstraction benefit as high-level programming languages - focus on problem logic rather than implementation details.
Next section: Database design principles for building maintainable systems.
Entity-Relationship Model Fundamentals
Systematic approach to modeling real-world data
The Entity-Relationship (ER) model provides a formal method for converting real-world concepts into database structures:
Entity - A distinguishable object or concept
- Represents a “thing” we want to store data about
- Examples: Flight, Passenger, Aircraft, Route
- Becomes a table in the relational model
Attribute - A property or characteristic of an entity
- Describes specific aspects of the entity
- Examples: flight_number, departure_time, passenger_name
- Becomes columns in the relational table
Relationship - An association between two or more entities
- Describes how entities interact or connect
- Examples: Passenger books Flight, Flight uses Aircraft
- Implemented through foreign keys and linking tables
Domain - The set of valid values for an attribute
- Defines data type and constraints
- Examples: flight_number must be alphanumeric, passenger_count ≥ 0
ER Diagram symbols:
- Rectangle = Entity
- Oval = Attribute
- Diamond = Relationship
- Underline = Primary Key
Mathematical foundation: ER modeling creates a formal specification that can be algorithmically converted to relational schema.
Relationship Types and Cardinality
Cardinality defines how many instances can participate in relationships
One-to-One (1:1) - Each entity instance relates to at most one instance of another entity
- Example: Aircraft ← assigned to → Flight (at any given time)
- Implementation: Foreign key in either table
- Rare in practice, often indicates entities should be combined
One-to-Many (1:N) - One entity instance relates to many instances of another entity
- Example: Aircraft → operates → Flights (one aircraft, many flights over time)
- Implementation: Foreign key in the “many” side table
- Most common relationship type
Many-to-Many (M:N) - Many instances of each entity can relate to many instances of the other
- Example: Passengers ←→ Flights (passengers can book multiple flights, flights carry multiple passengers)
- Implementation: Requires separate linking table
- Cannot be directly represented with simple foreign keys
Participation constraints:
- Total participation - Every entity instance must participate
- Partial participation - Some entity instances may not participate
Cardinality determines the physical implementation strategy in the relational model.
ER Diagram Construction Process
Systematic approach to building ER diagrams
Step 1: Identify Entities
- Look for nouns in requirements that represent distinct concepts
- Ask: “What things do we need to store data about?”
- Examples: Student, Course, Instructor, Room, Enrollment
Step 2: Identify Attributes
- Determine properties needed for each entity
- Identify which attribute(s) can serve as primary key
- Consider data types and constraints
Step 3: Identify Relationships
- Look for verbs connecting entities
- Determine cardinality for each relationship
- Identify any attributes that belong to relationships
Step 4: Validate the Model
- Can you answer all required queries?
- Are there redundant relationships?
- Do cardinalities make sense in the real world?
- Are primary keys unique and stable?
Common mistakes to avoid:
- Making attributes into entities
- Missing M:N relationships
- Incorrect cardinality specifications
Start simple and add complexity incrementally. Validate each step against real-world requirements.
Weak Entities and Identifying Relationships
Some entities cannot exist independently
Weak Entity - An entity that cannot be uniquely identified by its own attributes alone
- Depends on another entity (owner entity) for identification
- Primary key includes the owner entity’s primary key
- Common in hierarchical or dependent relationships
Identifying Relationship - The relationship that connects a weak entity to its owner
- Weak entity has total participation in this relationship
- Relationship is often 1:N from owner to weak entity
Examples:
Room (weak) depends on Building (owner)
- Room number alone isn’t unique (Room 101 in multiple buildings)
- Key: (building_id, room_number)
Order_Item (weak) depends on Order (owner)
- Line item number alone isn’t unique
- Key: (order_id, line_item_number)
Implementation: Weak entity table includes owner’s primary key as part of its composite primary key
Weak entities are common in real systems and require careful primary key design to maintain uniqueness.
Complex Relationship Patterns
Advanced ER modeling scenarios
Ternary Relationships - Relationships involving three entities
- Cannot be decomposed into binary relationships without loss of information
- Example: Student-Course-Instructor (a student takes a course with a specific instructor)
- Implementation: Single linking table with three foreign keys
Recursive Relationships - An entity related to itself
- Example: Employee manages Employee, Course has Prerequisite Course
- Implementation: Foreign key in same table referencing its own primary key
- May be 1:1, 1:N, or M:N
Multiple Relationships - Two entities connected by more than one relationship
- Example: Employee works_for Department, Employee manages Department
- Each relationship has different semantics and cardinality
- Implementation: Separate foreign keys or linking tables
ISA Relationships (Inheritance) - Subtype/supertype hierarchies
- Example: Person → Student, Faculty (inheritance)
- Implementation options: Single table, table per subtype, or table per hierarchy
- Choice depends on overlap and query patterns
These patterns require careful analysis to choose optimal relational representation.
Implementation example:
-- Ternary relationship
CREATE TABLE enrollments (
student_id INTEGER,
course_id INTEGER,
instructor_id INTEGER,
semester VARCHAR(10),
grade CHAR(2),
PRIMARY KEY (student_id, course_id,
instructor_id, semester)
);
-- Recursive relationship
CREATE TABLE employees (
employee_id INTEGER PRIMARY KEY,
name VARCHAR(100),
manager_id INTEGER,
FOREIGN KEY (manager_id)
REFERENCES employees(employee_id)
);Complex patterns require analyzing business rules and query requirements to choose implementation methods.
Composite Keys: When Multiple Attributes Define Uniqueness
Composite keys occur when no single attribute uniquely identifies records. The key design impacts both logical constraints and physical performance.
Query optimization with composite keys:
# Show index usage patterns
query = """
EXPLAIN (COSTS OFF, TIMING OFF)
SELECT passenger_id, price
FROM bookings
WHERE flight_id = 1 AND seat = '12A'
"""
result, _ = execute_query(query)
print("### Composite key lookup (optimal):")
for row in result['QUERY PLAN'].head(2):
print(f" {row}")### Composite key lookup (optimal):
Index Scan using bookings_flight_id_seat_key on bookings
Index Cond: ((flight_id = 1) AND ((seat)::text = '12A'::text))# Partial key usage
query = """
EXPLAIN (COSTS OFF, TIMING OFF)
SELECT passenger_id, price
FROM bookings
WHERE flight_id = 1
"""
result, _ = execute_query(query)
print("### Leading key column only (still uses index):")
for row in result['QUERY PLAN'].head(2):
print(f" {row}")### Leading key column only (still uses index):
Index Scan using idx_bookings_flight on bookings
Index Cond: (flight_id = 1)Column order in composite keys matters. The most selective or frequently queried column should be first, as B-tree indexes can only efficiently support left-to-right key prefixes.
Key Design Patterns and Performance Impact
The choice of key design affects not just data integrity, but system performance, storage efficiency, and maintainability. Different patterns serve different architectural needs.
Sequential integers provide optimal performance characteristics:
- B-tree insertion always occurs at the right edge, minimizing page splits
- Minimal storage footprint (4 bytes)
- Efficient foreign key joins through integer comparison
- Potential vulnerability: sequential values may leak information about record creation patterns
UUIDs offer global uniqueness at performance cost:
- 128-bit storage requirement (4× larger than integers)
- Random insertion patterns increase B-tree fragmentation
- Eliminates central coordination requirements in distributed systems
- Preferred when records must be unique across multiple databases
Composite keys preserve semantic relationships:
- Foreign key storage scales linearly with component count
- Join complexity increases with key width
- Index maintenance overhead grows with key size
- Column ordering directly impacts query performance patterns
Production systems typically use auto-incrementing integers for primary keys while maintaining natural key uniqueness through alternate indexes. This approach optimizes for system performance while preserving semantic access patterns.
Functional Dependencies: Mathematical Basis for Decomposition
Functional dependencies define mathematical relationships between attributes that govern how tables can be decomposed without information loss.
Functional dependency notation: A → B means “A functionally determines B”
- For every value of A, there exists exactly one value of B
- If two tuples have the same A value, they must have the same B value
- Violation indicates data inconsistency or incorrect schema design
Mathematical properties of functional dependencies:
- Reflexivity: If Y ⊆ X, then X → Y (trivial dependency)
- Augmentation: If X → Y, then XZ → YZ for any Z
- Transitivity: If X → Y and Y → Z, then X → Z
First Normal Form: Eliminating Repeating Groups
1NF requires that all attribute values be atomic - no repeating groups or nested structures within table cells.
1NF transformation process:
- Identify repeating groups within table cells
- Create separate rows for each value in the repeating group
- Add appropriate identifiers to maintain relationships
- Ensure each cell contains only atomic values
Result: Information is preserved but redundancy increases. Further normalization addresses redundancy issues.
Second Normal Form: Eliminating Partial Dependencies
2NF requires 1NF plus elimination of partial functional dependencies - no non-key attribute depends on only part of a composite primary key.
2NF decomposition algorithm:
- Identify composite primary key and all functional dependencies
- Find attributes that depend on only part of the primary key (partial dependencies)
- Create separate table for each partial dependency
- Remove partially dependent attributes from original table
- Use foreign keys to maintain relationships
Eliminates update anomalies where changing one attribute requires updating multiple rows.
Third Normal Form: Removing Transitive Dependencies
3NF requires 2NF plus elimination of transitive functional dependencies - no non-key attribute depends on another non-key attribute.
3NF decomposition process:
- Identify all functional dependencies in the table
- Find transitive dependencies: A → B → C where A is the primary key
- Create separate table for the transitive dependency (B → C)
- Remove transitively dependent attributes from original table
- Keep the intermediate attribute as foreign key
Trade-off consideration: 3NF eliminates redundancy but requires joins to reconstruct complete information.
Denormalization: Performance vs Redundancy Trade-offs
Denormalization deliberately introduces redundancy to improve query performance, reversing the normalization process for specific use cases.
Denormalization decision criteria:
Read-heavy workloads benefit most from denormalization:
- Reporting systems with complex aggregations
- Analytics platforms requiring fast dashboard queries
- E-commerce product catalogs with frequent browsing
Write-heavy workloads suffer from denormalization:
- Transaction processing systems
- Real-time data ingestion
- Systems requiring strict consistency
Selective denormalization strategies:
- Calculated columns: Store computed values (order totals, tax amounts)
- Flattened tables: Merge frequently joined tables into single table
- Summary tables: Pre-aggregate data at different time granularities
- Redundant foreign key data: Store commonly accessed related attributes
Maintenance considerations:
- Update multiple locations when source data changes
- Implement triggers or application logic to maintain consistency
- Monitor for data drift between redundant copies
- Plan for increased storage requirements
Denormalization should be applied selectively based on measured performance bottlenecks rather than preemptive optimization.
B-tree Indexes Reduce Query Complexity from O(n) to O(log n)
Without index: sequential scan reads every row
query = """
SELECT * FROM users WHERE email = 'alice@example.com';
"""
print("-- Scans all 1M users to find one record")
print("-- Reads: 1,000,000 rows")
print("-- Time: 250ms")-- Scans all 1M users to find one record
-- Reads: 1,000,000 rows
-- Time: 250msWith B-tree index: logarithmic search
query = """
CREATE INDEX idx_users_email ON users(email);
SELECT * FROM users WHERE email = 'alice@example.com';
"""
print("-- Traverses tree structure")
print("-- Reads: 3-4 index pages + 1 data page")
print("-- Time: 2ms")-- Traverses tree structure
-- Reads: 3-4 index pages + 1 data page
-- Time: 2msWhy B-trees work: Tree height grows slowly. Even 1 billion records need only 4-5 levels.
Single vs Composite Indexes
Index structure determines which queries can be optimized
Hierarchical Data: Trees in Relational Tables
Organizational charts, category trees, and nested data structures
Adjacency List (most common):
CREATE TABLE categories (
id INTEGER PRIMARY KEY,
name VARCHAR(100),
parent_id INTEGER REFERENCES categories(id)
);
-- Find all children of category 5
WITH RECURSIVE subcategories AS (
SELECT id, name FROM categories WHERE id = 5
UNION ALL
SELECT c.id, c.name
FROM categories c
JOIN subcategories s ON c.parent_id = s.id
)
SELECT * FROM subcategories;Good for: Frequent inserts, simple parent-child queries
Path Enumeration (for read-heavy):
CREATE TABLE categories (
id INTEGER PRIMARY KEY,
name VARCHAR(100),
path VARCHAR(255) -- '/1/3/7/'
);
-- Find all descendants of category 3
SELECT * FROM categories
WHERE path LIKE '/1/3/%';
-- Find depth
SELECT *, LENGTH(path) - LENGTH(REPLACE(path, '/', '')) - 1 as depth
FROM categories;Good for: Fast subtree queries, read-heavy workloads
Choice depends on query patterns: Adjacency lists for frequent updates, path enumeration for read-heavy analytics.
Partitioning: Splitting Large Tables
When single tables become too large for efficient queries or maintenance
Horizontal partitioning strategies:
# Range partitioning (common for time-series)
query = """
CREATE TABLE events (
id SERIAL,
user_id INTEGER,
event_type VARCHAR(50),
event_date DATE,
data JSONB
) PARTITION BY RANGE (event_date);
CREATE TABLE events_2024_q1 PARTITION OF events
FOR VALUES FROM ('2024-01-01') TO ('2024-04-01');
"""
print("Range partitioning: Groups related data together")Range partitioning: Groups related data together# Hash partitioning (for even distribution)
query = """
CREATE TABLE user_events (
user_id INTEGER,
event_data JSONB,
created_at TIMESTAMP
) PARTITION BY HASH (user_id);
CREATE TABLE user_events_0 PARTITION OF user_events
FOR VALUES WITH (MODULUS 4, REMAINDER 0);
"""
print("Hash partitioning: Spreads load evenly across partitions")Hash partitioning: Spreads load evenly across partitionsWhen to partition:
- Tables > 100GB or queries consistently slow
- Clear partition key (date, user_id, geographic region)
- Most queries filter on partition key
NoSQL connection: Many NoSQL databases automatically partition (shard) data using similar hash/range strategies.
Concurrent Access Creates Race Conditions
Two processes accessing shared data simultaneously produce incorrect results
Process A:
# Check seat availability
query = """
SELECT seats_available FROM flights
WHERE flight_id = 'UA101';
"""
print("Returns: 1")
print()
# Update seat count
query = """
UPDATE flights SET seats_available = 0
WHERE flight_id = 'UA101';
INSERT INTO reservations
VALUES ('user_a', 'UA101', NOW());
"""
print("Executes successfully")Returns: 1
Executes successfullyProcess B (simultaneously):
# Same query at same time
query = """
SELECT seats_available FROM flights
WHERE flight_id = 'UA101';
"""
print("Returns: 1")
print()
# Same update
query = """
UPDATE flights SET seats_available = 0
WHERE flight_id = 'UA101';
INSERT INTO reservations
VALUES ('user_b', 'UA101', NOW());
"""
print("Also executes successfully")Returns: 1
Also executes successfully
Database state progression:
- Initial:
seats_available = 1 - Both processes read
seats_available = 1 - Both processes execute
UPDATE ... SET seats_available = 0 - Final:
seats_available = 0, but 2 reservations exist
Transaction Boundaries Provide Coordination
BEGIN/COMMIT creates atomic execution units
# Without transaction coordination
query = """
SELECT seats_available FROM flights WHERE flight_id = 'UA101';
-- Other processes can modify data here
UPDATE flights SET seats_available = seats_available - 1 WHERE flight_id = 'UA101';
INSERT INTO reservations VALUES ('user_a', 'UA101', NOW());
"""
print("Problem: Race condition between SELECT and UPDATE")Problem: Race condition between SELECT and UPDATE# With transaction coordination
query = """
BEGIN;
SELECT seats_available FROM flights WHERE flight_id = 'UA101' FOR UPDATE;
-- FOR UPDATE locks row, prevents concurrent modification
UPDATE flights SET seats_available = seats_available - 1 WHERE flight_id = 'UA101';
INSERT INTO reservations VALUES ('user_a', 'UA101', NOW());
COMMIT;
"""
print("Solution: Atomic execution prevents interference")Solution: Atomic execution prevents interferenceTransaction execution properties:
Transaction guarantees:
- Operations within BEGIN/COMMIT execute as single unit
- Other transactions cannot observe intermediate states
- Either all operations succeed (COMMIT) or all fail (ROLLBACK)
ACID Properties Address Specific Problems
Each property solves distinct classes of failures
ACID overview:
# Each property requires specific mechanisms
mechanisms = """
Atomicity: Write-ahead logging for rollback capability
Consistency: Constraint checking before commit
Isolation: Locking or timestamp-based concurrency control
Durability: Forced writes to persistent storage
"""
print(mechanisms)
Atomicity: Write-ahead logging for rollback capability
Consistency: Constraint checking before commit
Isolation: Locking or timestamp-based concurrency control
Durability: Forced writes to persistent storage
Database systems use coordinated mechanisms for reliable multi-user operation.
All-or-Nothing Execution
Atomicity prevents partial failures that leave systems in inconsistent states
Atomicity implementation:
# Money transfer with proper atomicity
query = """
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE account_id = 'A';
UPDATE accounts SET balance = balance + 100 WHERE account_id = 'B';
-- If any statement fails or system crashes: automatic ROLLBACK
COMMIT;
"""
print("Either both updates succeed, or both are undone")Either both updates succeed, or both are undoneWrite-ahead logging principle: Database logs all changes before applying them. Recovery process can undo incomplete transactions by reading the log.
Rollback Mechanisms
How databases implement all-or-nothing execution through logging
Write-ahead logging (WAL) sequence:
# What happens during transaction execution
sequence = """
1. BEGIN: Create transaction ID, start logging
2. UPDATE: Write change to log file (forced to disk)
3. UPDATE: Write second change to log file
4. COMMIT: Mark transaction complete in log
5. Later: Apply changes to database pages
Recovery after crash:
- Read log file
- Find incomplete transactions
- UNDO all changes from incomplete transactions
"""
print(sequence)
1. BEGIN: Create transaction ID, start logging
2. UPDATE: Write change to log file (forced to disk)
3. UPDATE: Write second change to log file
4. COMMIT: Mark transaction complete in log
5. Later: Apply changes to database pages
Recovery after crash:
- Read log file
- Find incomplete transactions
- UNDO all changes from incomplete transactions
Transaction states:
- Active: Executing statements
- Committed: All statements completed successfully
- Aborted: Failed or explicitly rolled back
Explicit rollback for application errors:
# Application-controlled rollback
query = """
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE account_id = 'A';
-- Check business rule
IF (SELECT balance FROM accounts WHERE account_id = 'A') < 0 THEN
ROLLBACK; -- Undo the UPDATE
ELSE
UPDATE accounts SET balance = balance + 100 WHERE account_id = 'B';
COMMIT;
END IF;
"""
print("Applications can explicitly undo transactions")Applications can explicitly undo transactionsRecovery guarantees: Any transaction that completed COMMIT before crash will survive. Any transaction that did not complete COMMIT will be completely undone.
Database Constraints vs Application Rules
Consistency divides responsibility between database structure and application logic
Database enforces structural integrity:
# Constraints enforced by database
query = """
CREATE TABLE accounts (
id VARCHAR(10) PRIMARY KEY,
balance DECIMAL(10,2) CHECK (balance >= 0),
account_type VARCHAR(20) NOT NULL,
customer_id INTEGER REFERENCES customers(id)
);
CREATE TABLE transfers (
from_account VARCHAR(10) REFERENCES accounts(id),
to_account VARCHAR(10) REFERENCES accounts(id),
amount DECIMAL(10,2) CHECK (amount > 0),
CHECK (from_account != to_account)
);
"""
print("Database prevents structurally invalid states")Database prevents structurally invalid statesApplication enforces business logic:
# Rules too complex for database constraints
rules = """
Business rules requiring application logic:
- "Premium customers get 2x rewards points"
- "Free shipping for orders over $100"
- "Refunds allowed within 30 days of purchase"
- "Students get 50% discount on weekdays"
- "Maximum 3 login attempts per hour"
Database cannot evaluate time-dependent or
complex conditional business rules.
"""
print(rules)
Business rules requiring application logic:
- "Premium customers get 2x rewards points"
- "Free shipping for orders over $100"
- "Refunds allowed within 30 days of purchase"
- "Students get 50% discount on weekdays"
- "Maximum 3 login attempts per hour"
Database cannot evaluate time-dependent or
complex conditional business rules.
Constraint checking during transactions:
# What happens when constraints are violated
query = """
BEGIN;
UPDATE accounts SET balance = balance - 500 WHERE id = 'A';
-- If account A only has $300, CHECK (balance >= 0) fails
UPDATE accounts SET balance = balance + 500 WHERE id = 'B';
COMMIT;
-- Result: ERROR - entire transaction rolled back
-- Both accounts remain unchanged
"""
print("Any constraint violation forces complete rollback")Any constraint violation forces complete rollbackConstraint enforcement timing:
Consistency guarantee: Database ensures no transaction can leave data in a state that violates declared constraints.
Concurrent Transaction Interference
Isolation prevents transactions from observing each other’s intermediate states
# Dirty read example
print("Transaction A:")
print("BEGIN;")
print("UPDATE accounts SET balance = 1000 WHERE id = 'savings';")
print("-- Balance changed to 1000, but not yet committed")
print()
print("Transaction B (simultaneously):")
print("SELECT balance FROM accounts WHERE id = 'savings';")
print("-- Without isolation: sees 1000")
print("-- With isolation: sees original value")
print()
print("Transaction A continues:")
print("ROLLBACK; -- Balance returns to original value")
print()
print("Problem: Transaction B made decisions based on data that never existed")Transaction A:
BEGIN;
UPDATE accounts SET balance = 1000 WHERE id = 'savings';
-- Balance changed to 1000, but not yet committed
Transaction B (simultaneously):
SELECT balance FROM accounts WHERE id = 'savings';
-- Without isolation: sees 1000
-- With isolation: sees original value
Transaction A continues:
ROLLBACK; -- Balance returns to original value
Problem: Transaction B made decisions based on data that never existedNon-repeatable reads within same transaction:
Phantom reads - new rows appear:
# Phantom read scenario
phantom_example = """
Transaction A:
SELECT * FROM orders WHERE date = '2024-01-15';
-- Returns 5 orders
-- Transaction B inserts new order with date = '2024-01-15'
Transaction A (repeats same query):
SELECT * FROM orders WHERE date = '2024-01-15';
-- Returns 6 orders - phantom row appeared
"""
print(phantom_example)
Transaction A:
SELECT * FROM orders WHERE date = '2024-01-15';
-- Returns 5 orders
-- Transaction B inserts new order with date = '2024-01-15'
Transaction A (repeats same query):
SELECT * FROM orders WHERE date = '2024-01-15';
-- Returns 6 orders - phantom row appeared
Applications assume database state remains consistent during transaction execution. Without isolation, business logic can make incorrect decisions.
Isolation Through Locking
Databases coordinate concurrent access through lock-based mechanisms
# Locking prevents interference
query = """
-- Transaction A
BEGIN;
SELECT * FROM inventory WHERE product_id = 'laptop' FOR UPDATE;
-- FOR UPDATE acquires exclusive lock on rows
-- Transaction B tries to modify same rows
UPDATE inventory SET quantity = quantity - 1 WHERE product_id = 'laptop';
-- BLOCKED - must wait for Transaction A to complete
-- Transaction A continues
UPDATE inventory SET quantity = quantity - 5 WHERE product_id = 'laptop';
COMMIT; -- Releases lock
-- Now Transaction B can proceed
"""
print("Lock coordination ensures serializable execution")Lock coordination ensures serializable executionLock types and behavior:
Deadlock detection:
# Deadlock scenario
deadlock = """
Transaction A:
UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
-- Locks account A
Transaction B:
UPDATE accounts SET balance = balance - 50 WHERE id = 'B';
-- Locks account B
Transaction A (waiting for B):
UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
Transaction B (waiting for A):
UPDATE accounts SET balance = balance + 50 WHERE id = 'A';
Result: DEADLOCK DETECTED
One transaction automatically rolled back
"""
print(deadlock)
Transaction A:
UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
-- Locks account A
Transaction B:
UPDATE accounts SET balance = balance - 50 WHERE id = 'B';
-- Locks account B
Transaction A (waiting for B):
UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
Transaction B (waiting for A):
UPDATE accounts SET balance = balance + 50 WHERE id = 'A';
Result: DEADLOCK DETECTED
One transaction automatically rolled back
Performance cost: Locking adds coordination overhead. Transactions may wait for locks, reducing concurrent throughput.
Isolation Levels: Performance vs Consistency Trade-offs
Isolation levels trade consistency guarantees for performance
Choosing isolation levels:
# Application-specific isolation choices
choices = """
Banking transfers: SERIALIZABLE
- Absolute consistency required
- Performance secondary to correctness
Web analytics: READ COMMITTED
- Occasional inconsistent reads acceptable
- High throughput more important
Reporting queries: REPEATABLE READ
- Consistent snapshots needed
- Can tolerate some phantom reads
Real-time dashboards: READ UNCOMMITTED
- Speed most important
- Dirty reads acceptable for approximate data
"""
print(choices)
Banking transfers: SERIALIZABLE
- Absolute consistency required
- Performance secondary to correctness
Web analytics: READ COMMITTED
- Occasional inconsistent reads acceptable
- High throughput more important
Reporting queries: REPEATABLE READ
- Consistent snapshots needed
- Can tolerate some phantom reads
Real-time dashboards: READ UNCOMMITTED
- Speed most important
- Dirty reads acceptable for approximate data
NoSQL connection: Many NoSQL databases default to weaker isolation levels (eventual consistency) to achieve higher performance and availability.
Committed Data Survives System Failures
Durability ensures completed transactions persist through crashes and hardware failures
# Durability guarantee test
scenario = """
User completes online order:
1. BEGIN;
2. INSERT INTO orders VALUES (12345, 'user123', 'laptop', 999.99);
3. UPDATE inventory SET quantity = quantity - 1 WHERE product = 'laptop';
4. COMMIT;
5. Application responds: "Order confirmed"
System crashes 10 seconds later.
Power restored, database restarts.
Question: Is order 12345 still in the database?
Answer: YES - durability guarantees committed data survives
"""
print(scenario)
User completes online order:
1. BEGIN;
2. INSERT INTO orders VALUES (12345, 'user123', 'laptop', 999.99);
3. UPDATE inventory SET quantity = quantity - 1 WHERE product = 'laptop';
4. COMMIT;
5. Application responds: "Order confirmed"
System crashes 10 seconds later.
Power restored, database restarts.
Question: Is order 12345 still in the database?
Answer: YES - durability guarantees committed data survives
Write-ahead logging ensures durability:
Durability performance cost:
# Performance impact of durability
comparison = """
Without forced writes (fsync disabled):
- 50,000 small transactions/second
- Risk: committed data lost on crash
With durability (fsync enabled):
- 5,000 small transactions/second
- Guarantee: committed data always survives
10x performance reduction for crash safety
"""
print(comparison)
Without forced writes (fsync disabled):
- 50,000 small transactions/second
- Risk: committed data lost on crash
With durability (fsync enabled):
- 5,000 small transactions/second
- Guarantee: committed data always survives
10x performance reduction for crash safety
Distributed durability through replication:
# Multiple machine durability
replication = """
Single machine durability:
- Write-ahead log on local disk
- Survives software crashes, some hardware failures
- Vulnerable to disk failure, fire, natural disasters
Multi-machine durability:
- Replicate commits to multiple servers
- Survives individual machine failures
- Higher availability but lower performance
- Required for mission-critical systems
"""
print(replication)
Single machine durability:
- Write-ahead log on local disk
- Survives software crashes, some hardware failures
- Vulnerable to disk failure, fire, natural disasters
Multi-machine durability:
- Replicate commits to multiple servers
- Survives individual machine failures
- Higher availability but lower performance
- Required for mission-critical systems
ACID properties guarantee reliable multi-user database operation, with each property addressing specific failure modes that would otherwise require complex application-level coordination.
Query Execution Plans Expose Performance Problems
EXPLAIN shows where databases spend time during query execution
# Slow query: Find popular products and their reviews
slow_query = """
SELECT p.name, p.price, AVG(r.rating), COUNT(r.*)
FROM products p
JOIN reviews r ON p.product_id = r.product_id
WHERE p.category = 'electronics'
GROUP BY p.product_id, p.name, p.price
ORDER BY COUNT(r.*) DESC
LIMIT 10;
-- Execution time: 2.3 seconds on 1M products, 5M reviews
"""
print("Query takes 2.3 seconds - where is the time spent?")Query takes 2.3 seconds - where is the time spent?# EXPLAIN reveals the execution plan
explain_output = """
EXPLAIN (ANALYZE, BUFFERS)
SELECT p.name, p.price, AVG(r.rating), COUNT(r.*)...
Limit (cost=180420.17..180420.19 rows=10) (actual time=2287.453..2287.455 rows=10)
-> Sort (cost=180418.67..180420.17 rows=599) (actual time=2287.451..2287.452 rows=10)
Sort Key: (count(r.*)) DESC
Sort Method: top-N heapsort Memory: 25kB
-> HashAggregate (cost=180389.67..180395.66 rows=599) (actual time=2287.021..2287.142 rows=245)
-> Hash Join (cost=15623.00..165389.67 rows=2000000) (actual time=156.234..1834.567 rows=1987543)
Hash Cond: (r.product_id = p.product_id)
-> Seq Scan on reviews r (cost=0.00..89034.00 rows=5000000) (actual time=0.034..456.123 rows=5000000)
-> Hash (cost=15610.50..15610.50 rows=1000) (actual time=156.189..156.189 rows=1000)
-> Seq Scan on products p (cost=0.00..15610.50 rows=1000) (actual time=0.045..156.078 rows=1000)
Filter: (category = 'electronics')
Rows Removed by Filter: 999000
"""
print("Sequential scans dominate execution time")Sequential scans dominate execution timePerformance breakdown from execution plan:
Reading execution plans:
- Seq Scan: Reading entire table - expensive for large tables
- Index Scan: Using index to find specific rows - fast for selective queries
- Hash Join: Build hash table from smaller relation, probe with larger
- Nested Loop: For each row in outer relation, find matches in inner
- Cost numbers: Database’s estimate of relative expense
- Actual time: Real measured execution time
Index creation eliminates sequential scans:
# Adding indexes transforms performance
index_creation = """
CREATE INDEX idx_products_category ON products(category);
CREATE INDEX idx_reviews_product_id ON reviews(product_id);
-- Same query now runs in 68ms instead of 2.3 seconds
-- Sequential scans replaced with index lookups
"""
print("Proper indexing strategy derived from execution plan analysis")Proper indexing strategy derived from execution plan analysisDatabase Optimizer Cost Calculations
Query planners evaluate multiple execution strategies and choose lowest estimated cost
Cost calculation factors:
# What influences optimizer decisions
cost_factors = """
Table statistics (updated by ANALYZE):
- Row counts: 100,000 customers, 500,000 orders
- Data distribution: 1000 customers in NYC (1%)
- Index selectivity: customer_id index 99% unique
Cost parameters:
- Sequential page read: cost 1.0
- Random page read: cost 4.0
- CPU tuple processing: cost 0.01
- Memory available: 256MB work_mem
Estimation logic:
- Nested loop good for small outer relation (1000 NYC customers)
- Hash join good when one side fits in memory
- Merge join good for pre-sorted data
"""
print(cost_factors)
Table statistics (updated by ANALYZE):
- Row counts: 100,000 customers, 500,000 orders
- Data distribution: 1000 customers in NYC (1%)
- Index selectivity: customer_id index 99% unique
Cost parameters:
- Sequential page read: cost 1.0
- Random page read: cost 4.0
- CPU tuple processing: cost 0.01
- Memory available: 256MB work_mem
Estimation logic:
- Nested loop good for small outer relation (1000 NYC customers)
- Hash join good when one side fits in memory
- Merge join good for pre-sorted data
When optimizer makes poor choices:
# Common optimizer failures
failures = """
Outdated statistics:
- Table grew from 1K to 1M rows
- Index selectivity changed dramatically
- Solution: Run ANALYZE more frequently
Parameter correlation:
- WHERE city = 'NYC' AND state = 'NY'
- Optimizer assumes independent conditions
- Reality: 100% correlation
- Solution: Multi-column statistics
Complex expressions:
- WHERE EXTRACT(year FROM order_date) = 2024
- Optimizer cannot use date indexes
- Solution: Add computed column or rewrite query
"""
print(failures)
Outdated statistics:
- Table grew from 1K to 1M rows
- Index selectivity changed dramatically
- Solution: Run ANALYZE more frequently
Parameter correlation:
- WHERE city = 'NYC' AND state = 'NY'
- Optimizer assumes independent conditions
- Reality: 100% correlation
- Solution: Multi-column statistics
Complex expressions:
- WHERE EXTRACT(year FROM order_date) = 2024
- Optimizer cannot use date indexes
- Solution: Add computed column or rewrite query
Statistics drive plan quality:
Optimizer effectiveness depends entirely on accurate table statistics. Regular ANALYZE operations maintain good query performance.
Connection Establishment Dominates Small Query Performance
Creating database connections requires significant overhead that dwarfs simple query execution
# Measuring connection vs query time
timing_test = """
# Without connection pooling
import time
import psycopg2
start = time.time()
conn = psycopg2.connect("postgresql://localhost/test") # 45ms
cursor = conn.cursor()
cursor.execute("SELECT count(*) FROM users") # 2ms
result = cursor.fetchone()
conn.close() # 3ms
total = time.time() - start
print(f"Total time: {total*1000:.1f}ms")
print("Connection overhead: 48ms (96% of total time)")
print("Query execution: 2ms (4% of total time)")
"""
print("Connection setup dominates performance for simple queries")Connection setup dominates performance for simple queriesConnection establishment process:
Connection pooling eliminates repeated overhead:
# With connection pooling
pooling_solution = """
# Application startup: Create connection pool
pool = psycopg2.pool.ThreadedConnectionPool(minconn=5, maxconn=20)
# Per request: Reuse existing connection
start = time.time()
conn = pool.getconn() # 0.1ms (from pool)
cursor = conn.cursor()
cursor.execute("SELECT count(*) FROM users") # 2ms
result = cursor.fetchone()
pool.putconn(conn) # 0.1ms (return to pool)
total = time.time() - start
print(f"Total time: {total*1000:.1f}ms")
print("Pool overhead: 0.2ms")
print("Query execution: 2ms")
print("27x faster than new connections")
"""
print("Connection pooling transforms performance for high-frequency queries")Connection pooling transforms performance for high-frequency queriesPool sizing considerations:
Pool sizing guidelines:
- Too small: Requests block waiting for available connections
- Too large: Memory waste, database connection limits
- Rule of thumb: 2-3x number of CPU cores for OLTP workloads
- Monitor: Connection wait time, pool utilization, database connection count
Single Machine Performance Boundaries
Vertical scaling reaches economic and physical limits at predictable points
# Measured single-node database limits
performance_limits = """
Write-heavy OLTP workload (PostgreSQL on high-end hardware):
- CPU: 64 cores, 2.5 GHz
- Memory: 512 GB RAM
- Storage: NVMe SSD array, 1M IOPS
- Network: 25 Gbps
Measured limits:
- Write throughput: ~15,000 transactions/second
- Read throughput: ~200,000 simple queries/second
- Concurrent connections: ~5,000 (limited by memory)
- Database size: ~10TB (before query performance degrades)
Bottleneck progression:
1. Disk I/O (solved with SSDs)
2. CPU (solved with more cores)
3. Lock contention (fundamental limit)
4. Memory bandwidth (hardware limit)
"""
print(performance_limits)
Write-heavy OLTP workload (PostgreSQL on high-end hardware):
- CPU: 64 cores, 2.5 GHz
- Memory: 512 GB RAM
- Storage: NVMe SSD array, 1M IOPS
- Network: 25 Gbps
Measured limits:
- Write throughput: ~15,000 transactions/second
- Read throughput: ~200,000 simple queries/second
- Concurrent connections: ~5,000 (limited by memory)
- Database size: ~10TB (before query performance degrades)
Bottleneck progression:
1. Disk I/O (solved with SSDs)
2. CPU (solved with more cores)
3. Lock contention (fundamental limit)
4. Memory bandwidth (hardware limit)
Scaling curves show saturation points:
Resource exhaustion patterns:
# What limits single-machine databases
bottlenecks = """
Storage I/O saturation:
- Random writes limited by disk seek time
- Solution: SSDs, but expensive for large datasets
CPU saturation:
- Complex query processing
- JSON/XML parsing overhead
- Solution: More cores, but diminishing returns
Memory pressure:
- Working set larger than available RAM
- Swapping kills performance
- Solution: More memory, but limited by motherboard
Lock contention:
- Hot rows accessed by many transactions
- Single-threaded bottlenecks
- Solution: Application redesign, not hardware
Network bandwidth:
- Large result sets
- Replication traffic
- Solution: Better queries, compression
"""
print(bottlenecks)
Storage I/O saturation:
- Random writes limited by disk seek time
- Solution: SSDs, but expensive for large datasets
CPU saturation:
- Complex query processing
- JSON/XML parsing overhead
- Solution: More cores, but diminishing returns
Memory pressure:
- Working set larger than available RAM
- Swapping kills performance
- Solution: More memory, but limited by motherboard
Lock contention:
- Hot rows accessed by many transactions
- Single-threaded bottlenecks
- Solution: Application redesign, not hardware
Network bandwidth:
- Large result sets
- Replication traffic
- Solution: Better queries, compression
Economic scaling wall:
# Cost analysis of vertical scaling
cost_analysis = """
Performance doubling costs:
2 cores → 4 cores: $1,000 → $2,000 (2x cost, 1.8x performance)
8 cores → 16 cores: $4,000 → $8,000 (2x cost, 1.6x performance)
32 cores → 64 cores: $16,000 → $50,000 (3x cost, 1.3x performance)
64 cores → 128 cores: $50,000 → $200,000 (4x cost, 1.1x performance)
Breaking point: ~32-64 cores
- Hardware costs grow exponentially
- Performance gains diminish
- Single point of failure remains
"""
print("Vertical scaling becomes economically inefficient beyond 32-64 cores")Vertical scaling becomes economically inefficient beyond 32-64 coresDistribution Creates New Problems
Moving to multiple machines solves capacity limits but introduces consistency and coordination challenges
# Query that works on single machine but fails distributed
problematic_query = """
-- Works fine on single PostgreSQL instance:
SELECT u.name, COUNT(o.order_id), SUM(o.total)
FROM users u
JOIN orders o ON u.user_id = o.user_id
WHERE u.registration_date > '2024-01-01'
GROUP BY u.user_id, u.name
ORDER BY SUM(o.total) DESC
LIMIT 100;
-- Fails when data is sharded across multiple databases:
-- users table on shard A (user_id 1-1000000)
-- orders table on shard B (user_id 1000001-2000000)
-- Cannot JOIN across different database servers
"""
print("Cross-shard JOINs require application-level coordination")Cross-shard JOINs require application-level coordinationRead replica lag introduces inconsistency:
Network partitions break assumptions:
# CAP theorem implications
cap_example = """
Banking system with accounts distributed across 3 servers:
Normal operation:
- All servers communicate
- Transfers between any accounts work
- Strong consistency maintained
Network partition scenario:
- Server A isolated from servers B and C
- Servers B and C can still communicate
Choice forced by partition:
1. Availability: Allow operations on both sides
- Risk: Account balances become inconsistent
- User withdraws $100 from A, $100 from B simultaneously
2. Consistency: Reject operations on minority side
- Server A refuses all operations (unavailable)
- Only servers B+C accept transactions
- Consistency maintained but reduced availability
Cannot have both perfect consistency and availability during partitions
"""
print(cap_example)
Banking system with accounts distributed across 3 servers:
Normal operation:
- All servers communicate
- Transfers between any accounts work
- Strong consistency maintained
Network partition scenario:
- Server A isolated from servers B and C
- Servers B and C can still communicate
Choice forced by partition:
1. Availability: Allow operations on both sides
- Risk: Account balances become inconsistent
- User withdraws $100 from A, $100 from B simultaneously
2. Consistency: Reject operations on minority side
- Server A refuses all operations (unavailable)
- Only servers B+C accept transactions
- Consistency maintained but reduced availability
Cannot have both perfect consistency and availability during partitions
Distributed coordination overhead:
Why NoSQL databases emerged:
Many applications discovered they could trade ACID guarantees for horizontal scalability:
- Eventual consistency instead of strong consistency
- Application-level joins instead of database joins
- Partition tolerance instead of perfect availability
- Simple queries instead of complex SQL
This creates the foundation for understanding NoSQL design choices in distributed systems.