A Guide to Optimizing Vector Indexes in OceanBase

🔧 Curious about the “fast and slow” of vector indexes? Head over to https://github.com/oceanbase/seekdb and try it yourself! Asynchronous builds, parallel optimization, rebuilds—all these hardcore features are waiting for you to explore~

Only by examining things can knowledge be perfected.

—— The Book of Rites

Prologue

OceanBase recently released the seekdb database, built around “lightweight + vector + AI.”

After seekdb’s release, we received many user questions about using vector indexes in seekdb, such as: how to optimize slow index creation, the memory requirements during creation, at what increment scale a rebuild is needed, and how to eliminate the performance impact of rebuilding—and so on.

So today, our vector-index engineer Xia Jin will devote this article to exactly these questions, starting from the build process of OceanBase / seekdb vector indexes and giving an in-depth, detailed analysis of all the above. If you have any questions, feel free to leave a comment~🙋

How a Vector Index Is Built

Many people notice that creating just one vector index produces a whole bunch of auxiliary tables.

CREATE TABLE t1(
  c1 INT,
  c2 VECTOR(10),
  PRIMARY KEY(c1),
  VECTOR INDEX idx1(c2) WITH (distance=l2, type=hnsw, lib=vsag));

select
   table_id,
   table_name,
   table_type
from oceanbase.__all_table
where database_id = 500001;
+----------+---------------------------------------------+------------+
| table_id | table_name                                  | table_type |
+----------+---------------------------------------------+------------+
|   500055 | t1                                          |          3 |
|   500061 | __AUX_LOB_META_500061_                      |         13 |
|   500062 | __AUX_LOB_PIECE_500062_                     |         12 |
|   500056 | __idx_500055_idx1                           |          5 |
|   500059 | __idx_500055_idx1_index_id_table            |          5 |
|   500060 | __idx_500055_idx1_index_snapshot_data_table |          5 |
|   500057 | __idx_500055_rowkey_vid_table               |          5 |
|   500058 | __idx_500055_vid_rowkey_table               |          5 |
+----------+---------------------------------------------+------------+
8 rows in set (0.01 sec)

For the meaning of table_type, see the seekdb open-source project code[2]. Here we’ll just show one figure rather than going into detail.

The Components of a Vector Index

Before understanding how a vector index is built, you first need to understand the components of the entire vector index. Taking the HNSW (Hierarchical Navigable Small World) index as an example, it consists of two parts: the in-memory index and the on-disk index.

The blue portion in the upper half of the figure above is the structure of the in-memory index. It is made up of three parts: the snapshot index (0-1), the increment in-memory index (0-3), and the valid_bitmap in-memory structure (0-3), which together form the in-memory portion of the vector index.

The black portion in the lower half is the on-disk index, which contains five auxiliary tables:

• Table 1, rowkey_vid_table, stores the mapping between rowkey and vid.

As the editor understands it, Table 1 records the correspondence between the primary table’s primary key and the vid. “vid” stands for vector id, though it would be clearer to interpret it as vector index value id.

• Table 2, vid_rowkey_table, stores the same content as Table 1. It exists because in certain application scenarios—such as query scenarios—it’s convenient to obtain a vid and then get the rowkey from that vid.

As the editor understands it, Table 2’s purpose is, after a vector-index query completes, to find the rowkey by vector_id in order to look up the primary table.

Both Table 1 and Table 2 have the same two columns (rowkey + vid). The difference is that Table 1’s primary key is the primary table’s rowkey, while Table 2’s primary key is the vid.

• Table 3, delta_buffer_table, mainly takes in the incremental data written by external DML operations on the primary table; the data is written directly into Table 3.

As the editor understands it, Table 3 mainly records the changed VectorID and Type. Type has only two values: ‘I’ for insert and ‘D’ for delete; each ID is written at most once and deleted at most once.

• Table 4, index_id_table, is actually a superset of Table 3, containing Table 3’s data across different time windows. A background user periodically flushes Table 3’s data into Table 4, in order to improve query efficiency in certain large-data scenarios. For example, in billing scenarios, where historical data is enormous, directly full-scanning Table 3 would take a long time; periodically importing Table 3’s accumulated data into Table 4 keeps Table 3 at a relatively stable, low data watermark, thereby improving query efficiency.
• Table 5, index_snapshot_data_table, stores the vector data. This vector data is first written into a Lob Meta table; after the Lob Meta table is written, the address of each segment corresponding to the Lob Meta table is stored in Table 5. In short, Table 5 stores the index’s vector data.

