A device comprising: a processing unit (114; 134); and a computer-readable medium (116, 136) including modules configured for execution by the processing unit (114, 134), the modules comprising: a sampling module configured to determine a first subset of a data set, the first subset comprising first data records selected from the data set based at least in part on respective measure values of the first data records, wherein the measure value is a value that can be added to other measure values in the first subset, and wherein probability of each of the first data records being selected is proportional to the measure value in each of the first data records; an indexing module configured to determine an index comprising a mapping from a predicate to one or more second data records of the data set associated with the predicate and to respective approximation values associated with the one or more second data records; and a querying module configured to: process a query against the first subset to provide a first result and a first accuracy value; determine that the first accuracy value does not satisfy a predetermined accuracy criterion; and process the query against the index to provide a second result. a processing unit (114; 134); and a computer-readable medium (116, 136) including modules configured for execution by the processing unit (114, 134), the modules comprising: a sampling module configured to determine a first subset of a data set, the first subset comprising first data records selected from the data set based at least in part on respective measure values of the first data records, wherein the measure value is a value that can be added to other measure values in the first subset, and wherein probability of each of the first data records being selected is proportional to the measure value in each of the first data records; an indexing module configured to determine an index comprising a mapping from a predicate to one or more second data records of the data set associated with the predicate and to respective approximation values associated with the one or more second data records; and a querying module configured to: process a query against the first subset to provide a first result and a first accuracy value; determine that the first accuracy value does not satisfy a predetermined accuracy criterion; and process the query against the index to provide a second result. a sampling module configured to determine a first subset of a data set, the first subset comprising first data records selected from the data set based at least in part on respective measure values of the first data records, wherein the measure value is a value that can be added to other measure values in the first subset, and wherein probability of each of the first data records being selected is proportional to the measure value in each of the first data records; an indexing module configured to determine an index comprising a mapping from a predicate to one or more second data records of the data set associated with the predicate and to respective approximation values associated with the one or more second data records; and a querying module configured to: process a query against the first subset to provide a first result and a first accuracy value; determine that the first accuracy value does not satisfy a predetermined accuracy criterion; and process the query against the index to provide a second result. process a query against the first subset to provide a first result and a first accuracy value; determine that the first accuracy value does not satisfy a predetermined accuracy criterion; and process the query against the index to provide a second result.