Improving Database Performance in a Multithreading Environment-1

Introduction:

     Today many database systems run in multithread environments.In a multithread environment the most important and critical issue is to obtain and maintain a good performance as well as with a success of concurrent access to the resources. In this write we'll talk about two points related to database performance "Concept of Denormalization" and "Join Methods and Techniques". In the future writes we'll be talking about the other aspects that effect the database performance.

Concept of Denormalization:

     Normalization is the process of reorganizing the tables and fields to minimize redundancy and tight dependency. This optimize update cost since the value is stored in only one place and you only need to update that place. However, retrieving many different but related values usually requires going to many different places. This cause to slower retrieval process. Conceptual diagrams, either entity-relationship or object oriented, are a precursor to designing relational table structures.Many database systems are designed such that the tables are at least in third normal form (3NF) base on conceptual models, but the more you normalize the more level you will need to reach the data you want. As client-server platforms are going to be cheaper rather than strong mainframes, the performance will decrease because of the normalization. One critical fact is the need to continue to provide a satisfactorty level of system performance, usually reflected by the systems response time, for online transactional systems. A fully normalized database schema can fail to provide adequate system response time due to excessive table join operations.

How to Perform Denormalization:

     When denormalization takes into place you must consider both good system response time and avoiding various anomalies and problems associated with denormalized table structures. Before denormalization you have to analyze critical transactions in detail. This analyse should include the specification of primary and secondary access paths for tables that comprise the end-user view of the database. Furthermore, denormalization should only be considered under conditions that allow designers to collect detail performance mesasurements for comparison with system performance requirements. Relational performance theory provides guidelines for achieving an idealized representaion of data and data relationships. On the contrary, client-server systems require physical database design that optimize performance for specific target systems under less than ideal conditions. The final database schema should be adjusted for characteristics of the environment such as harware, software and other constraints.

The general steps of denormalization could be the following:

1.) Analyze the queries that required a lot of join operations to get the related data. We may say that any queries that requires more than three joins should be considered as a candidate for denormalization. Also you need to measure system performance by simulating the production environment to prove the need for denormalization.

2.) You should try to reduce the number of foreign keys in order to reduce the index maintenance during insert, update and delete operations. Reducing foreing keys means to reduce number of relational tables.

3.) Data maintenance which is the main purpose of normalization should also be provided by the denormalized schema. Therefore, the denormalized approach should'nt require excessive programming effort like triggers to maintain data integrity and consistency.

A Denormalization Example:

     We can examine denormalization from 3NF to 2NF by the following example. The relationship between the Customer and Order entities is one-to-many (many orders can be processed by a single customer, but an order is normally associated with one and only one customer). The 3NF solution for the Customer and Order tables is given below, along with a denormalized 2NF solution.

3NF:
CUSTOMER (CustomerId, CustomerName,...)
ORDER (OrderId, OrderDate, DeliveryDate, Amount, CustomerId)

Denormalized 2NF:
CUSTOMER (CustomerId, CustomerName,...)
ORDER (OrderId, OrderDate, DeliveryDate, Amount, CustomerId, CustomerName)

Here we see that CustomerId in the Order table is a foreign key relating the Order and Customer tables. Denormalizing the table structures by duplicating the CustomerName in the Order table results in a solution that is 2NF because the non-key CustomerName is determined by the non-key CustomerId field. If we analyse the denormalized situation we may discover that most end-user requests require getting customer name, not the customer identification number. However the 3NF solution requires joining the Customer and Order tables. 
When we compare the 3NF solution with the denormalized 2NF solution, we see that customer name could easily be recorded to the denormalized Order table at the time that the order transaction takes place. In the denormalized form we may question the need to maintain the consistency of the data between the Order and Customer tables. In this situation, the requirement to support name changes for customer is very small, and only occurs when a customer changes her name due to marriage. Furthermore, the necessity to update the Order table in such a situation is a decision for management to make and such data maintenance may be ignored, since the important issues for customers usually revolves around whether or not they get paid their charge, and the denormalized 2NF solution supports payroll activities as well as the production of standart end-user views of the database.
It's crucial to remember that denormalization was initially implemented for performance reasons. If the environment changes the denormalization process should be reconsidered. Also its possible that, given a changing hardware and software environment, denormalized tables may be causing performance degredation instead of performance gains.

