Identifying skewed queries in an MMP system

Apparatus and methods for determination of unacceptable skew for query in a massively parallel processing system. The apparatus and methods may use data associated with processing the query that has been stored in computer logs. The processing data may be used to determine the actual level of skew for the query. The apparatus and methods may calculate an acceptable level of skew. If the actual skew exceeds the acceptable skew, the query may be considered unacceptably skewed and may be flagged for tuning.

FIELD OF TECHNOLOGY

Aspects of the disclosure relate to massively parallel database processing. In particular, the disclosure relates to identifying unacceptably skewed queries that may require tuning.

BACKGROUND

A massively parallel processing system (“MPP system”) is a computer system with many independent arithmetic units or entire microprocessors running in parallel. The system may incorporate hundreds or thousands of central processing units (“CPUs”) working together.

A query processed on the system may be broken up and distributed over more than one CPU for processing. In almost all cases, the processing times for the individual CPUs working on the query will not be exactly equal. Skew occurs when one processor is performing more work than the others.

The higher the variation between processors performing the least and most amounts of work, the greater the degree of skewing. Too much skew can significantly impair the efficiency of the system. When one CPU is working on a query for a disproportionate amount of time, other queries waiting to be processed will be backed up.

Conventionally, acceptable skew is determined by hand based on analyst experience.

For a given query, the associated information regarding processing history, such as total CPU time expended, and average CPU time per processor are stored in computer logs. Conventionally, this information is analyzed by hand to determine if the amount of skew for the query is acceptable, and if not, whether the query is a candidate for tuning. This approach is time consuming and requires analysts experienced in assessing the query data.

It would be desirable, therefore, to provide apparatus and methods for electronically identifying unacceptably skewed queries processed in an MPP system.

SUMMARY OF THE INVENTION

It is an object of this invention to provide apparatus and methods for electronically identifying unacceptably skewed queries processed in an MPP system. Apparatus and methods for making such an electronic identification are provided.

Processing data associated with a query may be stored in computer logs. The apparatus and methods may extract processing data for a query from the logs.

The apparatus and methods may filter the information obtained from the logs to eliminate categories of queries that are unsuitable for tuning.

For a query which may be a candidate for tuning, the apparatus and methods may determine a value for the actual amount of skew. The apparatus and methods may calculate a value for an acceptable amount of skew. If the actual amount of skew exceeds the acceptable amount, the query may be considered unacceptably skewed and may be flagged for tuning.

DETAILED DESCRIPTION OF THE INVENTION

Apparatus and methods for electronically identifying unacceptably skewed queries processed in an MPP system are provided.

Skewing is an unavoidable result in massively parallel processing. However, too much skewing can waste significant processing time and impair the efficiency of a processing system. A query which is unacceptably skewed may be tuned to enable the elements of the query to be more efficiently distributed among the parallel processing units.

The determination of whether a query requires tuning is based on processing data stored in computer logs. Conventionally, experienced analysts review the processing data stored in the logs by hand. In many cases these personnel could be more profitably employed on other products. In addition, the time spent waiting on analysis may delay the deployment of new queries.

Under the principles of the invention, a determination of unacceptable skewing may be made electronically. Developers testing a query may obtain results immediately, without waiting for analyst review. Testing for skewing, tuning and retesting may become an organic part of the development process.

The apparatus and methods may begin by extracting query processing data from the computer logs for analysis. Examples of processing data include the total CPU time used, the CPU time for each processor, the total number of blocks read or written by the disk subsystem (“I/O operations”), the number of I/O operations per processor and any other suitable data.

The apparatus and methods may filter groups of queries which are not suitable for tuning. Examples of queries not suitable for tuning include help queries, drop queries and any other appropriate query.

Equations 1-4, below, illustrate a method in accordance with the principles of the invention. The apparatus and methods may determine the amount of skew and whether that degree of skew is acceptable. An unacceptably skewed query may be flagged for further tuning. In the method illustrated below, skewing is measured in terms of CPU processing time and number of I/O operations, but any suitable measure of skew may be applied.

The apparatus and methods may determine the amount of actual skew for the query.

Actual skew based on CPU processing time may be calculated as shown in Equation 1 or using any other suitable measure of CPU skew. In Equation 1, CPU skew is measured as the processing time on the busiest processor divided by the average processing time.

In Equation 1, Tnis the processing time in seconds for CPU n working on the query. The term TBis the processing time on the busiest processor. Processing times for each individual processor may be extracted from the log and ranked for analysis. N is the number of active processors.

Actual skew based on the number of I/O operations may be calculated as shown in Equation 2 or using any other suitable measure of I/O skew. In Equation 2, I/O skew is calculated as the number of I/O operations on the busiest processor divided by the average number of I/O operations.

In Equation 2, the term Oncorresponds to the total number of I/O operations for a processor and term N corresponds to the number of processors working on the query. The term OBis the number of I/O operations on the busiest processor.

