`have_seen_events` is eating up time while processing state and auth events while backfilling

This issue has been migrated from [#13625](https://github.com/matrix-org/synapse/issues/13625).

---

*Mentioned in [internal doc](https://docs.google.com/document/d/1lvUoVfYUiy6UaHB6Rb4HicjaJAU40-APue9Q4vzuW3c/edit#bookmark=id.8eo3xt7lhv6b). Part of https://github.com/matrix-org/synapse/issues/13356*

---

Optimize `have_seen_events` because when backfilling `#matrix:matrix.org`, 20s is just calling `have_seen_events` on the 200k state and auth events in the room.

- `have_seen_events` (157 `db.have_seen_events`) takes 6.62s to process 77k events
- `have_seen_events` (246 `db.have_seen_events`) takes 13.19s to process 122k events

---

Benchmark and timing is from the in-flight PR, https://github.com/matrix-org/synapse/pull/13561

The `@cachedList` is so slow 🐌 and we're better off removing it at this point. Would be good see if `@cachedList` can be improved or if we can improve things further with a better cache.

\# events | Timing | Timing (removing the `@cachedList` cache)
--- | --- | ---
50k | .

Benchmark time (1 cold cache ): 3.7170820236206055
Benchmark time (2, warm cache): 0.2985079288482666
Benchmark time (3, warm cache): 0.28847789764404297
Benchmark time (4, odds      ): 0.1537461280822754
Benchmark time (5, odds      ): 0.14780497550964355
Benchmark time (6, evens     ): 0.1475691795349121
Benchmark time (7, evens     ): 0.14868617057800293

| .

Benchmark time (1 cold cache ): 0.3248419761657715
Benchmark time (2, warm cache): 0.32351016998291016
Benchmark time (3, warm cache): 0.3136260509490967
Benchmark time (4, odds      ): 0.15899014472961426
Benchmark time (5, odds      ): 0.15054106712341309
Benchmark time (6, evens     ): 0.15465688705444336
Benchmark time (7, evens     ): 0.1412408351898193

100k | .

Benchmark time (1 cold cache ): 8.10055136680603
Benchmark time (2, warm cache): 0.6121761798858643
Benchmark time (3, warm cache): 0.6093218326568604
Benchmark time (4, odds      ): 0.29950785636901855
Benchmark time (5, odds      ): 0.3049640655517578
Benchmark time (6, evens     ): 0.3025388717651367
Benchmark time (7, evens     ): 0.29833483695983887

| .

Benchmark time (1 cold cache ): 0.8466510772705078
Benchmark time (2, warm cache): 0.8022150993347168
Benchmark time (3, warm cache): 0.7888422012329102
Benchmark time (4, odds      ): 0.3941817283630371
Benchmark time (5, odds      ): 0.416118860244751
Benchmark time (6, evens     ): 0.42328405380249023
Benchmark time (7, evens     ): 0.3695280551910400

200k | .

Benchmark time (1 cold cache ): 19.106724977493286
Benchmark time (2, warm cache): 22.98161005973816
Benchmark time (3, warm cache): 23.126408100128174
Benchmark time (4, odds      ): 11.401129007339478
Benchmark time (5, odds      ): 0.6159579753875732
Benchmark time (6, evens     ): 12.087002992630005
Benchmark time (7, evens     ): 0.6241748332977295

| .

Benchmark time (1 cold cache ): 1.328582763671875
Benchmark time (2, warm cache): 1.279066801071167
Benchmark time (3, warm cache): 1.2781598567962646
Benchmark time (4, odds      ): 0.6520607471466064
Benchmark time (5, odds      ): 0.647273063659668
Benchmark time (6, evens     ): 0.6393017768859863
Benchmark time (7, evens     ): 0.6427278518676758