bcheck and retrurned value in index b-tree

Hello,

Under Solaris 10 and 9, we are using a product which use an IBM C-ISAM
database to store a lot of data.

We had some problem with a database, some crash due to a database
corruption and impossibility to our software to replay a record on the
database, so the server was unable to update the database... ANYWAY !

When i run : bcheck <file> where file is an entity of the database, i
don't have an error but the index b-tree is high. In this exemple, the
index b-tree = 11 :

<a number> index node(s) used -- 11 index b-tree level(s) used

i d'ont know why, but after some weeks of investigation, the editor of
the software and IBM for the database believe that the problem occur
when the index b-tree exceeds 10.

i am not a DBA and i know nothing about C-ISAM database, but could you
give me your opinion please ?

What does it mean to have an big value of index b-tree ?

Thank You very much.

Regards
Rahan

Rahan wrote:

Under Solaris 10 and 9, we are using a product which use an IBM C-ISAM
database to store a lot of data.

We had some problem with a database, some crash due to a database
corruption and impossibility to our software to replay a record on the
database, so the server was unable to update the database... ANYWAY !

When i run : bcheck <file> where file is an entity of the database, i
don't have an error but the index b-tree is high. In this exemple, the
index b-tree = 11 :

a number> index node(s) used -- 11 index b-tree level(s) used

i d'ont know why, but after some weeks of investigation, the editor of
the software and IBM for the database believe that the problem occur
when the index b-tree exceeds 10.

i am not a DBA and i know nothing about C-ISAM database, but could you
give me your opinion please ?

What does it mean to have an big value of index b-tree ?

Seeing a B-Tree depth of 11 levels means several things all at once.

There is a limit of 10 levels in the code. This dates back to at least
1986; I don't have earlier code accessible. Why you are seeing 11 in
the output becomes contentious - it could be 10 levels apart from the
root node, perhaps.

It also means you have a honking big file. That is, your C-ISAM file
must contain many millions of records. In fact, it would interesting
indeed to have some basic statistics on your file - maybe the output of
of bcheck.

It also most probably means you have a huge index key size - you are
indexing some very long fields. Again, it would be interesting to have
the output of bcheck.

It also means that in theory, it will take 12 disk accesses to read each
row of data via the index (one for each level of the index, plus one to
retrieve the actual row of data). That observation needs to be
qualified with "but a sequential scan won't need that many accesses" and
"but the o/s will probably provide caching in its buffer pool of the
upper levels of the index so the actual physical disk accesses will be
smaller, but the number of read system calls could be close to a dozen
per row fetched". Also, note that reading 12 pages to get to the right
row is more efficient in general than scanning the entire file to find
the right row -- assuming you are selecting one or a very few records at
a time. If you are really fetching almost everything, then you might be
doing 12 times as much disk access as really necessary.

Basically, an index of depth over about 6 levels is a potential source
of concern in any B-Tree system (IDS as well as C-ISAM). It may be
unavoidable - but you should do your utmost to avoid it.

Do you know if your index uses either leading or trailing compression
(or both)? Could it? Should it?

[I've seen a few questions raised about this from the inside. At least,
I'd be surprised if you are not the people which caused the question
that was asked internally about this. And IDS has a limit of 20 levels
on the B-Tree. With large page sizes, it doesn't bear thinking about
how big a single table would have to be to overflow that. And the
calculation of how many rows you can fit gets, ... interesting! There
are lots of factors that affect the actual density of the index.]

--
Jonathan Leffler #include <disclaimer.h>
Email: jleffler (AT) earthlink (DOT) net, jleffler (AT) us (DOT) ibm.com
Guardian of DBD::Informix v2007.0914 -- http://dbi.perl.org/

publictimestamp.org/ptb/PTB-2182 haval 2008-01-03 06:00:04
C70CF9C9C126042A89BA3C218E19F609

Jonathan Leffler wrote:

Rahan wrote:

Under Solaris 10 and 9, we are using a product which use an IBM C-ISAM
database to store a lot of data.

We had some problem with a database, some crash due to a database
corruption and impossibility to our software to replay a record on the
database, so the server was unable to update the database... ANYWAY !

When i run : bcheck <file> where file is an entity of the database, i
don't have an error but the index b-tree is high. In this exemple, the
index b-tree = 11 :

a number> index node(s) used -- 11 index b-tree level(s) used

