기본적으로 순서 유지 컬렉션(배열과 리스트), 범위range, 발생기generator, 반복자 또는 Stream.sorted를 호출해서 얻는 스트림은 순서를 유지한다. 순서 유지 스트림의 결과들은 원본 요소들의 순서로 쌓이고, 전체적으로 예측 가능하게 동작한다. 따라서 같은 연산들을 두 번 실행해도 완전히 같은 결과를 얻는다.
순서 때문에 병렬화를 이용할 수 없는 것은 아니다. 예를 들어, stream.map(fun)을 계산할 때 스트림은 n개 세그먼트로 분할되어 각각이 동시에 처리될 수 있다. 그런 다음 순서대로 재조립된다.
몇몇 연산은 순서에 대한 요구 사항을 버리면 더 효과적으로 병렬화될 수 있다. Stream.unordered 메서드를 호출함으로써 순서에는 관심이 없음을 나타낼 수 있다. 이로부터 이점을 얻을 수 있는 한 가지 연산은 Stream.distinct다. 순서 유지 스트림에서 distinct는 같은 요소 중 첫 번째를 보존한다. 하지만 이 동작은 병렬화를 방해한다(세그먼트를 처리 중인 스레드는 이전 세그먼트가 처리되기 전에는 어느 요소들을 버려야 하는지 알 수 없다). 유일한 요소라면 어느 것이든 보존해도 괜찮다면 (중복을 추적하기 위해 공유 집합을 사용해) 모든 세그먼트를 동시에 처리할 수 있다.
순서를 포기하면 limit 메서드를 빠르게 할 수 있다. 스트림에서 단지 n개 요소를 원할 뿐 어느 것을 얻는지는 상관하지 않는다면 다음과 같이 호출한다.
Stream<T> sample = stream.parallel().unordered().limit(n);