Sunday, January 5, 2014

How SQL Server retrieves the data?

The toughest thing for an amateur DBA is to understand the architecture of RDBMS. Everyone can write queries and get or update data but the one who knows how the data is retrieved and updated, he/she is the one who can master RDBMS.

In this article, I'm gonna speak about how data is retrieved by SQL Server when a user queries it using SELECT statement.

SQL Server architecture and Windows Operating System's architecture have resemblance in most of the cases. In fact some features of SQL Server work based on the functioning of Windows. In Windows, when a user opens a file, it is fetched from Secondary Storage and kept in RAM until the user closes it. The same happens with SQL Server while reading the data from a table.

Data in table is stored in the form of Pages and Extents. The size of a page is 8KB. Eight contiguous pages is called as Extent. They are stored on disk physically. When data is queried from the table, there exists a component called Buffer Manager which checks for the requested data pages on disk. If pages are found then it copies them from disk to Buffer Cache. They are stored in Buffer Cache until there exists a memory deficit in the Buffer Cache. Buffer Manager deletes the pages that are not used frequently. I'll write about Buffer Management in my future posts.

Reading Pages can be of two types namely,

                                                   1. Logical Reads.
                                                   2. Physical Reads.

Logical Read occurs when SQL Server reads the pages which are present in Buffer Cache. Physical Read means reading pages from the disk. Suppose the requested page doesn't exist in Buffer Cache, it is copied from disk to Buffer Cache and then it is read from Buffer Cache. The read operation that is performed from disk to Buffer Cache is called Physical Read.

For reading pages, SQL Server has a mechanism called Read-Ahead Mechanism. It manages all the read operations. Suppose a query is submitted to SQL Server, Read-Ahead predicts what are the pages required for the query's execution plan and copies them into Buffer Cache from disk. The number of Buffers for the pages is allocated based on requirement. This is done before the query uses the pages actually. While reading the pages, if any page is found existing in Buffer Cache, that page is discarded by Read-Ahead after reading it. It doesn't copy the page again from disk to Buffer Cache. There are two ways in which Read-Ahead mechanism works like,

                                                   1. Reading Data Pages.
                                                   2. Reading Index Pages.

Reading Data Pages


For reading data pages without an index, SQL Server uses Table Scan operator. It is a very efficient operator. Index Allocation Map (IAM) pages list the extents used by table. Every data row has a memory address in which it is stored. As rows are present in an order on the disk, SQL Server sorts the addresses of the rows which are to be read, in the same order. For this, it reads the IAM and then forms the sorted order of addresses. Now storage engine optimizes its I/O as the addresses are read in a sequential manner.

Reading Index Pages


Reading Index Pages differ with the type of index used. Generally two indexes are created namely Clustered Index and Non-Clustered Index.

Reading Clustered Index


Clustered Index has a three level architecture. The leaf nodes contain a key value and data rows. The Intermediate Level nodes contain the key values of Leaf Level nodes. The root node points to the Intermediate Level nodes. It means Intermediate Level Nodes contain the list of Leaf Level Nodes available.

While reading Clustered Index, the Storage Engine doesn't go to Leaf Nodes directly. Instead it goes to the Intermediate Level nodes and list out what all Leaf Nodes to be read. After making the list, the Read-Ahead Mechanism reads the respective nodes and copies them from disk to Buffer Cache. Those Leaf Nodes are read in the order of their key values. If there are contiguous pages, they are read in a single READ operation. If there are more pages to be read then it schedules a block of reads at a time. 

Reading Non-Clustered Index


As Non-Clustered Index stores the addresses of data rows in its leaf nodes unlike Clustered Index, Storage Engine uses Prefetching mechanism to have a speed base table lookups. Storage Engine goes to the leaf nodes of Non-Clustered Index and gets the memory addresses of the data rows. Then it goes to the address and fetches the data rows. This is an asynchronous process. It means, scanning the index and retrieving the data rows from the index values which are already read is done simultaneously. This means, some data rows are retrieved before the Index Scan is completed. This results in faster data retrieval and is independent of presence of Clustered Index in the table.

The Enterprise edition of SQL Server supports more prefetching than other editions. It facilitates more pages to be Read-Ahead. The level of prefetching cannot be configured by user in any edition of SQL Server.

Advanced Scanning


There is one more reading mechanism supported only by the Enterprise Edition of SQL Server. It is an advanced scanning which is also called Merry-Go-Round Scanning. 

Imagine, there are 1000 data pages in a table. One transaction TRAN1 is reading them completely. When it completed reading 100 pages, another transaction TRAN2 tries to read the table completely. Now TRAN2 should get all the 1000 pages from table. For this, it needs to wait for buffers occupied by TRAN1 until TRAN1 frees them. This may result to deadlock sometimes. To avoid this conflict, TRAN2 gets rows from 101th page along with TRAN1. The same buffers are used for both the transactions. Every page is read and passed to both of them. This goes on until all the pages are read completely. 

Right now, TRAN1 has all 1000 pages while TRAN2 has 900 pages. Now SQL Server scans the table again to get first 100 pages for TRAN2 and stops reading when it gets 100 pages which lets the TRAN2 to have all 1000 pages with it.

The knowledge for writing this article is acquired from the following Microsoft Official Documentation. Please do read it.

http://technet.microsoft.com/en-us/library/ms191475(v=sql.105).aspx

No comments:

Post a Comment