Join Methods and Techniques:

     In a query based application the need to join two or more tables is one of the most performance degredation operation. Generally when joining tables the Database Management System first chooses one of the tables which is called "outer table", and get that table to memory for quick access. Then this outer table is prepared for the join operation and finally combined with the second choosen table which is called "inner table". If there are more than two tables to join, the same operation is done using the result of first join and the choosen third table.
When designing and programming a database application one should take into account the following techniques.

• Choose smaller table as the outer table: Since the outer table will get to the memory, a smaller table will get with less cost. Also the bigger one that is the inner table will be accessed less, since it will be accessed only by the qualifying rows of the outer table.
• Choose the outer table as if it can use the selective predicate in the where clause: By that way, the inner table will be called only for the satisfying rows of the outer table.
• Choose the outer table as if it has less duplicate rows:
• Choose the inner table as if it can be access using index lookup: Index lookup means we don't need to go to table to get the information and get all the information from the index. Today many Database Management Systems keeps indexed in memory. As we mentioned, we get also the outer table into the memory during the initial phase of joining. Hence in that case both outer and inner table are in memory , and it greatly improves the performance.

We can now look up to the join methods. Today's database systems are usually using three main join methods.

      

1.) Nested Loop Join (NLJ):

     With the NLJ, a qualifying row is identified in the outer table, and then the inner table is scanned searching for a match. A qualifying row is one in which the predicated for colums in the table match. When the inner table's scan is complete, another qualifying row in the outer table is identified. The inner table is scanned for a match again, and so on. The repeating scanning of the inner table is usually accomplished with an index to minimize I/O cost.

2.) Merge Join (MJ):

     With the MJ, the tables of the join operation need to be ordered by the join predicates. That means that each table must be accessed in order by the columns that specify the join criteria. This ordering can be result of either a sort or indexed access. After ensuring both the outer and the inner table are properly sequenced, each table is read sequentially and the join columns are matched up. Neither table is read more than once during a merge join.

3.) Hash Join (HJ):

     Hash join requires one or more predicated of the form table1.ColX = table2.ColY where the column types are same. The inner table is scanned and the rows are copied into the memory buffers drawn from the sort heap allocation.The memory buffers are divided into partitions based on a "hash code" computed from column(s) of the join predicate(s). If the size of the first table exceeds the available sort heap space, buffers from the selected partitions are written to temporary tables. After processing the inner table, the outer table is scanned and it's rows are matched to the inner table rows by comparing the "hash code". Hash joins can require a significant amount of memory. Therefore, for the hash join to produce realistic performance benefits, you many need to change the value of the database configuration parameters that are related with the memory management.

     When do we know, which of these join methods should be used ? In general, the nested loop join is preferred in terms of execution cost when a small number of rows qualified for the join.As the number of qualifying rows increases, the merge join becomes a better choose. Finally, in the case of a hash join, the inner table is kept in memory buffers. If there are too few memory buffers, then the hash join possibly will fail. The optimizer attempts to avoid this and so pick the smaller of the two tables as the inner table, and the larger one as the outer table.
     Results of performance generalizations will depend on the exact number of qualifying rows as well as other factors such as your database design, database organization, accuracy of statictics, type of hardware and the setup of your environment.Today's database systems chooses the join technique automatically with the help of an optimizer. However, looking to the situation, one can change the join method by changing the query and table definition to obtain a better performance. 

