Why is the /paths endpoint on my custom Horizon deployment abnormally slow?

Question

I was wondering if anyone has an idea what could be causing our Horizon (0.17.6) /paths endpoint to be extremely slow.

A simple query takes 1m22s on our custom deployment. On public SDF Horizon the same query takes only 3.8s.

Custom deployment

[root@horizon ~]# time curl -s -o /dev/null "localhost:8000/paths?source_account=GCO2IP3MJNUOKS4PUDI4C7LGGMQDJGXG3COYX3WSB4HHNAHKYV5YL3VC&destination_account=GCO2IP3MJNUOKS4PUDI4C7LGGMQDJGXG3COYX3WSB4HHNAHKYV5YL3VC&destination_asset_type=native&destination_asset_code=XLM&destination_asset_issuer=&destination_amount=0.1"

real    1m21.546s

Public SDF

[root@horizon ~]# time curl -s -o /dev/null "https://horizon.stellar.org/paths?source_account=GCO2IP3MJNUOKS4PUDI4C7LGGMQDJGXG3COYX3WSB4HHNAHKYV5YL3VC&destination_account=GCO2IP3MJNUOKS4PUDI4C7LGGMQDJGXG3COYX3WSB4HHNAHKYV5YL3VC&destination_asset_type=native&destination_asset_code=XLM&destination_asset_issuer=&destination_amount=0.1"

real    0m3.814s

This is my my Horizon configuration

ExecStart=/usr/local/bin/horizon --stellar-core-url=http://stellar-core-server.com:11626 --port=8000 --per-hour-rate-limit=1000000 --max-db-connections=250 --sse-update-frequency=1 --connection-timeout=60 --log-level=info --log-file=/var/log/horizon.log --ingest=true --history-retention-count=0 --history-stale-threshold=0 --enable-asset-stats=false --max-path-length=3

As you can see I lowered --max-path-length to 3 already. With 2 it works very fast 0.332s but this isn't really desirable. With the default setting (4) it's taking more than three minutes (and at that point I canceled).

I noticed that there isn't any activity in Postgresql for most of the time while the endpoint is being invoked so maybe the problem is somewhere else.

Active SQL queries while endpoint is busy for 1m22s:

postgres=# SELECT datname,pid,query FROM pg_stat_activity ORDER BY pid ;
 datname  | pid  |                                           query
----------+------+-------------------------------------------------------------------------------------------
 horizon  | 2416 | SELECT * FROM gorp_migrations
 horizon  | 2430 | SELECT * FROM gorp_migrations
 horizon  | 2433 |                                                                                          +
          |      |                 SELECT base_fee, sequence                                                +
          |      |                 FROM history_ledgers                                                     +
          |      |                 WHERE sequence = (SELECT COALESCE(MAX(sequence), 0) FROM history_ledgers)+
          |      |
 horizon  | 2440 | SELECT COALESCE(MAX(sequence), 0) FROM history_ledgers
 horizon  | 2441 | SELECT COALESCE(MAX(sequence), 0) FROM history_ledgers
 horizon  | 2442 | SELECT COALESCE(MIN(sequence), 0) FROM history_ledgers
 postgres | 2644 | SELECT datname,pid,query FROM pg_stat_activity ORDER BY pid ;

None of these seem relevant to /paths.

I know that there are efforts to move the query into memory (https://github.com/stellar/go/issues/849), which should speed things up considerably but this might still take a while and I am at a loss about what is going on. Any hints appreciated. Thank you!