Major performance degradation with joins in 15.8 or 15.7?

Hello! I have a database installation that goes back about 10 years. It's using a hardware RAID consisting of enterprise-caliber spinning drives. I upgraded the installation to PostgreSQL 15.8 a couple months ago.

Sometime after that, it was noticed that one of our application's queries suffered major performance degradation. This query "suddenly" went from taking 40-50 milliseconds to ~9 seconds, approximately 180-200 times longer. Vacuuming and analyzing the table didn't help.

The good news is that, after some research and experimentation, I was able to fix this performance degradation by setting random_page_cost = 2.0. We've always used the default values for seq_page_cost and random_page_cost (1.0 and 4.0, respectively, I think?). A lot of the advice I found online suggested these *_page_cost settings are too high?

The table in question has ~350,000 rows and only 5 text columns. It might have increased in size by about a thousand rows in the past couple of months, but the table has not grown in size significantly.

Did upgrading PostgreSQL to 15.8 cause this performance degradation? Did the page costs calculation change in 15.8 (or 15.7)? The PostgreSQL version is the only thing that has appreciably changed with this database this whole year.

Or do you think the size of the table just incrementally reached some threshold that resulted in the optimizer changing its plan based on the page costs?

I was able to simplify the query in my testing down to something like this:

select * from atablename a inner join btablename b on a.somekey = b.somekey and b.otherparam='value' where b.otherparam2='other value';

All of the columns are text fields and indexed. Unfortunately, I don't have the "EXPLAIN (ANALYZE, BUFFERS)" output from before I changed the random_page_cost setting. It's no longer in my scollback buffer.

Any theories or suggestions appreciated.

Thanks,
Ed