get-convex / get-convex/geospatial

sortKey range filters silently misfilter: tupleKey encoding uses little-endian Float64

Open
#50 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
TypeScript
Stars
29
Forks
6
PR merge metrics
No merged PRs in 30d

Description

### Summary

Range filters on `sortKey` (`.gte`, `.lt`, `.gt`, `.lte`) silently return wrong results across typical numeric ranges, because the `tupleKey` encoding writes the sortKey bits **little-endian**. `tupleKey` is used as the string primary cursor of `pointsByCell`, so its bytes are compared lexicographically — and IEEE 754 Float64 is only order-preserving under **big-endian** byte-wise comparison (with the total-order fixup for negatives that the code already applies). LE encoding sorts by the low-order mantissa byte instead of sign+exponent+high-mantissa, i.e. effectively randomly w.r.t. the numeric value.

Net effect: `cellRange`'s `.gte`/`.lt` bounds land at an arbitrary position in the actual sorted stream and the component scans unrelated docs. In my case, asking for condo listings under \$500k returned prices up to \$800k.

### Environment

- `@convex-dev/geospatial` `0.2.1`
- `convex` `1.35.1`
- Node `v24.12.0`
- Reproducible against current `main` at [`0c42603`](https://github.com/get-convex/geospatial/commit/0c42603362c2ad888372f6761e0685527bdb4e23d).

### Root cause — deep links

Both branches of `encodeTupleKey` pass `littleEndian: true`:

- [`src/component/lib/tupleKey.ts#L18-L19`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/lib/tupleKey.ts#L18-L19) — `setFloat64(1, sortKey, true)`
- [`src/component/lib/tupleKey.ts#L21`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/lib/tupleKey.ts#L21) / [`#L31`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/lib/tupleKey.ts#L31) — total-order fixup round-tripped via `getBigUint64`/`setBigUint64` with `littleEndian: true`
- Mirror flags in `decodeTupleKey` at [`#L61-L72`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/lib/tupleKey.ts#L61-L72) must flip together (round-trip still works, but the on-disk bytes change).

Call sites that rely on the ordering invariant:

- [`src/component/streams/cellRange.ts#L30`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/streams/cellRange.ts#L30), [`#L37`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/streams/cellRange.ts#L37), [`#L59`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/streams/cellRange.ts#L59), [`#L81`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/streams/cellRange.ts#L81) — `encodeBound(...)` used as `.gte`/`.lt` cursor bounds on `pointsByCell`.

Why this slipped through: the only test for this file is a round-trip test and never asserts order-preservation:

- [`src/component/lib/tupleKey.test.ts`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/lib/tupleKey.test.ts)

### Standalone repro — no Convex deployment needed

`repro.mjs` — mirrors the exact `encodeTupleKey` logic (including `d64`) and prints numeric-sorted vs string-sorted order for both endianness settings.

```js
// node repro.mjs
const CHARS = ".PYFGCRLAOEUIDHTNSQJKXBMWVZ_pyfgcrlaoeuidhtnsqjkxbmwvz1234567890"
.split("").sort().join("");

function d64encode(data) {
const view = new DataView(data);
let s = "", hang = 0;
for (let i = 0; i < view.byteLength; i++) {
const v = view.getUint8(i);
switch (i % 3) {
case 0: s += CHARS[v >> 2]; hang = (v & 3) << 4; break;
case 1: s += CHARS[hang | (v >> 4)]; hang = (v & 0xf) << 2; break;
case 2: s += CHARS[hang | (v >> 6)]; s += CHARS[v & 0x3f]; hang = 0; break;
}
}
if (view.byteLength % 3) s += CHARS[hang];
return s;
}

function encodeTupleKey(sortKey, pointId, littleEndian) {
const buf = new ArrayBuffer(9);
const view = new DataView(buf);
view.setUint8(0, 0x0d);
view.setFloat64(1, sortKey, littleEndian);
let u = view.getBigUint64(1, littleEndian);
if ((u & (1n << 63n)) !== 0n) u = ~u & ((1n << 64n) - 1n);
else u |= 1n << 63n;
view.setBigUint64(1, u, littleEndian);
return `${d64encode(buf)}:${pointId}`;
}

const sortKeys = [-1_000_000, -1, -0.5, 0, 0.5, 1, 100, 1_000, 100_000, 500_000, 1_000_000, 2_000_000, 3_000_000];

for (const le of [true, false]) {
const rows = sortKeys.map((k) => ({ sortKey: k, tupleKey: encodeTupleKey(k, "p", le) }));
const byNumeric = [...rows].sort((a, b) => a.sortKey - b.sortKey);
const byString = [...rows].sort((a, b) => a.tupleKey < b.tupleKey ? -1 : a.tupleKey > b.tupleKey ? 1 : 0);
const ok = byNumeric.every((r, i) => r.sortKey === byString[i].sortKey);
console.log(`\n=== littleEndian: ${le} — order preserving: ${ok} ===`);
console.log("numeric:", byNumeric.map(r => r.sortKey).join(", "));
console.log("string :", byString.map(r => r.sortKey).join(", "));
}
```

Actual output on Node 24.12:

```
=== littleEndian: true — order preserving: false ===
numeric: -1000000, -1, -0.5, 0, 0.5, 1, 100, 1000, 100000, 500000, 1000000, 2000000, 3000000
string : 0, 100, 0.5, 1, 1000, 100000, 3000000, 500000, 1000000, 2000000, -1000000, -1, -0.5

=== littleEndian: false — order preserving: true ===
numeric: -1000000, -1, -0.5, 0, 0.5, 1, 100, 1000, 100000, 500000, 1000000, 2000000, 3000000
string : -1000000, -1, -0.5, 0, 0.5, 1, 100, 1000, 100000, 500000, 1000000, 2000000, 3000000
```

Note the LE string order is nonsensical vs. the numeric order — `0` comes before `0.5`, `3_000_000` comes before `500_000`, negatives sort *after* positives, etc.

### Failing unit test to drop into the existing suite

Add to [`src/component/lib/tupleKey.test.ts`](https://github.com/get-convex/geospatial/blob/0c42603362c2ad888372f6761e0685527bdb4e23d/src/component/lib/tupleKey.test.ts). Fails on `main`, passes after flipping the endianness flags. Run with `npm run test`.

```ts
test("encodeTupleKey is order-preserving under string compare", () => {
const sortKeys = [-1_000_000, -1, -0.5, 0, 0.5, 1, 100, 1_000, 1_000_000, 3_000_000];
const tuples = sortKeys.map((k) => ({
sortKey: k,
tupleKey: encodeTupleKey(k, "p" as Id<"points">),
}));
const byNumeric = [...tuples].sort((a, b) => a.sortKey - b.sortKey).map((t) => t.sortKey);
const byString = [...tuples]
.sort((a, b) => (a.tupleKey < b.tupleKey ? -1 : a.tupleKey > b.tupleKey ? 1 : 0))
.map((t) => t.sortKey);
expect(byString).toEqual(byNumeric);
});
```

### End-to-end repro against a Convex deployment

```ts
import { GeospatialIndex } from "@convex-dev/geospatial";
import { components } from "./_generated/api";
import { internalMutation } from "./_generated/server";

const idx = new GeospatialIndex(components.geospatial);

export const repro = internalMutation({
handler: async (ctx) => {
await idx.insert(ctx, "a", { latitude: 45.5, longitude: -73.6 }, { k: "x" }, 1_000_000);
await idx.insert(ctx, "b", { latitude: 45.5, longitude: -73.6 }, { k: "x" }, 2_000_000);
await idx.insert(ctx, "c", { latitude: 45.5, longitude: -73.6 }, { k: "x" }, 3_000_000);

const res = await idx.query(ctx, {
shape: { type: "rectangle", rectangle: { west: -74, south: 45, east: -73, north: 46 } },
filter: (q) => q.eq("k", "x").gte("sortKey", 2_500_000),
limit: 10,
});

// Expected: [c]
// Actual on v0.2.1: [a, b, c] — filter bound lands in the wrong place in the sorted stream
return res.results.map((r) => r.key);
},
});
```

### Suggested fix

Flip both `littleEndian` flags in `encodeTupleKey` — and the mirror flags in `decodeTupleKey` — from `true` to `false`. The total-order fixup already applied (flip all bits for negatives, flip sign bit for non-negatives) is correct for BE byte comparison.

Storage-format change: deployments with existing rows must re-insert them after upgrading, since on-disk `tupleKey` values are not reinterpretable under the new encoding. Worth calling out in release notes or gating behind a major version.

### Workaround (until fixed)

Drop `sortKey` range predicates from the `filter` callback and apply the range post-load. S2-cell viewport scoping still works; you lose in-component range narrowing on sortKey:

```ts
const res = await idx.query(ctx, {
shape: { type: "rectangle", rectangle },
filter: (q) => q.in("source", sources),
limit: 500,
});
const rows = [];
for (const r of res.results) {
const doc = await ctx.db.get(r.key);
if (!doc) continue;
if (doc.price < priceMin || doc.price > priceMax) continue;
rows.push(doc);
}
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.