A system, comprising: one or more hardware computing devices comprising a plurality of nodes, wherein the plurality of nodes comprise: storage for a plurality of data ranges corresponding to a distribution of data stored in a plurality of data blocks for a database table; storage for respective probabilistic data structures for individual ones of the plurality of data blocks, wherein the respective probabilistic data structure for a respective data block of the plurality of data blocks indicates which data ranges of the plurality of data ranges correspond to data values not stored in the respective data block; at least one node of the plurality of nodes configured to: detect a rebalancing event for the distribution of the data in the plurality of data blocks; and in response to detecting the rebalancing event: modify, based on a change to the distribution of the data corresponding to the rebalancing event, one or more of the plurality of data ranges; and update respective probabilistic data structures for respective ones of the plurality of data blocks, wherein said update is according to the modified one or more of the plurality of data ranges. one or more hardware computing devices comprising a plurality of nodes, wherein the plurality of nodes comprise: storage for a plurality of data ranges corresponding to a distribution of data stored in a plurality of data blocks for a database table; storage for respective probabilistic data structures for individual ones of the plurality of data blocks, wherein the respective probabilistic data structure for a respective data block of the plurality of data blocks indicates which data ranges of the plurality of data ranges correspond to data values not stored in the respective data block; storage for a plurality of data ranges corresponding to a distribution of data stored in a plurality of data blocks for a database table; storage for respective probabilistic data structures for individual ones of the plurality of data blocks, wherein the respective probabilistic data structure for a respective data block of the plurality of data blocks indicates which data ranges of the plurality of data ranges correspond to data values not stored in the respective data block; at least one node of the plurality of nodes configured to: detect a rebalancing event for the distribution of the data in the plurality of data blocks; and in response to detecting the rebalancing event: modify, based on a change to the distribution of the data corresponding to the rebalancing event, one or more of the plurality of data ranges; and update respective probabilistic data structures for respective ones of the plurality of data blocks, wherein said update is according to the modified one or more of the plurality of data ranges. detect a rebalancing event for the distribution of the data in the plurality of data blocks; and in response to detecting the rebalancing event: modify, based on a change to the distribution of the data corresponding to the rebalancing event, one or more of the plurality of data ranges; and update respective probabilistic data structures for respective ones of the plurality of data blocks, wherein said update is according to the modified one or more of the plurality of data ranges. modify, based on a change to the distribution of the data corresponding to the rebalancing event, one or more of the plurality of data ranges; and update respective probabilistic data structures for respective ones of the plurality of data blocks, wherein said update is according to the modified one or more of the plurality of data ranges.