A implementação do BSD join é bastante simples de seguir e parece ser linear em relação ao número de linhas nos arquivos. Isso praticamente não mudou em todos os sistemas BSD desde pelo menos o BSD 4.4 Lite2. O trecho abaixo vem do sistema atual do OpenBSD , para comparação, é um link para o código BSD 4.4 Lite2 originalmente enviado por Keith Bostic em 1991 (substituindo uma versão anterior do utilitário):
/*
* We try to let the files have the same field value, advancing
* whoever falls behind and always advancing the file(s) we output
* from.
*/
while (F1->setcnt && F2->setcnt) {
cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
if (cval == 0) {
/* Oh joy, oh rapture, oh beauty divine! */
if (joinout)
joinlines(F1, F2);
slurp(F1);
slurp(F2);
}
else {
if (F1->unpair
&& (cval < 0 || F2->set->cfieldc == F2->setusedc -1)) {
joinlines(F1, NULL);
slurp(F1);
}
else if (cval < 0)
/* File 1 takes the lead... */
slurp(F1);
if (F2->unpair
&& (cval > 0 || F1->set->cfieldc == F1->setusedc -1)) {
joinlines(F2, NULL);
slurp(F2);
}
else if (cval > 0)
/* File 2 takes the lead... */
slurp(F2);
}
}
Eu olhei para o código para join em GNU coreutils , mas o código GNU tem tanta coisa acontecendo que eu realmente só posso adivinhar , baseado nos comentários no código, que ele mais ou menos também implementa o mesmo tipo de algoritmo:
/* Keep reading lines from file1 as long as they continue to
match the current line from file2. */
[...]
/* Keep reading lines from file2 as long as they continue to
match the current line from file1. */
[...]
Se você considerar a classificação e assumir um algoritmo de classificação N*log(N) , a complexidade completa do tempo será N*(1 + log(N)) , ou N*log(N) para grandes valores N . Ou seja, a operação JOIN é mais rápida que a classificação.
Você não pode fazer melhor do que linear para uma operação JOIN, porque você não pode pular linhas (a menos que você tenha um índice pré-calculado de alguma descrição e não inclua a indexação na complexidade do tempo). O melhor cenário possível é que nenhuma das linhas se junte, nesse caso você precisa ler todas as linhas de um dos dois arquivos e compará-las com a primeira linha do outro arquivo. A pior das hipóteses é que todas as linhas se juntem, caso em que você precisa ler os dois arquivos e fazer comparações de pares entre os dois conjuntos de linhas (uma operação linear em arquivos classificados). Se o usuário solicitar ver linhas não pareadas, você será forçado a ler os dois arquivos completamente.
Se você conseguir fazer algo pior do que linear apenas para o JOIN, então está fazendo algo errado.