From: Lars-Erik Bjørk Date: May 14 2009 10:17am Subject: Some more on IndexWalkers List-Archive: http://lists.mysql.com/falcon/731 Message-Id: <16278A70-C8DB-4223-B9DB-5D310E4C97BD@Sun.COM> MIME-Version: 1.0 Content-Type: text/plain; CHARSET=US-ASCII; delsp=yes; format=flowed Content-Transfer-Encoding: 7BIT Hi Ann, and the crew! After pushing http://lists.mysql.com/commits/73707 for bug #43630 'A SELECT using ORDER BY and LIMIT sometimes returns no rows' I have been looking at the remaining cases where we are returned too few, or no, rows when doing a LIMIT query. It seems that when we find a node with a recordNumber >= 0 as the first node on a page, we forget to expand the key. I believed that this was deliberate, as the key should already be expanded, being identical to the last entry on the previous page. Looking at this in the debugger however, this does not seem to be the case. When we start searching the first page that actually contains valid entries, IndexWalker::keyLength and IndexWalker::key has the following values: (gdb) p keyLength $4 = 2 (gdb) x/bt key 0x7fab4cfaf810: 10111111 (gdb) x/bt key+1 0x7fab4cfaf811: 11110000 whereas the index node we are looking at has the following: (gdb) p node $2 = {node = 0x7fab4cfa7750, nextNode = 0x7fab4cfa7755, offset = 0, length = 1, key = 0x7fab4cfa7754 "\300\001", number = 329} (gdb) p node.length $3 = 1 (gdb) x/bt node.key 0x7fab4cfa7754: 11000000 The keys and keylengths do not match. The recordKey created from the record when comparing in IndexWalker::getValidatedRecord, however, looks the same as the node: (gdb) p recordKey.keyLength $5 = 1 (gdb) x/bt recordKey.key 0x7fab3fcb88e8: 11000000 Since all the fields have the same value, expanding the key for the following nodes is a no-op, because the offset will be 1 and the length 0. Therefore we miss a lot of rows until we reach a node with offset 0 and length 1. This is maybe a supernode, since it seems to be fully expanded? If I add the following line of code: int32 WalkIndex::getNextNode(void) { for (;; first = true) { if (first) { first = false; recordNumber = node.getNumber(); if (recordNumber >= 0) { node.expandKey(&indexKey); // <==== This line return recordNumber; } we only experience some cases where we miss 1 row, opposed to often missing a lot. We still have the other problem with too many rows though :) Is it correct that we miss to expand the key here, or is it something else that is fishy? (I know there is fishy stuff here, but hopefully not regarding this particular issue :) ) For the curious, a little information about the nodes searched is presented below: Page = page number dup = number of entries reported as duplicates nrec = number of entries that have no matching record ncan = number of entries that had no visible records nmis = number of entries who's key does not match with the key generated from the record nret = number of entries returned as valid entries This is presented in search order Page:137, dup:0, nrec:0, ncan:0, nmis: 35, nret:0 Page:138, dup:0, nrec:0, ncan:0, nmis: 1000, nret:0 Page:181, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:175, dup:0, nrec:0, ncan:0, nmis: 206, nret:465 (valid) Page:136, dup:0, nrec:0, ncan:0, nmis: 515, nret:0 Page:219, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:147, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:174, dup:0, nrec:0, ncan:0, nmis: 2, nret:329 (valid) Page:199, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:173, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:214, dup:1, nrec:0, ncan:0, nmis: 451, nret:0 Page:149, dup:1, nrec:0, ncan:0, nmis: 459, nret:0 Page:139, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:156, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:185, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:159, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:229, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:164, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:165, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:186, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:191, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:228, dup:0, nrec:0, ncan:0, nmis: 91, nret:0 Page:230, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:234, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:235, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:158, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:160, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:155, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:151, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:162, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:236, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:237, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:161, dup:0, nrec:0, ncan:0, nmis: 23, nret:0 Page:143, dup:1, nrec:0, ncan:0, nmis: 506, nret:0 Page:140, dup:0, nrec:0, ncan:0, nmis: 1, nret:0 Page:142, dup:0, nrec:0, ncan:0, nmis: 24, nret:0 Page:141, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Page:218, dup:0, nrec:0, ncan:0, nmis: 0, nret:0 (empty) Number of empty pages: 11 Number of pages with vaild entries: 2 Number of pages processed: 38 This query returned 794 rows, while 1000 rows were expected /Lars-Erik