feat: Add R*Tree spatial indexing support

claude · claude · commit 6194c8e31ca1 · 2026-01-07T12:23:38.000Z
Implement full support for SQLite R*Tree virtual tables for multi-dimensional
spatial indexing. This enables efficient geospatial queries, collision detection,
and time-range operations.

Features:
- Table creation using :rtree =&gt; true option in Ecto migrations
- Support for 1D to 5D spatial indexes (3-11 columns including ID)
- Automatic validation of R*Tree column structure and constraints
- Comprehensive query pattern documentation and examples
- Full integration with Ecto schemas using fragments

Implementation:
- New create_rtree_table/3 helper in connection.ex for virtual table DDL
- validate_rtree_columns!/1 helper for column structure validation
- Generates CREATE VIRTUAL TABLE ... USING rtree(...) syntax
- Test coverage in test/rtree_test.exs for all dimensions and operations

Documentation:
- Complete guide in AGENTS.md with geographic and time-series examples
- R*Tree vs Vector Search comparison matrix
- Migration and query pattern examples
- Updated README.md and CHANGELOG.md

Closes el-4oc
diff --git a/AGENTS.md b/AGENTS.md
@@ -13,7 +13,7 @@ Welcome to ecto_libsql! This guide provides comprehensive documentation, API ref
 - How to integrate ecto_libsql into your Elixir/Phoenix application
 - Configuration and connection management
 - Ecto schemas, migrations, and queries
-- Advanced features (vector search, encryption, batching)
+- Advanced features (vector search, R*Tree spatial indexing, encryption, batching)
 - Real-world usage examples and patterns
 - Performance optimisation for your applications
 
