kapsee wrote:

My application is using the C interface to execute queries against firebird most of which are updates. I find that firebird consumes a lot of CPU while this is happening.

Ann W.Harrison answers:

The problem is likely to be garbage collection. Garbage collection - the removal of unnecessary versions of records - is an on-going process in all Firebird databases. The expensive part of garbage collection is not removing the data itself, but removing index entries. In particular, removing index entries when the index contains thousands of instance of that particular key value is very expensive.

The process that you can turn on and off is called "sweeping". A sweep is an separate thread that reads every record in the database and garbage collects unnecessary versions. Sweep also resets the oldest interesting transaction marker by changing the state of transactions from rolled back to committed once all their changes have been removed from the database. Sweeping is expensive and should not be done during high use periods. But it is not the only time garbage collection is done.

In Classic, garbage collection is performed by the transaction that finds the unneeded data. Any time any transaction finds an unnecessary record version it removes it, releasing the space it used for use in storing new records. It also removes index entries for those record versions.

SuperServer 1.0x and 1.5x have a separate garbage collect thread. When a transaction encounters an unnecessary record version, it posts that record to the garbage collect thread. When the garbage collect thread runs, it attempts to remove the version and its index entries. Where there are large numbers of duplicate values for the index entry being removed, the cost of garbage collection can exceed the quantum of time allocated to the garbage collect thread, so it must abandon its work. That leads to lots of CPU use with not much progress to show for it.

In SuperServer version 2, some garbage collection is done immediately by the transaction that encounters the unneeded record version - saving the extra I/O required for the garbage collect thread to read the page. More complex operations - where removing the unnecessary version would involve additional I/O - are deferred to the garbage collect thread.

More significantly, I think, Version 2 changes the index structure and makes garbage collecting index duplicates much less expensive.

Let me see if I can describe the problem simply. When you store a record, it typically goes at the end of the table. Not always, because space released by deleted records and garbage collected old versions will be used first, but typically new records show up at the end of the table. In Version 1.0x and 1.5x, duplicate index entries, on the other hand, are stored at the beginning of the list of duplicates.

OK, so you've got two lists - record data is stored with the most recent record last, duplicate index entries are stored with the most recent record first.

You decide to update or delete a group of records. No problem, that's fast and doesn't affect the indexes. When another transaction starts to read the table - whether in natural order or by index - it will read the table in storage order - effectively oldest first. So the oldest records are removed first. But their index entries are at the end of the list of duplicates. Finding that entry requires reading the whole list of duplicates. Removing the oldest entry in a list of 32,000 duplicates requires checking 32,000 index entries. Removing the second oldest requires checking 31,999 index entries, and so on...

Version 2 indexes order duplicates by the record number of the record to be deleted. The garbage collect thread can look up the entry to be removed by a combination of the value - not very selective - and the record number - very selective. For the purpose of garbage collection, all indexes are unique. Instead of examining 32,000 entries, the garbage collector goes directly to the one it needs to remove.

And that's a huge saving.

V2.0 will be released when it's finally judged ready. There is an alpha release available. However, you can identify and fix the indexes that are causing problems. Run gstat with the -r and -a switches, directing the output to a file.

The results will include some header information, then a description of each table. Most of the information is specialized and might be of interest under circumstances I can't really imagine. However, here is the interesting stuff.

Here's the first part of a table entry. It's followed by fill distribution which is of great interest to somebody, I suppose, but no practical value to you.

   Primary pointer page: 553, Index root page: 554
   Average record length: 50.91, total records: 3495877
   Average version length: 9.00, total versions: 10307, max versions: 2345

The first line is the table name (CONTACT) and the internal table id. Nothing much you can do with that. The second line is also internal information.

The third line says that the average length of a compressed record in the table is 50.91 bytes - which may be interesting in general but isn't pertinent for this discussion.

The fourth line does have some interesting information. The first part is the length of a back version - not interesting. The second part (total versions) is the number of back versions of records. Since its over 10 thousand, it suggests that garbage collection isn't going well for this table. The final entry on the line - which probably wraps for you - is called max versions and it is the maximum number of back versions for any single record in the table. In this (fictitious) case there is one record that has been modified two thousand three hundred and forty five times since it was garbage collected. That suggests that the application is doing something odd ... perhaps deliberately using the record as a gateway to protect something else ... but distinctly worth looking at.

Following the table entry are a series of entries describing all the indexes defined for the table. Here's an entry for a very suspect index. Again, I've left off the fill distribution as not being very interesting.

Index CONTACT_IDX1 (5)
   Depth: 3, leaf buckets: 5430, nodes: 3505877
   Average data length: 0.00, total dup: 2635903, max dup: 2005297

The first line is the name of the index and the internal index id - the scope of the id is the table...

The first item of the first line of detail is important. The depth of an index should be 3 or less. To decrease the depth of indexes, you must backup the database and restore it with a larger page size. The rest of the line describes the width of the index - not interesting - and the number of "nodes" - a node is an index entry. You'll often find that the number of nodes is higher than the number of records in the table. That happens when there are back versions that have separate index entries.

The second line is also interesting. The average data length is the length of the data portion of the index key after compression. Zero looks like a good number but it usually means that there are lots of duplicates in the index. The "total dup" is the total number of duplicated entries in the index. That number can be quite large without affecting performance, as long as the duplicates are distributed across all the entries. The "max dup" number is the real red flag. That's the largest number of instances of a single value in the index. In this case, it's two million five thousand two hundred and ninety seven.

When you find an index with a "max dup" number greater than about 30 thousand, you've found a candidate for replacement. If records are deleted from the table or modified to a different key value, that index will cause slow, CPU intensive garbage collection. But you can fix it. First, find the index definition and the table definition. Then drop the index. Finally, recreate the index with its existing keys first, followed by they primary key field(s) from the table. The index will continue to work (nearly) as well as it did before, and will no longer cause problems for the garbage collector.

Or, you can wait for Version 2.

Follow up...

So, following your directions I did a gstat and observed results. Now I have 2 questions:

  1. Most of my indexes with "max versions" > 30000 were used in foreign keys. So, what is your recommendation in that case? Maybe I should use some kind of trigger based referential integrity?

Ah yes. I should have mentioned that but was a bit short of time. Most of the really bad indexes are foreign key indexes, which is why the change in V2 is so very valuable. Until then, my best suggestion is to use triggers to check referential integrity. It's marginally less reliable than constraint based checking, but doesn't have the performance problems.

  1. I found an index with very good selectivity (0,0000063...), but which contains about 35K records with null value. So statistics shows "max versions = 35K". Is this a problem?

Could be. If records are normally stored with the field null then modified later to a real value, that modification will cause the null index entry to be garbage collected eventually, at considerable cost. I'd make a compound key for that index, trying to remember to simplify it later when the new index format is available.

Like this post? Share on: TwitterFacebookEmail

Related Articles


Firebird Community

Reading Time

~7 min read



Gems from Firebird Support list