Techniques are provided for using of zone maps to improve the performance of a much wider range of queries than those for which zone maps are currently used. Specifically, techniques are provided for using zone maps to improve performance of queries by providing aggregate values for a wide range of aggregate operations, including SUM, AVG, etc., providing aggregate values for aggregate queries that specify filter conditions, distinguishing between situations in which the aggregate values for a zone are invalid for pruning purposes and when the aggregate values are invalid for query-answering purposes, determining when aggregate values may be used in multi-table zone maps where the type of join specified by a query differs from the type of join used to generate the aggregate values in the zone map, and selecting among different aggregate values for the same zone based on the type of join specified in a query.