The guy explained that it has been "slowly getting worse" over many years, which is what you'd expect if there's table scans going on over a steadily growing volume of data.

IMHO, this is such as prevalent problem that it's the pandemic disease of SQL databases. They really should have indexing on by default for most columns, with the option of disabling unused indexes (perhaps even automatically).

Instead what happens is that 90-95% of all databases are 2-5 orders of magnitude slower than they ought to be, because developers are just unable to grasp these fundamental concepts. Developers haven't gotten any better at this over the last three decades. The tools have to get better to compensate instead.

PS: Almost all "no-SQL" databases are automatically or implicitly indexed. When people say that they're "much faster than SQL", I just assume that this is one of the biggest reasons. They're not inherently faster. Instead they're faster by default.