i d'ont know why, but after some weeks of investigation, the editor of
the software and IBM for the database believe that the problem occur
when the index b-tree exceeds 10.

i am not a DBA and i know nothing about C-ISAM database, but could you
give me your opinion please ?

What does it mean to have an big value of index b-tree ?


Seeing a B-Tree depth of 11 levels means several things all at once.

There is a limit of 10 levels in the code. This dates back to at least
1986; I don't have earlier code accessible. Why you are seeing 11 in
the output becomes contentious - it could be 10 levels apart from the
root node, perhaps.

It also means you have a honking big file. That is, your C-ISAM file
must contain many millions of records. In fact, it would interesting
indeed to have some basic statistics on your file - maybe the output of
of bcheck.

It also most probably means you have a huge index key size - you are
indexing some very long fields. Again, it would be interesting to have
the output of bcheck.

It also means that in theory, it will take 12 disk accesses to read each
row of data via the index (one for each level of the index, plus one to
retrieve the actual row of data). That observation needs to be
qualified with "but a sequential scan won't need that many accesses" and
"but the o/s will probably provide caching in its buffer pool of the
upper levels of the index so the actual physical disk accesses will be
smaller, but the number of read system calls could be close to a dozen
per row fetched". Also, note that reading 12 pages to get to the right
row is more efficient in general than scanning the entire file to find
the right row -- assuming you are selecting one or a very few records at
a time. If you are really fetching almost everything, then you might be
doing 12 times as much disk access as really necessary.

Basically, an index of depth over about 6 levels is a potential source
of concern in any B-Tree system (IDS as well as C-ISAM). It may be
unavoidable - but you should do your utmost to avoid it.

Do you know if your index uses either leading or trailing compression
(or both)? Could it? Should it?

[I've seen a few questions raised about this from the inside. At least,
I'd be surprised if you are not the people which caused the question
that was asked internally about this. And IDS has a limit of 20 levels
on the B-Tree. With large page sizes, it doesn't bear thinking about
how big a single table would have to be to overflow that. And the
calculation of how many rows you can fit gets, ... interesting! There
are lots of factors that affect the actual density of the index.]

Hello Jonathan and thank you very much for your answer.

this is the output of bcheck :

---------------------------------------------------------------------
BCHECK C-ISAM B-tree Checker version ISAM Version 7.26.UC1
Copyright (C) International Business Machines Corporation 2001.All rights
reserved.
Software Serial Number <XXXXXX>

C-ISAM File: <XXXXXXXXX>.dat

Checking dictionary and file sizes.
Index file node size = 1024
Current C-ISAM index file node size = 1024
Checking data file records.
Checking indexes and key descriptions.
Index 1 = unique key (0,17,0) (17,30,0)
49420 index node(s) used -- 7 index b-tree level(s) used
Index 2 = unique key (17,30,0) (47,71,0) (0,17,0)
132848 index node(s) used -- 11 index b-tree level(s) used
Checking data record and index node free lists.
183060 index node(s) used, 75086 free -- 440220 data record(s) used,
199739 free
---------------------------------------------------------------------

Please see the line with the index b-tree is 11 (exceeds 10).

Could you provide me your opinion please.

Thanks a lot.

Best Regards
Rahan

On Jan 3, 1:04 pm, Rahan <Ra... (AT) rahan (DOT) net> wrote:

Jonathan Leffler wrote:
Rahan wrote:

Under Solaris 10 and 9, we are using a product which use an IBM C-ISAM
database to store a lot of data.

We had some problem with a database, some crash due to a database
corruption and impossibility to our software to replay a record on the
database, so the server was unable to update the database... ANYWAY !

When i run : bcheck <file> where file is an entity of the database, i
don't have an error but the index b-tree is high. In this exemple, the
index b-tree = 11 :

a number> index node(s) used -- 11 index b-tree level(s) used

i d'ont know why, but after some weeks of investigation, the editor of
the software and IBM for the database believe that the problem occur
when the index b-tree exceeds 10.

i am not a DBA and i know nothing about C-ISAM database, but could you
give me your opinion please ?

What does it mean to have an big value of index b-tree ?

Seeing a B-Tree depth of 11 levels means several things all at once.

There is a limit of 10 levels in the code. This dates back to at least
1986; I don't have earlier code accessible. Why you are seeing 11 in
the output becomes contentious - it could be 10 levels apart from the
root node, perhaps.

