Checkpoints

A checkpoint is a recorded recovery point from which a DBMS can restart after a crash by replaying logs only from that point forward (instead of from the beginning).

• Blocking: A “sharp” checkpoint that briefly pauses normal work (or gates new transactions) while dirty pages are flushed to make the on-disk state self-consistent.

• Consistent: A checkpoint that captures a self-consistent on-disk state (no dirty pages older than the checkpoint LSN), so recovery can start exactly there.

• Fuzzy: Non-blocking checkpointing that trickles dirty buffers to disk in small batches; the on-disk state may not be fully consistent, so recovery replays logs after the checkpoint LSN to finish the job.

• Non-Blocking: Checkpointing that does not acquire exclusive DB locks or halt new transactions (often synonymous with “fuzzy”).

• Not Supported: The engine does not expose or implement checkpointing (rare in general-purpose DBs).
  Citations: InnoDB fuzzy checkpoints; SQL Server checkpoint purpose; TimesTen blocking vs non-blocking. Oracle Documentation+2Microsoft Learn+2

Compression

Columnar and index encodings reduce I/O and memory by exploiting value locality and order.

• Bitmap Encoding: Encodes membership of values/keys in bitmaps (often 1 bit per row per value or per predicate).

• Bit Packing / Mostly Encoding: Stores small-domain integers using the minimum bit-width (bit-packing). “Mostly” styles combine bit-packing with RLE for runs; Parquet’s “RLE/bit-packed hybrid” is the canonical example. Apache Parquet

• Delta Encoding: Stores differences between consecutive values rather than absolute values; great for sorted timestamps/IDs. Computer Science

• Dictionary Encoding: Maps distinct values to small integer codes; the column stores codes, and a dictionary maps codes → values. Imply

• Incremental Encoding: A flavor of delta/prefix encoding that records shared prefixes/suffixes (especially on sorted strings) so they’re not duplicated. CMU 15-445/645

• Naïve (Page-Level): Apply a general compressor (e.g., LZ) to each page/block as a whole.

• Naïve (Record-Level): Compress each tuple/record individually (less effective than column-wise).

• Null Suppression: Omits storing explicit null/zero bytes and reconstructs them on decode (a.k.a. sparse/zero suppression).

• Prefix Compression: In B-tree pages or sorted columns, store a shared prefix once and keep only suffixes per key/value. Microsoft

• Run-Length Encoding (RLE): Compress consecutive runs of the same value as (value, run-length); powerful on sorted/low-cardinality columns.

Concurrency Control

Policies that ensure correct results under concurrent transactions.

• Deterministic Concurrency Control: Pre-orders transactions (e.g., via a global log) and executes them in that order at all replicas/partitions (Calvin). Eliminates most runtime conflicts and many coordination costs. cs.yale.edu+1

• Multi-version Concurrency Control (MVCC): Readers see a consistent snapshot while writers create new versions; reads don’t block writes (and vice versa). PostgreSQL

• Not Supported: Engine lacks transactional CC (typical of some key/value or analytics engines when used in append-only modes).

• Optimistic Concurrency Control (OCC): Transactions proceed without locks and validate at commit time; on conflict, abort/retry. Best when conflicts are rare. eecs.harvard.edu

• Timestamp Ordering: Assigns a timestamp to each tx; operations must respect timestamp order for serializability (often lock-free, but with aborts). CMU 15-445/645

• Two-Phase Locking (Deadlock Detection): Pessimistic locking with lock-acquire phase then release at commit; system detects/deals with deadlocks (e.g., waits-for graph).

• Two-Phase Locking (Deadlock Prevention): Variants (e.g., wait-die/wound-wait) avoid deadlocks by ordering lock waits or preempting transactions.

Coordination

How a distributed DB decides order/commitment of actions.

• Centralized Coordinator: One node orders/coordinates transactions, commits, and membership (single leader / consensus hub).

• Conflict-Free Replicated Data Type (CRDT): Data type with mathematically defined, order-independent merge (associative/commutative/idempotent), enabling coordination-free eventual consistency. Wikipedia

• Decentralized: No single coordinator; nodes use protocols (gossip, quorum, consensus) to converge.

Data Model

The logical shape of data and relationships.

• Array / Matrix: N-dimensional arrays (scientific/time-series/ML; e.g., SciDB/TileDB).

• Column Family / Wide-Column: Tables with sparse, dynamic columns grouped into families (Bigtable/Cassandra). AWS Documentation

