how to efficiently prove the query result is empty?
Obviously something needs to be trusted. If there is no prior  trusted something it can't be done.
In one setup used in DNSsec a trusted party signs empty intervals according to some ordering. So when you want to give a negative answer you provide the signed empty interval.
Obviously there is a problem with the validity of such answers when the data changes. You may get a properly signed but obsolete answer. Though people can in many cases commit on a  certain record remaining valid for a significant time frame. Commiting to a range remaining empty is much harder.