WHERE句で
Replace(TelNumber, '-', '') = '09011112222'
のように、カラムに対して何かしらの演算を行うSQLは遅いクエリになりがちです。
インデックスを張っていても効かないのでIndex Scanになってしまうからですね。
計算列をテーブルに追加し、その列にインデックスを追加すれば解決できますが、その場合は既存のクラスタ化インデックスにカラム追加＋追加で非クラスタ化インデックスを作成する必要があるため、レコード数が多いとディスク容量も結構増えます。
また、実稼動しているテーブルにカラムを追加するのはなかなか心理的なハードルも高いです。他テーブルと「Select * From...」でUnionしてた日にはエラーになっちゃいますし。。
何か良い解決策はないかと調べていたところ、インデックス付Viewが良さそうでした。
https://technet.microsoft.com/ja-jp/library/ms187864(v=sql.105).aspx
テーブルのカラム構成も変わらないし、追加インデックス分しか増加しないので良い感じです。
ただ懸念点として、上記ページに
インデックス付きビューは、基になるデータを更新する頻度が低い場合に最も効果的です。インデックス付きビューをメンテナンスする方が、テーブル インデックスのメンテナンスよりもコストがかかる場合があります。基になるデータを頻繁に更新する場合、インデックス付きビューの使用によるパフォーマンス向上よりも、インデックス付きビューのデータ メンテナンスにかかるコスト増加の方が大きい場合があります。
とあります。非クラスタ化インデックス1つ追加したときに比べて、とても更新コストが増えてしまう印象を抱いてしまいました。
心配になったため開発環境で試したところ、速度的に問題はなさそうです。
リファレンスの文章の意味を考えると、count_big()やsum()などの集計処理を含むインデックス付Viewの場合には更新コストが大きいので、頻繁に基テーブルが更新されるようなケースではインデックス付Viewは不適切な選択だ、という意味かなと解釈しました。
今回のケースのようにReplace演算を行う程度であれば、頻繁に更新するテーブルを含んだIndex付Viewを作成しても問題なさそうです。