The query planner does not seem to notice that we are trying to know if
any row exists matching a set of dependency values, and it keeps scanning
multiple row for each value - which is unproductive.
So split dependency queries from (pseudo-code)
  WHERE <column{,s}> IN <values{, pairs}>
to unions of
  WHERE <column{,s}> = <value{, pair}> LIMIT 1
which produces query plans which do stop immediately when finding a
candidate row.
On a serialization_tag query with 40 values and real-world indexations,
this reduces the number of rows scanned by mariadb from 500 (<10%
efficiency) to 40 (100% efficiency).
The produced SQL is significantly larger (~3x, around 500kB on
real-world sample data, but may vary a lot depending on value length),
but if this has any effect is is more than compensated by the improved
query plan efficiency.