matrixorigin / matrixorigin/matrixone

[Bug]: IVFFLAT l2_distance range predicates use a different boundary value than scalar evaluation

Open
#29,040 1 comment 0 reactions 0 assignees View on GitHub
kind/bug needs-triage
Dominant language
Go
Stars
1.9k
Forks
311
Avg merge
1d 3h
Merged PRs (30d)
768

Description

## Description

An IVFFLAT scan evaluates `l2_distance` range predicates with a different numeric value from the public SQL function. At an exact boundary, the index path can return a row for which the same `WHERE` predicate evaluates to false, or omit a row that satisfies an inclusive predicate.

## Environment

- Branch: `main`
- Commit: `01d60e1c4ded1b0f3fc1a4ecd75ce54e95e23b90`
- Deployment: local multi-CN launch, 2 CN / 1 TN / 1 LogService; SQL endpoints `16001` and `16002`

## Steps to reproduce

```sql
SET experimental_ivf_index = 1;
SET probe_limit = 1;

DROP DATABASE IF EXISTS ivf_l2_boundary_min;
CREATE DATABASE ivf_l2_boundary_min;
USE ivf_l2_boundary_min;

CREATE TABLE t(id INT PRIMARY KEY, v VECF32(4));
INSERT INTO t VALUES
(29, '[2.189,-1.676,2.08,-1.578]'),
(99, '[10,10,10,10]');

CREATE INDEX i USING IVFFLAT ON t(v)
LISTS=1 OP_TYPE 'vector_l2_ops';

-- The public function says row 29 is exactly on the boundary and `>` is false.
SELECT id,
l2_distance(v,'[1.125,-0.625,0.375,1.75]') AS d,
l2_distance(v,'[1.125,-0.625,0.375,1.75]') > 4.02731990814209 AS satisfies
FROM t WHERE id=29;

-- Exact table-scan control excludes row 29.
SELECT id, l2_distance(v,'[1.125,-0.625,0.375,1.75]') AS d
FROM t
WHERE l2_distance(v,'[1.125,-0.625,0.375,1.75]') > 4.02731990814209
ORDER BY l2_distance(v,'[1.125,-0.625,0.375,1.75]')
LIMIT 10 BY RANK WITH OPTION 'mode=force';

-- IVFFLAT incorrectly includes row 29.
SELECT id, l2_distance(v,'[1.125,-0.625,0.375,1.75]') AS d
FROM t
WHERE l2_distance(v,'[1.125,-0.625,0.375,1.75]') > 4.02731990814209
ORDER BY l2_distance(v,'[1.125,-0.625,0.375,1.75]')
LIMIT 10 BY RANK WITH OPTION 'mode=post';
```

## Actual behavior

The scalar evaluation is:

```text
id d satisfies
29 4.02731990814209 0
```

`mode=force` excludes row 29. The IVFFLAT path returns it with a different score:

```text
id d
29 4.027320069947357
99 18.771237971961252
```

The opposite boundary is also wrong: `l2_distance(...) <= 4.02731990814209` includes row 29 under `mode=force`, but all tested IVFFLAT modes omit it.

## Expected behavior

An index access path must preserve the public SQL predicate semantics. A row for which the scalar `l2_distance(...) > bound` expression is false must not be returned by the same indexed query, and inclusive bounds must not lose qualifying rows.

## Stability and controls

- Reproducer: 3 independent indexes on each of 2 CN endpoints, 3/3 per endpoint.
- Affected modes: `post`, `pre`, `auto`, and `include`.
- Matrix result: 48/48 boundary checks produced the same wrong membership (`>` false positive and `<=` false negative).
- `l2_distance_sq`: all 168 corresponding checks matched `mode=force`.
- `l2_distance` bounds shifted by `+1e-5` or `-1e-5`: all controls matched `mode=force`.
- Equality, `<`, and `>=` controls at the same bound matched in this fixture.
- No panic, hang, restart, or data mutation was observed.

## Evidence

The full differential reproducer is `evidence/ivfflat_distance_boundary_differential.py` in the local validation worktree. It compares exact row membership rather than only query completion.

## Code analysis

The scalar `l2_distance` implementation returns the square root cast back to the vector element type. For `VECF32`, `metric.L2Distance[T]` therefore rounds the result to `float32` before the SQL function exposes it as `float64` (`pkg/vectorindex/metric/distance_func_amd64.go`).

IVFFLAT stores/searches squared L2 and converts it through `DistanceTransformIvfflat`, which applies `math.Sqrt` and retains the `float64` result (`pkg/vectorindex/metric/types.go`, called by `pkg/vectorindex/ivfflat/search.go`). `filterEntryDistanceRange` compares that transformed value directly with the peeled SQL bound (`pkg/vectorindex/ivfflat/relation_search.go`), so the original predicate is not re-evaluated with the public function's value.

For the reproducer row those paths produce `4.02731990814209` and `4.027320069947357`, respectively, which changes boundary membership.

## Regression coverage

After the fix, add a vector regression that compares IVFFLAT and `mode=force` for exact `>`, `>=`, `<`, and `<=` boundaries under `post`, `pre`, `auto`, and `include`, with both `l2_distance` and `l2_distance_sq`.

## Related

- Source exploration: #28943
- Separate cache-function issue: #29038

Contributor guide

Open the contributing guide

Research direction

Start with evidence/ivfflat_distance_boundary_differential.py and trace the distance handling through pkg/vectorindex/metric/distance_func_amd64.go, pkg/vectorindex/metric/types.go, pkg/vectorindex/ivfflat/search.go, and pkg/vectorindex/ivfflat/relation_search.go. Run the reproducer and add vector regression coverage for both distance functions, all four boundary operators, and the listed IVFFLAT modes. Done means indexed results match mode=force at exact boundaries.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.