A mechanism is provided for updating attribute value information for a data table. The data table involves a set of attributes. The data table has multiple records associated with multiple data blocks. Attribute value information is associated with each data block of the multiple data blocks. The attribute value information is descriptive of at least one attribute of the set of attributes. A first data block may be marked as modified in response to a delete process for deleting from a first data block of the multiple data blocks a record having at least one attribute value that is used for generating the attribute value information of the first data block. In response to scanning the marked first data block, the attribute value information associated with the first data block may be updated based on the scan results.