• Document / XML: Semi-structured docs (JSON, BSON, XML) with flexible schema; indexed paths. Wikipedia

• Entity-Attribute-Value (EAV): Triples (entity, attribute, value) to model sparse or dynamic attributes. Prometheus

• Entity-Relationship: Conceptual modeling with entities/relationships/attributes (Chen). GraphDB

• Graph: Nodes/edges/properties; supports traversals and patterns (property graphs/RDF).

• Hierarchical: Tree-structured parent/child records (IMS). Stack Overflow

• Key/Value: Opaque values accessed by key; simple, fast primitives.

• Multi-Value: Keys map to sets/lists of values (PICK-style). Ontotext

• Network: CODASYL set-type pointers (general graph of records). MongoDB

• Object-Oriented: Persistent objects/classes with identity and methods. Wikipedia

• Object-Relational: Relational tables + types/UDTs/inheritance. Wikipedia

• Relational: Tables, keys, declarative SQL, normalization.

• Triplestore / RDF: (subject, predicate, object) triples with graph semantics/entailment. Labelbox

• Vector: Dense high-dimensional vectors (embeddings) for similarity search (cosine/inner-product/L2). IBM

Fault Tolerance

Mechanisms for surviving failures.

• Asynchronous Replication: Primary commits locally and ships updates later; lower latency, risk of data loss on failover.

• Conflict Resolution: Policies to reconcile divergent replicas (LWW, vector clocks, app rules).

• Quorum-based Replication: Reads/writes succeed when a majority (or R/W quorums) acknowledge, ensuring overlap for consistency (Dynamo-style). Medium

• Read Repair: On reads, stale replicas are repaired in the background. Dremio

• Synchronous Replication: Primary waits for replicas before commit; higher latency, stronger durability.

Foreign Keys

• Supported: Engine enforces referential integrity (insert/update/delete checks, cascades).

• Not Supported: Engine won’t enforce parent/child constraints (app must).

Indexes

Physical structures that accelerate access.

• Adaptive Radix Tree (ART): Radix trie that adapts node size to child count; fast, cache-friendly for main-memory. Apache Avro

• AVL-Tree: Height-balanced BST with rotations (in-memory).

• B-epsilon Tree (Bε-tree / Fractal Tree): Buffered B-tree variant that batches inserts for high write throughput. Wikipedia

• BitMap: Bit vectors per value/predicate; efficient for analytics and set operations.

• Block Range Index (BRIN): Summaries per page range; tiny index that’s great for large, naturally ordered tables. Pure Storage Blog

• B+Tree: Disk-optimized multi-way search tree; default for most OLTP engines. CMU 15-445/645

• Bw-Tree: Latch-free B-tree with delta records and indirection layer; designed for multicore/flash.

• Hash Table: Exact-match lookups by hash; no order.

• Hierarchical Navigable Small World (HNSW): Graph-based approximate-nearest-neighbor (ANN) index enabling fast vector similarity search.

• Inverted Index (Full Text): Term → posting lists (docs/positions), enabling keyword/proximity queries.

• K-D Tree: Space-partitioning tree for k-dimensional points (exact NN in low-D).

• Log-Structured Merge Tree (LSM): Hierarchy of sorted runs; batched writes + compaction (typical in KV stores). GeeksforGeeks

• MassTree: Cache-efficient trie of B-trees for strings/keys with high locality. Semantic Scholar

• Not Supported: Engine provides no secondary indexing.

• Patricia/Radix Trie: Compressed prefix trie for fast prefix/probing lookups. Wikipedia

• Red-Black Tree: Balanced BST (OS/engine internals).

• R-Tree: Bounding-box hierarchy for spatial data (rectangles/points).

• Skip List: Probabilistic layered lists offering log-time search/insert. CMU 15-721

• T-Tree: In-memory balanced tree for main-memory DBs.

Isolation Levels

Degree of visibility among concurrent transactions.

• Cursor Stability (CS): Locks the current row while the cursor is positioned; roughly DB2’s variant of Read Committed. IBM+1

• Not Supported: Isolation is not configurable/exposed.

• Read Committed: No dirty reads; each statement sees only committed data. Microsoft Learn

• Read Stability (RS): Once a qualifying row is read, others can’t update/delete it until tx end; prevents some anomalies beyond CS. IBM+1

• Read Uncommitted: Allows dirty reads (rarely advisable).

