This documentation is part of the "Projects with Books" initiative at zenOSmosis.

The source code for this project is available on GitHub.

Index and Optimization Tests

Relevant source files

Purpose and Scope

Index and Optimization Tests validate that SQLite's query optimizer correctly utilizes indexes when executing queries, particularly those involving the BETWEEN operator and complex WHERE clauses. These tests ensure that:

Queries produce identical results regardless of index configuration
The BETWEEN operator is semantically equivalent to its expanded form (col >= lower AND col <= upper)
Query optimization works correctly across varying data volumes and complexity levels

For SQL language specification compliance tests covering DDL, DML, and DQL commands, see SQL Language Evidence Tests. For detailed coverage of BETWEEN operator test variations, see BETWEEN Operator Test Suites.

Sources: test/index/between/1/slt_good_0.test:1-108 test/index/between/10/slt_good_0.test:1-150

Test Organization Structure

Index tests are organized hierarchically by data volume, enabling validation across different dataset sizes that may trigger different optimization strategies.

Test Volume Characteristics:

graph TD
    ROOT["test/index/"]
BETWEEN["between/"]
SET1["1/"]
SET10["10/"]
SET100["100/"]
FILE1_0["slt_good_0.test\n1 data row per table"]
FILE10_0["slt_good_0.test\n10 rows"]
FILE10_1["slt_good_1.test\n10 rows"]
FILE10_2["slt_good_2.test\n10 rows"]
FILE10_3["slt_good_3.test\n10 rows"]
FILE10_4["slt_good_4.test\n10 rows"]
FILE10_5["slt_good_5.test\n10 rows"]
FILE100_0["slt_good_0.test\n100+ rows"]
ROOT --> BETWEEN
 
   BETWEEN --> SET1
 
   BETWEEN --> SET10
 
   BETWEEN --> SET100
    
 
   SET1 --> FILE1_0
 
   SET10 --> FILE10_0
 
   SET10 --> FILE10_1
 
   SET10 --> FILE10_2
 
   SET10 --> FILE10_3
 
   SET10 --> FILE10_4
 
   SET10 --> FILE10_5
 
   SET100 --> FILE100_0

Directory	Rows Per Table	Test Files	Purpose
`between/1/`	1	1	Minimal data validation
`between/10/`	10	6	Standard regression suite
`between/100/`	100+	1+	Performance validation

Sources: test/index/between/1/slt_good_0.test:1-10 test/index/between/10/slt_good_0.test:1-100

Table Schema and Index Configurations

Each test file creates five tables with identical schema but different index configurations. This design validates that query results remain consistent regardless of which indexes the optimizer chooses to use.

Standard Table Schema

All tables use this schema:

Index Configuration Matrix

Index Configuration Patterns:

Table	Index Strategy	Key Characteristics
`tab0`	None	Baseline for full table scans
`tab1`	Single-column	Indexes on col0, col1, col3, col4
`tab2`	Compound	Multi-column and descending indexes
`tab3`	Unique	UNIQUE constraints with compound keys
`tab4`	Mixed	Combination of unique and descending

Sources: test/index/between/1/slt_good_0.test:3-67 test/index/between/10/slt_good_0.test:4-100

Test Methodology

Query Equivalence Validation

Each test validates that BETWEEN produces identical results to its expanded form. The test pattern repeats for each table configuration:

sequenceDiagram
    participant TF as Test File
    participant DB as Database
    participant V as Validator
    
    Note over TF,V: For each table (tab0..tab4)
    
    TF->>DB: Execute query with BETWEEN
    DB->>V: Result Set A
    
    TF->>DB: Execute equivalent query with >= AND <=
    DB->>V: Result Set B
    
    V->>V: Compare Result Set A vs B
    
    alt Results Match
        V->>TF: PASS
    else Results Differ
        V->>TF: FAIL (optimizer bug)
    end

Label-Based Test Groups

