In mathematics, semantics, and philosophy of language, the principle of compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them.
You're confused how sentences could have meaning without compositionality. This is probably because word order is the only way you've ever seen it done so you conflate compositionality with word order. Word order is not the only kind of rules you can have for combining constituent expressions. There are rules in free word order languages for combining them, but instead of using word order, they use case marking. It's entirely arbitrary to mark the relation between the words with word order. The only thing that matters is that there is some way it is marked. Furthermore, free word order only pertains to subject, verb, object order, not to the order of all words. There can be word order rules for other constructions of the sentence. For instance, the placement of an adjective might have a fixed word order in a "free word order" language.
Both word order and case marking tag words to show whether they are subject or object. Word order tags a word but it's an invisible tag, because the tag is its place in the sentence. Case marking tags the word by putting a sound on the word.
Free word order does not mean having no set syntactical structure. Basque does not violate the principle of compositionality.