Computer systems, machine-implemented methods, and stored instructions are provided herein for maintaining information that describes aggregate characteristics of data within zones. Stored data may be separated into defined zone(s). Data structure(s), such as zone map(s), may store, for each of the zone(s), aggregate characteristic(s) of data in the zone, and a stored indication of whether or not the zone is stale. When a change is made to data in a particular zone that was not stale, a zone manager causes the particular zone to become stale if the change can result in the particular zone having data that is not included in the particular zone's stored aggregate characteristic(s). On the other hand, if the change cannot result in the particular zone having data that is not included in the particular zone's stored aggregate characteristic(s), then the zone manager does not cause the particular zone to become stale.