Conclusion:

      In this write, we examine a database application performance in a multithread environment in terms of two points. There are many aspects that affect the performance of such an application. The normalization is one of the most critical issues in a database design. However, too much normalization will cause many join operation and negatively affect the performance, so we have to try to denormalize the tables without breaking the data maintenance. Even if we denormalize some tables, there may be still some normalized tables that we have to join them in some requirements. When we join the tables not only the expected results but also at least on of the tables will get to the memory.Specifying that table is crucial. As we join tables, there are some rules to consider, like first get the smaller table into the memory in NLJ. If we rewrite out sql by considering those facts, the DBMS will get the results quickly by using the appropriate join method. In the next paper we'll be talking about "Minimizing Contention" in multithreading environment.

References and Resources:

- John Goodson and Robert A. Steward, The Data Access Handbook Achieving Optimal Database Application Performance and Scalability, Prentice Hall, Chapter 1-2 (2009)

- Douglas B. Bock and John F. Schrage, Department of Computer Management and Information Systems, Southern Illinois University Edwardsville, published in the 1996 Proceedings of the Decision Sciences Institute, BENEFITS OF DENORMALIZED RELATIONAL DATABASE TABLES , Orlando, Florida, November, 1996

- Craig Mullins, Tuning DB2 SQL Access Paths, http://www.ibm.com/developerworks/data/library/techarticle/0301mullins/0301mullins.html

Improving Database Performance in a Multithreading Environment-2

Introduction:

     We mentioned about some concepts on improving database performance in the first part of this paper[1]. Now we continue with another concept "Minimizing Contention" that one should consider when try to improve database performance.

Minimizing Contention:

     In a multithread environment, we can call every thread as a transaction. A transaction usually means a sequence of information exchange and related work (such as database update) that is treated as a unit for the purposes of satisfying a request and for ensuring database integrity. There are four important properties of a transaction, Atomicity, Consistency, Isolation and Durability. We call them by capital letters as ACID properties.

1.) Atomicity:

     All changes to data are performed as if they are a single operation. That is, all the changes are performed or none of them are. For example, in an application that transfers funds from one account to another, the Atomicity property ensures that, if a debit is made successfully from one account to another, the correspending credit is made to the other account.

2.) Consistency:

     Data is in a consistent state when a transaction starts and ends.For example, in an application that transfers funds from one account to another, the Consistency property ensures that the total value of funds in both accounts is same, both at the start and end of the transaction.

3.) Isolation:

     The intermediate state of a transaction is invisible to other transactions.As a result, transactions that run concurrently should be serialized.For example, in an application that transfers funds from one account to another, the Isolation property ensures that other transactions see the transferred fund in one account or the other, but not in both nor in neither.

4.) Durability:

     After a transaction successfully completes, changes to the data persists and are not undone, even in the event of a system failure.For example, in an application that transfers funds from one account to another, the Durability property ensures that the changes made to the each account will not be reversed.

We now describe the Anomalies that can be encountered in a multithread environment.

1.) Dirty Reads:

     A dirty read happens when a transaction reads data that is being modified or reads data that recently inserted by another transaction that has not yet been committed. As an example;

• Transaction A begins,
• Update Employee Set salary = 30450 Where empno = '000070', (by transaction A)
• Transaction B begins,
• Select * From Employee Where empno = '000070' (by transaction B),
• Transaction A rollback.

Transaction B sees data updated by transaction A. This update has not yet been committed.

2.) Non-Repeatable Reads:

     Non-Repeatable reads happen when a query returns data that would be different if the same query were repeated in the same transaction. Non-Repeatable reads can occur when other transactions are modifying data that a transaction is reading. As an example;

• Transaction A begins,
• Select * From Employee Where empno = '000070', (by transaction A)
• Transaction B begins,
• Update Employee Set salary = 30000 Where empno = '000070' (by transaction B)
• Select * From Employee Where empno = '000070', (by transaction A)

Transaction B updates row viewed by transaction A before transaction A commits. If transaction A issues the same Select statement the result will be different.

