Techniques are disclosed relating to methods that include preprocessing, by a computer system, records of a database to create one or more token sets for a given record. The created token sets may correspond to ones of a plurality of search string functions, and may include token sets that include a plurality of possible substrings located within data strings of a corresponding database record. The methods may further include receiving a query for a search of the database. The query may include at least one of the plurality of search string functions. The method may also include performing the search by traversing, using at least a portion of the records, at least one token set corresponding to the included search string functions, as well as returning results for the search based on the query and the traversing.