Puppet doesn't actually query every package individually.
The first time a package resource is processed, Puppet invokes the prefetch method on the YUM package provider. The prefetch method queries the entire RPM database, parses out package names, version numbers, etc. and caches the result. The same is done with the YUM Updates list.
For each package defined, Puppet must compare the requested resource state against the current state. Because we've pre-fetched the package list, this is a simple comparison of data structures. This step happens individually; the package may have changed between Puppet runs, but the desired properties of the package resource in the supplied catalog may have changed as well.
Another factor is that the Package type and provider interface is standardized across a couple dozen different package providers. A package is a generic abstraction that different back ends may be plugged into. Although it might be possible to query whether or not the catalog and RPM database has changed, this approach is not guaranteed to work for all package providers. Implementing this special feature would be a high cost to avoid a simple rpm -qa.
"Implementing this special feature would be a high cost to avoid a simple rpm -qa".... It's a very quick check with a very low cost, with a huge benefit. It would lower my puppet run time from 330 seconds to 30 seconds.
Check your catalog. Are any of your packages marked "ensure => latest"? The 'latest' property invokes "yum check-update" to determine the latest available release of your package. 'Yum check-update' is a costly operation that must download the package metadata from all your configured package repositories. Puppet attempts to avoid this operation if possible
It is not possible for Puppet to completely avoid this check without breaking 'latest' for folks who rely on Puppet and a package channel to update their software.
rpm -qa is an extremely fast operation; you can confirm this by running it on the console. It shouldn't add more than a second to your overall runtime.