1. A computer-implemented method performed by data processing apparatus comprising one or more computers in data communication, the method comprising: determining, for a particular native application on a user device, a history rate limit that limits an amount of history data provided by the native application over time; capping the amount of history data received for the native application on the user device so as the amount of history does not exceed the rate limit when the amount of history data received for the native application on the user device over a period of time exceeds the rate limit; receiving, from a first user device, a search query input for a search application that provides a search environment in which a user can input a search query and receive search results from a search service, the search query input comprising one or more characters; accessing native application history data for the first user device, the native application history data describing content presented by a plurality of native applications at the first user device, each of the plurality of native applications being different from the search application; generating, based on the search query input and the native application history data for the first user device, one or more query suggestions; and providing, to the first user device, the one or more query suggestion for presentation in the search environment of the search application.