As the editor understands it:

Tables 1 and 2, because both relate to the primary table’s primary key, are shared auxiliary tables used in common by all vector indexes on that table.

Tables 3, 4, and 5 are auxiliary index tables exclusive to each vector index, and all have a vid column.

You probably don’t need to dwell on the exact roles of these last three tables. Simply put: vector data has a very loose dimensionality limit, so it needs to be stored using a large object like a LOB. Large objects shouldn’t be stored repeatedly, so only one copy is kept in Table 5; the other tables exist to ensure the update and query efficiency of the large objects in the vector index.

The Vector Index Build Flow

Now that we understand the overall structure of the index auxiliary tables in memory and on disk, let’s look at the build flow of the index tables.

First, you need to create the 5 auxiliary tables mentioned above along with their contents. Currently the auxiliary tables are created using the OceanBase DDL framework, primarily implemented in the form of DDL tasks. A DDL task is implemented mainly as a state machine, advancing the execution and transition of each state and handling the creation of the different auxiliary tables.

The state machine flow has three steps in total.

• Step 1: create Table 1, rowkey_vid table. If the table already exists, this step can be skipped; if not, it directly creates Table 1’s schema and then backfills the data in the table. When this state finishes, it moves to the next state.
• Step 2: create Table 3 (delta_buff_table) and Table 4 (index_id_table). No data backfill is needed here, because when Table 5 (index_snapshot_data_table) is created later, the data will be imported uniformly into Table 5; therefore Tables 3 and 4 don’t need a backfill operation. Once Table 3 is created, it can start receiving incremental data from external DML operations.
• Step 3: create Table 2 (vid_rowkey_table) and Table 5 (index_snapshot_data_table). Creating Table 2 is similar to creating Table 1: first create the schema, then backfill the data. Creating Table 5 is different from all the above: it requires creating both the in-memory index and the on-disk index. It first adds the data to the in-memory increment index, and once the data is complete, deserializes the data from the in-memory index into Table 5—two steps in all.

Once all the above is done, the index enters the active state, the index creation flow ends, and it’s ready to use.

State Advancement in the Build Flow

The execution flow of a DDL task is handled primarily as a state machine. The main logic is to process the current state accordingly and transition to the next state. Some users may wonder: why introduce an index state machine?

There are two main benefits of using a state machine: first, flow visualization, and second, state persistence.

Consider abnormal scenarios such as an LS (LogStream) leader switch, a restart, or a crash. In these abnormal scenarios, if Table 5’s data-backfill flow is in progress when a leader switch or restart occurs, then once the scenario recovers to normal, it only needs to continue from Table 5’s in-progress state rather than starting all over again—improving fault tolerance in abnormal scenarios.

Build Performance and Memory Analysis

Analysis of Time-Consuming Points

Let’s use two figures to analyze the time-consuming points during the index build.

The cluster in the figure has 20 million local rows. Building an index on this cluster and then querying the internal table __all_rootservice_event_history to obtain the time taken by each state of the index build, we can see:

• The WAIT_VID_RPWKEY_TABLE_COMPLEWEMT state ran from 10:53 all the way to 14:28, spanning about 3.5 hours.
• All other states took only a few minutes each.

Therefore, most of the time in the entire index build was concentrated in the WAIT_VID_RPWKEY_TABLE_COMPLEWEMT state.

By querying the internal table __all_rootservice_event_history for the states and times of the build sub-tasks under the WAIT_VID_RPWKEY_TABLE_COMPLEWEMT state, we can see that the most time-consuming one is the REDEFINITION state at 3.5 hours—essentially matching the time of the WAIT_VID_RPWKEY_TABLE_COMPLEWEMT state above. In other words, the time-consuming point of the WAIT_VID_RPWKEY_TABLE_COMPLEWEMT state lies in the REDEFINITION state.

Analysis of Build Time

Editor’s key point:

Be sure to read what follows from here!

We recommend bookmarking it for future reference~

The GV$SESSION_LONGOPS view shows the execution status and progress of cluster DDL operations; from this view we can derive the various states of the build process.

