Arno Brinkman wrote:

>
>
>>Consider a case... index pages 123, 124, 125. I'm reading backward
>>and have a read lock on 125. As long as I have that lock, nobody can
>>change that page. My left hand pointer says I read page 124 next. OK.
>>But, at the same time, another transaction tries to add an entry to page
>>124, finds the page full, and splits it, putting half the contents into
>>page 345. Now the correct order of the pages is 123, 124, 345, 125.
>>Half then entries that had been in 124 are now on page 345 and will be
>>missed if the backward walker doesn't read that page.
>
>
> But with an lock on page 125, page 345 can't update 125 with the new
> left-sibling page? So it will wait untill the page is unlocked?

Right. The thread that's doing the bucket split will request a write
lock on 125 so it can fix the left pointer. The backward walker will be
signaled to release 125, but won't get the new information because it
won't re-read the page. And, if it did re-read page 125, there's no
guarantee that page 125 will still be there either...

A worse, and more likely case is that I'm merrily walking backward from
page 125 when some other thread notices that pages 123 and 124 have
fallen below the compression point, combines them, and release 124. The
last step of the release is to request a write lock on 125 to fix the
back pointer. Then my backward=walker releases 125, requests 124 ....
with one of these results:

1) 124 hasn't actually been used, so it contains information that is
duplicated in 123

2) 124 has been released and reused and it contains something totally
different - it's become a TIP or a data page, in which case the database
appears corrupt.

3) 124 has been released and reused in the current index in a different
spot.

>
> If i understand your proposal then index-pages shouldn't be
> collected together anymore when they get
> under a certain threshold. Empty index pages aren't possible at
> the moment and this will certainly lead to weird behaviour
> (empty keys with pagenumbers in non-leaf pages somewhere in
> the middle?).

Index compression was added in V4, so it's certainly possible for
an index to allow empty nodes, and probably Jim remembers how it
worked.

>
> The descing index is only interesting for the navigation through
> the records and not for index-lookup.

That's right. For lookup, the direction of the index is irrelevant.

>
> Another proposal:
> - Remember left-sibling page and current-page, key, recordnumber
> - <time expired>

OK. Lets suppose that we actually remember a key and record number
that we have verified as being valid for our current transaction.
That way it (probably) won't be garbage collected while we're mucking
around trying to find our place again.

> - Next record asked which is before the buffered exploded page.
> - Fetch left-sibling page and check if next-page is current-page
> - if found ---------------------------------------------------------|

Not entirely OK. Remember that the "current page" isn't locked, so it
could have been combined, released, and re-used while we're looking at
its decompressed contents. As could it's left neighbor. In fact, they
could both have been moved to the end of the index, still be neighbors,
and not have any relationship to their former contents.

> - not found, lookup key, recordnumber from index-root-page

That works in snapshot mode, and currently works in read-committed
read-write, but it doesn't work in read-committed read-only where the
record whose key and record number we saved could have disappeared.

> - Find key, recordnumber <--------------------------------------|
> - Fetch previous record

Which puts us back in the previous problem - once you've released a page
of a type that can be released, there's no guarantee what you'll find
when you go back.

Regards,


Ann