Unfortunately it turned out small optimizations do not help much. The problem is that the OSS repository contains more than 60.000 (!) packages. Iterating over dependencies of all packages will take lot of time, speed optimizations can help only a bit. In pkg-bindings we have Pkg.PkgQueryProvides() function (https://github.com/yast/yast-pkg-bindings/blob/3ed52e693ca6a79fd7ee6db41e024137268d517c/src/Package.cc#L115) which handles the "Provides" RPM dependency in a very efficient way. I thought we could create a similar function (PkgQuerySupplements) which would handle the "Supplements" dependency used in by AutoYaST. Unfortunately libzypp does not support that, it only supports WhatProvides (https://github.com/openSUSE/libzypp/blob/master/zypp/sat/WhatProvides.h) and WhatObsoletes (https://github.com/openSUSE/libzypp/blob/master/zypp/sat/WhatObsoletes.h). So my proposal is: 1) Switch from "Supplements: autoyast(foo)" to Provides: Provides: autoyast-tag() Provides: autoyast-tag(foo) ("autoyast-tag" is just a proposal, feel free to suggest anything better ;-)) 2) In the code: a) first get packages providing "autoyast-tag()" using Pkg.PkgQueryProvides("autoyast-tag()"), that should return few packages (like a dozen or so) b) then for that few packages get all dependencies and find out that "autoyast-tag(.*)" details That should be both fast and memory efficient.