Ever asked your self how things work inside the SQL Select statement? In this article we won’t be talking about how to write SQL Select statement but rather we will be talking about the algorithms and the methodology behind the Select statement and how SQL decides which algorithm it will use to filter out the results and return our expected results.
Selecting an Algorithm:
In fact you can’t do so, it is up to the SQL Optimizer implementation to determine the selected algorithm that best match the query you are going to invoke in order to enhance the query performance or in other words Optimize it, so you don’t have control over selecting the algorithm although some SQL Optimizer implementations tried to enable the DB Admin to specify which selection algorithm is suitable based on the admin knowledge (for example the admin might know that binary search –we will mentioned that latter- might be the best choice).
We need to get prepared first and get familiar with the terminologies that we will be using through the article
Before we go further we need to know the types of indexes:
• Primary index – allows records to be read in an order that corresponds to the physical order in the file.
• Secondary index – any index that is not a primary index.
When we make an index we create something like a database for Indexing except it only include the key being indexed and the location counter which holds the location on the record in the database itself (the one that contains the data).
Access path: An access path is an algorithm used by Database to satisfy the requirements of SQL statements.
The Selection Criteria:
As all of us know the SQL Select operation is used to filter and select results based on criteria.
For a simple selection there are two methods to base the selection on:
-Table Scan (AKA File scan): the scan scans all the records of the table. For large tables, this can take a long time. But for very small tables, a table scan can actually be faster than an Index Seek and we get the records that satisfy the search criteria in a fast manner.
-Index Scan: as the name implies all the rows in the leaf level of the index are scanned this means that all of the rows of the table or the index are examined instead of the table directly (this involve a search which would use an index).
Optimizer in Action:
When the SQL is first time executed, the optimizer must first determine whether an index exists. You can query any column of any table and an index is not required to do so. So, the optimizer must be able to access non-indexed data; it does this using a scan. In most cases the preference is to use an index as an index greatly optimizes data retrieval. However, an index cannot be used if one does not exist. And certain types of SQL statements simply are best satisfied with a complete scan of the data as shown below.
“ Select * from Employee”
-Linear Search: considered the easiest and most straightforward search through the database as it retrieves every record and tests it against the criteria to see if it satisfies it or no.
The linear search can either retrieve the data itself (as in the Select operation) or the data location (as in the Update operation)
“ Select Emp_Name from Employee where SSN=’123456789’ ”
-Using Primary Index: when the condition involves equality comparison on a key attribute with primary index (SSN in this case), then the primary index is used to retrieve at most one record.
“ Select Emp_Name from Department where Dep_Number=5 ”
Complex selection contains 2 types:
-Conjunctive Selection using composite index (multiple attributes): if two or more attributes are involved in equality in the conjunctive condition and a composite index exists on a combined filed we can use the index directly in other words we will search index directly if selection specifies an equality condition on 2 or more attributes and a composite index exists so in this case access path that depends on the index will be taken into consideration(linear and binary search wont be used) for example: here we created an index on the composite key (Customer_ID ,Product_ID)
“ Select * from CustomerProduct where Customer_ID=15 AND Product_ID=250 ”
-Disjunction selection: compared to a conjunctive selection a disjunctive selection is harder to process and optimize, in such situation the optimization that can be done is not that much as the records satisfy the disjunction condition are the union of the records satisfying the individual conditions.
If any one of the conditions doesn’t have access path then we will be forced to use linear search and if we have access path for every single condition then we can apply optimization by retrieving the records satisfying every condition and then union the outcome to eliminate duplicates
“ Select * from Employee where Employee_Gender=’M’ OR Employee_Salary > 10000 OR Employee_Department=5”
When a single condition specifies the selection (simple selection) we can check if an access path exists on the attribute involved in that condition, if yes then this access path will be used for the execution otherwise the linear search will be used.
The Query Optimization won’t be able to do much in the case we have only single simple condition on the opposite it will do a great job when there are conjunctive queries this is whenever more than one of the attributes involved in the select condition have access path, here the query optimizer takes action and choose the access path that returns the fewest records the in most efficient manner by estimating the different costs and choosing the method with the least estimated cost.
In this article we have seen how SQL Optimizer optimizes the select statement in order to achieve the best performance, optimizer uses index to satisfy the selection condition if the following criteria were met:
• One of the columns (in any indexable select condition) must exist as a column in an available index.
And the optimizer would use a linear search if the above criteria weren’t met.
After that the optimizer will go one step further and try to determine which access path (if exists) would return the fewest records in the most efficient manner and that’s by doing an estimate of the costs for each access paths. Next time we will be talking about algorithms behind this estimate so stay tuned ;)