Vector top-K results change when LIMIT changes

Open
#176,171 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
48/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Active
Tech stack
go, sql
Domain
backend, databases

Research direction

Start by reproducing the SQL example and compare the plans chosen for LIMIT 100 and LIMIT 105; the payload does not name CockroachDB files or tests. Trace how vector search and scan access paths handle NULL vectors in distance-ordered queries. Done when both paths apply the same NULL semantics and increasing LIMIT preserves the smaller result set.

Written by the indexing model from the issue text.

Description

C-bug O-community T-specialized-indexing X-blathers-triaged

Describe the problem

For a distance-ordered vector query, changing only LIMIT can switch the plan
between vector search and a scan. The vector-search path omits rows whose
vector is NULL, while the scan path returns the NULL-vector row first. The
larger-LIMIT result is therefore not an extension of the smaller-LIMIT result.

In the case below, LIMIT 100 excludes the row with id = 999, while
LIMIT 105 includes it as the first row.

To Reproduce

DROP TABLE IF EXISTS vector_null_limit;

CREATE TABLE vector_null_limit (
    id INT PRIMARY KEY,
    cat INT,
    vec VECTOR(4),
    VECTOR INDEX (vec)
);

INSERT INTO vector_null_limit
SELECT g,
       g % 3,
       (('[' || ((g % 7))::float8::text || ',' ||
                ((g * 3 % 11))::float8::text || ',' ||
                ((g * 5 % 13))::float8::text || ',' ||
                ((g * 7 % 17))::float8::text || ']')::VECTOR(4))
FROM generate_series(1, 200) AS g;

INSERT INTO vector_null_limit VALUES (999, 2, NULL);

SELECT id
FROM vector_null_limit
ORDER BY vec <-> '[2,3,4,5]'
LIMIT 100;
-- First rows: 71, 115, 144, 37, 1
-- The NULL-vector row (id = 999) is absent.

SELECT id
FROM vector_null_limit
ORDER BY vec <-> '[2,3,4,5]'
LIMIT 105;
-- First rows: 999, 71, 115, 144, 37
-- The NULL-vector row (id = 999) is present.

SELECT
    (SELECT count(*) FROM (
        SELECT id FROM vector_null_limit
        ORDER BY vec <-> '[2,3,4,5]'
        LIMIT 100
    ) AS q100 WHERE id = 999) AS null_row_in_limit_100,
    (SELECT count(*) FROM (
        SELECT id FROM vector_null_limit
        ORDER BY vec <-> '[2,3,4,5]'
        LIMIT 105
    ) AS q105 WHERE id = 999) AS null_row_in_limit_105;
-- null_row_in_limit_100 | null_row_in_limit_105
-- ----------------------+-----------------------
--                     0 |                     1

Expected behavior

Both access paths should apply the same NULL-vector semantics. Increasing the
LIMIT should preserve the rows returned by the smaller LIMIT and only append
additional rows. Therefore, the two counts above should be equal.

Environment:

  • CockroachDB version: v26.3.0-alpha.00000000-dev-13cb3eb27674b4a981e5c526d04c2387e81efd0b
  • Server OS: Linux amd64
  • Client app: psql 16.15

Jira issue: CRDB-70499

Dominant language
Go
Stars
32.6k
Forks
4.2k
PR merge metrics
No merged PRs in 30d

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from cockroachdb/cockroach

All issues in cockroachdb/cockroach

Similar issues

More Go issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.