Si claro...
non seleciones todos los records en la primera query, porque m parece que solo utilizas el id, o sea
Código PHP:
$where = array();
if($id_categoria) $where[] = "id_categoria=$id_categoria";
if($id_marca) $where[] = "id_marca=$id_marca";
$where_string = (count($where)>0)? "WHERE ".implode(' AND ', $where):"";
$conn = db_connect();
$query_r = " SELECT id_relacion FROM relaciones $where";
$result_r = @$conn->query($query_r);
$num_rows_r = $result_r->num_rows;
if($num_rows_r) {
// ...
$results = $result_r->fetch_assoc(); // aqui tendrias que tener todos los id_relaciones selecionados con la primera query
$query = "SELECT * FROM productos
WHERE MATCH (nombre_producto, texto_producto)
AGAINST ('$frase' IN BOOLEAN MODE)
AND id_relacion IN (".implode(",",$results).")
ORDER BY $orden ASC";
$final_result = mysql_query($query);
/*
* sigue....
*/
}