• Repeatable Read: A row read once can be read again with the same values; prevents non-repeatable reads but not all phantoms. Microsoft Learn

• Serializable: Results equivalent to some serial order of transactions; the strictest ANSI level (can be via 2PL or SSI). PostgreSQL

• Snapshot Isolation: Each tx reads from a consistent versioned snapshot; readers don’t block writers (and vice versa). Microsoft Learn

Joins

Physical join strategies/operators.

• Broadcast Join: Replicates small side to all workers to avoid shuffles.

• Hash Join: Build hash table on one input, probe with the other.

• Index Nested Loop Join: Outer tuples probe an index on the inner relation.

• Nested Loop Join: For each outer row, scan inner side (with or without index).

• Not Supported: Engine cannot join (client-side only).

• Semi Join: Return rows from left side that have matches on right, without duplicating right columns.

• Shuffle Join: Repartition both sides on join keys before join (massively parallel systems). TigerData

• Sort-Merge Join: Sort both sides on join keys, then merge.

• Worst-Case Optimal Join: Multiway join algorithms (e.g., NPRR, Leapfrog Triejoin) whose cost matches worst-case output bounds for cyclic joins. orc.apache.org

Logging

Crash-recovery records of changes.

• Command Logging: Log high-level operations (e.g., SQL) then re-execute on recovery.

• Logical Logging: Log logical changes (insert tuple X in table T). Compact but complex with concurrency. CMU 15-721

• Not Supported: No write-ahead logging (uncommon for transactional engines).

• Physical Logging: Log before/after images of pages/records (simple, large logs). Alibaba Cloud

• Physiological Logging: Hybrid—log physical changes scoped to a page plus logical record IDs; foundation of ARIES. People at EECS

• Shadow Paging: Copy-on-write page replacement; commits by atomically flipping pointers (log-free alternative). Wikipedia

Parallel Execution

How a DB runs a plan in parallel.

• Bushy: Execute multiple independent subtrees (subplans) in parallel. paperhub.s3.amazonaws.com

• Inter-Operator (Vertical): Pipeline producers/consumers concurrently (e.g., scan → filter → join in flight). paperhub.s3.amazonaws.com

• Intra-Operator (Horizontal): Partition the same operator across threads/nodes (e.g., many parallel scans or parallel hash-join build/probe). paperhub.s3.amazonaws.com

Query Compilation

Reducing interpretation overhead by compiling plans.

• Code Generation: Generate native code for operators/expressions (e.g., HyPer-style compilation). EECS Michigan

• JIT Compilation: On-the-fly compilation (e.g., PostgreSQL + LLVM) of hot expressions/operators. PostgreSQL

• Not Supported: Purely interpreted engine.

• Stored Procedure Compilation: Precompile stored routines to native code or bytecode in the engine.

Query Execution

Operator scheduling and tuple flow.

• Materialized Model (Operator-at-a-Time): Each operator fully materializes its output before the next consumes it (common in column stores for some phases).

• Tuple-at-a-Time Model (Volcano/Iterator): Pull-based iterators producing one tuple per next() call; very general but interpretive overhead.

• Vectorized Model: Process batches/vectors of tuples (SIMD-friendly) to reduce function call overhead and improve cache usage. CMU 15-721+1

Query Interface

APIs and languages a DB accepts.

• Command-line / Shell: Interactive REPL/CLI for queries and admin.

• Custom API: Proprietary client API/SDK (RPC/Thrift/gRPC).

• Cypher: Declarative property-graph query language (patterns, paths) for Neo4j and others. cs-people.bu.edu

• Datalog: Declarative, rule-based language (recursive queries via logic rules). cidrdb.org

• GraphQL: Application-centric query API for hierarchical JSON graphs; not a DB language per se but often backed by databases. Medium

• Gremlin: Imperative graph traversal language. CMU School of Computer Science

• HTTP / REST: RESTful endpoints for CRUD/queries.

• PartiQL: SQL-compatible language over structured/semi-structured (JSON) data. Ontotext

• PL/SQL: Oracle’s procedural SQL extension for stored programs.

• PromQL: Time-series query language for Prometheus metrics. Wikipedia

• QUEL: Ingres relational query language (historical). Wikipedia

• RDFS++: An RDFS/OWL-Horst-style entailment rule set used by some RDF engines (often called “RDFS Plus”) for richer inference than plain RDFS.