First, pay attention to parallelism. In the figure, the parallelism PARALLELISM is 1—that is, only one build process runs at a time, and the data-backfill operation within the build also has a parallelism of 1. Therefore the backfill process in this scenario is fairly slow, meaning a major factor in the slow build is that parallelism wasn’t enabled.

The second factor is the sampling points during the backfill process.

In the figure above, the red boxes are the values of each sampling point: the first is 122,000, the second 178,000, the third 297,000, the fourth 406,000, the fifth 642,000, and the sixth 648,000.

The second sampling point differs from the first by about 50,000, so the first shard has about 50,000 rows.

By the same reasoning: the second shard has about 120,000 rows, the third about 110,000, the fourth about 200,000, and the fifth only about 6,000. Starting from the third shard, the sampled data sizes diverge more and more, yet the fifth shard has only 6,000 rows.

We can draw a conclusion: the sampling may be uneven.

So what do these shards mean, and what are they used for during the build?

During backfill, OceanBase leverages the PX parallel framework, and you can specify the number of threads to use when creating the index. In the backfill process above, parallelism was 1—likely because no Hint specifying parallelism was added when creating the index, so only one thread was used for backfill.

Suppose 10 threads are used for backfill. The PX framework first samples out some data; because shards are of different sizes and backfill is allocated per thread, suppose there are ten chunks of data corresponding to ten shards, with each thread handling one shard. If sampling is uneven, one shard might be especially large while another is especially small.

For example, with 1 million rows, 10 threads specified, split into 10 shards, the first shard might handle 990,000 rows while the second shard or the remaining shards handle only a few thousand. Ultimately most of the time is spent in the first thread, making the overall index build inefficient. So the second factor that slows the index build is uneven sampling.

The third reason the index build is slow is slow single-row writes. If the table is non-partitioned, backfilling a non-partitioned table is equivalent to having only one in-memory index. Suppose the in-memory index stores 1 million rows; during backfill, all 1 million rows are written into a single partition. The HNSW index is an HNSW graph structure, and when inserting into the index, the larger the graph’s data volume, the longer the graph search takes. After inserting perhaps 900,000 rows, insertion may already become very slow. If you convert the table to a partitioned table—for example, spreading 1 million rows across 10 partitions—that’s equivalent to using parallelism, and insertion efficiency becomes much faster than with a single partition.

Therefore, there are three methods to optimize a slow index build: add parallelism, raise the sampling rate, and switch to a partitioned table.

Memory Analysis

By querying the __all_virtual_vector_index_info catalog table, we can obtain several key pieces of information.

The in-memory index is made up of three main parts:

• Increment index memory
• Snapshot index memory
• Vbitmap memory

Most of the memory footprint is in the increment index memory and the snapshot index memory, so these two parts are the main targets for memory optimization.

The stages that drive high memory usage are mainly the memory usage during the build process and the DML and persistence operations after the build is complete.

Memory-Usage Analysis and Optimization Recommendations

For memory-usage analysis, here are optimization recommendations for several scenarios.

• Scenario 1: high increment memory usage.
  • Periodically rebuild the index. For example, if the index has already been built and has undergone DML operations for a long time, and you find that the in-memory index’s usage is fairly high—i.e., increment memory usage is high—you can manually trigger a periodic rebuild. If you don’t trigger it manually, the background runs one every 24 hours by default. Rebuilding the index is a good way to reduce memory usage.
• Scenario 2: follower-replica memory usage (when weak reads aren’t needed).
  • If your scenario doesn’t need to support weak reads, you can remove the follower replica’s memory usage by tuning a parameter. Suppose you have multiple nodes, including leader and follower replicas; if you don’t need to query data on follower replicas, you can simply turn off loading the in-memory index on follower replicas, saving half the memory.
• Scenario 3: using a non-BQ index.
  • We recommend replacing the native HNSW index with an HNSW BQ index, which is equivalent to changing float (32-bit floating point) into Bit storage, greatly reducing the actual memory footprint of the vectors and thereby solving the high-memory problem of HNSW indexes.

In addition, we recommend using memory estimation to plan memory ahead of time. In response to feedback from some customers—for example, errors or stalls caused by running out of memory in later stages—you can use a tool to estimate memory before building the in-memory index. For example, OceanBase’s official DBMS tool can estimate memory and let you plan ahead, avoiding such errors down the line.

