In case of million inserts or bulk load with constraints on, these few cycles spent in ordering the constraints might be problematic, unless the ordering happens only once for a series of inserts.
As far as I can see this sort only occurs when a new relation is loaded into the relcache. Relations are cached in the relcache when they're accessed for the first time in each backend, and the cache will be invalidated when the current backend or another backend perform DDL on that relation.
Without relcache we'd need to lookup the system catalogs for just about every SQL statement... This would be very slow indeed!