• RPC: Remote procedure calls (binary protocols to invoke DB methods).

• SPARQL: W3C standard for RDF graph queries (triple patterns). Brown University Computer Science

• SQL: Standard relational language (DDL/DML/DCL/TCL).

• Stored Procedures: Server-side routines callable like functions.

• XPath: Path expressions over XML trees.

• XQuery: Declarative XML query and transformation language.

Storage Architecture

Where the working set lives.

• Disk-oriented: Buffer pool + pages; optimized for disks/SSDs.

• Hybrid: Mix (e.g., columnar on disk with in-memory caching).

• In-Memory: Primary state in RAM; persistence via logs/snapshots.

Storage Format

On-disk/in-memory serialization of tables/columns.

• Apache Arrow: In-memory columnar format enabling zero-copy interchange across systems. LinkedIn

• Apache Avro: Row-oriented binary format with embedded schema; great for streaming/logs. Wikipedia

• Apache CarbonData: Indexed columnar file format for fast analytics in Hadoop/Spark. carbondata.apache.org

• Apache Hudi: Table format with upserts/time-travel on data lakes. Medium

• Apache Iceberg: Open table format (schemas/partitioning/metadata) enabling ACID tables on object stores. Wikipedia

• Apache ORC: Columnar file format with stripes, indexes, and rich encodings. Wikipedia

• Apache Parquet: Columnar file format with nested data support and hybrid RLE/bit-packing encodings. Wikipedia

• CSV: Text rows with delimited columns; ubiquitous, inefficient at scale.

• Custom: Engine-specific page/segment layout.

• DataFrame: Columnar, in-memory tabular representation (e.g., Arrow-backed) used by analytics engines.

• HDF5: Hierarchical scientific dataset container with chunking/compression. Hacker News

• N-Triples: Line-based RDF triple serialization. VLDB

• RCFile: Early Hadoop columnar layout (row groups with column chunks). PostgreSQL

• SequenceFile: Hadoop key/value binary container. Microsoft Learn

• Trevni: Columnar format by Doug Cutting that influenced Parquet. Estuary

• Vortex: New LF AI project—extensible columnar format targeting faster random access/scans vs Parquet. Vortex

Storage Model

How tuples/attributes are physically grouped.

• Custom: Engine-specific hybrid or specialized layout.

• Decomposition Storage Model (Columnar): Store each column contiguously (great compression & analytics).

• Hybrid: Mix of row and column layouts (PAX/columnar segments).

• N-ary Storage Model (Row/Record): Store full rows together (OLTP-friendly).

Storage Organization

How files/pages are organized.

• Copy-on-Write / Shadow Paging: Writes go to new pages, then atomically “flip” to commit. Wikipedia

• Heaps: Unordered pages; separate indexes for access paths.

• Indexed Sequential Access Method (ISAM): Static index over sorted data; overflow chains for updates. CMU School of Computer Science

• Log-structured: Append-only segments with periodic compaction/merge.

• Sorted Files: Data kept sorted on a key (fast range scans, slower random inserts).

Stored Procedures

• Supported: Engine executes server-side routines (procedural SQL or external languages).

• Not Supported: No server-side stored program facility.

System Architecture

How nodes share hardware/state.

• Embedded: DB library linked into the application process (e.g., SQLite). Wikipedia

• Shared-Disk: Many nodes share the same disk array; cache/locking coordination (e.g., Oracle RAC). Georgia Tech Faculty

• Shared-Everything: Single server shares CPU/memory/I/O among threads.

• Shared-Memory: Multi-threaded instance on one machine with shared RAM.

• Shared-Nothing: Nodes own private CPU/memory/disk and communicate over network; scales out horizontally. IBM

User-Defined Functions

Server-side functions you can write and register to run “close to the data.”

• Custom Language: Engine provides its own sandboxed language.

• Java / Javascript / Perl / PHP / Python / R / Ruby / Rust / TCL: UDFs written in these languages (inside the engine or via safe runtimes). PostgreSQL and others support multiple PLs; SQL Server supports CLR; Oracle uses PL/SQL and Java. arXiv+1

• PL/SQL / T-SQL: Vendor procedural SQL dialects for Oracle / SQL Server. People at EECS

Views

Virtual or precomputed projections/joins.

• Materialized Views: Persisted view result maintained by refresh; accelerates repeated queries.

• Not Supported: Engine lacks view support.

• Virtual Views: Logical definitions that run on demand (no stored result).