RDBMS! Everyone got involved with something related to RDBMS even if it was just a small task. In this article we will be talking about how SQL statements work (if we want to implement our own statements in java) For example the select statement we now how to use it and how to query the table we want but do we know what happens when we ask the DB system to query for a specific data from a table? In this part we will be talking about how Order By works.
Behind the scene:
Before we dive into how the SQL Order By clause works we need to look how data are preserved in the database and how tables are structured (we will be talking about MSSQL as our case study)
Page is the storage unit in MS SQL, in SQL server 2000 the page size is limited to 8 K (so for each MB we have 128 page that holds data), in SQL Sever 2005 has a mechanism to dynamically over-flow data off page or pulls data in page as a record size increases beyond 8k or decreases to fit within an 8k page (but that’s not our concern now)
Before SQL server 2000 the size of the page were limited to 2K (prior to v 7.0)
These 8 K isn’t dedicated for the data only, the first 96 byte is used to store information about the page type, free space, object id, and which table does this page belong to and so on.
After the header information, the data itself comes in (data rows) which are inserted after each other in a serial manner
Indexing:
If we take a look at the tables we will see that each table consists of data and these data are preserved in Pages but what we didn’t mention above is that each page has pointer (one for previous page and one for next page) these pointer information is preserved in the header info(pages are linked in a list)
SQL server tables has two methods in organizing their data pages
-Clustered tables: clustered tables are tables that have clustered index, the data rows are sorted in order based on the clustered index key and this index is implemented as B-tree structure (supports fast retrieval) , and pages are linked in a doubly linked list
-Heaps: Heaps are tables that have no clustered index so the data in the pages are stored in any order and there is no order also between pages (they are not linked in liked list manner)
Order By clause:
When you run a query and specify an ORDER BY clause you will get sorted results that match your criteria but not only the Order By that benefits from sorting algorithm but also JOIN, UNION and so many other.
Such sorting headache can be avoided if the right index existed to allow direct access to the records
External or Internal!:
As we mentioned before that the Order By clause uses sorting algorithm so does this mean that the sorting for the whole table information is done in the same time in the memory?
Not actually there is something called “External Sorting” which is a sorting algorithm type when you have large data -resides on disk- that you want to sort and you don’t have enough memory for it (same as our database case for example we have a table of 5 G of data and we only have 1 G of memory) as I can remember this was a question in Google’s interview which I read before (how can you sort a 5 G of data and you have only 100 M of memory or something like that)
One example of external sorting is “Merge-Sort” which is very efficient and widely used.
Sorting in Action:
Below is the merge sort for external sorting
set
i<--1;j<--b; {size of the file in blocks}
k<--ns; {size of buffer in blocks}
m<--(j/k); {Sort phase}
while(i<=m)
do{
read next k blocks of the fine into the buffer of if there are less than k blocks remaining then read them sort the records in the buffer and write them as temp sub files
i<--i+1;
}
{Merge phase: merge subfiles until only 1 subfile remain}
set
i<--1;
p<--logk-1 m {p is the number of phases for merging phases}
while(i<=p)do{
n<--1;
q<-- j/(k-1) {number of sub files to write in this pass}
while(n<=q)
do{
read next k-1 subfiles or remaining subfiles (from previous pass) one block at a time.
Merge and write as new subfile
n<--n+1;
}
j<--q;
i<--i+1;
}
As shown above in the pseudocode there are two phases, phase 1 the sorting phase and phase 2 which is the merging phase
1-sorting phase
2-merging phase
In step 1 (sorting step)
Only pieces of the file that can fit in the memory are loaded and then sorted using internal sort (internal sort is the opposite of external sorting which is suitable for sorting data that can fit entirely in the memory) usually this internal sorting is done with Quick Sort and then the sorted data are written back to the disk in a sub files (also called runs).
Number of runs (nr) =number of file blocks (b) /available buffer space (nb)
For example if we have number of blocks (nb) =5 and the size of the of the file (b) = 1024 blocks
runes =1024/5=205 sorted temporary run on disk (we use approximation here)
In step 2 (merging step)
After the first step is finished we need now to sort these sub files these sub files will be merged in one or more pass.
Degree of merging (dm) is the number of runs that can be merged together in each pass.
In each pass one buffer block is needed for holding one block form each run being merged and one block is needed to contain one block on the merged results
So the (dm) value can be calculated as follow:
dm= the smaller of (nb-1) and the (nr)
And the number of passes can be calculated as: logdm(nr)
So as we mentioned above we have 205 sorted run (sub files) and we have dm=4 so number of passes would be 4
So in these 4 passes we would have the following sorted runs:
52 in the first pass
13 in second pass
4 in the third pass
1 in the fourth pass
What the!
Now we know how the order by clause works, but what will we benefit from this? If you don’t want to use a RDBMS and want to have your own implementation for data storage so you avoid the headache of RDBMS, bottlenecks well you could use some of these algorithms to implement your own version like Google’s BigTable and facebook’s Cassandra.
Why did they do this?
Some people say: “Relational databases give you too much. They force you to twist your object data to fit a RDBMS” (well I have to agree with them)
As web has grown more social and shifted away from read to heavily read/write, most people have done this by relying less on the features provided by traditional relational databases and engineering more database logic in their application code. Essentially, they stop using relational databases the way they were intended to be used, and they instead use them as dumb data stores.
Other people have engineered new database systems from the ground up, each with a different set of tradeoffs and differences from relational database.
Nice but still why do they need this?
-Cheap PC server: PC clusters can be easily and cheaply expanded without the involving cutting up databases into multiple tables to run on large clusters or grids.
-Performance bottleneck: SQL can’t fit well for procedural code, and almost all code is procedural. For data upon which users expect to do heavy, repeated manipulations, the cost of mapping data into SQL is "well worth paying ... But when your database structure is very, very simple, SQL may not seem that beneficial.
-No overkill: While conceding that relational databases offer an unparalleled feature set and a rock-solid reputation for data integrity, NoSQL proponents say this can be too much for their needs.
I totally agree with the NoSQL in the above points but what about if we need to make statistics and analysis on the data we have, ensure transactions and so on these wont fit in NoSQL products (and if we implemented such features we will be just concentrating on something other than the business logic itself so it would be a waste of time and it would be like re-inventing the wheel)
In the end NoSQL is fine for applications that need simple data and won’t benefit from RDBMS features
Conclusion:
In this part we have talked about Order by clause and how does it work in next part we will be talking about SQL “select” clause so stay tuned till the next part.
Read more!
Posts
