Bug#1067440:

[Laurențiu Nicola <lnicola@dend.ro>]

Correction: because of full-text search, it might actually be quadratic in the number of packages (I didn't check). And it might be possible to fix it, by going through the compressed stream just once, instead of restarting (assuming the results are returned in the file order, which seems reasonable).