Search

Key concepts and definitions across all sections.

Section 1: SQL

Basic SQL

• SELECT
• FROM
• WHERE
• LIMIT

Joins

• INNER JOIN
• LEFT JOIN
• CROSS JOIN
• Self Join

Aggregations

• GROUP BY
• HAVING
• COUNT
• SUM

Window Functions

• Window Function
• PARTITION BY
• ROW_NUMBER
• RANK
• DENSE_RANK

Common Table Expressions

• CTE (Common Table Expression)
• WITH Clause

NULL Handling

• NULL
• Three-Valued Logic
• NULL in NOT IN
• IS NULL

SQL Patterns

• The Funnel
• The Ladder
• The Timeline
• The Comparison
• The Exception Finder

Data Privacy

• Differential Privacy
• Synthetic Data

Section 2: System Basics

IO

• Storage Hierarchy
• IO Cost

Hashing

• Locality Sensitive Hashing (LSH)
• H3 (Geospatial Index)
• Vector/Embedding Hashing

Bloom Filters

• Bloom Filter
• False Positive Rate

Compression

• Run-Length Encoding (RLE)
• Dictionary Encoding
• Delta Encoding
• Bit Packing

Section 3: Big Data Systems

Storage

• Row Storage
• Columnar Storage
• Page

Algorithms

• Hash Partitioning
• BigSort
• Block Nested Loop Join (BNLJ)
• Hash Partition Join (HPJ)
• Sort-Merge Join (SMJ)
• IO Cost Summary

Indexing

• B+ Tree
• LSM Tree
• SSTable
• Compaction

Query Optimization

• Query Optimizer
• Query Plan
• Selectivity
• Cardinality
• IO Cost Summary (Plans)

Section 4: Transactions

Motivation

• Transaction
• Scale
• Complexity

ACID Properties

• ACID
• Atomicity
• Consistency
• Isolation
• Durability

Transaction Examples

• Ticket Purchase Transaction
• User Purchase Limits
• Banking Transfer
• Inventory Reservation

Building Transactions

• Serial Schedule
• Concurrent Schedule
• Transaction Manager

Transaction Scheduling

• Reordering Rules
• Interleaved Schedule

Concurrency Primer

• Concurrency
• Parallelism
• Optimistic Concurrency Control (OCC)
• Pessimistic Concurrency Control (PCC)
• Multi-Version Concurrency Control (MVCC)

Lock Foundations

• Shared Lock (S-Lock)
• Exclusive Lock (X-Lock)
• Lock Compatibility Matrix

Two-Phase Locking (2PL)

• Two-Phase Locking (2PL)
• Strict Two-Phase Locking (S2PL)
• Cascading Abort
• Growing Phase
• Shrinking Phase

Microschedules

• Microschedule
• WaitsFor Graph
• Deadlock
• Cycle

Correctness

• Conflict
• Read-Write Conflict
• Write-Read Conflict
• Write-Write Conflict
• Conflict Serializability
• Conflict Graph
• Macroschedules
• Topological Sort

Connecting Together

• 2PL Theorem

Problem Solving

• Lock Contention
• Lock Duration
• Lock Granularity

Recovery Overview

• Recovery
• Crash

Recovery Concepts

• UNDO
• REDO
• COMMIT
• ABORT

Write-Ahead Logging (WAL)

• Write-Ahead Logging (WAL)
• Trace Tables
• WAL Protocol Rules

Post-Crash Recovery

• Analysis Phase
• Redo Phase
• Undo Phase
• Checkpoint