Scoping Routes with Composite Tenant-Geometry Indexes

A tenant-scoped radius query that leans on a native point index seeks the bounding box first and checks tenancy last. On a shared graph that is exactly backwards: the point index ranks candidates by proximity alone, so a NodeIndexSeek on location reads every tenant’s nodes inside the corridor, and a trailing Filter tenant_id = $t drops the foreign ones only after they have been materialized. The db hits scale with the number of tenants co-located in that box, and the gap between the seek and the filter is the same window where a missing predicate leaks a neighbour’s depot into a route. This page fixes the access path rather than the query text: it folds tenant_id into a single composite index so one seek resolves the tenant equality and the spatial range together — and it confronts head-on the fact that Neo4j point indexes cannot be composite, which is where most attempts at this quietly fall back to a scan.

The broader isolation model — parameterized Cypher, per-tenant GDS projections, and why the boundary is a security control — lives in enforcing multi-tenant security in spatial graphs. Here the scope is narrower and mechanical: the index structure that makes the composite seek possible, and proving push-down with PROFILE.

Prerequisites & Versions

The technique needs a composite range index and a precomputed scalar spatial key on every routable node. No GDS or APOC dependency is required for the seek itself.

pip install "neo4j>=5.18"

Every :Location node must already carry a tenant_id, a WGS 84 location point, and a precomputed geocell grid key before the index is built — back-filling the scalar key afterward leaves nodes that satisfy the geometry but sit outside the composite seek.

Implementation

Neo4j point indexes are single-property, so ON (n.tenant_id, n.location) cannot be a point index — that constraint is the whole reason this technique exists. The workaround that keeps a true composite seek is to precompute a scalar spatial key, a coarse integer grid cell, alongside the point, then build a composite range index whose leading key is tenant_id and whose trailing key is that cell. The tenant equality resolves the leading key exactly; the covering cells for the search box resolve the trailing key by membership; the exact point.distance() guard clips the box corners afterward.

The Python side computes the search box, enumerates the grid cells overlapping it, and passes tenant_id plus the cell list as parameters. Coordinates below are for a Chicago logistics tenant.

import asyncio
import math
from dataclasses import dataclass
from neo4j import AsyncDriver, AsyncGraphDatabase

CELL_DEG = 0.01          # ~1.1 km grid cell near the equator
_ROW_STRIDE = 100_000    # packs (row, col) into one collision-free integer


def geocell(lat: float, lon: float) -> int:
    """Deterministic integer grid cell — the composite index trailing key."""
    row = math.floor((lat + 90.0) / CELL_DEG)
    col = math.floor((lon + 180.0) / CELL_DEG)
    return row * _ROW_STRIDE + col


def bounding_box(lat: float, lon: float, radius_m: float) -> tuple[float, float, float, float]:
    R = 6_371_000.0
    d_lat = math.degrees(radius_m / R)
    d_lon = math.degrees(radius_m / (R * math.cos(math.radians(lat))))
    return lat - d_lat, lat + d_lat, lon - d_lon, lon + d_lon


def covering_cells(min_lat: float, max_lat: float, min_lon: float, max_lon: float) -> list[int]:
    """Every grid cell id that overlaps the query box — the IN-list for the trailing key."""
    r0 = math.floor((min_lat + 90.0) / CELL_DEG)
    r1 = math.floor((max_lat + 90.0) / CELL_DEG)
    c0 = math.floor((min_lon + 180.0) / CELL_DEG)
    c1 = math.floor((max_lon + 180.0) / CELL_DEG)
    return [r * _ROW_STRIDE + c for r in range(r0, r1 + 1) for c in range(c0, c1 + 1)]


@dataclass
class TenantRadiusQuery:
    tenant_id: str
    lat: float
    lon: float
    radius_m: float


RADIUS_CYPHER = """
MATCH (n:Location)
WHERE n.tenant_id = $tenant_id AND n.geocell IN $cells
WITH n, point.distance(
       n.location, point({srid: 4326, latitude: $lat, longitude: $lon})) AS dist_m
WHERE dist_m <= $radius
RETURN n.id AS id, dist_m
ORDER BY dist_m ASC
LIMIT 100
"""


async def ensure_schema(driver: AsyncDriver) -> None:
    """Composite RANGE index: tenant_id (equality) then geocell (range/IN)."""
    async with driver.session() as session:
        await session.run(
            "CREATE INDEX location_tenant_cell IF NOT EXISTS "
            "FOR (n:Location) ON (n.tenant_id, n.geocell)"
        )
        # Point index still backs the exact point.distance guard on the survivors.
        await session.run(
            "CREATE POINT INDEX location_geo IF NOT EXISTS "
            "FOR (n:Location) ON (n.location)"
        )


async def query_tenant_radius(driver: AsyncDriver, q: TenantRadiusQuery) -> list[dict]:
    min_lat, max_lat, min_lon, max_lon = bounding_box(q.lat, q.lon, q.radius_m)
    cells = covering_cells(min_lat, max_lat, min_lon, max_lon)
    async with driver.session(database="neo4j") as session:
        result = await session.run(
            RADIUS_CYPHER,
            tenant_id=q.tenant_id,
            cells=cells,
            lat=q.lat,
            lon=q.lon,
            radius=q.radius_m,
        )
        return [record.data() async for record in result]


async def main() -> None:
    driver = AsyncGraphDatabase.driver(
        "neo4j+s://your-cluster.databases.neo4j.io",
        auth=("neo4j", "secure-password"),
        max_connection_pool_size=40,
        connection_acquisition_timeout=5.0,
    )
    try:
        await ensure_schema(driver)
        q = TenantRadiusQuery(tenant_id="acme-logistics", lat=41.8781, lon=-87.6298, radius_m=3000)
        hits = await query_tenant_radius(driver, q)
        print(f"{len(hits)} nodes within {q.radius_m} m for tenant {q.tenant_id}")
    finally:
        await driver.close()