3.) Phantom Reads:

     Records that appear in a set being read by another transaction. Phantom reads can occur when other transactions insert rows that would satisfy the Where clause of another transaction. As an example;

• Transaction A begins,
• Select * From Employee Where salary > 30000, (by transaction A)
• Transaction B begins,
• Insert Into Employee (empno, firstname, midinit, lastname, job, salary) Values ('000350', 'TEST', 'TEST', 'TEST', 'TEST', 75000), (by transaction B)
• Select * From Employee Where salary > 30000, (by transaction A)

Transaction B inserts a row that would satisfy the query in Transaction A if it were issued again.

All these anomalies can be prevented by using the third property of ACID which is Isolation. There are four possible Isolation Levels;

1.) TRANSACTION_READ_UNCOMMITTED: Allows dirty read, non-repeatable read and phantom read.

2.) TRANSACTION_READ_COMMITTED: Prevents dirty read, allows non-repeatable read and phantom read.

3.) TRANSACTION_REPEATABLE_READ: Prevents dirty read and non-repeatable read, allows phantom read.

4.) TRANSACTION_SERIALIZABLE: Prevents dirty read, non-repeatable read an phantom read. 

As we see, if we use TRANSACTION_SERIALIZABLE isolation level, we can get rid of all the anomalies that we may encounter. However, when we consider in terms of performance, using such a high level isolation would break down our system and we would get very high response time in our applications. What we have to do is to design the system as it will allow concurrent access to the database resources. To do this we can apply several steps;

• Divide the physical database into partititons as they don't interrupt with each other. Using partitions may allow us to read committed data since no thread will wait others that deal with data that in different partitions.(Consider a case where all your clients data are in different partitions so they can work individually without waiting others, so no need to read uncommitted data, every client can read their committed data.) To be another example suppose you have partitioned table on a column, but you need to run parallel jobs on that table that select data on a different column's range. In that case the parallel jobs most likely lock each others jobs since the table is not partitioned on the column that used in the parallel jobs.Therefore, you need to carefully desing and choose the partition columns.
• Redesign the application in a way that it won't allow to long transactions and increase commit frequency.
• Put the data manipulation operations at the end of the transaction.

Even we apply all these steps, we may still get locks, deadlocks and livelocks if our application does some Update and Delete operations. Even if we select uncommitted data , the nature of Update, Delete and Insert operations still cause some locks on the system. There are basically three types of locks. These locks can be on row, page, table, partition or tablespace. Before going into the lock modes let's explain the Lock Scopes.

1.) Row Lock:

     You can lock one row of a table. A program can lock one row or selection of rows while other programs continue to work on others rows of the same table. This type of lock uses more CPU resource than other locks, so it has a drawback in usage.

2.) Page Lock:

     The database server stores data in units called disk pages. A disk page contains one or more rows. In some cases it is better to lock a disk page than to lock individual rows on it. For example, with operations that requires changing large number of rows, you might choose page-level locking because row level locking (lock per row) might not be cost effective.

3.) Table Lock:

     Table locks lock the entire table, as if one process continues on the table the other processes must wait. This lock is not suitable for online transactional processing applications, and usually used by online analytical processing applications.

Now we can look for Lock Modes.

1.) Shared Locks (S-Locks):

     The lock owner and any concurrent process can read, but not change the locked page or row. Concurrent processes can acqiure S or U lock on the page or row or might read data without acquiring page or row lock. For example, simple Select statement cause S-lock.

2.) Update Locks (U-Locks):

     The lock owner can read but not change the locked page or row. Concurrent processes can acqiure S lock or might read data without acquiring page or row lock. But no concurrent process can acquire U lock. For example, Select For Update statement cause U-lock.

3.) Exclusive Locks (X-Locks):

     The lock owner can read or change the locked page or row. A concurrent process cannot acqiure S, U or X lock on page or row. However, a concurrent process might read data without acquiring page or row lock. For example, Update, Delete or Insert statement cause X-lock.

