Conditions in the WHERE clause combined with OR operator/queries with UNION operator.
Quick sort: If a table size is small and can be accommodated into current memory, then quick sort can be used. As the name suggests it is simple and easy method of sorting.
Merge Sort: For the larger tables which cannot be accommodated in the current memory, this type of sorting is used. It has better performance compared to quick sort.
Memory cannot hold all the records of large tables; In the example above, it can hold up to 4 records only. Suppose Initial table has 12 records . When merge sort is applied, the records are grouped into 3 with two blocks each. Each block is merged at pass 1 and sorted for the pass 2, where it again merged and sorted. At the last stage blocks at pass 2 are merged and sorted to give the final result.
Joins: When we use the joins in the queries, the query optimizer decides which joins to be used. Based on the better cost of the query, any one of the following join method will be used by the query optimizer.
Nested Loop Join:
r theta join s
r is outer relation and s the inner relation of join.
Result: tr*ts
*no indices
*expensive as it examines every pair of tuples in the two relations.
Algorithm
cost: nr*bs +br block transfers. it is always better to put smaller tables in the inner loop, if it accommodated into its memory. Then the cost will reduce to 2 seeks leading to br+bs block transfers. Cost of nested loop join depends on number of records, blocks and positioning of the tables. However, the cost of nested loop join is very expensive compared to other joins.
Block Nested Loop Join (process relations on a per block basis, rather than on a per-tuple basis):
Every block of the inner relation is paired with every block of outer relation.
Here, in addition to looping each record in outer and inner tables, their blocks are also added for looping. Hence, this method selects block of records from both the tables and compares the records in them. Hence the processing is done block wise.
Here, it traverses each block of records in a loop. Each of outer block reads inner table records only once. So cost of this method is better compared to NLJ.The number of seeks required is 2 BR and the number of block transfer is given as (Br * Bs) + Br. In the best case where records of both table fit into memory block, the cost is given as 2 seeks and Br+ Bs block transfers. If join condition is on candidate key of the tables, then it need not traverse through all the records or blocks of inner table. At one point seek itself, it will get the record.
If an index is available on the inner loop's join attribute, replace file scans with efficient index lookups.
Indexed Nested Loop Join:
If an index is available on the inner loop's join attribute in a NLJ, index lookups can replace file scans. for each tuple tr in the outer relation r, the index is used to look up tuples in s that will satisfy the join condition with tuple tr.
* Can be used with existing indices as well as with temporary indices .
*When indexes are used, there is no sequential scan of records. For the indexes are used on the columns in join condition, it will not scan each records of inner table. It will directly fetch matching record. * Indexes are useful when natural joins or equijoins are used.
In the worst case, the cost of INLJ is calculated as br*(tT+tS) +nr*C, where nr is the number of records in relation r, tT and tS are each records of table T and S respectively, and C is the cost of fetching single record in the index table.
INLJ is the most efficient one among all.
Merge Join:
*Tables may be sorted or not sorted
*Uses merge-sort technique to sort the records in two tables as it is cost-effective. After sorting, join condition is applied to get the result
*sort-merge join - used to compute natural joins and equi-joins
Eg: r(R) natural join s(S) have R intersection S common attributes. if these attributes are sorted, join can be computed like merge-sort algorithm.
Assuming all records fit in memory block, Cost of Seeks: [br/bb] + [bs/bb] , where bb buffer blocks are associated to each relation.
Cost of Block Transfer: BR + BS
Hybrid Merge Join:
Uses If one relation is sorted, and the other has a secondary B+-tree
index on the join attribute.
*Merge the sorted relation with the leaf entries of the B+-tree .
* Sort the result on the addresses of the unsorted relation’s tuples
*Scan the unsorted relation in physical address order and merge with previous result, to replace addresses by the actual tuples
Sequential scan is more efficient than random lookup.
Hash Join
*used to implement natural joins and equi joins
*hash function h is used to partition tuples of both relation.
*Partition tuples into sets that have same hash value on the join attribute.
tr natural join ts - concatenation of tuples tr and ts.
performs a seperate INLJ on each of partition pairs for i=0..nh. It first builds a hash index on each si and then probes(looks up si) with tuples from ri. The relation s is build input and r is probe input.
Hybrid Hash Join
*useful when memory sizes are relatively larger; but not all of the build relation fits in the memory.
For complex joins (query with more than two tables) ,use conjunctions and disjunctions with effective joining techniques. Create index on joining conditions. it will fetch the matching record in one shot, rather than traversing each record of tables. This method performs pair join rather than joining with one table at a time which means all matching records are fetched in one step.
Eliminating Duplicates and Aggregation
If the user wants to eliminate duplicate records, use DISTINCT keyword in the query.
SELECT DISTINCT * FROM student; -- retrieves unique records from the student table and shows only one record for multiple occurrence of the records.
Cost for deleting the duplicate will depend on the technique used to group the duplicate values and the cost of identifying and deleting those records. This is expensive.
Aggregation operation uses sorting or hashing techniques to get similar groups of records together and group using SUM, AVG etc. Cost estimate for implementing aggregation operation is same as the cost of duplicate elimination, for aggregate functions such as min, max, sum, count and avg. Implement aggregation operations sum, min, max, count and avg on the fly as the groups are being constructed.
In hashing method, sorting can be optimized during run generation or merge passes. During run or merge passes, it can calculate the partial aggregate values in that block and can pass it to next merge pass.
For on the fly aggregation techniques, only one tuple needs to be stored for each of the groups. So sorted tree structure or hash index fits in memory and the aggregation can be processed with b block transfers ( 1 seek) instead of 3br transfers.
Set Operations
Set operations like UNION, INTERSECTION, MINUS etc are implemented using hashing or merge join methods. But it needs tables to be sorted before.
*Partition the two relations by same hash function
*create partitions r0, r1, r2....rnh and s0, s1, s2...snh.
*system takes these steps on each partition i-0,1,2....nh.
r union s
*Build in memory hash index on ri, add tuples in si to the hash index if not present and add tuples in the hash index to result.
r intersection s
*Build in memory hash index on ri, for each tuple in si, probe the hash index and output the tuple to the result only if it is already present in the hash index.
r minus s
*Build in memory hash index on ri, probe the hash index and delete if tuple is already present in the hash index. Add remaining tuples in the hash index to result.
Join
The FULL OUTER JOIN keyword return all records when there is a match in either left (table1) or right (table2) table records.
SELECT column-names
FROM table-name1 FULL JOIN table-name2
ON column-name1 = column-name2
WHERE condition
Note: FULL OUTER JOIN can potentially return very large result-sets!
The LEFT JOIN keyword returns all records from the left table (table1), and the matched records from the right table (table2). The result is NULL from the right side, if there is no match.
SELECT column-names
FROM table-name1 LEFT JOIN table-name2
ON column-name1 = column-name2
WHERE condition
The RIGHT JOIN keyword returns all records from the right table (table2), and the matched records from the left table (table1). The result is NULL from the left side, when there is no match.
A self JOIN is a regular join, but the table is joined with itself.
The INNER JOIN keyword selects records that have matching values in both tables.
SELECT column-names
FROM table-name1 INNER JOIN table-name2
ON column-name1 = column-name2
WHERE condition
Eg:
Table 1
ID | NAME | AGE | ADDRESS | SALARY |
+----+----------+-----+-----------+----------+
| 1 | Jis | 32 | Bhandup | 2000.00 |
| 2 | Jomini | 25 | Delhi | 1500.00 |
| 3 | komalam | 23 | Kota | 2000.00 |
| 4 | Chaithan | 25 | Mumbai | 6500.00 |
| 5 | Haven | 27 | Bhopal | 8500.00 |
| 6 | Kimma | 22 | MP | 4500.00 |
Table 2:
+-----+---------------------+-------------+
|OID | DATE CUSTOMER_ID | AMOUNT |
+-----+-------------------------+--------+
| 102 | 2009-10-08 3 | 3000 |
| 100 | 2009-10-08 3 | 1500 |
| 101 | 2009-11-20 2 | 1560 |
| 103 | 2008-05-20 4 | 2060 |
SELECT ID, NAME, AGE, AMOUNT
FROM Table 1, Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID;
+----+----------+-----+--------+
| ID | NAME | AGE | AMOUNT |
+----+----------+-----+--------+
| 3 | komalam | 23 | 3000 |
| 3 | komalam | 23 | 1500 |
| 2 | Jomini | 25 | 1560 |
| 4 | Chaithan | 25 | 2060 |
+----+----------+-----+--------+
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 LEFT JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID;
+----+----------+--------+---------------------+
| ID | NAME | AMOUNT | DATE |
+----+----------+--------+---------------------+
| 1 | Jis | NULL | NULL |
| 2 | Jomini | 1560 | 2009-11-20
| 3 | komalam | 3000 | 2009-10-08
| 3 | komalam | 1500 | 2009-10-08
| 4 | Chaithan | 2060 | 2008-05-20
| 5 | Haven | NULL | NULL |
| 6 | Kimma | NULL | NULL
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 RIGHT JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID;
+----+----------+--------+---------------------+
| ID | NAME | AMOUNT | DATE |
+----+----------+--------+---------------------+
| 3 | Komalam | 3000 | 2009-10-08
| 3 | Komalam | 1500 | 2009-10-08
| 2 | Jomini | 1560 | 2009-11-20
| 4 | Chaithan | 2060 | 2009-10-08
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 FULL JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID;
+------+----------+--------+---------------------+
| ID | NAME | AMOUNT | DATE |
+------+----------+--------+---------------------+
| 1 | Jis | NULL | NULL
| 2 | Jomini | 1560 | 2009-11-20
| 3 | Komalam | 3000 | 2009-10-08
| 3 | Komalam | 1500 | 2009-10-08
| 4 | Chaithan | 2060 | 2008-05-20
| 5 | Haven | NULL | NULL
| 6 | Kimma | NULL | NULL
| 3 | komalam | 3000 | 2009-10-08
| 3 | komalam | 1500 | 2009-10-08
| 2 | Jomini | 1560 | 2009-11-20
| 4 | Chaithan | 2060 | 2008-05-20
+------+----------+--------+---------------------+
mySQL does not support full join. Instead we can use UNION ALL. it will produce same result shown above.
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 LEFT JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID
UNION ALL
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 RIGHT JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID;
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 LEFT JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID
UNION
SELECT ID, NAME, AMOUNT, DATE
FROM Table 1 RIGHT JOIN Table 2
WHERE Table 1.ID = Table 2.CUSTOMER_ID;
+------+----------+--------+---------------------+
| ID | NAME | AMOUNT | DATE |
+------+----------+--------+---------------------+
| 1 | Jis | NULL | NULL
| 2 | Jomini | 1560 | 2009-11-20
| 3 | Komalam | 3000 | 2009-10-08
| 3 | Komalam | 1500 | 2009-10-08
| 4 | Chaithan | 2060 | 2008-05-20
| 5 | Haven | NULL | NULL
| 6 | Kimma | NULL | NULL
Use hash join or merge join to perform equijoin in first step. In other words, natural outer joins and outer joins with an equi-join condition can be computed by extensions of the merge-join and hash-join algorithms.
Let us have query like below:
SELECT * FROM takes r LEFT OUTER JOIN student s ON r.ID = s.ID;
The processor picks all matching records of takes and student by using the best join algorithm , then it picks the records of takes which are not selected by hash join or merge join and adds them to the result set by appending NULLs to the columns of takes.
Read this for understanding more about joins
http://www.sql-join.com/sql-join-types/
Methods of evaluating a query written in SQL
1) Materialization -generate results of an expression whose inputs are relations or are already computed, materialize(store) it on disk. Repeat.
To be specific, queries are broken into individual queries and then the results of which are used to get the final result.
Eg: SELECT c.name FROM department s, instructor c
where s.building='Watson';
DBMS breaks the query into two and evaluates the first query and stores it in the temporary table in the memory. This temporary table data will be then used to evaluate the second query. This is the example of two level queries in materialization method. We can have any number of levels and so many numbers of temporary tables. This is called materialized evaluation as the results of each intermediate operation are created (materialized) and are used for evaluation of next-level operations.
Cost of materialized evaluation is always more. It takes the time to evaluate and write into temporary table, then retrieve from this temporary table and query to get the next level of result and so on. Hence cost of evaluation in this method is:
Cost = cost of individual SELECT + cost of write into temporary table
2) Pipelining
In this method, DBMS do not store the records into temporary tables. Instead, it queries each query and result of which will be passed to next query to process and so on. It will process the query one after the other and each will use the result of previous query for its processing.
*No extra cost of writing into temporary tables. It has only cost of evaluation of individual queries; hence it has better performance than materialization.
*Quick query results
*Low memory requirements, as the results of an operation are not stored for long.
Pipeline Implementation
*construct a single complex operation that combines the operations that constitute the pipeline.
1) Demand -driven pipeline (Lazy evaluation)
In this method, the result of lower level queries are not passed to the higher level automatically. It will be passed to higher level only when it is requested by the higher level. In this method, it retains the result value and state with it and it will be transferred to the next level only when it is requested.
In our example above, building 'Watson' will be retrieved first from the department table, but it will not be passed to select query immediately. It will pass only when it is requested. Once it gets the request, it is passed to instructor query to retrieve name of instructor and that query will be processed.
System makes repeated requests for tuples from the operation at the top of the pipeline. Each time an operation receives a request for tuples, it computes the next tuples to be returned and then returns the tuple.
functions in iterator
open()
next()- return the next output tuple of the operation
close()-no more tuples are required
iterator maintains the state of its execution in between calls, so that successive next() requests receive successive result tuples
2) Producer-driven pipeline (Eager Pipelining/Push and Pull pipelining)
* Lower level queries eagerly pass the results to higher level queries. It does not wait for the higher level queries to request for the results.
*Lower level query creates a buffer to store the results and the higher level queries pulls the results for its use. if the buffer is full, then the lower level query waits for the higher level query to empty it.
Operations do not wait for requests to produce tuples, but instead generate the tuples eagerly. Each operation in a producer-driven pipeline is modelled as a separate thread within the system that input tuples from its pipelined inputs and generates tuples stream for its output.
Other pipelining methods: Linear and non-linear methods of pipelining, left deep tree, right deep tree
*Producer driven pipeline- pushing data up an operation tree from below, tuples are generated eagerly
Demand driven pipeline- pulling data up an operation tree from the top, tuples are generated lazily on demand. This is used more commonly than producer driven pipelining.
Double pipelined hash join technique- If two inputs to pipeline into the join are not already sorted, use this technique. Input tuples for both input relations r and s are already pipelined and are queued for processing in a single queue.