if __name__ == "__main__":
    asyncio.run(main())

To scope a route rather than a radius, anchor the endpoints through the same composite predicate — MATCH (s:Location) WHERE s.tenant_id = $tenant_id AND s.geocell IN $cells AND s.id = $start_id — so the origin and destination lookups seek the composite index before any shortestPath expansion begins, keeping the whole traversal inside the tenant’s cells.

How It Works

The seek behaviour follows from key order, and each piece maps to a line above.

• The leading key is an equality predicate. A composite range index is ordered first by tenant_id, then by geocell. Because the query pins tenant_id = $tenant_id exactly, the planner descends straight to that tenant’s slice of the index and never touches another tenant’s entries. The geocell IN $cells membership then resolves the trailing key as a set of bounded sub-seeks within that slice.
• The grid cell is the spatial key the range index can seek. A range index cannot do a two-dimensional bounding-box seek the way a point index does, so covering_cells flattens the box into a one-dimensional set of integer cells computed client-side. Passing them as an IN list keeps the predicate index-seekable and the plan cacheable; deriving cells per row in Cypher would defeat the seek exactly as a per-row trig box does in distance filter query patterns.
• The point distance guard restores exact geometry. Grid cells are square and coarser than the radius, so point.distance() on the bounded survivors clips the corners back to a true circle. It runs on a candidate set already reduced to one tenant, so its cost is bounded by local density, not by the whole label.

Client-side box and cell computation is what keeps tenant_id as the resolved leading key rather than a predicate the engine discovers mid-scan — the same planner-seek discipline detailed in graph query planner optimization.

Common Failure Patterns

1. Trying to make the point index composite. CREATE POINT INDEX ... FOR (n:Location) ON (n.tenant_id, n.location) fails — point indexes take exactly one property. There are two honest ways to get a composite access path, and picking one is a real trade-off:

// Option A (this page): composite RANGE index on a precomputed scalar cell.
CREATE INDEX location_tenant_cell IF NOT EXISTS
FOR (n:Location) ON (n.tenant_id, n.geocell);

// Option B: tenant-partitioned label with a native per-tenant POINT index.
// Keeps exact point-index seeks, but multiplies indexes and complicates admin.
CREATE POINT INDEX loc_tenant_acme IF NOT EXISTS
FOR (n:Location:Tenant_acme) ON (n.location);

Option A keeps one index for all tenants and a true two-dimensional seek collapses to a cell-set seek; Option B keeps native point semantics but you pay an index and a label per tenant, which fragments badly past a few dozen tenants. Choose A for many small tenants, B for a handful of large ones — and see spatial indexing strategies for how the cell key relates to geohash and quadtree encodings.

2. Tenant predicate applied after expansion. If the tenant filter lands after a variable-length MATCH, it becomes a post-traversal Filter and the expansion has already crossed into foreign subgraphs. Keep tenant_id = $tenant_id on the anchor node, before any -[:CONNECTS*]->, so the composite seek bounds the traversal at its root.

3. Wrong key order. Building the index as ON (n.geocell, n.tenant_id) inverts the seek: the leading key is now the cell, so the engine reads every tenant present in those cells and filters tenancy last — the exact post-scan shape this technique is meant to remove. The equality predicate must lead. Prove it with PROFILE:

PROFILE
MATCH (n:Location)
WHERE n.tenant_id = $tenant_id AND n.geocell IN $cells
RETURN count(n)
// Base operator must be NodeIndexSeek on location_tenant_cell,
// never NodeByLabelScan or a NodeIndexSeek on geocell feeding a Filter on tenant_id.

Reading these operator trees end to end is covered in reading EXPLAIN and PROFILE plans for spatial queries.

Performance Notes

The win is a selectivity change at the storage layer. For a box holding $N_{\text{box}}$ nodes across $T$ evenly distributed tenants, the two plans read

$$\text{rows}{\text{post-scan}} \approx N{\text{box}}, \qquad \text{rows}{\text{composite}} \approx \frac{N{\text{box}}}{T}$$

so the composite seek cuts db hits by roughly a factor of $T$ before the distance guard runs — and on a platform with hundreds of tenants sharing a metro, that factor is the difference between an index seek and an effective scan.

The trailing-key cost is the covering-cell count. For box half-extents $\Delta\phi, \Delta\lambda$ over a cell edge $c$ degrees, the IN list carries

$$\lvert \text{cells} \rvert \approx \left(\frac{2\Delta\phi}{c} + 1\right)\left(\frac{2\Delta\lambda}{c} + 1\right)$$

cells, each a sub-seek. Size $c$ near the typical query radius: too coarse and each cell overfetches nodes the distance guard must discard; too fine and the IN list balloons into thousands of sub-seeks. At CELL_DEG = 0.01 a 3 km radius resolves to a handful of cells, which is the sweet spot for city-scale logistics. The composite index does add write amplification — every insert updates the tenant-ordered key as well as the point index — so absorb it with per-tenant batch loads rather than interleaved single-row writes.

Related

• Enforcing Multi-Tenant Security in Spatial Graphs — the broader isolation model, parameterized Cypher, and per-tenant GDS projections this index underpins.
• Spatial Indexing Strategies — geohash, quadtree, and R-tree encodings behind the scalar cell key.
• Reading EXPLAIN and PROFILE Plans for Spatial Queries — confirming the composite seek instead of a post-scan filter.
• Distance Filter Query Patterns — the box-then-distance predicate the point guard reuses.

This guide is part of Spatial Security Boundaries, within Spatial Graph Database Fundamentals for Python.