Systems and methods are disclosed to implement a Boolean query evaluation system that allows clients to specify a latency constraint for evaluating Boolean queries. In embodiments, the system evaluates queries using data from multiple external data sources. If some data sources fail to return data in a timely fashion to satisfy the specified latency constraint, the system will evaluate the query using the data that it was able to obtain and generate a partial answer to the query—a partial true or a partial false. In embodiments, the query response may include a reason for the partial answer, and indicate the list of data sources that failed to provide timely results. In embodiments, the system may publish a table indicating different latency constraints specified for a category of queries and the types of answers returned for those queries. Clients may use the table select latency constraints for future queries.