I did not look more precisely into the code, but dokuwiki's search engine seems quite slow too: http://isfates.mandragor.org/toto/ufr/dokuwiki_search.png
Disabling dokuwiki's search engine improves considerably it's performances! I have a dokuwiki running without last page versions, last edits, search and pages index... It's working quite great now! But lacks a few features ;) Improving performances of theses features would make dokuwiki one of the greatest wiki out there!!
Keep up the good work! Yann