mysql: может ли у поля с типом varchar быть primary key?

Чем меньше значения в индексе, тем меньше сам индекс. Маленький индекс занимает меньше памяти и поиск по нему обычно быстрее. Varchar(255) требует гораздо больше места, чем unsigned int (storage requirements) и строить по нему индекс -- плохая затея.

Для идентификации записей в mysql обычно используют автоинкементирующийся суррогатный id (то есть, он не имеет отношения к самим данным и служит только для идентифкации). Такой идентификатор очень удобен, когда надо работать с записями, которые были предварительно получены из бд. Например, мы поискали в базе и теперь хотим обновить или удалить несколько записей, благодаря id доступ к ним будет довольно быстрый.

Но что если требуется искать по varchar? Строить индекс по нему не лучшая затея. Но только если это не хеш-индекс для поиска по поному совпадению. В InnoDB хеш-индексы не поддерживаются (если не ошибаюсь), но можно приделать костыль в виде поля содержащего хэш значения от того, по которому нужен поиск. К entity_id добавляете entity_id_crc и при записи туда кладёте crc32(entity_id) (обратите внимание, что функция crc32 возвращает unsigned int, значит колонка должна иметь именно этот тип). По такой колонке можно создать неуникальный индекс и при поиске писать where entity_id_crc=crc32('foobar') and entity_id='foobar' (так как поле entity_id_crc не уникально, то обязательно надо добавлять и проверку основного поля, но благодаря индексу такая проверка будет выполняться только для нескольких значений, а не всех записей в таблице).

Таким образом вам следует завести id int unsigned not null autoicrement, который будет первичным ключом. Операции по изменению и удалению записей можно производить по этому идентификатору (where id=123, where id in (123, 456)). Для поиска нужно построить индекс по тем полям, которые будут участвовать в выражении where (возможно не всем, а только наиболее селективным). При этом следует избегать b-tree индексов по текстовым полям (они вряд ли будут полезны). Если искать по текстовым полям всё-таки надо (речь о полном совпадении entity_id = 'foobar'), то можно построить хеш-индекс (или если ваша подсистема хранения не поддерживает его, воспользоваться костылём описанным выше).