>Do I have to modify all records? I have so far 1000 records already of that format :(

If the records are already in format of first 3 characters of the field are actual character, then no... the index will work without changing the actual record values...