Yea, I kind of figured it out later. The problem though is that RPM actually has an index of all files – so rpm -qf is fast. dpkg-query -S actually have to search through the file list for each installed package in dpkg database – and it can take a while on a system with many files that have lived a while (the dpkg databased gets slower and slower the more you install and upgrade packages).