It might be more logical to use inheritance instead of aggregation:

class FullColumnDescription extends ColumnDescription

I started out that way, but since we don't have any cross-use cases between the two I think it's better to keep them separate. If we want to add inheritance later we can without breaking stuff. If we ever wanted to remove inheritance though we'd be out of luck. :)

What about passing them as an argument:

// somewhere in a customer's code
void takimgCareAboutTheSchema(Iterable< ColumnDescription > descriptions)

How can I pass FullColumnDescription to this ^^ routine?

Not sure that we need to pre-cache keys stuff, since not all users need to use it.

IMO, it is better to introduce utilitarian assessors which will return newly created collections each time. As a result caching will be performed on the user side, if the user really needs this.

I lean the other way, we can easily create it while in the constructor, and then we have an entire immutable object once we're done. If we do it later then we're saving 8? object references, and introducing more code and possible race conditions later.

Since the whole instance is immutable from the user perspective, there shouldn't be any race conditions. On the other hand, as we are not expecting that user will execute describe table each second, I think that we can leave this as is.