Dovrebbe essere sufficiente fare un like:

codice:
$query = "SELECT * FROM table  WHERE Nick like 'a%' ORDER BY `Nick` ASC";