Table of 4 columns "definition is too large"

I'm trying to optimize a large(4M rows) and busy table of mine. It's currently

CREATE TABLE person_search (
    token CHAR(63), -- each word of the person's name
    person_id BIGINT(20) UNSIGNED, -- foreign key on person.id; not constrained because MyiSAM
    birth_date DATE NULL, -- for ordering the results
    gender ENUM('male', 'female') NULL, -- additional filtering
    INDEX (token, birth_date, person_id),
    INDEX (person_id, token)
) ENGINE='MyISAM';

Searches are performed by INNER JOINing this table with itself as many times as needed for the number of tokens in the user's query. (For performance, searches are always prefix searches (LIKE 'foo%'); not sub-string searches (LIKE '%foo%')). To potentially improve performance, I tried MODIFYing the token column to be a massive ENUM():

ALTER TABLE person_search MODIFY token ENUM(
    'AAB',
    'AABYE',
    'AACH',
    -- snip ~110'000 values; longest value is 20 chars
    'ZYSTRA',
    'ZYWYLO',
    'ZYZAK'
) NOT NULL;

but after a few seconds, MySQL returned the error ERROR 1117 (HY000): Table definition is too large. [Googling it](https://www.google.com/search?q=mysql+%22Table+definition+is+too+large%22) didn't help. I think MySQL/MyiSAM can't do this, and I'll have to handle the enumeration myself in the application instead of the DB, or make a person_search_token_enum table and add more inner joins. But maybe I'm missing a setting or something. It's not a shared server; I can make any configuration changes I want.