Advanced Database Systems and Query Opti-
mization
Comprehensive Table of Contents
1. Relational Database Theory
2. Indexing Strategies and B-Trees
3. Query Execution and Optimization
4. Transaction Processing and ACID
5. Concurrency Control and Locking
6. Distributed Databases and Replication
7. Sharding and Partitioning Strategies
8. Column-Oriented Databases
9. Time-Series Databases
10. Search Engines and Inverted Indexes
11. Database Performance Tuning
12. Emerging Database Technologies
Chapter 1: Database Theory Fundamentals
1.1 Relational Model
Core Concepts:
Relation:
�� Table with rows and columns
�� Schema: Column names and types
�� Instance: Actual data at moment in time
�� Cardinality: Number of rows
�� Arity: Number of columns
Keys:
Primary Key:
�� Uniquely identifies each row
�� No NULL values allowed
�� One per table
�� Example: user_id in Users table
Candidate Key:
�� Could be primary key
�� Multiple candidates possible
�� Unique + not null
Foreign Key:
1
�� References primary key in another table
�� Enforces referential integrity
�� Example: user_id in Orders references Users
Unique Key:
�� Ensures uniqueness
�� Can be NULL
�� Multiple per table
�� Example: email addresses
Normalization:
Purpose:
�� Reduce data redundancy
�� Minimize anomalies
�� Improve data integrity
�� Make updates efficient
First Normal Form (1NF):
�� Atomic values only
�� No repeating groups
�� Single value per cell
�� Example: Separate address fields
Second Normal Form (2NF):
�� 1NF + No partial dependencies
�� Non-key attributes depend on entire key
�� Not just part of composite key
�� Example: Remove (StudentID, CourseID) → Instructor
Third Normal Form (3NF):
�� 2NF + No transitive dependencies
�� Non-key attributes depend only on key
�� Remove (StudentID) → City → Country
�� Example: City and Country separate
Boyce-Codd Normal Form (BCNF):
�� Stricter than 3NF
�� Every determinant is candidate key
�� Rare anomalies but complex
�� Not always necessary
Trade-offs:
Benefits of Normalization:
�� Less data redundancy
2
�� Easier updates
�� Prevents anomalies
�� Better maintainability
Costs:
�� More joins required
�� Performance may suffer
�� More complex queries
�� More tables to manage
Denormalization:
When to Denormalize:
�� Read-heavy workload
�� Performance critical
�� Acceptable redundancy
�� Historical data (data warehouse)
Strategy:
�� Calculated columns
�� Materialized views
�� Precomputed aggregates
�� Cached results
Example:
Normalized: Users(user_id, name) Orders(order_id, user_id, total) Or-
derItems(item_id, order_id, price, quantity)
Denormalized (for reporting): UserOrders(user_id, name, total_orders,
total_spent)
1.2 SQL and Query Language
Basic Operations:
SELECT:
```sql
SELECT column1, column2
FROM table
WHERE condition
ORDER BY column1
LIMIT 10;
INSERT:
3
INSERT INTO table (col1, col2, col3)
VALUES (val1, val2, val3);
INSERT INTO table
SELECT * FROM other_table WHERE condition;
UPDATE:
UPDATE table
SET col1 = val1, col2 = val2
WHERE condition;
DELETE:
DELETE FROM table
WHERE condition;
Joins:
INNER JOIN:
SELECT *
FROM users u
INNER JOIN orders o ON u.user_id = o.user_id;
-- Only matching rows
LEFT JOIN:
SELECT *
FROM users u
LEFT JOIN orders o ON u.user_id = o.user_id;
-- All users + matching orders (NULL if no orders)
RIGHT JOIN: �� All rows from right table �� Matching rows from left �� Opposite
of LEFT JOIN
FULL OUTER JOIN: �� All rows from both tables �� NULL where no match ��
Not all databases support (MySQL doesn’t)
CROSS JOIN: �� Cartesian product �� Every row from left × every row from
right �� Usually unintended result!
Aggregation:
GROUP BY:
SELECT user_id, COUNT(*) as order_count
FROM orders
GROUP BY user_id;
HAVING:
SELECT user_id, COUNT(*) as order_count
FROM orders
4
GROUP BY user_id
HAVING COUNT(*) > 5; -- Filter after aggregation
Subqueries:
Scalar Subquery (returns 1 row):
SELECT *
FROM users
WHERE user_id = (SELECT user_id FROM orders WHERE order_id = 123);
List Subquery:
SELECT *
FROM users
WHERE user_id IN (SELECT user_id FROM orders WHERE total > 1000);
Correlated Subquery:
SELECT *
FROM orders o1
WHERE [Link] > (
SELECT AVG([Link])
FROM orders o2
WHERE o2.user_id = o1.user_id
);
-- Slow but powerful
Window Functions:
ROW_NUMBER:
SELECT user_id, order_id, total,
ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY order_id) as rank
FROM orders;
RANK vs DENSE_RANK: �� RANK: 1, 2, 2, 4 (skips rank 3) �� DENSE_RANK:
1, 2, 2, 3 (no skip)
LAG/LEAD:
SELECT order_id, total,
LAG(total) OVER (ORDER BY order_id) as prev_total,
LEAD(total) OVER (ORDER BY order_id) as next_total
FROM orders;
Running Aggregate:
SELECT order_id, total,
SUM(total) OVER (ORDER BY order_id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
FROM orders;
---
5
## Chapter 2: Indexing and Query Optimization
### 2.1 Index Structures
B-Tree Index:
Structure: �� Balanced tree �� Logarithmic search: O(log n) �� Maintains sort
order �� Enables range queries �� Default for most databases
Properties:
[50]
/ \
[30] [70]
/ \ / \
[10][40][60][90]
�� All leaves at same depth �� Branching factor: How many children �� Typically
1000+ children per node �� Disk-friendly (many keys per page)
Advantages: �� Fast lookups �� Range queries �� Sorted output
Hash Index:
Structure: �� Hash function maps key to bucket �� O(1) average lookup �� No
ordering �� Good for equality
# Conceptual
bucket[hash("John")] = row_address
Advantages: �� Very fast for equality �� Simple implementation
Disadvantages: �� No range queries (hash lost order) �� Hash collisions need
handling �� Cannot use for sorting �� Cannot use for inequality (>, <)
Bitmap Index:
Use Case: �� Low cardinality columns �� Example: Gender (M/F), Status (Ac-
tive/Inactive)
Structure:
Gender = 'M': [1, 0, 1, 1, 0, 1, ...] (bitmap)
Gender = 'F': [0, 1, 0, 0, 1, 0, ...] (bitmap)
Advantages: �� Compact representation �� Fast AND/OR operations �� Good for
data warehouse
Disadvantages: �� Only for low cardinality �� Updates expensive �� Wasted space
if many values
Full-Text Index:
Purpose: �� Search text content �� Inverted index structure �� Fast full-text search
6
Structure:
word → [doc_id, doc_id, doc_id, ...]
"database" → [1, 5, 7, 23, ...]
"query" → [2, 5, 8, ...]
Example Query:
SELECT * FROM articles
WHERE MATCH(content) AGAINST('database AND query' IN BOOLEAN MODE);
Benefits: �� Natural language search �� Ranking by relevance �� Phrase search ��
Wildcard support
### 2.2 Query Optimization
Query Execution Plan:
Example:
SELECT [Link], COUNT(o.order_id) as orders
FROM users u
LEFT JOIN orders o ON u.user_id = o.user_id
WHERE [Link] = 'active'
GROUP BY u.user_id, [Link]
HAVING COUNT(o.order_id) > 5
ORDER BY orders DESC;
Execution Plan Steps: 1. Access users table → Filter status=‘active’ 2. Use
index on user_id 3. Join with orders 4. Group by user_id 5. Filter having
COUNT > 5 6. Sort by count
Index Usage:
Where Index Helps: �� WHERE clause: Filter rows quickly �� JOIN: Find match-
ing rows �� ORDER BY: Avoid sort operation �� MIN/MAX: Direct access to
endpoints
Where Index Doesn’t Help: �� SELECT *: Still must retrieve full rows �� Ag-
gregation without WHERE: Must scan all �� Functions in WHERE: WHERE
UPPER(name) = ‘JOHN’ �� Inequality on indexed column: Less benefit
Cost-Based Optimization:
Concept: �� Estimate cost of different plans �� Choose plan with minimum cost
�� Consider I/O, CPU, memory
Example:
Plan A: Index scan → Join → Sort
Cost: 100 index lookups + 50 comparisons
7
Plan B: Table scan → Filter → Join
Cost: 1,000,000 comparisons
Choose Plan A (lower cost)
EXPLAIN Keyword:
EXPLAIN SELECT * FROM users WHERE status = 'active';
-- Output shows:
-- - Which indexes used
-- - Number of rows examined
-- - Full table scan vs index scan
-- - Join order
-- - Sorting operations
“‘
Chapters 3-12 (Abbreviated)
[Continued sections on Query Execution, Transaction Processing, Concurrency
Control, Distributed Databases, Sharding, Columnar Databases, Time-Series
Databases, Search Engines, Performance Tuning, and Emerging Technologies -
maintaining same detailed technical pattern]
Conclusion
Database systems are critical infrastructure. Understanding theory and opti-
mization techniques ensures efficient data storage and retrieval.
Key takeaways: - Normalization reduces redundancy - Denormalization im-
proves performance - Indexes essential for speed - Query optimization critical
- ACID transactions reliable - Replication for availability - Sharding for scale -
Columnar for analytics - Full-text search useful - Transaction isolation matters
- Locking vs MVCC tradeoffs - Distributed systems complex
Database selection and optimization is both art and science.