An online system identifies and ranks records using multiple machine learning models in response to a search query. Therefore, the online system can provide selected records that are of the most relevance to a user of a client device that provided the search query. More specifically, the online system applies a first machine learning model that is of low complexity, such as a regression model. Therefore, the first machine learning model can quickly narrow down the large number of records of the online system to a first set of candidate records. The online system analyzes candidate records in the first set by applying a more complex, second machine learning model that more accurately determines records of interest for the user. In various embodiments, the online system can apply subsequent machine learning models of higher complexity for selecting and ranking records for provision to the client device.