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.