A document search engine facilitates input prediction for searching content within stored documents associated with a user by maintaining a data structure comprising entries that are each associated with one of the stored documents, wherein each entry comprises textual content of one of the stored documents, and wherein the textual content comprises a plurality of characters. The textual content of each entry in the data structure is analyzed to identify sequential relationships between the characters in the textual content. An input text comprising a text character is received from a user as part of a search query, and a predicted text to follow the input text is determined, where the predicted text is based on the one or more sequential relationships between the characters in the textual content. The document search engine then provides the search query including the input text and the predicted text to the client device.