6

I was wondering if anyone would know the complexity of the Unix join command? I had assumed that it might be linear since both files need to be sorted.

Someone insisted to me that it was logarithmic which I doubt. Or perhaps it depends on the files and can be logarithmic (or N*log(N)) when one of the files is small and approach linear when both are large?

7

The BSD join implementation is quite simple to follow and seems to be linear with regards to the number of lines in the files. This has gone mostly unchanged in all BSD systems since at least BSD 4.4 Lite2. The snippet below comes from a current OpenBSD system, for comparison, this is a link to the BSD 4.4 Lite2 code originally committed by Keith Bostic in 1991 (replacing an earlier version of the utility):

/*
 * 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);
        }
}

I looked at the code for join in GNU coreutils, but GNU code has so much going on in it that I really only can guess, based on the comments in the code, that it more or less also implements the same sort of algorithm:

/* 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.  */

[...]

If you take the sorting into account, and assume an N*log(N) sorting algorithm, then the complete time complexity would be N*(1 + log(N)), or N*log(N) for large N values. That is, the JOIN operation is faster than the sorting.

You can't do better than linear for a JOIN operation, because you can't skip lines (unless you have a precalculated index of some description and don't include the indexing in the time complexity). The best case scenario is that none of the lines join, in which case you need to read all lines from one of the two files and compare these to first line of the other file. The worst case scenario is that all lines join, in which case you need to read both files and do pairwise comparisons between both sets of lines (a linear operation on sorted files). If the user requests to see unpaired lines, then you are forced to read both files completely.

If you manage to do worse than linear for the JOIN alone, then you're doing something wrong.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.