Pokud se zdá, že se výkon stává problémem, může je dobré vytvořit kopii prvního např. 255 znaků dlouhého textu, přidejte na něj index a použijte startswith s tím.
BTW, na této stránce se píše :"Pokud potřebujete provést párování s rozlišováním velkých a malých písmen, deklarujte svůj sloupec jako BINARY; nepoužívejte ve svých dotazech LIKE BINARY k přetypování nebinárního sloupce. Pokud tak učiníte, MySQL nebude používat žádné indexy v tomto sloupci. " Je to starý tip, ale myslím, že stále platí.