Checking B+tree leaf nodes list consistency in InnoDB

If we have InnoDB pages there are two ways to learn how many records they contain:

  • PAGE_N_RECS field in the page header
  • Count records while walking over the list of records from infimum to supremum

In some previous revision of the recovery tool a short summary was added to a dump which is produced by the constraints_parser.

But if a page is lost and page_parser hasn’t found it, all records from this page are lost. In other words per-page recovery statistics gives us little idea about whether or not a recovered table is complete.

To cover this flaw a new tool index_check is introduced in the revision 80

As you might know InnoDB stores a table in a clustered index called PRIMARY.

The PRIMARY index is a B+tree structure. It has a nice feature that all leaf nodes have pointers to a next leaf node, so following the pointers we can read whole index in the primary key order. InnoDB extends the structure and stores also a pointer to the previous node. The previous node of the head is NULL as well as the next node of the tail.

Based on this knowledge we can check if we have all elements of the list. If we can get from any InnoDB page to the beginning and the end of the list then our set of pages is complete.

This is exactly what index_chk does – it reads files from a directory with InnoDB pages (that is produced by page_parser) and tries to walk over the list of pages back and forth.

Let’s review an example. I took some corrupt InnoDB tablespace and split it with a page_parser:

# ./page_parser -f /var/lib/mysql/ibdata1
Opening file: /var/lib/mysql/ibdata1
File information:
ID of device containing file:        64512
inode number:                     27037954
protection:                         100660 (regular file)
number of hard links:                   1
user ID of owner:                      107
group ID of owner:                     116
device ID (if special file):             0
blocksize for filesystem I/O:         4096
number of blocks allocated:          86016
time of last access:            1374662334 Wed Jul 24 06:38:54 2013
time of last modification:      1374233938 Fri Jul 19 07:38:58 2013
time of last status change:     1374233938 Fri Jul 19 07:38:58 2013
total size, in bytes:             44040192 (42.000 MiB)
Size to process:                  44040192 (42.000 MiB)
8.26% done. 2013-07-24 08:39:58 ETA(in 00:00 hours). Processing speed: 3637248 B/sec
95.70% done. 2013-07-24 08:40:09 ETA(in 00:00 hours). Processing speed: 4399053 B/sec

Now let’s take some index and check if it has all pages:

# ls pages-1374669586/FIL_PAGE_INDEX/0-410/
00000000-00000145.page  00000000-00000235.page  00000000-00000241.page  00000000-00000247.page  00000000-00000254.page
00000000-00000147.page  00000000-00000236.page  00000000-00000243.page  00000000-00000249.page  00000000-00000255.page
00000000-00000148.page  00000000-00000239.page  00000000-00000244.page  00000000-00000251.page
# ./index_chk -f pages-1374669586/FIL_PAGE_INDEX/0-410
Couldn't open file pages-1374669586/FIL_PAGE_INDEX/0-410/00000000-00000140.page

Bad news, a page with id 140 is missing!

Indeed the previous page before page#145 is page#140, but it’s missing.

# hexdump -C pages-1374669586/FIL_PAGE_INDEX/0-410/00000000-00000145.page | head -2
00000000  d4 cd 68 41 00 00 00 91  00 00 00 8c ff ff ff ff  |..hA............|
00000010  00 00 00 00 2b 6c ea 90  45 bf 00 00 00 00 00 00  |....+l..E.......|

For a cheerful ending let’s check an index that has all pages:

# ls pages-1374669586/FIL_PAGE_INDEX/0-2/* # this is SYS_COLUMNS table
pages-1374669586/FIL_PAGE_INDEX/0-2/00000000-00000010.page  pages-1374669586/FIL_PAGE_INDEX/0-2/00000000-00002253.page
# ./index_chk -f pages-1374669586/FIL_PAGE_INDEX/0-2

Thus, a table is fully recovered if and only if two conditions are met:

  • Command grep “Lost records: YES” table.dump | grep -v “Leaf page: NO” outputs nothing
  • ./index_chk -f pages-1374669586/FIL_PAGE_INDEX/<inde_id of=”” my=”” table=””> reports OK

The post Checking B+tree leaf nodes list consistency in InnoDB appeared first on MySQL Performance Blog.


Finally. How to verify if all MySQL records were recovered

How to verify if all MySQL records were recoveredAfter nearly every recovery case the same question arises: How many MySQL records were recovered and how many were lost.

Until now there was no way to answer the question without manual investigation. As it turned out a small change can make a big difference.

There are two ways to know how many records an InnoDB page stores. The index page has a header PAGE_N_RECS – this is a number of records the page stores. Obviously it doesn’t count any deleted records. The second method to confirm how many records are in the page is to follow records pointers – and count them.

As you might know, records inside an InnoDB page are organized in an unidirectional list. The list is sorted by primary key and starts with the internal record infinum and ends with another internal record supremum. If you follow record pointers from the infinum and end up with the supremum record then two conclusions can be make:

  1. The page structure is not corrupt
  2. You know how many records to expect

This is what constraints_parser does before it tries to find any records in the page:

./constraints_parser -5f pages-actor/FIL_PAGE_INDEX/0-1599/00000000-00000003.page -V
Checking a page
Infimum offset: 0x63
Supremum offset: 0x70
Next record at offset: 0x7F (127)
Next record at offset: 0xA8 (168)
Next record at offset: 0xCE (206)
Next record at offset: 0x70 (112)
Page is good
Format: COMPACT, Records list: Valid, Expected records: (200 200)

Here you can see “Expected records”: 200 in the header and 200 records were found by pointers.

Then the contraints_parser tries to recover the records. It checks whether fields have permitted values, etc. In the end it knows how many records were actually recovered.

This statistics are printed along with the recovered records:

-- Page id: 3, Format: COMPACT, Records list: Valid, Expected records: (200 200)
000000001917    DB000001720110  actor   1       "PENELOPE"      "GUINESS"       "2006-02-15 04:34:33"
000000001917    DB00000172011B  actor   2       "NICK"  "WAHLBERG"      "2006-02-15 04:34:33"
000000001917    DB000001720126  actor   3       "ED"    "CHASE" "2006-02-15 04:34:33"
000000001917    DB000001720131  actor   4       "JENNIFER"      "DAVIS" "2006-02-15 04:34:33"
000000001917    DB0000017209E4  actor   200     "THORA" "TEMPLE"        "2006-02-15 04:34:33"
-- Page id: 3, Found records: 200, Lost records: NO, Leaf page: YES

From the output above we know that 200 records were expected, 200 – recovered. So, no records were lost.

It’s worth noting that records are stored in the leaf pages only, so if an index has more than one page no records will be found in the root page.

For the root page it will print “Leaf page: NO” and it can be ignored.

The post Finally. How to verify if all MySQL records were recovered appeared first on MySQL Performance Blog.

Powered by WordPress | Theme: Aeros 2.0 by TheBuckmaker.com