Slow Query for Alphabetically Adjacent Terms

[Chad Cluff]

I have a large table (19,112,023 rows) that contains a text column that users search. One of the features our users have requested is the ability to get an alphabetical list of terms that are adjacent to their search term.

The table:

DROP TABLE IF EXISTS `textinfo`.`master_heading`;
CREATE TABLE  `textinfo`.`master_heading` (
  `rec_id` int(10) unsigned NOT NULL,
  `field_id` smallint(6) NOT NULL,
  `heading_id` smallint(6) NOT NULL,
  `heading_seq` tinyint(3) unsigned NOT NULL,
  `field_tag` smallint(6) NOT NULL,
  `heading` varchar(1000) NOT NULL,
  `norm_type` tinyint(3) unsigned NOT NULL,
  KEY `headIdx` (`heading`(333)),
  KEY `rec_id` (`rec_id`),
  FULLTEXT KEY `heading` (`heading`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

I've come up with this query:

(SELECT rec_id, heading as head FROM master_heading m WHERE heading > "SEARCH TERM" ORDER BY heading ASC LIMIT 5)
UNION
(SELECT rec_id, heading as head FROM master_heading m2 WHERE heading < "SEARCH TERM" ORDER BY heading DESC LIMIT 5)
ORDER BY head;

Which does return the desired results, it just tends to take approximately 120 - 160 seconds.

Explain gives me this:

1, 'PRIMARY', 'm', 'ALL', 'headIdx,heading', '', '', '', 19112023, 'Using where; Using filesort'
2, 'UNION', 'm2', 'range', 'headIdx,heading', 'headIdx', '1001', '', 742279, 'Using where; Using filesort'
, 'UNION RESULT', '<union1,2>', 'ALL', '', '', '', '', , 'Using filesort'

Is there a way I can better optimize this? Our users would prefer quicker results.

Thanks for any help.