It also means you have a honking big file. That is, your C-ISAM file
must contain many millions of records. In fact, it would interesting
indeed to have some basic statistics on your file - maybe the output of
of bcheck.

It also most probably means you have a huge index key size - you are
indexing some very long fields. Again, it would be interesting to have
the output of bcheck.

It also means that in theory, it will take 12 disk accesses to read each
row of data via the index (one for each level of the index, plus one to
retrieve the actual row of data). That observation needs to be
qualified with "but a sequential scan won't need that many accesses" and
"but the o/s will probably provide caching in its buffer pool of the
upper levels of the index so the actual physical disk accesses will be
smaller, but the number of read system calls could be close to a dozen
per row fetched". Also, note that reading 12 pages to get to the right
row is more efficient in general than scanning the entire file to find
the right row -- assuming you are selecting one or a very few records at
a time. If you are really fetching almost everything, then you might be
doing 12 times as much disk access as really necessary.

Basically, an index of depth over about 6 levels is a potential source
of concern in any B-Tree system (IDS as well as C-ISAM). It may be
unavoidable - but you should do your utmost to avoid it.

Do you know if your index uses either leading or trailing compression
(or both)? Could it? Should it?

[I've seen a few questions raised about this from the inside. At least,
I'd be surprised if you are not the people which caused the question
that was asked internally about this. And IDS has a limit of 20 levels
on the B-Tree. With large page sizes, it doesn't bear thinking about
how big a single table would have to be to overflow that. And the
calculation of how many rows you can fit gets, ... interesting! There
are lots of factors that affect the actual density of the index.]

Hello Jonathan and thank you very much for your answer.

this is the output of bcheck :

---------------------------------------------------------------------
BCHECK C-ISAM B-tree Checker version ISAM Version 7.26.UC1
Copyright (C) International Business Machines Corporation 2001.All rights
reserved.
Software Serial Number <XXXXXX

C-ISAM File: <XXXXXXXXX>.dat

Checking dictionary and file sizes.
Index file node size = 1024
Current C-ISAM index file node size = 1024
Checking data file records.
Checking indexes and key descriptions.
Index 1 = unique key (0,17,0) (17,30,0)
49420 index node(s) used -- 7 index b-tree level(s) used
Index 2 = unique key (17,30,0) (47,71,0) (0,17,0)
132848 index node(s) used -- 11 index b-tree level(s) used
Checking data record and index node free lists.
183060 index node(s) used, 75086 free -- 440220 data record(s) used,
199739 free
---------------------------------------------------------------------

Please see the line with the index b-tree is 11 (exceeds 10).

Could you provide me your opinion please.

Your index is big; your table is very fragmented. Bcheck doesn't
indicate the record size, which is odd. Can you tell me how big the
data records are? Or send the 'ls -l' output of the .dat and .idx
files; you can mask the actual file name again as I'm only interested
in the sizes. Your 'index 2' is on 3 columns, and the total key size
is 118 bytes (30 + 71 + 17) of character data (that's the 0 at the end
of each triplet; the first number in the triplet is the starting
offset for the field). So, with a unique index, there is a 4-byte
record ID for each key in the index structure. So, with index nodes
of 1 KB, you can fit 8 keys per page. If your index was fully
compressed, you'd not reach 11 levels until you got to 8 G (8 billion
or so) records - for N levels, you'd have 8^N records if fully
compressed. Clearly, with a few hundred thousand records, you are
nowhere near that theoretical limit - there is a lot of fragmentation
in the index. With 440 K rows in the table, you'd expect to need at
least 5 levels in the index, even with perfectly balanced splitting of
the nodes.

I see that bcheck claims that 49420 + 132848 = 182268 nodes in use;
but it then also says 183060 nodes are in use. I wonder where the
extra 792 nodes are being used. This may be indicative of problems
due to exceeding the 10 level of the btree, or something else. It may
be food for Tech Support. I see no evidence that you are using
variable length records, which simplifies life.

I expect you'll tell me that this is a 24x7x52 mission critical
system. Nevertheless, with 440K rows of active data, 200K rows of
deleted data, and the index bumping into 10 or 11 levels, the best
thing to do would be to rebuild the table and indexes.

Given that you need this to work while the system is running, I think
that what I'd plan to do is some variant on:

