In terms of computational complexity, this is of course extravagantly exponential, and the length of the human genome, about 30 megabases, makes it more expensive still. It's not just a simple comparison, either. There are many regions of the genome which will be identical or nearly so between individuals, because they code for the same things. But there's no guarantee that they'll be in the same place across two individuals' genomes, both because DNA doesn't exactly work that way, and because DNA sequencing doesn't either. So, before you can perform the comparison at the core of GWAS, you have to find and line up these common subsequences. This is called "local sequence alignment"; it is in itself quadratic, and you have to do it for every pair of genomes. So the total process, counting all that and the various ancillaries involved, is (n^2)^n plus a bit - a complexity class which, to my knowledge, no computer scientist has thus far dared to name, or not in printable terms at least.
Given this enormous requirement for both CPU and storage, it should come as no surprise that the first successful GWAS [4] was published only as recently as 2002, and that it was only about ten years ago that the technique really became feasible to deploy on a wide scale. Even in so short a time, though, it's proven an almost fantastically fecund field of study; to call it an almost fundamental revolution in the study of biological inheritance really isn't too strong a description, and I'm really looking forward to seeing what researchers develop with it over the course of the next couple of decades.
It's reasonable to wonder, specifically, why this technique should be able to tell us so much. Some traits - whether beneficial, harmful, or neutral - are heritable at the genetic level, i.e., in entire genes. These are currently described as "Mendelian traits" or, when not innocuous, "Mendelian disorders". Because those require only sufficient resolution to identify the presence or absence of specific genes, they were identifiable prior to the wide availability of GWAS. The variations identified by GWAS, by contrast, can be and often are as small as a difference in a single base (i.e. A instead of G, C instead of T), hence the frequently encountered term "single-nucleotide polymorphism" or SNP (pronounced 'snip'); NCBI has a database [2] of about three-quarters of a billion known SNPs, and about a hundred thousand of those [3] are considered likely to have clinical significance - that is, they're significantly more likely to be found in the genome of people who have, or go on to develop, some illness, to the point where awareness of their presence may usefully inform treatment of a patient who has them.
It's important to note that these aren't genetic variations, but genomic; that is, while SNPs can and frequently do occur within genes, it's the study of the genome as a whole in which they are identified. They also aren't mutations; where a mutation is uncommon and generally has an observable effect on the phenotype of the organism in which it appears, SNPs are highly common and typically don't have any direct effect on the phenotype. That's why, of the about 760 million SNPs in the NCBI database, only about a hundred thousand are individually listed as clinically significant; typically it's with a combination of SNPs, rather than a single one, where a correlation is found.
This relatively weak signal is why such a complex, statistical method is required to identify these variations in the first place: mostly they don't affect the individual whose genome displays them, and even when they do, it's often only in a very subtle way, such as elevating or reducing risk of some disorder - something I actually talked about here fairly recently [6], discussing the results of a GWAS investigating possible associations with SIDS risk - in the event, the study found that there are some genomic associations with SIDS, but that they represent so slight an adjustment in actual risk that it's not reasonably possible even to evaluate that risk delta in the case of an individual infant.
This is solidly typical of the sort of results you find in a given GWAS paper, and it militates strongly against considering any individual paper as dispositive of much of anything in advance of close reading. For example, I recently addressed a concern here over whether a sizable (~80k) GWAS examining associations with sexuality, specifically with likelihood of being either heterosexual or not boring, could potentially lend itself to selective abortion or some other sort of intervention - shades of the old "gay gene" debate from the 90s. I was happy to be able to explain that, not only can the GWAS results not be used that way, the GWAS results pretty conclusively disprove that anything even exists in the human genome which could be used that way. But it's easy to understand how someone would be concerned! I was too, before I read the paper; while it isn't likely that such a targetable complex of variations might exist, neither is it impossible. But if a GWAS of that size failed to find it, that's because it isn't there to be found.
Another common genre is studies in which SNPs are found to cause variation in the way already known genes are expressed - this isn't really surprising, although it may sound so; the interactions between DNA and the transcriptase which produces RNA from it, and between RNA and the ribosome which uses the encoded information to build proteins, are physical, and the physical structure of these nucleic acid molecules is strongly dependent on the bases in which the information they carry is encoded. These structures can, and do, affect the function of the proteins that interact with these molecules. The eye color paper that we're talking about here [1] describes such a result; to pick a specific example, it identifies a SNP in a non-coding region of DNA, adjacent to the genes which have the strongest effect on eye color, whose presence or absence influences the likelihood with which those genes are expressed (ie, affect the organism's phenotype), and thus influences the probability distribution of the eye colors which result. And, more broadly, this paper clarifies much that was previously unknown with regard to how eye colors, other than the already fairly well understood blue and brown, occur.
As it happens, I have hazel eyes, so this paper is pretty interesting to me! But in any case, I hope I've helped clarify some of the background for you, with regard to why and how papers like this come about, and how it can be that something as seemingly well-understood as the genomic origins of human eye color can still be open to so broad a clarification as this paper provides.
(I'm not a researcher myself; I just have friends and former colleagues in the field, and spent about a year working as a staff engineer in a genomics institute. Most of what I've just described, I picked up while I was there, and while I've done the best I could, my understanding may be both imprecise and outdated in ways which would dismay my erstwhile collaborators. If someone with more current or more accurate knowledge should happen by, I hope they'll take the time to set me straight wherever I need it!)
(Oh, also, it's not wise to put too much faith in "popularizers of science", whether that be Malcolm Gladwell or just the PR department of some university or other. They always screw it up. For example, "50 new genes for eye color" is just a straight-up lie - the paper neither identified nor sought to identify any new genes at all. I concede that a more detailed and accurate explanation, such as the one I've given, both requires considerably more effort to write, and considerably more effort to read; no doubt it would be less likely to be read and understood even if it appeared in place of the junk that's linked in this HN submission. What I don't understand is, if they're not going to try to actually educate anyone but just put out a bunch of nonsense that's of no use to anyone, why they even bother at all.)
(Well, that's a bit of a lie, too. They do it because they believe it will help get them grants. I've never understood how that is supposed to work; at the institute where I worked, grants happened because of grant writers, and the grant writers there spent as far as I know none of their highly valuable time on misleading laypeople with glib pop sci crap. So maybe I'm not so sure after all.)
[1] https://advances.sciencemag.org/content/7/11/eabd1239
[2] https://www.ncbi.nlm.nih.gov/snp/
[3] https://www.ncbi.nlm.nih.gov/snp/?term=%22pathogenic%22%5BCl...
[4] https://pubmed.ncbi.nlm.nih.gov/12426569/