Background: By entering the era of mega-scale genomics, we are facing many computational issues with standard genomic evaluation models due to their dense data structure and cubic computational complexity. Several scalable approaches have have been proposed to address this challenge, like the Algorithm for Proven and Young (APY). In APY, genotyped animals are partitioned into core and non-core subsets, which induces a sparser inverse of genomic relationship matrix. The partitioning into subsets is often done at random. While APY is a good approximation of the full model, the random partitioning can make results unstable, possibly affecting accuracy or even reranking animals. Here we present a stable optimisation of the core subset by choosing animals with the most informative genotype data. Methods: We derived a novel algorithm for optimising the core subset based on the conditional genomic relationship matrix or the conditional SNP genotype matrix. We compared accuracy of genomic predictions with different core subsets on simulated and real pig data. The core subsets were constructed (1) at random, (2) based on the diagonal of genomic relationship matrix, (3) at random with weights from (2), or (4) based on the novel conditional algorithm. To understand the different core subset constructions, we have visualised population structure of genotyped animals with the linear Principal Component Analysis and the non-linear Uniform Manifold Approximation and Projection. Results: All core subset constructions performed equally well when the number of core animals captured most of variation in genomic relationships, both in simulated and real data. When the number of core animals was not optimal, there was substantial variability in results with the random construction and no variability with the conditional construction. Visualisation of population structure and chosen core animals showed that the conditional construction spreads core animals across the whole domain of genotyped animals in a repeatable manner. Conclusions: Our results confirm that the size of the core subset in APY is critical. The results further show that the core subset can be optimised with the conditional algorithm that achieves a good and repeatable spread of core animals across the domain of genotyped animals.