Systems, methods, apparatuses, and software for distributed database systems in computing environments are provided herein. In one example, a method of operating a database system is provided that includes providing an interface to a database service that hosts at least a data store across a plurality of storage elements distributed with respect to each other, and receiving, in the interface, lookup requests to determine if first keys indicated by the lookup requests are present in the data store. The method includes processing the lookup requests with at least a bloom filter initialized with second keys associated with the data store to determine presence statuses of the first keys with respect to the data store, and indicating the presence statuses responsive to the lookup requests.