시스템 구성이 어떻게 되어있는지 모르니 도움이 되는 답변이 될지는 모르겠습니다.

테이블 구조와 검색쿼리를 알려주시면 같이 고민해볼 수 있을듯 합니다.

말씀 하신대로 날짜에 index가 걸려있고 단어를 찾는 필드는 index가 안걸려있는 상황이라면 4천만건에 대한 full scan이 됩니다.

생각나는 대로 한번 적어보겠습니다.

어차피 정답은 없는 답변입니다.

1. innodb type-> myisam type으로 변경하고 fulltext index를 이용해서 검증

아래 윤호님과는 좀 다른 생각입니다만 현재 innodb 의 경우에는 fulltext 검색을 지원하지 않는 것으로 알고 있습니다.

그리고 4000만건의 데이터가 select가 거의 대부분일듯 한데 selected 위주라면 myisam도 나쁘진 않을 듯 싶습니다.

2. 검색 속도를 위해서라면 테이블 분리하는것도 나쁘진 않을것 같습니다. 

분리하는 방법으로는 

4000만건의 데이터를 적당한 크기로 잘라서 여러 테이블들을  만들고 순차적으로 검색하고 그 결과를 합쳐서 

보여주던지 하는겁니다. 이럴 경우에는 DB쪽 보다는 웹서버쪽에 로드가 더 갈듯 합니다.

두번째로는 적당한 크기의temp_table을 만들어서 이용해보는겁니다.

세번째로는 DB 파티셔닝을 통해서 가상으로 테이블을 나눠서 사용해보는 것입니다.

3. 검색전문 엔진을 사용합니다.

무료로 사용이 가능한 검색엔진들이 있으니 찾아서 테스트 해보시는것도 좋을듯 합니다.

좋은 결과 있으시길 바라겠습니다.