The *_gid_redirect tables used to be used only for lookups by MBID, for which there is an index due to the MBID (gid column) being the primary key. However, now there is a load_gid_redirects method for JSON-LD that queries these tables by new_id instead, requiring a sequential scan of the whole table (since the 2015-01-12 release). Indexes on that column need to be added.