B+-Tree Performance Analysis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

-- PostgreSQL: Comprehensive Index Health Check
WITH index_stats AS (
    SELECT
        schemaname,
        tablename,
        indexrelname as index_name,
        pg_relation_size(indexrelid) as index_size,
        pg_relation_size(relid) as table_size,
        idx_scan as index_scans,
        idx_tup_read as tuples_read,
        idx_tup_fetch as tuples_fetched
    FROM pg_stat_user_indexes
    JOIN pg_index ON indexrelid = pg_index.indexrelid
),
bloat_estimate AS (
    SELECT
        schemaname,
        tablename,
        indexrelname,
        -- Estimate bloat based on index vs table ratio
        CASE 
            WHEN table_size > 0 THEN 
                (index_size::float / table_size * 100)::numeric(5,2)
            ELSE 0 
        END as index_to_table_pct
    FROM index_stats
)
SELECT 
    s.schemaname || '.' || s.tablename as table_name,
    s.index_name,
    pg_size_pretty(s.index_size) as index_size,
    pg_size_pretty(s.table_size) as table_size,
    b.index_to_table_pct || '%' as size_ratio,
    s.index_scans,
    CASE 
        WHEN s.index_scans = 0 THEN 'UNUSED'
        WHEN s.index_scans < 100 THEN 'LOW'
        ELSE 'ACTIVE'
    END as usage_status
FROM index_stats s
JOIN bloat_estimate b ON s.index_name = b.indexrelname
ORDER BY s.index_size DESC
LIMIT 20;
 
-- MySQL InnoDB: Index Statistics
SELECT 
    TABLE_SCHEMA,
    TABLE_NAME,
    INDEX_NAME,
    NON_UNIQUE,
    CARDINALITY,
    SUB_PART,
    INDEX_TYPE
FROM INFORMATION_SCHEMA.STATISTICS
WHERE TABLE_SCHEMA = 'your_database'
ORDER BY TABLE_NAME, INDEX_NAME;
 
-- MySQL: InnoDB Buffer Pool Hit Rate
SHOW STATUS LIKE 'innodb_buffer_pool_read%';
-- Calculate: 1 - (reads / read_requests) = hit_rate
 
-- Oracle: Index Clustering Factor Analysis
SELECT 
    index_name,
    num_rows,
    distinct_keys,
    clustering_factor,
    -- Lower is better; < table blocks means good clustering
    (SELECT blocks FROM user_tables WHERE table_name = ui.table_name) as table_blocks,
    blevel + 1 as tree_height
FROM user_indexes ui
WHERE index_type = 'NORMAL'
ORDER BY num_rows DESC;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

-- PostgreSQL: Estimate Index Bloat
-- Using pgstattuple extension (most accurate)
CREATE EXTENSION IF NOT EXISTS pgstattuple;
 
SELECT 
    indexrelid::regclass as index_name,
    pg_size_pretty(pg_relation_size(indexrelid)) as index_size,
    avg_leaf_density,
    avg_leaf_density as fill_percentage,
    CASE 
        WHEN avg_leaf_density < 50 THEN 'SEVERE BLOAT'
        WHEN avg_leaf_density < 70 THEN 'MODERATE BLOAT'
        WHEN avg_leaf_density < 85 THEN 'SOME BLOAT'
        ELSE 'HEALTHY'
    END as health_status
FROM (
    SELECT 
        indexrelid,
        (pgstatindex(indexrelid::regclass)).avg_leaf_density
    FROM pg_index
    WHERE indisvalid AND NOT indisprimary
    LIMIT 10  -- Check top 10 indexes
) stats
ORDER BY avg_leaf_density ASC;
 
-- PostgreSQL: Identify Bloated Indexes Needing REINDEX
-- Compare current size to estimated minimal size
WITH index_info AS (
    SELECT
        c.relname as index_name,
        c.relpages as current_pages,
        -- Estimate optimal pages from distinct keys and page capacity
        GREATEST(1, 
            CEIL(i.indrelid::regclass::text::regclass::oid::bigint / 500.0)
        ) as estimated_min_pages
    FROM pg_class c
    JOIN pg_index i ON c.oid = i.indexrelid
    WHERE c.relkind = 'i'
)
SELECT 
    index_name,
    current_pages,
    estimated_min_pages,
    ROUND(((current_pages - estimated_min_pages)::float / current_pages * 100)::numeric, 2) 
        as bloat_pct
