次のステップでは宣言的なクエリは論理的クエリ計画に変換される。クエリ計画は有向グラフでありノードが演算子でエッジが処理フローを表現する。クエリ計画にある個々の演算子はフィルタリングや集計などの特定の処理に関する意味をカプセル化する。DSMSではリレーショナルデータストリームの処理を行い、演算子は関係代数の処理そのものであるか似たものであり、選択、射影、結合、セットなどの処理がある。この演算子の概念はDSMSによる処理の柔軟性と網羅性を実現する。 
クエリの最適化.
さらに、DBMSのようなコストベースの最適化技術もあり、同等のいくつかのクエリ計画の中からコストが最低のものが選択される。一つの例は二つの連続した結合演算子の順序を選択するものである。DBMSではこの選択は対象となるデータベースの統計情報に基づいて決定される。しかし、データストリームのデータは前もって知ることができないため、DBMSのような統計は存在しない。だが、データストリームを観察することによって何らかの統計を得ることはできる。この統計を使用してその後でのクエリを最適化することができる。したがってDSMSには実行されているクエリ計画を新しいものに置き換える、計画移行戦略が必要である。
クエリの変換.
論理演算子は処理の意味にだけかかわり、何のアルゴリズムも含んでいないので、論理クエリ計画は対応する実行形式に変換されなければならない。これを物理クエリ計画と言う。論理演算子と物理演算子を区別することにより、一つの論理演算子に複数の実装を行うことができる。例えば結合では入れ子ループ結合やソートマージ結合などのアルゴリズムを実装することができる。これらのアルゴリズムは使用するストリームと処理モデルに強く依存する。最後に、クエリは物理クエリ計画として使用できるようになる。
クエリの実行.