Faster Index Block Searches

K.S. Bhaskar

YottaDB databases have a tree structure between blocks, but store records sequentially within a block, with the key of each record except the first stored as the difference from the preceding record’s key. While this is efficient for storage, records within a block are scanned linearly, which is less efficient than searching a tree structure. Since index blocks typically pack more records within a block than data blocks, searching within index blocks can consume a material percentage of an application’s CPU usage, especially for large databases, which can have many levels of index blocks.

This enhancement reduces the time spent searching index blocks by allocating a number of slots, called SEARCH_INDEX_SLOTS, each of SEARCH_INDEX_SIZE bytes. Each slot contains a sorted list of the expanded keys corresponding to a subset of records at different offsets within the block, so that linear scanning can start with an expanded key immediately preceding the key being sought while using a faster binary search to find that expanded key.

As an analogy, consider a key ring with many similar keys. Instead of going through them one at a time to find a key, you could insert labeled tags between the keys, so you only need to find a tag and then go through a smaller number of keys one at a time.

The GDE segment qualifiers SEARCH_INDEX_SLOTS and SEARCH_INDEX_SIZE are used to specify values used by MUPIP CREATE to set values in the database fileheader. The MUPIP SET qualifier SEARCH_INDEX_SIZE=<bytes>[,<slots>] is used to change the values in existing database files. The qualifiers SEARCH_INDEX and NOSEARCH_INDEX can be used to turn the feature on and off. Both GDE and MUPIP treat SEARCH_INDEX_SIZE=0 as instructing YottaDB to use the default values, of 1024 slots, each one quarter of the block size; so, for a database file with 4KiB blocks, the slots use 1MiB of shared memory. Changing the size or number of slots for an existing database file requires standalone access.

DSE DUMP FILEHEADER reports the values as “Search Index Slots” and “Search Index Size”.

In a large database file, the number of index blocks will almost certainly exceed the number of slots. A pessimal strategy would be to expand and cache an index block as soon as it is read into a global buffer – in an active database region, this would churn the slots, force each index block to incur the cost of expanding and caching, only to have this work discarded, resulting in slower performance than no caching. A heuristic attempts to prevent churning of the slots by reserving them for heavily used index blocks.

The enhancement works with both BG and MM access methods.

If you have a database file with very large global variables (e.g., four levels or more), and you feel some tuning might improve performance, you can empirically adjust the number of slots. A good starting point would be the sum number of index blocks above level 1 for the global variables in the database region. You can use MUPIP SIZE or MUPIP INTEG to determine that number. This would also be a good value to use for existing databases from prior YottaDB releases or GT.M versions.

MUPIP REORG disables the optimization when it runs, as it is likely to churn the slots.

Note that global variables that store cross references may pack more records in data blocks than index blocks. However, as cross references are often traversed in order when accessing data, using an optimization called “clues”, block searching in data blocks of cross reference global variables is not likely to benefit by extending this optimization to data blocks.

The table below summarizes the results of the threeen1gE.m program. This is a database stressing program to calculate the lengths of 3n+1 cycles which we use for evaluating database performance. You can see that the code that includes the new functionality has a trivial impact on performance when the feature is not used, but has a definite benefit when the feature is turned on with its default settings – we made no attempt to tune the settings for optimal performance.

Not unexpectedly, the enhancement had no impact on thesimulated interest posting benchmark. This is because the performance of that benchmark is sensitive to critical section performance, as discussed in our blog post Critical Section Performance in r2.04.

The functionality is now merged into the code base, and will be in the next release. If you would like to try it before the next release, download ydbinstall.sh make it executable and run it with the command sudo ydbinstall.sh --from-source --branch=master. If you do, please share your opinion with us. Thank you.

Credits

• Images generated by Google Gemini in response to prompting by the author.

Published on September 05, 2026

See All General