Hello,
I have experience with PostgreSQL, PostGIS, Python and geocoding data.
Is your data based on GNAF? I have developed an API based on that data some time ago.
If your autocomplete form can be designed in a "top-down" fashion (select state, then locality, then street and ultimately number) I think we can get quite fast results (a few milliseconds). If you need a single input for the whole address then it gets quite complicated due to the large number of records which can prove difficult even if using indexes like pg_trgm.
Best wishes,
iticus