FROM index_info
WHERE current_pages > estimated_min_pages * 1.3  -- >30% bloat
ORDER BY (current_pages - estimated_min_pages) DESC;
 
-- MySQL InnoDB: Check for Fragmentation
SELECT 
    TABLE_NAME,
    DATA_LENGTH,
    INDEX_LENGTH,
    DATA_FREE,
    ROUND((DATA_FREE / (DATA_LENGTH + INDEX_LENGTH)) * 100, 2) as fragmentation_pct
FROM INFORMATION_SCHEMA.TABLES
WHERE TABLE_SCHEMA = 'your_database'
  AND DATA_FREE > 0
ORDER BY DATA_FREE DESC;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

-- PostgreSQL OLTP Tuning
 
-- 1. Aggressive buffer pool sizing (75% of RAM if dedicated)
-- In postgresql.conf:
-- shared_buffers = '12GB'  -- For 16GB RAM server
-- effective_cache_size = '14GB'  -- Total expected cache
 
-- 2. Optimize for point lookups - smaller pages, more in cache
-- (Compile-time in PostgreSQL, but we can optimize indexes)
 
-- 3. Use covering indexes to avoid heap access
CREATE INDEX idx_orders_covering ON orders (
    customer_id,
    order_date
) INCLUDE (
    order_total,
    status
);
 
-- 4. Partial indexes for hot data
CREATE INDEX idx_orders_active ON orders (order_date)
WHERE status = 'active';
 
-- 5. Tune autovacuum for high-write tables
ALTER TABLE orders SET (
    autovacuum_vacuum_scale_factor = 0.05,  -- Vacuum at 5% dead tuples
    autovacuum_analyze_scale_factor = 0.02  -- Analyze at 2% changes
);
 
-- MySQL InnoDB OLTP Tuning
 
-- Buffer pool sizing (typically 70-80% of RAM)
-- SET GLOBAL innodb_buffer_pool_size = 12 * 1024 * 1024 * 1024;
 
-- Adaptive hash index (enabled by default, helpful for point lookups)
-- SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';
 
-- Change buffer for secondary index updates
-- SET GLOBAL innodb_change_buffer_max_size = 25;  -- % of buffer pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

-- OLAP-Oriented B+-Tree Tuning
 
-- 1. Larger pages for better sequential scan (if configurable)
-- MySQL: innodb_page_size = 32768  -- 32KB, set at init
 
-- 2. Higher fill factor for read-heavy workloads
CREATE INDEX idx_sales_analytics ON sales (
    sale_date,
    region_id,
    product_category
) WITH (fillfactor = 95);  -- PostgreSQL
 
-- 3. Compressed indexes (Oracle, SQL Server)
-- Oracle: 
-- CREATE INDEX idx_sales_date ON sales(sale_date) COMPRESS 2;
 
-- 4. Column order optimization for prefix scans
-- Most selective column that's always used in filters goes FIRST
-- Range scan column goes LAST
 
-- Good for: WHERE region = X AND date BETWEEN a AND b
CREATE INDEX idx_sales_region_date ON sales (region_id, sale_date);
 
-- 5. Consider bitmap indexes for low-cardinality (Oracle, PostgreSQL)
-- Good for: Large tables, few distinct values, OR conditions
-- PostgreSQL extension: CREATE INDEX ON sales USING gin(region_id);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

-- PostgreSQL: Find Unused Indexes
SELECT 
    schemaname,
    tablename,
    indexrelname,
    idx_scan as total_scans,
    pg_size_pretty(pg_relation_size(indexrelid)) as index_size
FROM pg_stat_user_indexes
WHERE idx_scan = 0  -- Never used
  AND indexrelid NOT IN (  -- Exclude constraint-backing indexes
      SELECT conindid FROM pg_constraint WHERE conindid IS NOT NULL
  )
ORDER BY pg_relation_size(indexrelid) DESC;
 
-- PostgreSQL: Find Duplicate/Redundant Indexes
SELECT 
    a.indexrelid::regclass as index1,
    b.indexrelid::regclass as index2,
    a.indkey as columns1,
    b.indkey as columns2