Tests use labels to group related queries:

query I rowsort label-0
SELECT pk FROM tab0 WHERE col3 < 6 OR col3 < 1 AND col3 BETWEEN 2 AND 7
----

query I rowsort label-0
SELECT pk FROM tab0 WHERE col3 < 6 OR col3 < 1 AND (col3 >= 2 AND col3 <= 7)
----

Each label-N represents a specific query pattern tested across all five table configurations, with both BETWEEN and expanded syntax.

Sources: test/index/between/1/slt_good_0.test:69-107 test/index/between/10/slt_good_0.test:102-150

Query Pattern Categories

Simple Range Queries

Basic BETWEEN operations on indexed columns:

Sources: test/index/between/1/slt_good_0.test:69-84

Complex Compound Predicates

Multi-condition queries combining BETWEEN with other operators:

Sources: test/index/between/1/slt_good_0.test:109-157

Nested Subquery Integration

BETWEEN within subquery predicates:

Sources: test/index/between/10/slt_good_0.test:152-190

NULL Handling with BETWEEN

Tests validate BETWEEN behavior with NULL values:

Sources: test/index/between/1/slt_good_0.test:159-207

Query Complexity Spectrum

Tests progressively increase in complexity to stress-test the optimizer:

Complexity Distribution:

Label Range	Predicate Count	Query Features
label-0 to label-10	1-3	Basic BETWEEN, simple OR/AND
label-20 to label-30	4-6	Multiple columns, NULL checks
label-40 to label-50	7-10	Nested conditions, IN clauses
label-60+	10+	Deep nesting, subqueries, complex boolean logic

Sources: test/index/between/1/slt_good_0.test:69-247

Result Validation Approach

Hash-Based Comparison

Tests use hash-threshold 8 to enable result set hashing for efficient comparison:

hash-threshold 8

query I rowsort label-0
SELECT pk FROM tab0 WHERE col3 > 23 AND ((col0 <= 96)) OR (col3 >= 39)
----
10 values hashing to e20b902b49a98b1a05ed62804c757f94

The hash value ensures:

Result sets from different tables match exactly
BETWEEN and expanded syntax produce identical results
Order-independent comparison via rowsort

Sources: test/index/between/10/slt_good_0.test:1-110

Cross-Table Consistency Validation

Sources: test/index/between/1/slt_good_0.test:69-107

Data Type Coverage

Tests validate BETWEEN across all supported data types:

Data Type	Column	Test Examples
INTEGER	col0, col3	`col0 BETWEEN 7 AND 4`
FLOAT	col1, col4	`col4 BETWEEN 6.51 AND 4.36`
TEXT	col2, col5	Primarily in data setup, not BETWEEN predicates

Inverted Range Testing:

Many tests intentionally use inverted ranges (e.g., BETWEEN 7 AND 4 where 7 > 4) to validate that:

Empty result sets are handled correctly
Optimizer doesn't incorrectly rewrite the predicate
Semantic equivalence is maintained

Sources: test/index/between/1/slt_good_0.test:109-157 test/index/between/10/slt_good_0.test:272-350

Setup Phase:
- hash-threshold 8 directive
- CREATE TABLE statements for tab0-tab4
- INSERT INTO statements (1, 10, or 100+ rows)
- CREATE INDEX statements per table
Test Phase:
- Grouped by label-N identifiers
- Two queries per table per label (BETWEEN vs expanded)
- Expected results follow ---- separator
Validation:
- Hash-based result comparison
- Automatic failure on mismatch

Sources: test/index/between/1/slt_good_0.test:1-108 test/index/between/10/slt_good_0.test:1-150

Sources: test/index/between/1/slt_good_0.test:289-337

Multiple BETWEEN Clauses

Tests validate queries with multiple BETWEEN predicates:

Sources: test/index/between/1/slt_good_0.test:289-296

sqlite-sqllogictest-corpus Documentation