If you use utf8mb4 charset, Relevanssi database table may be missing an index. That’s because part of the index includes a column type that is of varchar(210) type. This is fine with utf8, but fails for utf8mb4, which only allows columns 191 characters long (because maximum column size is 767 bytes, and for 4-byte utf8mb4 characters that means 191 × 4 = 764 bytes).
To fix this, the column type needs to be shortened to varchar(191) and the index created again:
CREATE INDEX typeitem ON wp_relevanssi (type, item)
This seems to vary between servers; in some cases this fails and ends up with an error message, in some cases the index will automatically include only the first 191 characters of the column.
Also, if you shorten the column to 191 characters, you may run into problems if you have taxonomy slugs that are more than 191 characters long. Unlikely, yes, but something to be aware of.