FROM pg_index a
JOIN pg_index b ON a.indrelid = b.indrelid 
    AND a.indexrelid != b.indexrelid
    AND a.indkey::text LIKE b.indkey::text || '%'  -- a is prefix of b
WHERE a.indisunique = false;  -- Not unique constraint
 
-- MySQL: Find Unused Indexes
SELECT 
    object_schema,
    object_name,
    index_name,
    count_read,
    count_write
FROM performance_schema.table_io_waits_summary_by_index_usage
WHERE index_name IS NOT NULL
  AND count_read = 0
  AND object_schema NOT IN ('mysql', 'performance_schema')
ORDER BY count_write DESC;
 
-- Detect Function Calls Preventing Index Use
-- In query plans, look for:
-- "Filter: (upper(name) = 'JOHN')" vs "Index Cond: (name = 'john')"
EXPLAIN ANALYZE
SELECT * FROM users WHERE UPPER(email) = 'TEST@EXAMPLE.COM';
-- Fix: CREATE INDEX idx_email_upper ON users (UPPER(email));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

-- Composite Index Column Order Guide
 
-- RULE 1: Equality columns before range columns
-- Query: WHERE status = 'active' AND date BETWEEN x AND y
-- Good:  (status, date)  -- Equality first
-- Bad:   (date, status)  -- Range first breaks index use for status
 
-- RULE 2: High-selectivity before low-selectivity (for equality)
-- Query: WHERE department = 'Engineering' AND country = 'US'
-- If 5% are Engineering, 20% are US:
-- Good:  (department, country)  -- More selective first
-- Bad:   (country, department)  -- Less selective first
 
-- RULE 3: Consider all query patterns the index must serve
-- These queries all benefit from (customer_id, order_date, product_id):
-- SELECT * FROM orders WHERE customer_id = 100;
-- SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2024-01-01';
-- SELECT * FROM orders WHERE customer_id = 100 AND order_date = '2024-01-01' 
--   AND product_id = 5;
 
-- But this query CANNOT use the index efficiently:
-- SELECT * FROM orders WHERE order_date > '2024-01-01';  -- No leading column!
 
-- RULE 4: ORDER BY columns at the end
-- Query: SELECT * FROM products WHERE category = 'Electronics' ORDER BY price;
-- Index: (category, price)  -- Avoids sort operation!
 
-- RULE 5: Consider covering index for read-heavy patterns
CREATE INDEX idx_orders_customer_covering ON orders (
    customer_id,           -- Equality condition
    order_date DESC        -- Range + ORDER BY
) INCLUDE (
    total_amount,          -- Selected columns
    status                 -- Avoiding heap access
);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

-- PostgreSQL: Safe Production Index Creation
-- Always use CONCURRENTLY in production
CREATE INDEX CONCURRENTLY idx_new_index ON large_table (column)
WHERE condition;  -- Consider partial index
 
-- Monitor progress
SELECT * FROM pg_stat_progress_create_index;
 
-- If creation fails, clean up invalid index
SELECT indexrelid::regclass FROM pg_index WHERE NOT indisvalid;
DROP INDEX CONCURRENTLY idx_new_index;  -- If invalid
 
-- PostgreSQL: Statistics Update Procedure
-- After bulk data changes
ANALYZE table_name;  -- Quick statistics refresh
 
-- For more accurate statistics on important columns
ALTER TABLE orders ALTER COLUMN order_date 
SET STATISTICS 1000;  -- Default is 100
ANALYZE orders;
 
-- PostgreSQL: Online REINDEX (v12+)
REINDEX INDEX CONCURRENTLY idx_name;
 
-- Monitor reindex progress
SELECT 
    a.query,
    p.phase,
    p.lockers_total,
    p.blocks_total,
    p.blocks_done,
    round(100.0 * p.blocks_done / nullif(p.blocks_total, 0), 1) as pct_done
FROM pg_stat_activity a
JOIN pg_stat_progress_create_index p ON a.pid = p.pid
WHERE a.query LIKE '%REINDEX%';
 
-- MySQL: Online DDL for Index Operations (5.6+)
ALTER TABLE orders 
ADD INDEX idx_new (column_name),
ALGORITHM=INPLACE,  -- Online, no table copy
LOCK=NONE;          -- Concurrent DML allowed