Abstract:
A method and computer program are disclosed for increasing the efficiency of a row sequential database operation by transforming procedural logic, which applies serially to one row at a time, into set logic, which applies in parallel to many rows or all rows at once. The method includes dividing the row sequential operation into a plurality of portions. A hierarchy is determined for the portions. A set level operation is generated in accordance with the portion hierarchy.

Description:
TECHNICAL FIELD 
     The invention relates to database systems and, in particular, to set-level database access for row-sequential operation. 
     BACKGROUND 
     Conventional database systems store data in the form of records or rows. Each row includes one or more related items of information. For example, a row can include the date, number, amount and customer for an order. Certain groups of rows are organized into tables. For example, an Orders table can include all of the rows describing the characteristics of orders that have been received. 
     Users of database systems manipulate and extract information from the tables and rows that make up the system. Such requests are conventionally referred to as queries. Queries can range in complexity from a request for the display of the information in a particular row to an accumulation of data regarding rows and tables that comprise terabytes of information. Users of database systems also insert, delete, and update the information stored in the tables and rows. 
     Database systems that employ parallel processing can manipulate and extract information from multiple rows and tables at the same time. Such systems can also insert, delete, and update multiple rows and tables at the same time. Queries and other database system operations that only address a single row at a time do not take advantage of the abilities of parallel processing. 
     SUMMARY 
     In general, in one aspect, the invention features a method for increasing the efficiency of a row sequential database operation by transforming procedural logic, which applies serially to one row at a time, into set logic, which applies in parallel to many rows or all rows at once. The method includes dividing the row sequential operation into a plurality of portions. A hierarchy among the portions is then determined. Based at least in part on the hierarchy of portions, a set level operation is generated. 
     Implementations of the invention may include one or more of the following. A set level operation is generated that corresponds to a the row sequential operation that includes at least one IF . . . THEN . . . ELSE statement based on a condition. The generated set level operation includes a WHERE statement based on that condition. Another implementation includes levels in the hierarchy among the portions of the row sequential operation and as each of any assignment statements are located they are associated with one of the levels. 
     In general, in another aspect, the invention features a method for increasing the efficiency of a row sequential database operation by transforming procedural logic, which applies serially to one row at a time, into set logic, which applies in parallel to many rows or all rows at once. The method includes analyzing the row sequential database operation. The analyzed row sequential database operation is then translated and the result is optimized to produce a set level operation. 
     In general, in another aspect, the invention features a computer program, stored on a tangible storage medium, for use in increasing the efficiency of a row sequential database operation by transforming procedural logic, which applies serially to one row at a time, into set logic, which applies in parallel to many rows or all rows at once, the program including executable instructions that cause a computer to divide the row sequential operation into a plurality of portions. The computer then determines a hierarchy among the portions. The computer generates a set level operation in accordance with the portion hierarchy. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a node of a parallel processing database system. 
         FIG. 2  is a block diagram of a parsing engine. 
         FIG. 3  is a flow chart of a parser. 
         FIG. 4  is a flow chart for a method of set-level database access. 
         FIG. 5  is a flow chart of a method for analyzing row sequential database operations. 
         FIG. 6  is a flow chart of a method for translating analyzed database operations. 
         FIG. 7  is a flow chart of a method for optimizing analyzed and translated database operations. 
         FIG. 8  is a table of function translations. 
         FIG. 9  is a example of a row sequential database operation. 
         FIG. 10  is an example of a set-level database access operation corresponding to the row sequential database operation of  FIG. 9 . 
         FIG. 11  is a example of a row sequential database operation. 
         FIG. 12  is an example of a set-level database access operation corresponding to the row sequential database operation of  FIG. 11 . 
         FIG. 13  is a example of a row sequential database operation. 
         FIG. 14  is an example of a set-level database access operation corresponding to the row sequential database operation of  FIG. 13 . 
     
    
    
     DETAILED DESCRIPTION 
     A database operation optimization technique operates by translating a row sequential database operation to a set level database operation. Hierarchical relationships between portions of the row sequential database operation are identified. The functions are then translated based on the hierarchy. 
     The database operation optimization technique disclosed herein has particular application, but is not limited, to large databases that might contain many millions or billions of records managed by a database system (“DBS”)  100 , such as a Teradata Active Data Warehousing System available from NCR Corporation.  FIG. 1  shows a sample architecture for one node  105   1  of the DBS  100 . The DBS node  105   1  includes one or more processing modules  110   1 . . . N , connected by a network  115 , that manage the storage and retrieval of data in data-storage facilities  120   1 . . . N . Each of the processing modules  110   1 . . . N  may be one or more physical processors or each may be a virtual processor, with one or more virtual processors running on one or more physical processors. 
     For the case in which one or more virtual processors are running on a single physical processor, the single physical processor swaps between the set of N virtual processors. 
     For the case in which N virtual processors are running on an M-processor node, the node&#39;s operating system schedules the N virtual processors to run on its set of M physical processors. If there are 4 virtual processors and 4 physical processors, then typically each virtual processor would run on its own physical processor. If there are 8 virtual processors and 4 physical processors, the operating system would schedule the 8 virtual processors against the 4 physical processors, in which case swapping of the virtual processors would occur. 
     Each of the processing modules  110   1 . . . N  manages a portion of a database that is stored in a corresponding one of the data-storage facilities  120   1 . . . N . Each of the data-storage facilities  120   1 . . . N  includes one or more disk drives. The DBS may include multiple nodes  105   2 . . . N  in addition to the illustrated node  105   1 , connected by extending the network  115 . 
     The system stores data in one or more tables in the data-storage facilities  120   1 . . . N . The rows  125   1 . . . Z  of the tables are stored across multiple data-storage facilities  120   1 . . . N  to ensure that the system workload is distributed evenly across the processing modules  110   1 . . . N . A parsing engine  130  organizes the storage of data and the distribution of table rows  125   1 . . . Z  among the processing modules  110   1 . . . N . The parsing engine  130  also coordinates the retrieval of data from the data-storage facilities  120   1 . . . N  in response to queries received from a user at a mainframe  135  or a client computer  140 . The DBS  100  usually receives queries and commands to build tables in a standard format, such as SQL. 
     In one implementation, the rows  125   1 . . . Z  are distributed across the data-storage facilities  120   1 . . . N  by the parsing engine  130  in accordance with their primary index. The primary index defines the columns of the rows that are used for calculating a hash value. The function that produces the hash value from the values in the columns specified by the primary index is called the hash function. Some portion, possibly the entirety, of the hash value is designated a “hash bucket”. The hash buckets are assigned to data-storage facilities  120   1 . . . N  and associated processing modules  110   1 . . . N  by a hash bucket map. The characteristics of the columns chosen for the primary index determine how evenly the rows are distributed. 
     In one example system, the parsing engine  130  is made up of three components: a session control  200 , a parser  205 , and a dispatcher  210 , as shown in  FIG. 2 . The session control  200  provides the logon and logoff function. It accepts a request for authorization to access the database, verifies it, and then either allows or disallows the access. 
     Once the session control  200  allows a session to begin, a user may submit a SQL request, which is routed to the parser  205 . As illustrated in  FIG. 3 , the parser  205  interprets the SQL request (block  300 ), checks it for proper SQL syntax (block  305 ), evaluates it semantically (block  310 ), and consults a data dictionary to ensure that all of the objects specified in the SQL request actually exist and that the user has the authority to perform the request (block  315 ). Finally, the parser  205  runs an optimizer (block  320 ), which develops the least expensive plan to perform the request. 
     The optimizer  320  can develop plans based on the extent to which the SQL request is submitted in set level format. If the SQL request is submitted in a row sequential format, the optimizer will be less able to divide the execution of the request among the to data-storage facilities  120   1 . . . N  and associated processing modules  110   1 . . . N . 
       FIG. 4  is a flow chart depicting an implementation of a method for generating a set level operation from a row sequential operation. The row sequential database operation  400  is the input to the method  402 . A row sequential operation  400  can be defined by Procedural Logic or PL/SQL. For example, Oracle Extract, Cleansing, Transformation, and Load (ECTL) processes use PL/SQL. Equivalent set level operations be efficiently used on a database system that employs parallel processing. The method  402  of generating an equivalent set level operation includes three different steps. 
     The first step of the method  402  is analysis  404 . The details of analysis  404  of a row sequential operation are shown in more detail in  FIG. 5 . The second step of the method  402  is translation  406 . The details of translation  406  of an analyzed row sequential operation are shown in more detail in  FIG. 6 . The third step of the method  402  is optimization  408 . The details of optimization  408  of an analyzed and translated row sequential operation are shown in more detail in  FIG. 7 . The output of the optimization  408  is a set level database operation  410 . 
       FIG. 5  is a flow chart depicting the analysis  404  of a row sequential database operation  400 . Various portions of the operation definition are identified  502 , including packages, procedures, functions, loops, IF statements, and parameters. Various portions of operation definition are removed  504 , including comments, trailing semicolons, and EXECUTE IMMEDIATE statements. The analysis  404  changes “truncate table” to “delete from” and, for help in processing scripts that write to web pages with HTP. calls, it also changes “htp.*data( )” to “insert into htp.*data values( ),” and similarly for “htp.*header( ).”  506  Global variables are translated  508 . For example, if the definition of a row sequential operation to be used with Oracle includes the global variable sysdate, the global variable DATE is substituted. 
     The operation definition is grouped into lines and blocks  510 . In one implementation, a line is identified as any string that is terminated by a “;” or “then” or “loop” or “begin”. In one implementation, a block begins with one of the following key words: package, procedure, and function. In one implementation a block begins with the word following then, loop, begin, and else. A block ends with a line that starts with the word “end,” such as “end if;”, “end loop;” or simply “end;”. A block can also end with the word “else” or “elseif”. Every block is also assigned a level number  512 . For example, the block between an “if . . . then” line and an “else” line is one level higher than the block containing the if and else. In this way, a hierarchy of logical conditions is formed. An analyzed row sequential database operation  514  is output. 
       FIG. 6  is a flow chart depicting the translation  406  of an analyzed row sequential database operation  512 . The operation definition is scanned to locate assignment statements  602 . 
     In one implementation, each “:=” assignment operator is moved to the beginning of the line to simplify the next scan, so that “a :=b+c” becomes “:=a b+c”. During translation, “fetch . . . into” statements and “select . . . into” statements are transformed into assignment-like statements, the first word being “:=”  604 . Assignment substitutions are also performed  606 . For example, if “:=a b+c” is specified at one point, a subsequent “:=d a+e” becomes “:=d b+c+d”. Also, if “:=a a+b” is specified within a loop, this becomes “:=a SUM b” (to indicate that a is the sum of the b&#39;s). In one implementation, all variables are substituted with their source definitions, if possible, otherwise they are indicated as host variables with a preceding “:”. User-defined functions are modified with the RETURN statement translated into an “insert into function-name — RETURN . . . ”  608 . The insert is also translated. The result of the translation  406  is an analyzed and translated row sequential database operation  610 . 
       FIG. 7  is a flow chart depicting the optimization  408  of an analyzed and translated row sequential database operation  610 . The operation definition is scanned in execution sequence  702 . For example, a subprocedure is not scanned until it is invoked by the parent procedure. Procedure parameters are treated as host variables. A conditional hierarchy is generated and associated with assignment statements  704 . For example, IF statements are stored hierarchically until an assignment statements is found; each assignment statement is associated with this conditional hierarchy for later translation to a CASE operation or WHERE clause. The condition of an IF statement can be incorporated into a WHERE statement. For example, “IF order&gt;10 then { . . . }” becomes “WHERE (order&gt;10) { . . . }”. 
     The next three steps translate insert  706 , update  708 , and delete  710  statements to the extent they are found in the analyzed and translated row sequential operation. When an insert or update or delete statement is located, all the values and predicates in that statement are translated according to their associated substitutions and conditions. Whenever one of these assignments is found to have originated in a cursor, that cursor becomes one of the objects in the FROM part of the insert-select. A cursor is a definition of a set of rows from which rows are drawn sequentially. If an assignment is not associated with a cursor, it will appear as a host variable (i.e., preceded by a colon (:)). Each select-statement that is not associated with a cursor loop is also translated. 
     The final step translates row sequential functions, for example Oracle functions, to set level functions, for example Teradata functions  712 . Nested row sequential functions are translated into nested set level functions. A more detailed implementation of function translation is depicted in  FIG. 8 . For example, the nested row sequential function “decode(A,‘B’,nvl(C,″),″)” becomes the nested set level function “case A when ‘B’ then coalesce(C,″) else ″ end.” 
       FIG. 8  depicts a first group of row sequential functions and a corresponding second group of set level functions. As shown with respect to the to_char(v,f) function, more than one set level function can correspond to a row sequential function. In some implementations, additional functions can be added to either group. In some implementations, multiple set level functions can correspond to a single row sequential function based on the inputs of the row sequential function. 
       FIG. 9  depicts a row sequential operation defined by PL/SQL. The cursor statements identify information (for example for a: Amt, D_date, and acct_num) that is drawn one row at a time. A loop is provided that inserts various values based on the results of conditions in IF statements. The insert into MyDeposits occurs when amount&gt;0 for a particular row from the cursor a. 
       FIG. 10  depicts a set level operation define by SQL that is generated by one implementation of the disclosed method and computer program. The IF condition of amount&gt;0 becomes a condition of the WHERE statement. The IF condition ddate is null becomes the condition of a CASE WHEN statement. The global variable sysdate is replaced by DATE. The function to_char(acct_rec.AcctNum,‘9(9)’) is translated to the function cast(cast(B.AcctNum as (Format ‘9(9)’)) as char(9))). The set level operation is performed on groups of rows rather than sequential rows and is therefore more efficiently handled by a parallel processing database system. 
       FIG. 11  depicts a row sequential operation that is defined by a loop based on a cursor to sequentially access information in rows of the Deposits table. The loop tests the information for a single row by applying an IF . . . ELSEIF . . . ELSEIF . . . ELSE statement and chooses an assignment statement based on the condition that is met. Finally, a row of the Gen_Ledger table is inserted by values that are based at least in part on the assignment statement that was chosen. 
       FIG. 12  depicts a set level operation that corresponds to the row sequential operation of  FIG. 11 . The definition of the set level operation includes a single INSERT statement for all the rows of the Deposits table that employs a CASE statement to equivalently implement the conditions of the IF . . . ELSEIF . . . ELSEIF . . . ELSE statement. A parallel processing database system can insert rows stored in different data storage facilities at the same time to increase performance. 
       FIG. 13  depicts a row sequential operation that is defined by a loop based on a cursor to sequentially access information in rows of the Acct_Transactions table that is nested within a loop based on a cursor to sequentially access information in rows of the Accts table. The block containing the nested loop has a higher hierarchy level than the blocks containing the outside loop. The outside loop updates the Accts table.  FIG. 14  depicts a set level operation corresponding to the row sequential operation of  FIG. 13 . The definition of the set level operation includes a single UPDATE statement that includes a FROM statement and a WHERE statement corresponding to the hierarchy of the nested loops. 
     The foregoing description of the preferred embodiment of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.