Quote Originally Posted by KenEwald
You are quite right, it is a question of scale and, yes, I am joining this table with several other tables.

The core driving table (that has the columns for which I have criteria) is a very large table. If I use 'SMITH' in my query, it takes f.o.r.e.v.e.r (100+ seconds), if I use 'FUZ', it returns in 3 seconds.

I apologize, but I can't post the query. Don't you think the bottom line is the issue of selectivity?

Would Oracle Text help here?
Are these "fuzzy" matches, or are you searching for the entire name with an equality operator? If fuzzy, are you using any functions such as soundex to run with this? I have found that (using soundex) searching for "SMIT%" always takes considerably longer than searching for "FUZ%" (or whatever), even with histograms.

Oracle Text may or may not help if you are fuzzy matching. It depends of how often DML is performed on columns that have Text Indexes (different to "normal indexes"), and whether the overhead of maintaining the indexes is worth your while (EXEC CTX_DDL.SYNC_INDEX('idx')). To be honest, i'm not sure if using it for a column such as surname is the right way to go anyway (more designed for columns with 100s or 1000s of character values).