Chapter 15: Time-Series Databases & OLAP

15.1 OLTP vs OLAP

OLTP (Online Transaction Processing) systems handle operational workloads with many small read/write transactions. OLAP (Online Analytical Processing) systems handle analytical queries scanning large datasets. The fundamental difference drives completely different storage and optimization strategies.

Storage Layout Comparison

Why Separate Systems?

• Resource Contention: Heavy analytical queries can starve OLTP transactions of resources
• Different Optimization Goals: Row storage for transactions vs columnar for analytics
• Backup/Recovery: OLTP needs point-in-time recovery; OLAP can rebuild from source
• Schema Design: Normalized for consistency vs denormalized for query speed
• Data Lifecycle: OLTP keeps recent data; OLAP keeps years of history with compression

15.2 Columnar Storage

Columnar databases store each column separately on disk. This enables massive compression (same data types together) and allows reading only needed columns. SIMD/vectorized execution processes entire columns in CPU registers.

Row vs Column Layout

Parquet File Structure

Benefits of Columnar Storage

Vectorized Execution Example

// Scalar (row-by-row): 1 operation per loop
for (int i = 0; i < n; i++) {
    result[i] = array_a[i] + array_b[i];
}

// Vectorized (SIMD): 8 operations per loop (AVX)
for (int i = 0; i < n; i += 8) {
    __m256i a = _mm256_loadu_si256(&array_a[i]);
    __m256i b = _mm256_loadu_si256(&array_b[i]);
    __m256i sum = _mm256_add_epi32(a, b);
    _mm256_storeu_si256(&result[i], sum);
}
// 8x faster for integer addition

15.3 Column Compression Techniques

Columnar storage enables specialized compression schemes that exploit patterns in typed data. Compression reduces I/O (read less from disk) and fits more data in memory/cache.

Compression Schemes

Compression Comparison

Gorilla Algorithm Detail

Developed by Facebook for time-series compression. Exploits the fact that consecutive float values in metrics change slowly, so XOR produces many zeros.

// Gorilla compression for floats
timestamp: delta-of-delta encoding (most deltas ~same)
  1000, 1060, 1120, 1180 -> deltas: 60,60,60 -> delta-of-deltas: 0,0
  Store: base=1000, delta=60, then stream of 0s (1 bit each)

value: XOR + variable-bit encoding
  12.5, 12.6, 12.5 -> XOR(12.6, 12.5) = few bits differ
  Leading zeros: 54, Trailing zeros: 3, Meaningful bits: 7
  Store: control bits + 7 bits (not 64 bits)

15.4 Time-Series Databases

Time-series databases (TSDB) optimize for append-heavy workloads with timestamped data. Key features: automatic downsampling, retention policies, time-based aggregations, and specialized compression.

InfluxDB Architecture

TimescaleDB Architecture

Prometheus Architecture

Time-Series Database Comparison

Retention Policies & Downsampling

-- InfluxDB retention policies
CREATE RETENTION POLICY "one_week" ON "mydb"
  DURATION 7d REPLICATION 1 DEFAULT;

CREATE RETENTION POLICY "one_year" ON "mydb"
  DURATION 52w REPLICATION 1;

-- Continuous query: downsample to 5-minute averages
CREATE CONTINUOUS QUERY "cq_5m" ON "mydb"
BEGIN
  SELECT mean(value) INTO "one_year"."downsample"
  FROM "one_week"."measurements"
  GROUP BY time(5m), *
END

-- TimescaleDB continuous aggregate
CREATE MATERIALIZED VIEW metrics_5m
WITH (timescaledb.continuous) AS
SELECT time_bucket('5 minutes', time) AS bucket,
       host,
       AVG(cpu_usage) AS avg_cpu
FROM metrics
GROUP BY bucket, host;

15.5 OLAP Databases

OLAP databases excel at analytical queries over large datasets. Modern systems combine columnar storage, vectorized execution, distributed query processing, and intelligent caching.

ClickHouse Architecture

Druid Architecture

BigQuery Architecture

Snowflake Architecture

OLAP Database Comparison

15.6 Star Schema & Dimensional Modeling

Star schema is the standard for data warehouses. A central fact table contains measures (metrics), surrounded by dimension tables with descriptive attributes. Optimized for analytical queries with few JOINs.

Star Schema Structure

Star vs Snowflake Schema

Slowly Changing Dimensions (SCD)

Dimension attributes change over time (e.g., customer moves to new city). Strategies to track history:

SCD Type 2 Example

-- Dimension table with Type 2 tracking
CREATE TABLE dim_customer (
    customer_key SERIAL PRIMARY KEY,  -- surrogate key
    customer_id INT,                   -- natural key
    name VARCHAR(100),
    email VARCHAR(100),
    city VARCHAR(50),
    state VARCHAR(2),
    valid_from DATE,
    valid_to DATE,                     -- 9999-12-31 for current
    is_current BOOLEAN                 -- true for current version
);

-- Query: sales in last year, using customer's city at time of sale
SELECT c.city, SUM(f.revenue)
FROM sales_facts f
JOIN dim_customer c
  ON f.customer_key = c.customer_key
 AND f.sale_date BETWEEN c.valid_from AND c.valid_to
WHERE f.sale_date >= CURRENT_DATE - INTERVAL '1 year'
GROUP BY c.city;

15.7 Materialized Views & Pre-Aggregation

Materialized views store query results physically, trading storage and freshness for query speed. Essential for expensive aggregations (GROUP BY on billions of rows).

Materialized View Architecture

Refresh Strategies

Examples in Different Systems

-- PostgreSQL: Manual refresh
CREATE MATERIALIZED VIEW sales_daily AS
SELECT DATE(order_date) AS day, SUM(amount) AS revenue
FROM orders
GROUP BY day;

