Stream processing has become increasingly important with emergence of stream applications such as audio/video surveillance, stock price tracing, and sensor data analysis. A challenging problem is to provide optimal component composition in a distributed stream processing environment. The goal of optimal component composition is to achieve load balancing subject to multiple function, resource, and quality-of-service (QoS) constraints while composing stream applications. In this paper, we present an adaptive composition probing (ACP) approach to the problem. Different from previous work, ACP provides a new hybrid approach that combines distributed composition probing with coarse-grain global state management. Guided by the coarse-grain global state information, ACP selectively probes a subset of candidate components to discover an approximately optimal component composition. Further, ACP is self-tuning, which can adaptively adjust the number of probes to maintain a specified composition performance target (i.e., composition success rate) in a dynamic stream environment. While the optimal component composition problem is NP-hard, our ACP approach provides an adaptive polynomial approximation solution. We have conducted extensive simulation experiments to show the efficiency, scalability, and adaptability of the ACP approach by comparing with other alternative solutions.