Methods and apparatus to search datasets are disclosed. An example disclosed apparatus includes a grouper to reference statistics associated with a database to identify which criterion of a group of logically related criteria of a search request satisfies fewer ones of records in the database, an identifier to select the identified criterion of the group of logically related criteria as a driving criterion for the group of logically related criteria, a reduced set generator to form a subset of the records of the database based on the driving criterion, and an analyzer to reduce a search time associated with the search request by searching the subset of the records for a non-driving criterion of the group of logically related criteria.