1. A sub-second outage while you add an audit trail to the file.
2. Use a process to create a copy of the table, doing and index-order
scan of the original and inserting the data into the new.
3. Create the indexes on the new table.
4. Scan the audit trail to apply the changes since the audit trail
was created to the new file you've just created.
5. When you're ready, impose another sub-second outage while you flip
between the old and the new files.

And I'd recommend doing this periodically - say once a year, but your
mileage may vary - to keep the fragmentation down.

If you can afford the offline time, using iscluster() to rebuild the
table and indexes would be simpler - but it would take the file
offline while it runs. You could take a copy of the file and time how
long it takes to do the clustering -- and then make a business
decision whether the audit trail variant (which requires some non-
negligible coding) is better or whether the downtime for iscluster()
is OK.

And it isn't entirely clear how you enforce the sub-second outage,
either. Basically, you need to be able to ensure no process is able
to access the file while you switch between the old and the new. How
feasible that is depends on the way the application is written - and
how many copies of the application are running concurrently, and how
long each one takes to process a record, and whether the processes
hold the C-ISAM file open between operations, and whether each process
is a one-shot process or an iterative process, and whether you have a
transaction log in use, and ... on a lot of different factors. In
theory, you apply an X-lock (ISEXCLLOCK) to the file in one process;
everything else gets held up waiting; you switch files, and everyone
is able to get going again. I somehow doubt that it will be quite
that simple in practice.

You should continue working with IBM/Informix Tech Support on this.
They've had the benefit (or otherwise) of my inputs internally - and
are aware of this thread too.

-=JL=-

Jonathan Leffler wrote:

On Jan 3, 1:04 pm, Rahan <Ra... (AT) rahan (DOT) net> wrote:

Jonathan Leffler wrote:

Rahan wrote:

Under Solaris 10 and 9, we are using a product which use an IBM C-ISAM
database to store a lot of data.

We had some problem with a database, some crash due to a database
corruption and impossibility to our software to replay a record on the
database, so the server was unable to update the database... ANYWAY !

When i run : bcheck <file> where file is an entity of the database, i
don't have an error but the index b-tree is high. In this exemple, the
index b-tree = 11 :

a number> index node(s) used -- 11 index b-tree level(s) used

i d'ont know why, but after some weeks of investigation, the editor of
the software and IBM for the database believe that the problem occur
when the index b-tree exceeds 10.

i am not a DBA and i know nothing about C-ISAM database, but could you
give me your opinion please ?

What does it mean to have an big value of index b-tree ?

Seeing a B-Tree depth of 11 levels means several things all at once.

There is a limit of 10 levels in the code. This dates back to at least
1986; I don't have earlier code accessible. Why you are seeing 11 in
the output becomes contentious - it could be 10 levels apart from the
root node, perhaps.

It also means you have a honking big file. That is, your C-ISAM file
must contain many millions of records. In fact, it would interesting
indeed to have some basic statistics on your file - maybe the output of
of bcheck.

It also most probably means you have a huge index key size - you are
indexing some very long fields. Again, it would be interesting to have
the output of bcheck.

It also means that in theory, it will take 12 disk accesses to read each
row of data via the index (one for each level of the index, plus one to
retrieve the actual row of data). That observation needs to be
qualified with "but a sequential scan won't need that many accesses" and
"but the o/s will probably provide caching in its buffer pool of the
upper levels of the index so the actual physical disk accesses will be
smaller, but the number of read system calls could be close to a dozen
per row fetched". Also, note that reading 12 pages to get to the right
row is more efficient in general than scanning the entire file to find
the right row -- assuming you are selecting one or a very few records at
a time. If you are really fetching almost everything, then you might be
doing 12 times as much disk access as really necessary.

Basically, an index of depth over about 6 levels is a potential source
of concern in any B-Tree system (IDS as well as C-ISAM). It may be
unavoidable - but you should do your utmost to avoid it.

Do you know if your index uses either leading or trailing compression
(or both)? Could it? Should it?

[I've seen a few questions raised about this from the inside. At least,
I'd be surprised if you are not the people which caused the question
that was asked internally about this. And IDS has a limit of 20 levels
on the B-Tree. With large page sizes, it doesn't bear thinking about
how big a single table would have to be to overflow that. And the
calculation of how many rows you can fit gets, ... interesting! There
are lots of factors that affect the actual density of the index.]

Hello Jonathan and thank you very much for your answer.

this is the output of bcheck :