Below is a summary table of allowed locks.

Locking	S	U	X
S	Y	Y	N
U	Y	N	N
X	N	N	N

                                                                  Figure 1

If we examine these locks, we see that an Exclusive lock caused by an Update operation with a non-unique predicate may lock whole table (in the case of a table lock and with no Transaction_Read_Uncommitted isolation level).

You have to be careful with the default isolation level of your database system. For example if your database's default isolation level is read_committed, your select statements have to wait the release of lock if there is an update or delete on the region that you selected. If the default isolation level is repeatable_read then all the update and delete oparations have to wait the release of lock if there is a select on the region that you update or delete. Finally if the dafault level is serializable then all the insert operations that satifsy any select statement's range have to wait the release of lock of the select statement even if the insert of data will be on a different space than the locked space. If you want to select uncommitted data you should change the isolation level to read_uncommitted or do some database specific select statements. For example, the default isolation level of DB2 is read_committed and if you want uncommitted data to be selected then use select statement ending with UR(Uncommitted read) in DB2. 
As an important point for MYSQL users, the default isolation level of MYSQL is repeatable_read, so if you encounter some performance problems because of lock wait time in database, this may be the cause.

Example 1: As an example consider the following scenario that run on a DB2 database instance. We have table T1 using page lock with the following columns and values.

T1 --> There is a unique index on (Col1, Col2)

Col1	Col2
1	1000
2	2000
3	3000
4	4000

Let's say there are two pages, the first 3 rows are on page one, and 4th row is on page two.Now consider the following steps.

• Transaction A starts and execute Update T1.. Where Col1 = 1 (not committed yet)
• Transaction B starts and try to execute Update T1.. Where Col1 = 4

Here we have two update statements, so no need to care about the isolation level of the system. An update will always lock the target row or page and concurrent transactions must wait the release of that lock.

Even the transaction B not affect the transaction A being on different system pages, transaction B may still have to wait the transaction A, since the first or second sql statement has not have a unique predicate in the where clause and in our example the DBMS run the queries without using an index instead use a table scan (this happens especially when there is a small amount of data). That means transaction A locks the whole table until it commits and so the transaction B have to wait the commit of transaction A.

If we run transaction B with Delete operation, we might not get a lock. This is because usually delete lock is considered to be a lighter lock than update lock, since most of the DBMS systems doesn't delete the row physically instead it puts a flag indicating the row deleted and the row will physically removed at a later time choosed by the optimizer.

Here another point is using a unique predicate in the where clause. If we use unique predicate in one of the update statements above, depending on the implementation of the DBMS we possibly get no lock since it is enough having an unique predicate to maintain the concurrency.

Example 2: Consider a scenario again on a DB2 database instance. We have a table T1 using page lock and TRANSACTION_SERIALIZABLE isolation level with the following columns and values.

T1 --> There is a unique index on (Col1, Col2)

Col1	Col2
1	1000
2	2000
3	3001

Now consider the following steps.

• Transaction A starts and executes Select * From T1 Where Col1 > 1(not committed yet)
• Transaction B starts and executes Insert Into T1 (3, 3000) 

Here transaction B will have to wait the transaction A, since the Select statement does a range scan, and the Insert statement touches the result of the Select statement. Notice that insert statement will insert new data in some place that is not locked at that moment, that means Serializable isolation level check a logical lock in addition to the physical lock by comparing the where clause of the select statement and the new data that will come with the insert statement.

As you see if we use TRANSACTION_SERIALIZABLE isolation level, all transactions are serialized and this really slow down our application performance. So we should try to avoid using this high level isolation by changing the application logic.

Conclusion:

     In this write, we examine the database application performance in a multithread environment in terms of contention problems. There are many aspects that affect the performance of such an application. Contention is one of the most critical point in database performance since it can cause lock, deadlock or livelock problems. To be able to solve the contention problems one must understand and apply correctly, transaction anomalies, transaction levels, lock scopes and lock modes. In the next paper we'll be talking about another important concept in database performance "Optimizing Memory".

