Es necesario obtener todos los datos, solo necesitas un poco de lógica para evitar duplicados; ejemplo:
Código:
$provincia = '';
$categoria = '';
while($row = /* lectura de consulta */) {
if ($provincia != $row['provincia']) {
$provincia = $row['provincia'];
$categoria = '';
echo $provincia;
}
if($categoria != $row['categoria']) {
$categoria = $row['categoria'];
echo $categoria;
}
// Aquí muestras el resto de datos
}
Solo falta que apliques html/css necesarios.