Skip to content

64-bit IDs, with -1 for missing results #211

Open

Description

@gouyt13

Problem

Point IDs are row numbers of type uint32 (PID in include/rabitqlib/index/types.hpp),
and missing search results are marked with 2**32 - 1. One index therefore holds at most
2^32 - 1 points, and the Python API returns uint32 arrays.

Why now

RaBitQ-SSD (paper) extends IVF-RaBitQ to SSD-resident data and is planned to move into this library. It indexes datasets with more than 2^32 - 1 vectors (the paper's DINO-10B has ten billion), so its point IDs are 64-bit. There this is a compile-time option (RABITQ_PID64), and each build reads only the files it wrote. A Python wheel ships one build, so here the ID width must be 64-bit in the API and recorded in each file (#212). Moving the existing indexes to int64 IDs first gives every index the same ID type and the same missing-result marker: -1, which has the same bits as RaBitQ-SSD's all-ones kPidMax.

Proposal

  • search returns int64 IDs; missing results get -1 (the Faiss convention) instead of
    2**32 - 1, with distance inf as today.
  • add returns int64 IDs and remove takes them. IDs stay the row numbers the index
    assigns, so numbering does not change.
  • Saved files record the ID width (Index file format v2 with a written specification #212).

Caller-provided IDs (add(x, ids=...)) are not part of this issue. Adding them later is not a
breaking change, and the v2 format should leave room for an external-ID section so that it
needs no further format change.

Compatibility

This is a breaking change for code that compares IDs with 2**32 - 1 /
np.iinfo(np.uint32).max or relies on uint32 arrays. Since 0.8.2 the docs recommend
np.isfinite(distances), which works before and after. txtai currently checks
uid != 0xFFFFFFFF, so its migration (see #213) should switch to isfinite first.

Open questions

  • Should C++ PID become 64-bit for every index, or only at the API boundary and for the
    SSD index? HNSW-RaBitQ and SymphonyQG store a PID per neighbor, so a 64-bit PID
    doubles that part of graph memory; keeping 32-bit row numbers inside in-memory indexes
    avoids it.
  • Which C++ signatures change (search outputs, add return values, remove input), and is
    that change listed in the release notes for C++ users?

Activity

  1. added this to the 0.9 milestone on Nov 2, 2026
  2. gouyt13 commented on Nov 13, 2026

    @gouyt13
    MemberAuthor

    Status: the Python side is merged into dev/0.9 with #222. search and add return int64 IDs, remove takes them, and a missing result has ID -1.

    #234 proposes an answer to the two open questions above. The new C++ index classes it describes take and return 64-bit signed IDs, with -1 for a missing result, while the in-memory indexes keep 32-bit row numbers inside, so graph memory does not grow. PID and kPidMax stay as they are for the existing classes. Comments on that design are welcome in #234.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions