Skip to content

HNSW connect components can take an inordinate amount of time #14214

@benwtrent

Description

@benwtrent

Description

Connect components on Flush or merge, while good for graphs that are "almost OK" but need to be better connected, can just destroy performance if the vector distribution is poor.

I don't readily have test data, but if you have tightly clustered, or many duplicate vectors, it can take until the "heat death of the universe" to complete.

It seems to me that since connect Components is a "best effort fix up" of the graph, we should add a "cap" on the amount of work this does.

Marking as a bug as I have seen this for real users and it effectively takes a CPU hostage for hours (maybe days).

Version and environment details

No response

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions