Me sobrecarga el server

[matanga]

Dejando de lado el modelo de datos (no creo que sea lo mejor), lo que puedes hacer es:

1. Agregar un id numerico a la tabla nombres y a la tabla apellidos, de manera que queden

nombres (id number, nombre varchar)
apellidos (id number, apellido varchar)

2. Crear un indice unique sobre los campos id's de las dos tablas.
3. Crear dos numeros random, uno para el nombre y otro para el apellido.
4. Utilizar la consulta

select nombres.nombre, apellidos.apellido
from nombres, apellidos
where nombres.id = numero_random_1
and apellidos.id = numero_random_2

Esta consulta siempre entra por los indices, asi que no te afecta la cantidad de registros de las tablas.

Nota1, En caso que quieras 10 regitros, debes crear 10 numeros random y utiliar la condición nombre.id in (n1,n2,...,n10)
Nota2, El numero random debe ser menor que el numero maximo de los id's, asi te aseguras que siempre encuentre un registro.

Saludos