Execution of a restartable sub-tree of a query execution plan comprises determining whether use of parallel processes is a preferred or optimal mode of executing the sub-tree. The determination is based, at least in part, on how long it takes to restart the sub-tree using two or more parallel processes and/or how long it takes to probe the sub-tree, i.e., to fetch a row that meets one or more conditions or correlations associated with the sub-query, using the two or more parallel processes. Thus, a dynamic computational cost-based operation is described, which determines at query runtime whether to execute the restartable sub-tree using a single server process or multiple parallel server processes.