We have a large amount of users (e.g. a couple of millions) and we would like to start searching only after the user types in 2 characters or more.
What visual indication can be provided to users in such cases.
At the risk of sounding obvious I would recommend using a text hint e.g. "start typing to see matches" and if you have a minimum character count before beginning matches then provide feedback as soon as user starts typing e.g. "enter more characters to see matches"
None at all. You don't need visual indication in this case.
The "search as you type" is always optional feature. The missing of suggestion window is always perceived as "the system can't suggest anything" and there is no need for some special type of indication.
If the user wants to search for shorter words that is not suggested, he only have to press ENTER or click on Search button and the search will be performed, regardless of the suggested words.
It's as simple as placing ... within the field. This will indicate to the user that there is a min need. You could use JS if the user doesn't enter enough. A simple alert could fade in indicating that they needed to enter a min of X characters. Once the user did it could go away. Or, go away and allow the user to enter.