To receive the best performance when querying a large feature class, it is necessary to work with hierarchies, lookup tables and indices.
On the first hierarchical level the usage of a lookup table is recommended. See chapter A Lookup Table for details.
On lower levels it is recommended to work with combined database indices. The combined index has to match the order of the query (e.g. street + house number).

Combined Indices on a feature class in ArcCatalog