A database is a collection of stored data that is logically related and that is accessible by one or more users or applications. A popular type of database is the relational database management system (RDBMS), which includes relational tables, also referred to as relations, made up of rows and columns (also referred to as tuples and attributes). Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, thing, or other object about which the table contains information.
One of the goals of a database management system is to optimize the performance of queries for access and manipulation of data stored in the database. Given a target environment, an optimal query plan is selected, with the optimal query plan being the one with the lowest cost, e.g., response time, as determined by an optimizer. The response time is the amount of time it takes to complete the execution of a query on a given system.
In massively parallel processing (MPP) systems, dealing with data skew is critical to the performance of many applications. Partial redistribution, partial duplication (PRPD) mechanisms have been proposed for an optimizer to use when joining large tables where data skew is known to exist and the skewed data values are also known. For example, assume a join operation is to be performed on two relations that are evenly partitioned across all processing modules, e.g., Access Module Processors (AMPs), and none of the join attributes of either table are the respective tables' primary index, e.g., the values that are hashed to distribute the base table rows to the MPP AMPs. In such a situation, hash values are calculated on the attributes of the join operation, and the rows are redistributed to AMPs according to the hash values. In the event there is data skew in a column on which the join operation is applied, the hash redistribution of the rows to complete the join operation will result in an AMP receiving an excessive number of rows compared to other AMPs involved in the join operation. As referred to herein, an AMP or other processing module having an excessive load distributed thereto with respect to other AMPs or processing modules is referred to as a hot AMP. In such a situation, processing of the query may demonstrate a relatively slow response time due to the excessive load and system resource usage at the hot AMP, and consequently processing of the operation may exhibit a low overall system parallel efficiency. An AMP may receive significantly more table rows on which the query is applied due to various causes, such as a natural demographic data skew, e.g., high biased values, skew resulting from null values, or various other causes. Adding additional nodes or AMPs may decrease the overall parallel efficiency since adding more nodes may result in distribution of less rows to each non-hot AMP thereby producing a greater relative disproportionate distribution of rows to the hot AMP.
The avoidance of highly skewed data is extremely important to queries executed on any shared nothing parallel system. The PRPD mechanism mentioned above has been implemented to use when joining two large tables where data skew is known and the skewed data values are also known. Further, mechanisms have been implemented that extend the PRPD approach to a dynamic scenario for joins. However, contemporary systems do not effectively provide for dynamic skew avoidance to generic skewed query problems considering all issues which include query selectivity, lack of data statistics, possible source skewed data, etc.
Consider a table R having attributes c1 and c2, where c1 is the primary index and c2 is a column which needs to be redistributed due to a query on R, e.g., a join of R.c2 to another table or a selection of some aggregate values grouped on R.c2. Further assume that R.c2 is highly skewed on a certain value which is not known before the query due to a lack of statistics or inaccurate statistics.
If traditional redistribution mechanisms are utilized, a single AMP will receive all the skewed values from R.c2 which may result in typical problems, such as slow response time, unbalanced workload, and/or out of spool errors. Further, by using a dynamic approach, if the hot AMP is detected too late, it may not facilitate optimization in any manner. Still further, contemporary mechanisms do not consider the query selectivity, and thus mistakes may be made in detecting the hot AMP. Still further, even if the skewed valued of R.c2 is appropriately detected, if the attribute c1 is also skewed on a certain hot AMP “A”, the AMP A will still be hot even if the skewed R.c2 values are maintained locally.
Therefore, what is needed is a mechanism that overcomes the described problems and limitations.
USPTO Backgrounds
USPTO Backgrounds