Informix Forest of Trees Indexes

Abstract

The IBM Informix Dynamic Server (IDS) documentation page here gives this introduction:

“A forest of trees index is like a B-tree index, but it has multiple root nodes and potentially fewer levels. Multiple root nodes can alleviate root node contention, because more concurrent users can access the index. A forest of trees index can also improve the performance of a query by reducing the number of levels involved in buffer read operations.”

If your system has any indexes accessed by large numbers of users simultaneously, and if CPU usage is higher than expected, you might try replacing those most affected with FOT indexes. There are defects and caveats, so this should only be done when essential and after careful analysis.

Content

The following was an actual train of events at a customer running IDS 14.10 on Linux in VMware. The database instance contains real time data accessed by around 500 concurrent sessions from separate application servers. High CPU usage was being experienced, so the number of cores allocated to the VM was increased from 8 to 16 in the interim, and IDS CPU VPs changed correspondingly.

Meanwhile, we believed that index root node contention was a possible underlying cause. (The most expensive SQL query plans had already been checked and somewhat improved.) The visible symptom of that is spin lock waits, which can be viewed with “onstat -g spi“. The output is not directly readable as it contains part numbers rather than object names. We therefore use a shell script to parse the output with “awk”, and the object names are then looked up from the “sysmaster” database in SQL:

This produces a CSV file “spin_lock_waits.csv” in the current directory, including column headings. Results at the present time, after anonymising and beautifying in Excel, are as follows:

• These numbers may look very large but are in fact much improved. We previously had indexes at the top with waits several orders of magnitude more frequent, which were fixed by replacing with FOT indexes (see method below). We were then able to revert the number of cores and CPU VPs back to 8.
• There is not much that can be done for tables (rows with column “Index” empty) other than to ensure they have LOCK MODE ROW.
• Index “i1_apples” and “pk_pears” are not a concern as they have less contention than the table itself according to the row above in each case, and probably could not therefore be much improved.
• Index “3373_16002” actually has a space at the beginning of its name, and is an index implied by a constraint without being explicitly created beforehand with a more usable name. This would be the top remaining candidate for an FOT index (if not already so) followed by “pk_grapes” (primary key) and “fk2_lemons” (foreign key).

As an example of replacing a standard index with FOT, including common pitfalls, the following is from the schema of the standard “stores_demo” example database:

The above is exactly as in the output of “dbschema -d stores_demo -nw” but with keywords in uppercase and indentation improved for readability.

Imagine we found that there are disproportionately more frequent spin lock waits on the indexes implied by both the PRIMARY KEY and FOREIGN KEY above, so we wish to replace them with FOT. We will have to:

• drop the primary key constraint (also drops the foreign key and both implied indexes);
• create FOT indexes;
• add constraints.

Note that, whenever you drop a PRIMARY KEY constraint, you will always have to redeclare all FOREIGN KEY constraints that reference it (which we are doing anyway in this example), so you must identify them in advance for subsequent recreation, and keep a full schema for comparison afterwards. We can determine that – and also what existing constraints are called that were created without explicit names – using this SQL in the “stores_demo” database:

The above WHERE clause includes both the stated tables and others referencing them. Remove it to get a report across the whole database.

Results are:

All “idxname” values contain a leading space in the above cases, denoting a hidden index.

The SQL to replace the two indexes with FOT would be as follows (with applications stopped as exclusive table locks are required):

• Constraint “u102_3” is the primary key for table “orders” as shown by the previous SQL.
• Replacement visible indexes are created explicitly with meaningful names (best practice).
• Additional clauses “HASH ON (column)” and “WITH n BUCKETS” define the FOT.
• HASH ON must be leading column(s) of the index, so can only be “order_num” here.
• BUCKETS is most commonly set to 100, detailed research might suggest other numbers.
• Constraints are given explicitly meaningful names (best practice).
• NOVALIDATE saves time adding the FOREIGN KEY since we already know values conform.

A few days after creating FOT indexes, spin lock waits should be analysed again to check that those indexes have dropped down the list.

Caveats

Most systems do not need FOT indexes. They are only likely to be justifiable where there are hundreds or thousands of active sessions continually contending for the same index simultaneously. When used unnecessarily, they will increase the work required by the database engine, as will be seen in higher estimated costs in query plans. This may in turn result in the query optimizer not using the intended plan if other indexes exist on the table.

Recreating FOT indexes required by constraints on large tables will most likely involve a significant outage unless complex work-arounds are devised, such as creating and keeping replacement copies of affected tables and their new indexes up-to-date with loopback replication for subsequent swapping over.

There are major related defects, so be prepared to work around these or upgrade to the latest maintenance release. Recent examples are:

• IT35860: Forest of trees index becomes degraded following an in-place alter against columns which are not part of the index
• IT35888: Running oncheck -cI against a forest of trees index takes out a lock against every data row (or page) of the table

The following shell script lists FOT indexes and whether they need recreating because of defect IT35860:

Running that against the test database used for this article produces:

Conclusion

With the scripts provided in this article, it is easy to determine whether there are indexes that might be FOT candidates, and the syntax to recreate them is not difficult, but do so only when really necessary.

Disclaimer

Suggestions above are provided “as is” without warranty of any kind, either express or implied, including without limitation any implied warranties of condition, uninterrupted use, merchantability, fitness for a particular purpose, or non-infringement.