From: Kevin Lewis Date: May 14 2009 1:25pm Subject: Re: Some more on IndexWalkers List-Archive: http://lists.mysql.com/falcon/733 Message-Id: <4A0C1BB3.20705@sun.com> MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Lars-Erik, So the first node on the page is out of order? The unexpanded nodes after that would match if they were expanded? How can that be? Lars-Erik Bjørk wrote: > 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 >