Disclosed embodiments provide techniques for database query utilizing a multigram index. In embodiments, a search query is divided into multiple regex subcomponents. Regex subcomponent indexes are created and searched in parallel, and/or in a sequential manner on reduced data sets, increasing search performance, especially for NoSQL databases.