Package org.apache.lucene.util.hnsw

Class OnHeapHnswGraph

  • All Implemented Interfaces:
    Accountable
    public final class OnHeapHnswGraph
extends HnswGraph
implements Accountable
    An HnswGraph where all nodes and connections are held in memory. This class is used to construct the HNSW graph before it's written to the index.

    • Method Detail

      • getNeighbors

        public NeighborArray getNeighbors​(int level,
                                  int node)
        Returns the NeighborQueue connected to the given node.
        Parameters:
        level - level of the graph
        node - the node whose neighbors are returned, represented as an ordinal on the level 0.

      • size

        public int size()
        Description copied from class: HnswGraph
        Returns the number of nodes in the graph
        Specified by:
        size in class HnswGraph

      • maxNodeId

        public int maxNodeId()
        When we initialize from another graph, the max node id is different from size(), because we will add nodes out of order, such that we need two method for each
        Overrides:
        maxNodeId in class HnswGraph
        Returns:
        max node id (inclusive)

      • addNode

        public void addNode​(int level,
                    int node)
        Add node on the given level. Nodes can be inserted out of order, but it requires that the nodes preceded by the node inserted out of order are eventually added.

        NOTE: You must add a node starting from the node's top level

        Parameters:
        level - level to add a node on
        node - the node to add, represented as an ordinal on the level 0.

      • seek

        public void seek​(int level,
                 int targetNode)
        Description copied from class: HnswGraph
        Move the pointer to exactly the given level's target. After this method returns, call HnswGraph.nextNeighbor() to return successive (ordered) connected node ordinals.
        Specified by:
        seek in class HnswGraph
        Parameters:
        level - level of the graph
        targetNode - ordinal of a node in the graph, must be ≥ 0 and < FloatVectorValues.size().

      • nextNeighbor

        public int nextNeighbor()
        Description copied from class: HnswGraph
        Iterates over the neighbor list. It is illegal to call this method after it returns NO_MORE_DOCS without calling HnswGraph.seek(int, int), which resets the iterator.
        Specified by:
        nextNeighbor in class HnswGraph
        Returns:
        a node ordinal in the graph, or NO_MORE_DOCS if the iteration is complete.

      • numLevels

        public int numLevels()
        Returns the current number of levels in the graph
        Specified by:
        numLevels in class HnswGraph
        Returns:
        the current number of levels in the graph

      • entryNode

        public int entryNode()
        Returns the graph's current entry node on the top level shown as ordinals of the nodes on 0th level
        Specified by:
        entryNode in class HnswGraph
        Returns:
        the graph's current entry node on the top level

      • trySetNewEntryNode

        public boolean trySetNewEntryNode​(int node,
                                  int level)
        Try to set the entry node if the graph does not have one
        Returns:
        True if the entry node is set to the provided node. False if the entry node already exists

      • tryPromoteNewEntryNode

        public boolean tryPromoteNewEntryNode​(int node,
                                      int level,
                                      int expectOldLevel)
        Try to promote the provided node to the entry node
        Parameters:
        level - should be larger than expectedOldLevel
        expectOldLevel - is the old entry node level the caller expect to be, the actual graph level can be different due to concurrent modification
        Returns:
        True if the entry node is set to the provided node. False if expectOldLevel is not the same as the current entry node level. Even if the provided node's level is still higher than the current entry node level, the new entry node will not be set and false will be returned.

      • getNodesOnLevel

        public HnswGraph.NodesIterator getNodesOnLevel​(int level)
        WARN: calling this method will essentially iterate through all nodes at level 0 (even if you're not getting node at level 0), we have built some caching mechanism such that if graph is not changed only the first non-zero level call will pay the cost. So it is highly NOT recommended to call this method while the graph is still building.

        NOTE: calling this method while the graph is still building is prohibited

        Specified by:
        getNodesOnLevel in class HnswGraph
        Parameters:
        level - level for which to get all nodes
        Returns:
        an iterator over nodes where nextInt returns a next node on the level

      • ramBytesUsed

        public long ramBytesUsed()
        Description copied from interface: Accountable
        Return the memory usage of this object in bytes. Negative values are illegal.
        Specified by:
        ramBytesUsed in interface Accountable