Character Maps in Query Processing

(MSc Research Project / MSc Thesis)

Character maps in database systems are specialized data structures optimized for efficient string handling. Similar to Bloom filters, they allow quick checks for the presence of characters or substrings without full string comparisons. This makes them useful for accelerating string-related queries and improving overall search performance in databases.

The goal of this project is to delve deeply into character maps: What strategies for building character maps exist, and how do they compare to Bloom filters and prefix trees (aka tries)? How large do character maps need to be to provide significant performance improvements? Do they only benefit strings, or perhaps numbers and enums that follow a certain schema (e.g., phone numbers, person age, IBANs)? If the results are promising, a variant of the thesis could be submitted to a research conference as a workshop paper.