If your dpkg runs seem to take a long time in the “reading database” step, try this:
Step One: Clear the available file dpkg --clear-avail
Step Two: Forget old unavailable packages dpkg --forget-old-unavail
Step Three: If you use grep-available or other tools that rely on a useful available file, update the available file using sync-available (in the dctrl-tools package).
The few times I’ve tried it (all situations where the “reading database” step seemed to take ages), it has always sped the process up dramatically. There probably are situations where it won’t make much difference, but I haven’t run into them.