import time, MySQLdb
...
db = MySQLdb.connect(...)
cursor = db.cursor()
...
clock_before = time.clock()
cursor.execute("SELECT somequery")
elapsed_for_query = time.clock() - clock_before
print "検索にかかった時間: %4.2f 秒" %(elapsed_for_query)

とやればいいのでは？