REFRESH MATERIALIZED VIEW sales_daily;  -- manual trigger

-- ClickHouse: Streaming materialized view (auto-updated on insert)
CREATE MATERIALIZED VIEW events_hourly_mv
ENGINE = SummingMergeTree()
ORDER BY (hour, action)
AS SELECT
    toStartOfHour(timestamp) AS hour,
    action,
    count() AS count,
    sum(value) AS total_value
FROM events
GROUP BY hour, action;

-- BigQuery: Scheduled refresh
CREATE MATERIALIZED VIEW project.dataset.sales_daily
PARTITION BY day
CLUSTER BY product_id
AS SELECT DATE(order_date) AS day, product_id, SUM(amount) AS revenue
FROM project.dataset.orders
GROUP BY day, product_id;

-- Auto-refresh every 4 hours (BigQuery setting)

-- Snowflake: Automatic refresh (experimental)
CREATE MATERIALIZED VIEW sales_daily AS
SELECT DATE(order_date) AS day, SUM(amount) AS revenue
FROM orders
GROUP BY day;

-- Auto-refresh when base table changes (Snowflake manages)

Cube Pre-Aggregation

For multi-dimensional analytics (OLAP cubes), pre-compute aggregations at multiple granularities.

15.8 Approximate Query Processing

For massive datasets, approximate algorithms provide fast answers with bounded error. Key use cases: COUNT DISTINCT (unique users), top-K (most frequent items), percentiles (P95 latency).

Approximate Algorithms

Algorithm Comparison

HyperLogLog Example

-- PostgreSQL with HLL extension
CREATE EXTENSION hll;

-- Add HLL column to table
ALTER TABLE events ADD COLUMN user_hll hll;

-- Insert: hash user_id into HLL
UPDATE events SET user_hll = hll_add(hll_empty(), hll_hash_text(user_id));

-- Query: approximate COUNT(DISTINCT user_id)
SELECT hll_cardinality(hll_union_agg(user_hll)) AS approx_unique_users
FROM events
WHERE date >= '2024-01-01';

-- Exact (slow): 10 seconds, 1B rows scanned
SELECT COUNT(DISTINCT user_id) FROM events WHERE date >= '2024-01-01';

-- Approximate (fast): 100ms, 1.5KB per HLL aggregate
-- Error: actual=1,000,000, estimate=1,008,234 (0.8% error)

When to Use Approximate Queries

• Real-time dashboards: Users don't need exact counts (1,234,567 vs 1,234,890)
• Large cardinality: COUNT(DISTINCT) on billions of values is slow and memory-intensive
• Streaming data: Compute metrics on infinite streams without storing all data
• Monitoring: P99 latency approximation is acceptable (99.1% vs 99% is fine)
• NOT for financials: Never approximate revenue, invoice totals, payment amounts

15.9 Real-Time Analytics Architectures

Real-time analytics require processing streaming data with low latency. Two main architectures: Lambda (batch + speed layers) and Kappa (stream-only).

Lambda Architecture

Kappa Architecture

Lambda vs Kappa Comparison

Modern Trend: Unified Batch + Stream

Modern frameworks like Apache Flink and Spark Structured Streaming support both batch and streaming with the same API, reducing Lambda's complexity.

// Flink: Unified batch + stream processing
StreamExecutionEnvironment env = StreamExecutionEnvironment.getExecutionEnvironment();

// Stream: unbounded source (Kafka)
DataStream<Event> stream = env.addSource(new FlinkKafkaConsumer<>(...));

// Batch: bounded source (S3 files)
DataStream<Event> batch = env.readFile(new TextInputFormat(...), "s3://...");

// Same processing logic for both
stream.keyBy(e -> e.getUserId())
      .window(TumblingEventTimeWindows.of(Time.hours(1)))
      .aggregate(new CountAggregator())
      .addSink(new ClickHouseSink(...));

// Framework handles watermarks, state, exactly-once for both

15.10 Decision Framework: Choosing the Right System

No single database fits all analytical needs. Choose based on latency requirements, data volume, query complexity, and operational constraints.

Decision Flowchart

Use Case Recommendations

Cost Considerations

• Self-Hosted (ClickHouse, TimescaleDB): Lower cost at scale (pay for compute/storage), but operational burden (backups, upgrades, monitoring)
• Serverless (BigQuery, Athena): Pay per query (good for infrequent queries), zero ops, but unpredictable costs for high QPS
• Provisioned (Snowflake, Redshift): Pay for uptime (even idle), predictable costs, but waste if underutilized
• Managed SaaS (Databricks, ClickHouse Cloud): Middle ground (ops handled, but not serverless), typically 2-3x self-hosted cost

Migration Strategy

Summary

Time-series and OLAP databases optimize for analytical workloads with specialized storage, compression, and query execution. Key takeaways:

• Separate OLTP and OLAP: Different workloads need different storage (row vs columnar)
• Columnar storage: Reads only needed columns, compresses better, enables vectorized execution
• Compression: RLE, dictionary, bitmap, delta, Gorilla achieve 10-100x reduction
• Time-Series DBs: Specialized for metrics/logs with retention policies and downsampling
• OLAP Systems: ClickHouse (fast, self-hosted), BigQuery/Snowflake (serverless), Druid/Pinot (real-time)
• Star Schema: Fact table (measures) + dimension tables (attributes), use SCD Type 2 for history
• Materialized Views: Pre-compute aggregations, trade staleness for speed
• Approximate Queries: HyperLogLog (COUNT DISTINCT), T-Digest (percentiles), Count-Min Sketch (top-K)
• Real-Time Architectures: Kappa (stream-only) simpler than Lambda (batch + stream)
• Choose Based on Needs: Latency, volume, complexity, ops preference