How can I find out which countries the route passes through?

Question

Cartography

Now we use the Google Maps API to build routes.
Everything suits, except for one moment ...

We need to find out which countries the route passes through, Google does not give such information.
We tried using PostGIS to compare the route line with the polygons of all countries, but unfortunately such a request takes a very long time, about 20 minutes...

Do you know any services that will return the countries through which the route passes? Or perhaps there are other solutions.

(the route may have several stops)