References and Resources:

- IBM documents, http://publib.boulder.ibm.com/infocenter/cicsts/v3r2/index.jsp?topic=%2Fcom.ibm.cics.ts.productoverview.doc%2Fconcepts%2Facid.html

 - Guy Harrison, Oracle® Performance Survival Guide A Systematic Approach to Database Optimization, Prentice Hall, Part IV- V (2009)

Improving Database Performance in a Multithreading Environment-3

Introduction:

     We mentioned about "Minimizing Contention" on improving database performance in the second part of this paper[2]. Now we continue with another concept , "Insert Only Systems and Optimizing Insert Performance" that one may consider when try to improve database performance. Update and Delete operations are very likely to cause locks. If we plan an insert only system and don't choose "Serializable" isolation level and choose to select uncommitted data we'll get no lock in our system and have the highest concurrency. However, insert only systems may cause some other problems. One of them is - since every operation like update and delete is done using an insert - the amount of data in the database will increase rapidly. If we don't consider that, because of huge amount of data, we can get performance degredation. To solve that issue we have to archive our data properly and rapidly. Also we can use partitioning to behave our data as partitioned causing a decrease in the amount of data being operated. Another problem with insert only systems appears when an application has too hight insert rate. The reason for that is, almost all tables generally have a clustered index in which the order of the data is same with the table. When an insert request comes to the DBMS it tries to find a good place to the new data to obey the clustered rule. It causes a search operation to find out the correct place to insert. If there is too big data to search, it will slow down our application. 

Now we'll mention about some methods to optimize insert performance.

Insert Performance Issues:

1.) Indexes on tables are usually created for performance reasons to decrease the search time when selecting data. However every new index added to the table also has a negative impact which appears when an insert, update or delete operation is done. With these DML operations every index must be rearranged. Thus, one could try to decrease the number of indexes on the tables. 
Also most of the indexes on today DMBS systems are B tree indexes and if the levels of the index tree or number of pages at levels are high we possibly get performance degradation. To solve these issues many DBMS systems have capability to keep indexes in memory so we have to try to keep affected indexes, at least non-leaf pages which are %1 of total index pages, in memory by changing the cached memory size. 

2.) If there are sequential inserts on our insert only system, we can apply some methods to insert at the end of the table without searching for a place to obey the clustered colums rule. By this way, one can eliminate read I/O since no search will be done, and reduce write I/O since whole data will be written to the same place.

3.) By inserting rows to empty buffers that is to the memory and scheduling disk write to a later time is a good option. By this way, disk I/O eliminated and DBMS will do the I/O when the system is not heavy loaded.

4.) A DBMS system always keeps some logs for recovery reasons. We have to minimize that log records since it will get another I/O cost to our system. To do this, we may have to do different preventions, for example for DB2 database, we can put frequently changed and variable columns to the end of the table, because a variable lenght row is logged from the first changed byte to the end of the row when an update operation is done on that row (This issue is solved by the DB2 release 9 by automatically placing variable columns to the end of the table). We can also decrease log size by changing some parameters on DBMS system, for example in DB2 "LOAD Log No" parameter means there will be no log created when data is loaded. 

5.) Another issue is batch inserts. That means there will be no need to go the database system for every DML operation in a transaction like Update, Delete or Insert. Instead every operation will be finished in one step. As an example, this can be done with java prepared statement batch option. See in this post.

6.) Usually increasing the commit frequency is the preferred way to minimize the lock wait time.

Conclusion:

     In this write we examine database application performance in a multithread environment in terms of insert only systems to prevent lock issues. If we can design our system with a good archive mechanism we may use insert only systems preventing locks and increasing concurrent access.

References and Resources:

- Guy Harrison, Oracle® Performance Survival Guide A Systematic Approach to Database Optimization, Prentice Hall, Part IV- V (2009)