I discovered, that with old frontend (I believe it was 1.5.something), things were still fast and as a workaround, I used this for a while, but now I would like to get latest version to work as fast, as it was before.

So I looked the database processlist and found that there were two queries that took long time - they both located in include/graphs.inc.php in this function:

get_min_itemclock_by_graphid()

http://www.zabbix.com/forum/showthread.php?t=11782