Transaction Support for HNSW Indexes

Hierarchical Navigable Small World (HNSW) indexes are specialized, memory-only structures designed for efficient vector search. Once an HNSW index is created, any subsequent inserts, updates, or deletes (DML operations) performed on the base table will not be reflected in the index.

A transaction is a logical, atomic unit of work that contains one or more SQL statements. Transaction consistency for HNSW indexes is maintained in Oracle database using two main structures: a private journal and a shared journal.

A private journal is a per-transaction in-memory data structure that tracks vectors, added or deleted by a transaction (updates are in fact a delete followed by an insert). This is comparable to transaction journals that are used to maintain the in-memory column store data (explained in Oracle Database In-Memory Guide). These in-memory data structures are used for maintaining read consistency and are located in the Vector Memory Pool.

A shared journal is an on-disk table-based object used for read consistency purposes. It is created at the time of creation of an HNSW index, and is associated with only that HNSW index. The Shared Journal contains the committed System Change Numbers (SCNs) and their corresponding modified rows following a transaction on the base table. The Shared Journal also maintains the order of all committed DML operations impacting the HNSW index since it's inception. As transactions in the base table are committed, the changes recorded in the Private Journal are converted to rows, flushed, and then written to the Shared Journal.

Let us see how the previously defined structures are used in conjunction of each other to achieve overall better performance for transaction maintenance and read consistency on tables with HNSW indexes:

  1. Obtaining Transactionally-Consistent Top-K Results:

    Following DMLs, read consistency is achieved by taking into account both the existing HNSW graph in memory as well as the query's private journal and shared journal to determine the list of transactionally-consistent set of deleted and inserted vectors. This consists of identifying exact lists of deleted vectors from the journals, running an approximate top-K search through the current version of the HNSW index by augmenting the filter to ignore deleted vectors, running an exact top-k search of newly inserted vectors in the journals, and merging the results of the two searches.

    This is illustrated by the following diagram:

    Description of hnsw_index_with_private_and_shared_journal.eps follows
    Description of the illustration hnsw_index_with_private_and_shared_journal.eps
  2. HNSW Graph Refresh:
    Queries that come after an index is created would need to lookup the index as well as the DMLs that occurred after it to get the top-K result. As more DMLs accumulate, queries become slower as the exact search on the shared journal vectors becomes more expensive than the approximate search on the currently indexed HNSW graph. To minimize this impact, a graph refresh is done using either incremental snapshots, or full repopulation.
    1. Incremental Snapshots:

      An incremental snapshot is an incremental updated version of the existing in-memory graph index combined with a list of all deleted vectors so far. This snapshot is linked to a specific commit SCN and helps reduce the size of the shared journal. The system automatically creates a snapshot when the journal becomes too large impacting the performance. When a snapshot is created, new vectors are added to the existing HNSW graph using the same algorithm which is currently used for graph creation. This method carefully picks which other vectors each new vector connects to, based on the parameters defined during the index creation time. Deleted vectors are not actually removed from the graph. Instead, they are tracked using bit vectors and hidden during search. In terms of memory, if you have 10% new inserts, then the vector memory requirement for the incremental snapshot will be approximately 10% more than the original HNSW graph. Bit vectors for deleted vertices are considered negligible in term of memory footprint.

      This is illustrated by the following diagram:

      Figure 6-6 HNSW Snapshots


      Description of Figure 6-6 follows
      Description of "Figure 6-6 HNSW Snapshots"

      Note:

      • Snapshots are not supported in Oracle RAC environment.
      • There are two snapshots available at any given point of time. The snapshot creation is done in a double buffered manner by keeping the latest snapshot online for queries. The oldest snapshot is dropped before a new snapshot is created.
      • Any query that comes below the build SCN for the current latest snapshot runs into error ORA 51815 "INMEMORY NEIGHBOR GRAPH HNSW vector index snapshot is too old.”
      • You can query the V$VECTOR_GRAPH_INDEX_SNAPSHOTS view to understand several parameters related to snapshots such as snapshot ID denoted by SNAPSHOT_ID, the SCN at which the snapshot was created denoted by BUILD_SCN, the SCN at which the snapshot is open for queries denoted by VALID_SCN, the number of vectors present in the graph for the snapshot denoted by NUM_VECTORS, the number of vectors marked as deleted in the graph denoted by NUM_DELETES, etc.
      • You can also query the V$VECTOR_GRAPH_INDEX table for the HNSW index that is in use to understand how the MAX_SNAPSHOT parameter changes with increasing vectors, denoted by the NUM_VECTORS parameter.
    2. Full Repopulation:

      As incremental snapshots accumulate many DMLs, especially deletes, the search performance and memory efficiency begin to degrade. Since deletes are only masked and not physically removed, the graph becomes cluttered, leading to slower queries and wasted space. When this overhead crosses a predefined threshold, the system automatically triggers a full repopulation of the HNSW index. While incremental snapshots are optimized for minimal, frequent updates, balancing performance and memory use, full repopulation, though more resource-intensive, is necessary to restore both search quality and space efficiency when the graph becomes too fragmented.

      Unlike incremental snapshots, which updates an existing graph, full repopulation builds a fresh graph while keeping the old one active for ongoing queries. For example, if 10% of the vectors are new, the memory needed for the new graph is about 10% more than the original, resulting in a peak memory usage of 2.1 times, which later drops to 1.1 times after the switch.

      This is illustrated by the following diagram:

      Description of hnsw_repopulation.eps follows
      Description of the illustration hnsw_repopulation.eps

    Note:

    • At the time of full repopulation (until a new HNSW graph becomes available), if a query tries to access an older version of the HNSW graph that no longer exists, then the read consistency error ORA-51815 "INMEMORY NEIGHBOR GRAPH HNSW vector index snapshot is too old." is triggered.

    • You can query the V$VECTOR_GRAPH_INDEX table for the HNSW index which contains information about the newly created graph. It is also possible to use the V$VECTOR_GRAPH_INDEX_CHECKPOINTS and the V$VECTOR_GRAPH_INDEX_SNAPSHOTS views to gather data on the most recent checkpoint and the first snapshot of the new graph.

You can use the idx_rebuild_mode parameter of the DBMS_VECTOR.REBUILD_INDEX procedure to specify how the HNSW graph should be refreshed. This parameter accepts only one value : FULL. This enables a full graph rebuild. By default, idx_rebuild_mode is set to NULL. In this case, the system follows the existing behavior: drop and recreates the index. The idx_rebuild_mode allows for a fine-grained control when managing index refresh operations.

An example which triggers a full repopulation:

execute dbms_vector.rebuild_index('galaxies_hnsw_idx', 
                                           'galaxies', 
                                           'embedding', 
                                            NULL, 
                                            NULL, 
                                           'INMEMORY NEIGHBOR GRAPH', 
                                           'EUCLIDEAN', 
                                            95, 
                                            FULL, 
                                           '{"type" : "HNSW", "neighbors" : 3, "efConstruction" : 4 }') ;

Note:

This code assumes that the index galaxies_hnsw_idx is already created on the galaxies table. See the Oracle documentation on Hierarchical Navigable Small World (HNSW) index syntax and parameters for guidance on creating an HNSW index.

Parent topic: About In-Memory Neighbor Graph Vector Index