The apparatus and methods may determine an acceptable level of skew for the query. Acceptable skew defines the upper limit of skew that may be tolerated. Any skewing above this level may result in the query being recommended for tuning.

Equation 3 may be used to calculate an acceptable level of CPU skew and may be calculated based on the measured CPU processing time for the query.

Equation 3 is based on an empirically derived data set of acceptable skew levels that correspond to observed CPU processing times. This data set was used to develop a mathematical correlation between acceptable skew and CPU processing time. The correlation may define a curve passing through, or constrained by, the set of known data points.

The curve defined by the correlation may be adjusted to follow the shape of a curve derived by graphing average CPU skew as a function of processing time. The constants in Equation 3 apply to different sections of the curve and may be modified to adjust the shape of curve. The correlation shown in Equation 3 was developed using mathematical operations which are compatible with database programming, but other operations may be applied.

In Eqn. 3, ACCTSKEWCPUis acceptable CPU skew. Acceptable CPU skew is calculated as a function of T, the total CPU seconds needed to process the query. The default value for the constant MR is 2.5, but may be modified to alter the mid-range of the curve. The default value for the constant UR is 10.5, but may be modified to alter the upper range of the curve. The default value for the constant LR is 660, but may be modified to alter the lower range of the curve.

Equation 4 may be used to calculate an acceptable level of I/O skew based on the measured number of I/O operations for a query.

Equation 4 is based on an empirically derived data set of acceptable skew levels that correspond to observed numbers of I/O operations. This data set was used to develop a mathematical correlation between acceptable skew and number of I/O operations. The correlation may define a curve passing through, or constrained by, the set of known data points.

The correlation may be adjusted to follow the shape of a curve showing average I/O skew based on historical query data. The constants in Equation 4 apply to different sections of the curve and may be changed to adjust the curve if necessary. The correlation shown in Equation 4 was developed using mathematical operations which are compatible with database programming, but other operations may be applied.

In Equation 4, ACCTSKEWIOis the acceptable IO skew. Equation 4 calculates ACCTSKEWIOas a function of O the total number of I/O operations for the query, and N, the number of processing units working on the query.

The apparatus and methods may compare the actual CPU skew for a query as calculated in Equation 1 with the acceptable CPU skew for the query calculated in Equation 3. Where actual CPU skew exceeds acceptable CPU skew, the query may be considered unacceptably skewed based on CPU processing time.

The apparatus and methods may compare the actual I/O skew as calculated in Equation 2 with the acceptable I/O skew for the query calculated in Equation 4. Where actual I/O skew exceeds acceptable I/O skew, the query may be considered unacceptably skewed based on I/O operations.

The apparatus and methods may mark an unacceptably skewed query for tuning using any appropriate method. Embodiments of the invention will now be described with reference toFIGS. 1-6.

As will be appreciated by one of skill in the art upon reading the following disclosure, various aspects described herein may be embodied as a method, a data processing system, or a computer program product. Accordingly, those aspects may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects.

Furthermore, such aspects may take the form of a computer program product stored by one or more computer-readable storage media having computer-readable program code, or instructions, embodied in or on the storage media. Any suitable computer readable storage media may be utilized, including hard disks, CD-ROMs, optical storage devices, magnetic storage devices, and/or any combination thereof. In addition, various signals representing data or events as described herein may be transferred between a source and a destination in the form of electromagnetic waves traveling through signal-conducting media such as metal wires, optical fibers, and/or wireless transmission media (e.g., air and/or space).

FIG. 1is a block diagram that illustrates a generic computing device101(alternatively referred to herein as a “server”) that may be used according to an illustrative embodiment of the invention. The computer server101may have a processor103for controlling overall operation of the server and its associated components, including RAM105, ROM107, input/output module109, and memory125.

Input/output (“I/O”) module109may include a microphone, keypad, touch screen, and/or stylus through which a user of device101may provide input, and may also include one or more of a speaker for providing audio output and a video display device for providing textual, audiovisual and/or graphical output. Software may be stored within memory125and/or storage to provide instructions to processor103for enabling server101to perform various functions. For example, memory125may store software used by server101, such as an operating system117, application programs119, and an associated database121. Alternatively, some or all of server101computer executable instructions may be embodied in hardware or firmware (not shown). As described in detail below, database121may provide storage for query processing data, skew values, tuning recommendations and any other suitable information.

Server101may operate in a networked environment supporting connections to one or more remote computers, such as terminals141and151. Terminals141and151may be personal computers or servers that include many or all of the elements described above relative to server101. The network connections depicted inFIG. 1include a local area network (LAN)125and a wide area network (WAN)129, but may also include other networks. When used in a LAN networking environment, computer101is connected to LAN125through a network interface or adapter123. When used in a WAN networking environment, server101may include a modem127or other means for establishing communications over WAN129, such as Internet131. It will be appreciated that the network connections shown are illustrative and other means of establishing a communications link between the computers may be used. The existence of any of various well-known protocols such as TCP/IP, Ethernet, FTP, HTTP and the like is presumed, and the system can be operated in a client-server configuration to permit a user to retrieve web pages from a web-based server. Any of various conventional web browsers can be used to display and manipulate data on web pages.

