Is the complement system a part of innate or adaptive immunity
Yes, the complement system is part of the innate immune system. It can be activated by the:


classical pathway (activated through bound IgM and IgG molecules but
also by DNA, collagen (both are usually not available freely outside
of cells) and c-reactive protein)
lectin pathway (activation by binding of mannose through the mannose
binding lectin on the cell surface)
alternative pathway (activation by the constant hydrolysis of the
complement component 3 (or C3) in an antibody independent way)


My guess here would be, that the classical activation via antibodies is evolutionary younger than the other two possibilities which act more directly on bacteria and do not depend on the availability of specific (at least to some degree) antibodies. The Wikipedia article on the complement system is pretty extensive.