Samsung Galaxy S6 — Phone dialer lag

One of the great features of Android is that you don't need to search and select a specific contact to dial, but that you can simply start typing on the phone keypad the name of the contact that you're looking for. The dialer would then suggest contacts that match numbers /letters that you typed.

In my case I find that the suggested contacts takes very long to appear - up to a minute.

I've cleared both the contacts app cache as well as the system cache with no luck

Any help would be appreciated