Efficient query processing in mcdb-r
Alin Dobra, Ravi Jampani · 2012
Quantitative risk analysis has become an integral part of large financial institutions. For banking and insurance enterprises, calculating the risk of future insolvency is mandatory per the regulatory directives such as Solvency and Basel. Performing risk analysis in these enterprises is difficult because the systems are highly complex and have a large number of uncertain variables. One form of risk analysis is in understanding the impact of extreme events that have a low chance of occurrence. The common methods used to estimate this extreme risk come from statistics and rare event simulation fields, and are based on Monte Carlo sampling. However, these sampling-based methods produce huge amounts of data. Therefore, the current implementations of risk analysis methods have scalability problems, particularly as they relate to complex systems with a very large number of variables. Monte Carlo DataBase with Risk analysis (MCDB-R) is a database system designed to facilitate scalable risk analysis on large datasets. MCDB-R combines sampling-based statistical methods and relational database technology for scalability on large uncertain data sets. Uncertainties in data are modeled as probabilistic distributions. A query on this uncertain data with probability distributions results in another probabilistic distribution called query-result distribution. For a given scenario defined by a query, analyzing its extreme events requires examining the upper or lower areas of the query-result distribution, where the events occur with very low probability. The specific methods used in MCDB-R for this analysis are: Gibbs sampling from statistics and cloning from rare-event simulation. These methods are used to efficiently sample from the low probability areas of the query-result distribution for the analysis. This dissertation discusses three improvements to the query processor in MCDB-R. The first technique provides a mechanism to move the sample generation (during the query execution) closer to the location where those samples are actually processed. Huge number of samples are generated during the query execution in MCDB-R, and this new mechanism reduces the sample movement in the memory hierarchy. Response time of the queries is improved significantly; sometimes by an order of magnitude, as shown in the experiments. MCDB-R employs a rejection algorithm at the core of its sampling-based risk analysis. For each uncertain variable, the rejection algorithm looks at a series of samples and discards them unless the sample fits a given constraint. Sometimes the constraints are so stringent that the rejection algorithm needs to process millions of samples before finding a good fit. In MCDB-R, an instance like this will require the same number of samples to be produced for all variables. In the second technique, this problematic instance is isolated from the rest of the query execution and then run separately to find an acceptable fit. The normal execution restarts after finding the required sample. Finally, adding an anti-join operator to the MCDB-R execution engine is explained. This new operator enables the system to execute subset-based queries with not-in and not-exists clauses. Performing an anti-join in this system is not trivial because of the stochastic nature of the data. The system does not know which samples are actually used until the end of the query execution. Two methods to implement the anti-join operator are discussed and then compared through experiments.