Methods and apparatus to search datasets are disclosed. Example methods include in response to a search request including first and second logically related criteria, determining a first number of records in a database satisfying the first criterion and a second number of records in the database satisfying the second criterion; when the first number is less than the second number, selecting the first criterion as a basis for generating a subset of the records of the database; when the second number is less than the first number, selecting the second criterion as the basis for the identification of the subset of the records of the database; and searching the subset of the records.