1. A method of performing space-efficient data query operations, comprising: interning fields of a plurality of multi-field records to produce interned records representing the multi-field records; receiving a query to compute a result over the plurality of multi-field records; initializing a sparse bit set, said sparse bit set sized to accommodate a number of distinct values present in one of the fields of the plurality of multi-field records; dividing the interned records into two classes according to the query; and setting a bit in the sparse bit set for each interned record of one of the two classes, wherein an in-memory representation of the sparse bit set, exclusive of overhead, occupies fewer bits than the number of distinct values present in the one of the fields of the plurality of multi-field records.