---------------------------------------------------------------------
BCHECK C-ISAM B-tree Checker version ISAM Version 7.26.UC1
Copyright (C) International Business Machines Corporation 2001.All rights
reserved.
Software Serial Number <XXXXXX

C-ISAM File: <XXXXXXXXX>.dat

Checking dictionary and file sizes.
Index file node size = 1024
Current C-ISAM index file node size = 1024
Checking data file records.
Checking indexes and key descriptions.
Index 1 = unique key (0,17,0) (17,30,0)
49420 index node(s) used -- 7 index b-tree level(s) used
Index 2 = unique key (17,30,0) (47,71,0) (0,17,0)
132848 index node(s) used -- 11 index b-tree level(s) used
Checking data record and index node free lists.
183060 index node(s) used, 75086 free -- 440220 data record(s) used,
199739 free
---------------------------------------------------------------------

Please see the line with the index b-tree is 11 (exceeds 10).

Could you provide me your opinion please.


Your index is big; your table is very fragmented. Bcheck doesn't
indicate the record size, which is odd. Can you tell me how big the
data records are? Or send the 'ls -l' output of the .dat and .idx
files; you can mask the actual file name again as I'm only interested
in the sizes. Your 'index 2' is on 3 columns, and the total key size
is 118 bytes (30 + 71 + 17) of character data (that's the 0 at the end
of each triplet; the first number in the triplet is the starting
offset for the field). So, with a unique index, there is a 4-byte
record ID for each key in the index structure. So, with index nodes
of 1 KB, you can fit 8 keys per page. If your index was fully
compressed, you'd not reach 11 levels until you got to 8 G (8 billion
or so) records - for N levels, you'd have 8^N records if fully
compressed. Clearly, with a few hundred thousand records, you are
nowhere near that theoretical limit - there is a lot of fragmentation
in the index. With 440 K rows in the table, you'd expect to need at
least 5 levels in the index, even with perfectly balanced splitting of
the nodes.

I see that bcheck claims that 49420 + 132848 = 182268 nodes in use;
but it then also says 183060 nodes are in use. I wonder where the
extra 792 nodes are being used. This may be indicative of problems
due to exceeding the 10 level of the btree, or something else. It may
be food for Tech Support. I see no evidence that you are using
variable length records, which simplifies life.

I expect you'll tell me that this is a 24x7x52 mission critical
system. Nevertheless, with 440K rows of active data, 200K rows of
deleted data, and the index bumping into 10 or 11 levels, the best
thing to do would be to rebuild the table and indexes.

Given that you need this to work while the system is running, I think
that what I'd plan to do is some variant on:

1. A sub-second outage while you add an audit trail to the file.
2. Use a process to create a copy of the table, doing and index-order
scan of the original and inserting the data into the new.
3. Create the indexes on the new table.
4. Scan the audit trail to apply the changes since the audit trail
was created to the new file you've just created.
5. When you're ready, impose another sub-second outage while you flip
between the old and the new files.

And I'd recommend doing this periodically - say once a year, but your
mileage may vary - to keep the fragmentation down.

If you can afford the offline time, using iscluster() to rebuild the
table and indexes would be simpler - but it would take the file
offline while it runs. You could take a copy of the file and time how
long it takes to do the clustering -- and then make a business
decision whether the audit trail variant (which requires some non-
negligible coding) is better or whether the downtime for iscluster()
is OK.

And it isn't entirely clear how you enforce the sub-second outage,
either. Basically, you need to be able to ensure no process is able
to access the file while you switch between the old and the new. How
feasible that is depends on the way the application is written - and
how many copies of the application are running concurrently, and how
long each one takes to process a record, and whether the processes
hold the C-ISAM file open between operations, and whether each process
is a one-shot process or an iterative process, and whether you have a
transaction log in use, and ... on a lot of different factors. In
theory, you apply an X-lock (ISEXCLLOCK) to the file in one process;
everything else gets held up waiting; you switch files, and everyone
is able to get going again. I somehow doubt that it will be quite
that simple in practice.

You should continue working with IBM/Informix Tech Support on this.
They've had the benefit (or otherwise) of my inputs internally - and
are aware of this thread too.

-=JL=-

Hello Jonathan,

The ouput of "ls -al" of the .dat and .idx file gives :

..idx = 275 MB
..dat = 83 MB

Could you please provide me your opinion with this size ?

Great thanks for your help and your analysis.

Have a nice week-end and thanks again.

Best Regards
Rahan