1

To the best of my knowledge, this is what happens during a range scan of a table for some data when the table has got a clustered index:

The lower range is first found out, traced to the leaf node where it is present, then traversing the leaf level page by page through the next page pointer as long as the largest value in that page is less than the larger value of the range scan condition.

Once such a page is reached where the last row exceeds that, the process stops, does a binary search within that page to find out that record, and returns all records found till now.

This bringing up page after page can be expensive I/O operation if the pages are not in memory, hence to mitigate this, read-ahead scans are done at one level up by the parent pages, so that by the time the process advances to a leaf-level page to verify it, it has already been brought to memory by one of the parent level pages.

I am watching some SQL Server tutorial videos where it says that if there is logical fragmentation at the leaf level, so that the physical page order does not coincide with the logical page order, the read-ahead scan fails and the db is forced to do a full I/O operation to retrieve all pages.

Can someone tell me why? Why is the physical order important at all? Isn't the entire traversal done through logical traversal via the next page pointers of the leaf level pages?

What effect does the logical fragmentation have on the read-ahead scan exactly?

4

Can someone tell me why? Why is the physical order important at all?

Please note, I am speculating as to why the decisions were made given the best possible information I have available to me.

AFAIK it's due to the optimization of IO using a specific API which in this case is called ReadFileScatter.

ReadFileScatter requires a starting offset and a number of bytes to read from that point. Once read the number of contiguous on disk bytes are transferred into non-contiguous memory locations (aka buffers).

Because Read-Ahead, depending on version and edition, can read different amounts of data it ends up being a single large IO instead of a bunch of tiny ones which makes the throughput of the overall storage system more albeit at a cost to latency.

/Start of pure speculation/

Please keep in mind that when these APIs and choices were being made, rotational media (aka spinning rust) was the main source of storage and SSDs did not exist. Thus, having all of the items contiguous on disk means we don't have to reposition the track heads between reads which makes the overall single contiguous read faster than many smaller disjointed ones.

References and further reading:

The first reference includes a diagram you may find helpful:

BOL image

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.