SYSTEM AND METHOD FOR CREATING AN INTELLIGENT SYNOPSIS OF A DATABASE USING RE-PARTITIONING BASED SAMPLING

摘要

The present invention provides a re-partitioning-based sampling system and method which provides for generating a synopsis from large database tables such that an aggregation query performed on the synopsis provides an approximate answer to the aggregation query which is in prescribed error bounds relative to a query on the full database. The system includes a partition function generator, a synopsis vector calculator, and a synopsis constructor. The synopsis constructed by the system is sufficiently small to be held in memory to allow quick and resource efficient satisficing of aggregation queries.

主权项

1. A method for generating a synopsis of a database table, the method comprising:
receiving a first data sample from the database table; receiving a plurality of candidate functions for partitioning the data sample; selecting a selected function from the plurality of candidate functions, wherein partitioning the first data sample with the selected function divides the first data sample partition into two data sample partitions and wherein the selected function is selected such that a variance of the two data sample partitions over the other candidate functions of the plurality of candidate functions is minimized; re-partitioning the data sample with a plurality of selected functions until a stopping condition is met; generating a partition function using the plurality of selected functions; receiving a second data sample from the database table; partitioning the second data sample using the partition function; and generating the synopsis of the database table using the second data sample partitioned with the partition function.