Paginate performance issue I was wondering if anyone else has experienced a serious performance hit when implementing pagination?

By just using Safari's timeline, I can see my page takes 500ms to generate.  After introducing JUST the paginate tag (not including any loops etc), it now takes 1.5s!  

Is this normal behaviour?  If not, what should I be doing to improve the performance?

Thanks

EDIT:  Thanks for the suggestions regarding caching.  I am aware of the cache tag however, the paginated entries are the results of a search query with various filters so I'm concerned that the caching will have little effect.  Or am I wrong?
Add the following tags around your {% pagination %}

{% cache %}
{% endcache %}


Those tags will refresh every time the content changes, and when the content hasn't changed, it'll reduce your database queries significantly.

For more info see:


The craft docs
What are the best practices for using the cache tag