Suggestion: FT.VACUUM a new command for compacting an existing index

[eifrah-aws]

As the current implementation of the HNSWLIB does not support releasing memory, but instead allows to use re-use it, it makes sense to add a new command FT.VACUUM (inspired from sqlite3 vacuum's command) which re-builds the index, excluding deleted nodes.

A rough implementation:

• Create an empty index using the same attributes as the original index
• Traverse the existing index, skipping deleted nodes (a rough code could look like this):

    // Create a new index without deleted elements
    hnswlib::HierarchicalNSW<float>* CreateCompactedIndex() {
        // Get current valid count
        size_t valid_count = 0;
        std::vector<size_t> valid_labels;
        std::vector<std::vector<float>> valid_vectors;
        
        // Collect all non-deleted elements
        for (size_t i = 0; i < index->getCurrentCount(); i++) {
            if (!index->isMarkedDeleted(i)) {
                valid_count++;
                valid_labels.push_back(i);
                
                // Get the vector data for this label
                std::vector<float> vec(dim);
                index->getDataByLabel(i, vec.data());
                valid_vectors.push_back(vec);
            }
        }
        
        // Create new index with exact size needed
        auto* new_index = new hnswlib::HierarchicalNSW<float>(
            space, 
            valid_count,
            index->getM(),
            index->getEfConstruction()
        );
        
        // Add all valid elements to new index
        for (size_t i = 0; i < valid_vectors.size(); i++) {
            new_index->addPoint(valid_vectors[i].data(), valid_labels[i]);
        }
        
        return new_index;
    }

• The index will be locked for "READ" during the above phase
• Any new mutation that occurred during the initial creation phase, is recorded into a temporary buffer
• Once the index creation is completed we lock the index, this time for "WRITE" and add we replay the data collected in the temporary buffer
• We switch between the index pointers and release the lock

Use cases

• The suggested command is expensive, but it is called by the user and the user should be aware of the consequences.

• It provides a (IMO) reasonable mitigation for people who are running low on memory (a typical usage for this: a user creates a cron job that runs during low traffic hours to reclaim memory)

Thoughts?
@yairgott @allenss-amazon

[yairgott]

I like this idea! My main concern with your suggestion is around "we lock the index, this time for "WRITE"" which may lead to prolong query unavailability. I think we can avoid this query unavailability with a slight change:
Iterate over the old index to add entries to the new index as you described above. During the transition, we maintain two indexes, old and new:

• Ingestion
  ** If the key does not exist in both indexes but the key exists in the dictionary, it's an insert to the new index.
  ** If the key exist in the new index, the mutation, it's necessarily a delete or an update operation, is applied to the new index and is issued a delete on the old index, to keep consistency.
  ** If the key does not exist in the new index but exist in the old index, it's necessarily a delete or an update operation, perform the mutation directly on the old index. The correct value would eventually be populated to the new index as part of the process of iterating over the old index.
• Searches are performed on both indexes, and the results are merged.

WDYT?

[allenss-amazon]

Why not just implement the ALIAS commands? Once those are in place, then we're done. You just issue FT.CREATE onto a new index and then when it's done issue an ALIAS to swap the two. There's no prohibitions on read/write locking, etc.