Additionally, application program119, which may be used by server101, may include computer executable instructions for invoking user functionality related to communication, such as email, short message service (SMS), and voice input and speech recognition applications.

Computing device101and/or terminals141or151may also be mobile terminals including various other components, such as a battery, speaker, and antennas (not shown).

Terminal151and/or terminal141may be portable devices such as a laptop, cell phone, blackberry, or any other suitable device for storing, transmitting and/or transporting relevant information.

Query processing information, skew values, tuning recommendations, and any other suitable information may be stored in memory125.

FIG. 2shows illustrative system200. System200is an illustrative massively parallel processing database architecture. System200may include three primary components: client applications and servers201, parallel processing units204, and permanent data storage207.

A client may access the system (e.g., to submit a database query for processing) using client applications and servers201. Client data may be routed, e.g., via communications network210, for processing through routers202. Routers202may be configured with failover systems. The data may be routed through nodes203that may be channel attached (e.g., via TC/IP and channel connections) to the array of processors204. In a MPP system, each processor functions as a subsystem with its own memory and operating system. The processors communicate via a high speed interconnect.

Data may be routed from the processors back to the client servers for client access. Alternatively, data may be transferred through data connection device205to mainframe206and to channel attached storage devices207. Store devices207may include, for example, channel attached disk space212, tape silo214, and/or any other suitable storage devices. The many interconnections supplied by the extensive networking on this system may enable widespread access and unobstructed data flow between the three different areas of the system.

FIG. 3is a high level flow diagram showing illustrative process300for identifying a skewed query for tuning.

At step301, users submit queries on a massively parallel database system. At step302, query runtime statistics are stored in a computer log. At step303, procedures are executed to apply the formulae governing acceptable skewing to the logs. At step304, skewed queries are identified. At step305, analysts tune unacceptably skewed queries.

FIGS. 4 and 5show illustrative data used in creating the formulae shown in Equations 3 and 4. Graph401shows average historical CPU skew (vertical axis) for a given CPU processing time (horizontal axis). The data is drawn from CPU times collected across 5 million queries. Equation 3 is created using known acceptable skew data points and the correlation is adjusted to model the actual historical curve shown at graph401.

Graph501shows the average historical I/O skew (vertical axis) for a given number of I/O operations (horizontal axis). The data is drawn from I/O operations over 15 million queries. This curve is used to define the shape of the showing acceptable I/O skew. The mathematical correlation used for calculating acceptable I/O skew may be adjusted based on the shape of the historical curve shown.

FIGS. 6A and 6Bshows illustrative computer programming code for identifying unacceptably skewed queries. The illustrative code is programmed using a relational database management system sold under the trademark TERADATA, by the Teradata Corporation, Miamisburg, Ohio, but any suitable system may be used.

Section601of the code identifies variables that may be used in the illustrative query. Some of these variables are drawn from the computer logs and some may be calculated as part of the query instructions. Section602sets up the parameters of the query text variable, eliminating text that is null or blank.

Section603sets up the parameters for CPU skew compliance. A specific category of query is eliminated from consideration, as well as queries which require very little processing. The upper limit of acceptable CPU skew is labeled CPU break-even point (“CPUBEP”). Where actual CPU skew (“CPUskew”) exceeds acceptable CPU skew the query is flagged as non-compliant.

Section604sets up the parameters for I/O skew compliance. Again, a specific category of query is eliminated from consideration as are queries which require little processing. The upper limit of acceptable I/O skew is labeled I/O break-even point (“IOBEP”). Where actual I/O skew (“IOskew”) exceeds acceptable I/O skew the query is flagged as noncompliant.

Section605identifies another set of variables for consideration.

At section606, CPU skew is calculated as shown in Equation 1, above. In this illustration skew is calculated to two decimal places. At section607, I/O skew is calculated as shown in Equation 2, above. I/O skew is also calculated to two decimal places.

Section608identifies another set of variables for consideration. At section609, acceptable CPU skew is calculated as a function of processing time as shown in Equation 3, above. Any results below 1.25 are set at 1.25 which is the threshold for acceptable skew levels. At section610, acceptable I/O skew is calculated as shown in Equation 4, above. Again, any results below 1.25 are set at 1.25.

At section611, various query data is retrieved from the computer logs. Specific categories of queries are filtered out and are not considered candidates for tuning, regardless of the amount of skew in their processing. Thus, apparatus and methods for identifying skewed queries processed in an MPP system are provided. Persons skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration rather than of limitation, and that the present invention is limited only by the claims that follow.