The unordered nature of a source or the explicit releasing of the order contract via unordered() may affect all subsequent pipeline stages unless they introduce an order which can only happen with a sorted operation.
For stateless intermediate operations like filter and map, there is no difference anyway, but operations like skip, limit and distinct may exhibit a different behavior depending on whether the previous stream state was ordered or unordered. This answer shows an example of how distinct can be affected by a previous unordered().
Note that in principle, sorted, while introducing an order, may depend on the ordered state of previous stage, as it may use an unstable sort algorithm if the previous stream was unordered.
This answer provides a way to print the characteristics of a stream and evaluate how they change due to appending another operation.
When you chain a terminal operation, both, an unordered nature of the terminal operation itself or an unordered state of the last stage before the terminal operation may be sufficient to select an algorithm for the terminal operation that doesn’t try to preserve the order.
In principle, the unordered nature of the terminal operation could be used to affect previous stages, but since stateless intermediate operations are not affected anyway and skip, limit, distinct have to obey a previous ordered state, if present, the only operation that could be affected, is sorted that becomes obsolete if the subsequent operations don’t care about the order anyway.
In the current implementation, since Java 8 update 60, the unordered nature of a terminal operation does not affect the behavior of previous stages. This change was made, as in previous implementations, it wrongly affected skip and limit. Loosing the opportunity to elide obsolete sorting steps was not considered a problem, as chaining sort with unordered subsequent operations, is a corner case. See this answer, including the comments, if you want to know more about the related discussion.
So for
list.stream() // List.stream() returns an ordered stream
.unordered() // releases order contract
.distinct() // for equal elements, it may pick an arbitrary one
.sorted() // re-introduces an order
.skip(1) // will skip the minimum element due to the order
.forEach(System.out::println); // may print the remaining elements in arbitrary order
there is not a single ordered or unordered behavior for the stream pipeline.
In contrast, with
hashSet.stream() // HashSet.stream() has no order (unless being a LinkedHashSet)
.filter(Objects::nonNull) // not affected by order
.distinct() // may use unorderedness, but has no effect anyway, as already distinct
.skip(1) // may skip an arbitrary element
.forEachOrdered(System.out::println); // would respect order if there was one
the entire pipeline runs unordered, just because the source is unordered. With an ordered source, it would be entirely ordered.
So the answer to “is the evaluation of the entire stream pipeline ORDER characteristic done by going through the characteristics of source, intermediate operations and terminal operation even before the start of the execution?” is, yes, this is done right before starting the actual processing, by selecting the appropriate algorithm for the pipeline stages, when there is a choice, but this process does not necessarily result in a single characteristic for the entire pipeline.