@@ -32,6 +32,7 @@ Welcome to ecto_libsql! This guide provides comprehensive documentation, API ref
   - [Connection Management](#connection-management)
   - [PRAGMA Configuration](#pragma-configuration)
   - [Vector Search](#vector-search)
+  - [R*Tree Spatial Indexing](#rtree-spatial-indexing)
   - [Encryption](#encryption)
 - [Ecto Integration](#ecto-integration)
   - [Quick Start with Ecto](#quick-start-with-ecto)
@@ -1104,6 +1105,210 @@ distance_sql = EctoLibSql.Native.vector_distance_cos("description_embedding", qu
 )
 ```
 
+### R*Tree Spatial Indexing
+
+R*Tree is a specialized spatial index for efficient multi-dimensional range queries. Perfect for geospatial data, collision detection, and time-series queries.
+
+#### Creating R*Tree Tables
+
+R*Tree tables are created as virtual tables using the `:rtree => true` option in migrations:
+
+```elixir
+defmodule MyApp.Repo.Migrations.CreateLocationsRTree do
+  use Ecto.Migration
+
+  def change do
+    create table(:geo_regions, rtree: true) do
+      add :id, :integer, primary_key: true
+      add :min_lat, :float
+      add :max_lat, :float
+      add :min_lng, :float
+      add :max_lng, :float
+    end
+  end
+end
+```
+
+**Important R*Tree Requirements:**
+- First column must be named `id` (integer primary key)
+- Remaining columns come in min/max pairs (2D, 3D, 4D, or 5D)
+- Total columns must be odd (3, 5, 7, 9, or 11)
+- Minimum 3 columns (id + 1 dimension), maximum 11 columns (id + 5 dimensions)
+
+#### 2D Example: Geographic Boundaries
+
+```elixir
+# Create table for geographic regions
+Ecto.Adapters.SQL.query!(
+  Repo,
+  """
+  CREATE VIRTUAL TABLE geo_regions USING rtree(
+    id,
+    min_lat, max_lat,
+    min_lng, max_lng
+  )
+  """
+)
+
+# Insert bounding boxes for regions
+# Sydney: -34.0 to -33.8 lat, 151.0 to 151.3 lng
+Ecto.Adapters.SQL.query!(
+  Repo,
+  "INSERT INTO geo_regions VALUES (1, -34.0, -33.8, 151.0, 151.3)"
+)
+
+# Melbourne: -38.0 to -37.7 lat, 144.8 to 145.1 lng
+Ecto.Adapters.SQL.query!(
+  Repo,
+  "INSERT INTO geo_regions VALUES (2, -38.0, -37.7, 144.8, 145.1)"
+)
+
+# Find regions containing a point (Sydney: -33.87, 151.21)
+result = Ecto.Adapters.SQL.query!(
+  Repo,
+  """
+  SELECT id FROM geo_regions
+  WHERE min_lat <= -33.87 AND max_lat >= -33.87
+    AND min_lng <= 151.21 AND max_lng >= 151.21
+  """
+)
+# Returns: [[1]]
+```
+
+#### 3D Example: Spatial + Time Ranges
+
+```elixir
+# Create table for events with location and time bounds
+Ecto.Adapters.SQL.query!(
+  Repo,
+  """
+  CREATE VIRTUAL TABLE events USING rtree(
+    id,
+    min_x, max_x,      -- X coordinate bounds
+    min_y, max_y,      -- Y coordinate bounds
+    min_time, max_time -- Time bounds (Unix timestamp)
+  )
+  """
+)
+
+# Insert event: Conference at (100, 200) from Jan 1-3, 2025
+start_time = DateTime.to_unix(~U[2025-01-01 00:00:00Z])
+end_time = DateTime.to_unix(~U[2025-01-03 23:59:59Z])
+
+Ecto.Adapters.SQL.query!(
+  Repo,
+  "INSERT INTO events VALUES (1, 100, 100, 200, 200, #{start_time}, #{end_time})"
+)
+
+# Find events in area (90-110, 190-210) during Jan 2025
+query_start = DateTime.to_unix(~U[2025-01-01 00:00:00Z])
+query_end = DateTime.to_unix(~U[2025-01-31 23:59:59Z])
+
+result = Ecto.Adapters.SQL.query!(
+  Repo,
+  """
+  SELECT id FROM events
+  WHERE max_x >= 90 AND min_x <= 110
+    AND max_y >= 190 AND min_y <= 210
+    AND max_time >= #{query_start} AND min_time <= #{end_time}
+  """
+)
+```
+
+#### Using with Ecto Schemas
+
+While R*Tree tables are virtual tables, you can still define schemas for them:
+
+```elixir
+defmodule MyApp.GeoRegion do
+  use Ecto.Schema
+
+  @primary_key {:id, :integer, autogenerate: false}
+  schema "geo_regions" do
+    field :min_lat, :float
+    field :max_lat, :float
+    field :min_lng, :float
+    field :max_lng, :float
+  end
+end
+
+# Insert using Ecto
+region = %MyApp.GeoRegion{
+  id: 1,
+  min_lat: -34.0,
+  max_lat: -33.8,
+  min_lng: 151.0,
+  max_lng: 151.3
+}
+Repo.insert!(region)
+
+# Query using fragments
+import Ecto.Query
+
+# Find regions containing a point
+point_lat = -33.87
+point_lng = 151.21
+
+query = from r in MyApp.GeoRegion,
+  where: fragment("min_lat <= ? AND max_lat >= ?", ^point_lat, ^point_lat),
+  where: fragment("min_lng <= ? AND max_lng >= ?", ^point_lng, ^point_lng)
+
+regions = Repo.all(query)
+```
+
+#### Common Query Patterns
+
+```elixir
+# 1. Point containment: Does bounding box contain this point?
+"""
+SELECT id FROM rtree_table
+WHERE min_x <= ?1 AND max_x >= ?1
+  AND min_y <= ?2 AND max_y >= ?2
+"""
+
+# 2. Bounding box intersection: Do two boxes overlap?
+"""
+SELECT id FROM rtree_table
+WHERE max_x >= ?1 AND min_x <= ?2  -- Query box: ?1 to ?2
+  AND max_y >= ?3 AND min_y <= ?4  -- Query box: ?3 to ?4
+"""
+
+# 3. Range query: All items within bounds
+"""
+SELECT id FROM rtree_table
+WHERE min_x >= ?1 AND max_x <= ?2
+  AND min_y >= ?3 AND max_y <= ?4
+"""
+```
+
+#### R*Tree vs Vector Search
+
+**Use R*Tree when:**
+- You have bounding box data (geographic regions, time ranges)
+- You need exact range queries (all items within bounds)
+- Working with 1-5 dimensional coordinate data
+- Query performance is critical for range lookups
+
+**Use Vector Search when:**
+- You have high-dimensional embeddings (384-1536+ dimensions)
+- You need similarity/distance-based search
+- Working with semantic search, recommendations, or ML features
+- Approximate nearest neighbors is acceptable
+
+**Hybrid Approach:**
+```elixir
+# Combine both for location-aware semantic search
+"""
+SELECT p.*, vector_distance_cos(p.embedding, ?1) as similarity
+FROM products p
+JOIN geo_regions r ON r.id = p.region_id
+WHERE r.min_lat <= ?2 AND r.max_lat >= ?2
+  AND r.min_lng <= ?3 AND r.max_lng >= ?3
+ORDER BY similarity
+LIMIT 10
+"""
+```
+
 ### Connection Management
 
 Control connection behaviour and performance with these utilities (v0.7.0+):
@@ -4113,3 +4318,29 @@ Found a bug or have a feature request? Please open an issue on GitHub!
 ## License
 
 Apache 2.0
+
+## Landing the Plane (Session Completion)
+
+**When ending a work session**, you MUST complete ALL steps below. Work is NOT complete until `git push` succeeds.
+
+**MANDATORY WORKFLOW:**
+
+1. **File issues for remaining work** - Create issues for anything that needs follow-up
+2. **Run quality gates** (if code changed) - Tests, linters, builds
+3. **Update issue status** - Close finished work, update in-progress items
+4. **PUSH TO REMOTE** - This is MANDATORY:
+   ```bash
+   git pull --rebase
+   bd sync
+   git push
+   git status  # MUST show "up to date with origin"
+   ```
+5. **Clean up** - Clear stashes, prune remote branches
+6. **Verify** - All changes committed AND pushed
+7. **Hand off** - Provide context for next session
+
+**CRITICAL RULES:**
+- Work is NOT complete until `git push` succeeds
+- NEVER stop before pushing - that leaves work stranded locally
+- NEVER say "ready to push when you are" - YOU must push
+- If push fails, resolve and retry until it succeeds
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -9,6 +9,31 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 ### Added
 
+- **R*Tree Spatial Indexing Support**
+  - Full support for SQLite R*Tree virtual tables for multi-dimensional spatial indexing
+  - **Table creation**: Use `:rtree => true` option in Ecto migrations
+  - **Dimensions supported**: 1D to 5D (3 to 11 columns total including ID)
+  - **Column structure**: First column must be `id` (integer primary key), followed by min/max coordinate pairs
+  - **Validation**: Automatic validation of column count (odd numbers only), column naming, and dimensional constraints
+  - **Use cases**: Geographic bounding boxes, collision detection, time-range queries, spatial indexing
+  - **Migration example**:
+    ```elixir
+    create table(:geo_regions, rtree: true) do
+      add :id, :integer, primary_key: true
+      add :min_lat, :float
+      add :max_lat, :float
+      add :min_lng, :float
+      add :max_lng, :float
+    end
+    ```
+  - **Query patterns**: Point containment, bounding box intersection, range queries
+  - **Virtual table syntax**: Generates `CREATE VIRTUAL TABLE ... USING rtree(...)` DDL
+  - **Implementation**: New `create_rtree_table/3` and `validate_rtree_columns!/1` helpers in `connection.ex`
+  - **Comprehensive test coverage** in `test/rtree_test.exs` covering 2D/3D tables, validation, queries, and CRUD operations
+  - **Documentation**: Full guide in AGENTS.md with examples for geographic data, time-series, and hybrid vector+spatial search
+  - **Comparison guide**: R*Tree vs Vector Search decision matrix in documentation
+  - **Ecto integration**: Works with Ecto schemas using fragments for spatial queries
+
 - **Named Parameters Execution Support**
   - Full support for SQLite named parameter syntax in prepared statements and direct execution
   - **Three SQLite syntaxes supported**: `:name`, `@name`, `$name`
diff --git a/README.md b/README.md
@@ -90,6 +90,7 @@ For lower-level control, you can use the DBConnection interface directly:
 
 **Advanced Features**
 - Vector similarity search
+- R*Tree spatial indexing for multi-dimensional range queries
 - Database encryption (local AES-256-CBC and Turso remote encryption)
 - WebSocket and HTTP protocols
 - Cursor-based streaming for large result sets (via DBConnection interface)
diff --git a/lib/ecto/adapters/libsql/connection.ex b/lib/ecto/adapters/libsql/connection.ex
@@ -184,17 +184,23 @@ defmodule Ecto.Adapters.LibSql.Connection do
     table_name = quote_table(table.prefix, table.name)
     if_not_exists = if command == :create_if_not_exists, do: " IF NOT EXISTS", else: ""
 
-    # Check if we have a composite primary key.
-    composite_pk = composite_primary_key?(columns)
+    # Check if this is an R*Tree virtual table
+    if table.options && Keyword.get(table.options, :rtree, false) do
+      create_rtree_table(table_name, if_not_exists, columns)
+    else
+      # Standard table creation
+      # Check if we have a composite primary key.
+      composite_pk = composite_primary_key?(columns)
 
-    column_definitions =
-      Enum.map_join(columns, ", ", &column_definition(&1, composite_pk))
+      column_definitions =
+        Enum.map_join(columns, ", ", &column_definition(&1, composite_pk))
 
-    {table_constraints, table_suffix} = table_options(table, columns)
+      {table_constraints, table_suffix} = table_options(table, columns)
 
-    [
-      "CREATE TABLE#{if_not_exists} #{table_name} (#{column_definitions}#{table_constraints})#{table_suffix}"
-    ]
+      [
+        "CREATE TABLE#{if_not_exists} #{table_name} (#{column_definitions}#{table_constraints})#{table_suffix}"
+      ]
+    end
   end
 
   def execute_ddl({:drop, %Ecto.Migration.Table{} = table, _}) do
@@ -474,6 +480,60 @@ defmodule Ecto.Adapters.LibSql.Connection do
     {table_constraints, table_suffix}
   end
 
+  defp create_rtree_table(table_name, if_not_exists, columns) do
+    # R*Tree virtual tables require specific column structure:
+    # First column: integer primary key (id)
+    # Remaining columns: coordinate pairs (min/max)
+
+    # Extract column names for R*Tree
+    rtree_columns =
+      Enum.map(columns, fn {:add, name, _type, _opts} ->
+        Atom.to_string(name)
+      end)
+
+    # Validate column structure
+    validate_rtree_columns!(rtree_columns)
+
+    # Build R*Tree column list: id, min1, max1, min2, max2, ...
+    column_list = Enum.join(rtree_columns, ", ")
+
+    [
+      "CREATE VIRTUAL TABLE#{if_not_exists} #{table_name} USING rtree(#{column_list})"
+    ]
+  end
+
+  defp validate_rtree_columns!(columns) do
+    # R*Tree requires odd number of columns (3 to 11)
+    # First column is ID, then min/max pairs
+    num_columns = length(columns)
+
+    cond do
+      num_columns < 3 ->
+        raise ArgumentError,
+              "R*Tree tables require at least 3 columns (id + 1 dimension). Got #{num_columns} columns."
+
+      num_columns > 11 ->
+        raise ArgumentError,
+              "R*Tree tables support maximum 11 columns (id + 5 dimensions). Got #{num_columns} columns."
+
+      rem(num_columns, 2) == 0 ->
+        raise ArgumentError,
+              "R*Tree tables require odd number of columns (id + min/max pairs). Got #{num_columns} columns."
+
+      true ->
+        :ok
+    end
+
+    # Validate first column is 'id'
+    [first_column | _rest] = columns
+    unless first_column == "id" do
+      raise ArgumentError,
+            "R*Tree tables must have 'id' as the first column. Got '#{first_column}' instead."
+    end
+
+    :ok
+  end
+
   ## Query Helpers
 
   defp quote_table(nil, name), do: quote_name(name)
diff --git a/test/rtree_test.exs b/test/rtree_test.exs