The memory-estimation capability is supported in versions after OceanBase V4.3.5_BP3.

Build Performance and Memory Optimization Recommendations

In summary, the approaches for build-speed optimization and build-memory optimization are as follows.

Build-Speed Optimization

1. Disable daily merge (merging consumes a lot of CPU resources): alter system set major_freeze_duty_time = 'disable';
2. Raise the execution priority of DDL backfill (default 2, max 8): alter system set ddl_thread_score = xxx;
3. Increase the number of threads in the PX execution thread pool (set higher than the parallelism): set global parallel_servers_target = xxx;
4. Increase the number of samples in the PX backfill sampling phase (default 200, upper limit 100,000; if the data volume is large, you can set it to 5,000—but bigger isn’t always better, as it may increase the time cost): alter system set _px_object_sampling = 5000;

Build-Memory Optimization

1. With multiple replicas, prevent follower nodes from loading the in-memory index: alter system set load_vector_index_on_follower = false;
2. Prevent in-memory index creation during the build (only the auxiliary index tables are created during the build; the in-memory index is loaded back later by another background task or on the first query): alter system set vector_index_memory_saving_mode = true;

Rebuild Principles and Memory Analysis

Why Rebuild

As DML operations bring in more and more updated data, the cost of querying the in-memory increment index and the valid_bitmap grows. The goal of a rebuild is to reduce the increment index’s memory footprint and query cost.

How a Rebuild Works

The principle behind rebuilding an index is actually quite simple: create a new index table with the same name, complete the data import, then drop the old index, swap the index names, and make the new index take effect. The figure below is the framework diagram of an index rebuild—as shown, it’s driven from the RS, executing the DDL task flow to finally complete index creation.

Rebuild Syntax

The REBUILD_INDEX procedure performs a full refresh (i.e., rebuild) of a vector index. The syntax to trigger an index rebuild (without setting parallelism) is: call dbms_vector.rebuild_index('idx1','t1','c2').

For more details, see the documentation: OceanBase Official Docs — REBUILD_INDEX[3].

When to Rebuild

Rebuilding an index is a table-level Rebuild and is fairly time-consuming. In general, we recommend rebuilding when incremental data exceeds 20% of the snapshot data, or when query-time access hotspots appear in Table 3. It’s best to do it during periods when CPU and memory are idle.

Memory Usage During a Rebuild

Because both the old and new indexes exist simultaneously during a rebuild, peak memory usage may be up to 2x the original index, dropping back to the new index’s memory watermark after the rebuild completes. There are some optimization techniques available for this process: because backfill during an index build proceeds partition by partition—rather than backfilling all partitions at once—you can drop the original in-memory index immediately after a given partition’s index is rebuilt. For example, with a partitioned table of 10 partitions where the original index uses 10G of memory, under limited resources you can reserve only 11G or 12G of memory and rebuild a single partition’s index at a time, dropping it after each rebuild, so that overall you don’t occupy too much disk or memory.

After a rebuild, the vast majority of memory is concentrated in the snap_index (snapshot index). But if DML operations occur during the rebuild, the post-rebuild incr_index (increment index) will also incur new memory overhead. We therefore recommend turning off DML traffic while rebuilding the index.

Future Outlook

Here are 3 points of outlook on the future capabilities of seekdb and OceanBase vector indexes:

1. Partition-level automatic parallel rebuild. OceanBase V4.3.5_BP3 already supports partition-level automatic rebuild, enabled by default. But the automatic rebuild backfills data single-partition, single-thread, without parallelism, so write efficiency is relatively slow. In the future we hope to support parallel rebuilds to speed up partition-level automatic rebuild.
2. Increment in-memory index optimization. Beyond partition-level automatic rebuild, we hope the vector index itself can optimize memory—for example, by migrating the increment in-memory index’s data elsewhere, or directly reducing the in-memory index’s memory footprint.
3. Build-performance optimization. Build-performance optimization will continue to improve, in order to give users a better experience.

References

[1] Online demo environment: https://www.oceanbase.com/demo/ob-hybrid-search-quick-start

[2] seekdb open-source project code: https://github.com/oceanbase/seekdb/blob/develop/src/share/schema/ob_schema_struct.h

[3] OceanBase Official Docs — REBUILD_INDEX: https://www.oceanbase.com/docs/common-oceanbase-database-cn-1000000003980771