はじめまして。はしけむと申します。
現在、料理レシピを検索できるウェブサイトの構築を行っています。

SQLをいじりだして、２ヶ月程度です。

１０万件程度のデータから、レシピを高速に検索したいのですが、
以下のようなクエリで行き詰っています。
アドバイスをいただけけると助かります。

SELECT
	ID
FROM
	Recipe
WHERE
	MATCH( 'Title,Description' )
	AGAINST( '+"じゃがいも"' IN BOOLEAN MODE )
	AND
	CategoryA = 4
	AND
	CategorB = 2

このようなクエリをより高速にしたいのですが、
どのようにする方法がよいでしょうか？

CagetoryA、CategoryB について、インデックスを使用できない
でいることが、クエリが遅い原因だと考えています。

Categoryは、9種類あり、それぞれ、2〜8種類の値が入ります。
（Title、Descriptionは、UTF-8の文字列を分かち書きしてあります）

自分で考えた解決策としては、

案１：Categoryも文字列型にして、"CategoryA4 CategoryB2"のような値を
　　　入れて、全文検索のインデックスに含める

案２：Categoryごとに、前もって別のテーブルを作っておく。

　　　一日一回実行
	INSERT RecipeA4
	SELECT * FROM Recipe WHERE CategoryA = 4;

　　　検索時（Categoryの条件は別に処理しておいて、）
	SELECT ID FROM RecipeA4 WHERE MATCH,,,,

というものなのですが、これらの方法の可否、よりよい方法などについての
アドバイスなどありましたら、非常に助かります。
よろしくお願いいたします。