News Column

Patent Issued for Parallelizing Scheduler for Database Commands

January 30, 2014

By a News Reporter-Staff News Editor at Computer Weekly News -- Verisign, Inc. (Reston, VA) has been issued patent number 8631416, according to news reporting originating out of Alexandria, Virginia, by VerticalNews editors.

The patent's inventor is Rodriguez, John (Capitola, CA).

This patent was filed on March 31, 2011 and was published online on January 14, 2014.

From the background information supplied by the inventors, news correspondents obtained the following quote: "Databases are an essential part of computing and information management. Databases provide data storage and an interface to insert, update, delete, and retrieve the data found therein. Generally, a database processes instructions sequentially, one instruction after another. This is at least in part due to the typical operation of a database. Typically, a user will request information from the database as it is needed, insert a new record in the database as it is created, update a database record as soon as an edit is received, or delete a record as soon as it is no longer needed. Sequential operation of a database does have some advantages. For instance, data dependency is easily maintained. Because each statement executes one after another, there is little worry of retrieving out-of-date information. Not all database operations, however, need to occur sequentially. In fact, most probably do not.

"Due to the data integrity requirements of a database, each database vendor has its own methods of providing data quality assurances through the use of locking algorithms to ensure a particular database table, record, or field is not read if it is currently being accessed for a write operation. Processing instructions as they are received results in execution inefficiencies because a read operation may be unrelated to the next write operation or two sequential write operations may be on two different tables; these operations could be executed concurrently, reducing execution cycles, execution time, and execution overhead. The inefficiencies increase the cost of hardware and software required because more database servers are required to handle increased loads.

"These inefficiencies are also passed on to a backup database and a developmental database. For example, a production database server or cluster of servers might pass the instructions it receives to a backup database environment or developmental database. The backup database or developmental database must handle the same write load as the production database. This could result in significant costs in secondary database servers or clusters to support the backup or developmental databases. A method is needed to reduce the costs of operating such systems.

"With parallelization as an intermediary, the number of instruction cycles on the backup or developmental database can be significantly reduced, allowing for cheaper hardware and less additional software licenses. The database instructions may first be passed to the parallelizing scheduler and then to the secondary database which may then run the instructions in parallel in a multi-threaded operation. Another example where parallelization would be useful is when a database fails, because restoring the database from transaction logs can take a significant amount of time. Parallelization can optimize the transaction logs to significantly reduce the overall number of cycles, allowing for faster recovery. Transaction logs may even be parallelized in advance. Parallelization can also help further reduce costs by enabling the database operator to keep a backup database on a different database platform. For example, the production environment might use an expensive license based database, but with parallelization the backup may use an inexpensive, custom, or free database to greatly reduce operating costs. With the proliferation of dynamic web sites, parallelization implemented at the web site script code level would reduce the load on a database, prolonging the longevity of equipment without the need to upgrade as quickly or expand into more complicated multiple database setups. Finally, a database product could benefit from using a parallelizing scheduler in the processing of commands. Rather than simply processing commands sequentially, the parallelizing scheduler may store the commands in memory, optimize the commands, and run them in parallel.

"A simple example is where (i) data is written to Table A and (ii) data is read from Table B. Because these two instructions have no dependency on each other, they can be executed in parallel, rather than sequentially. In general, consider five basic SQL commands: SELECT, INSERT, UPDATE, DELETE, and CREATE. At their core these correspond to operations to READ, WRITE, WRITE, WRITE, and WRITE on the database, respectively. Now, consider a table with two columns, 'name' and 'phonenum.' When a READ statement requests data from the table after a WRITE statement to the table, then a true data dependency exists, i.e., executing the READ statement before the WRITE statement may result in unexpected results. When a WRITE statement to the table follows a READ statement to the table, then anti-dependency exists, i.e. executing the READ statement after the WRITE statement may result in unexpected results. When a WRITE statement to the table follows another WRITE statement to the table, then output dependency exists, i.e., executing the WRITE statements in the reverse order will result in incorrect values in the database. Note that the final combination of statements, the READ after READ statement will never result in a data dependency because the data is the same for each execution. Using these data dependency relationships, sequential database instructions may be construed into in parallel execution levels."

Supplementing the background information on this patent, VerticalNews reporters also obtained the inventor's summary information for this patent: "A computer-implemented method of parallelizing database commands includes receiving and processing by a computer a listing of sequential database commands into data dependent chains. The method includes grouping the database commands based on data dependencies into an execution schedule that enables the commands to be processed in parallel while maintaining their data dependencies. The method also includes delivering the execution schedule.

"It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the application, as claimed.

"The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate one (several) embodiment(s) of the application and together with the description, serve to explain the principles of the application."

For the URL and additional information on this patent, see: Rodriguez, John. Parallelizing Scheduler for Database Commands. U.S. Patent Number 8631416, filed March 31, 2011, and published online on January 14, 2014. Patent URL:

Keywords for this news article include: Software, Verisign Inc.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Computer Weekly News

Story Tools