Indexing partitions using distributed bloom filters

A method, comprising:

• generating, by a data indexing system, a plurality of indices for a plurality of partitions in a distributed object store, wherein the indices comprise a plurality of probabilistic data structures, and wherein an individual one of the probabilistic data structures corresponds to one or more fields of an individual one of the partitions;
• determining, by the data indexing system using the probabilistic data structures, a first portion of the partitions that possibly comprise a value and a second portion of the partitions that do not comprise the value;
• and
• determining, by the data indexing system based at least in part on a scan of the first portion of the partitions and not the second portion of the partitions, one or more partitions of the first portion of the partitions that comprise the value.

One or more non-transitory computer-readable storage media storing program instructions that, when executed on or across one or more processors, perform:

• generating a plurality of indices for a plurality of partitions in a distributed set of object stores, wherein the indices comprise a plurality of Bloom filters, and wherein an individual one of the Bloom filters corresponds to one or more fields of an individual one of the partitions;
• determining, using the Bloom filters, a first portion of the partitions that possibly comprise a value and a second portion of the partitions that do not comprise the value;
• and
• performing a scan of the first portion of the partitions and not the second portion of the partitions;
• and
• determining, based at least in part on the scan, one or more records that comprise the value in one or more partitions of the first portion of the partitions.