1. A method comprising: generating one or more individual sets of statistics for each of one or more intermediate relations of a workflow, wherein said one or more intermediate relations comprise results of one or more stages of any plan of the workflow, and wherein each individual set of statistics computes cardinality of the corresponding intermediate relation; determining a global set of statistics for the workflow, wherein said global set of statistics comprises at least one of the one or more individual sets of statistics for each of the one or more intermediate relations; instrumenting a given plan of the workflow to collect, the global set of statistics during execution; executing the given plan to collect the global set of statistics; and determining a plan of the workflow with the lowest cost by comparing the cost of multiple plans of the workflow, wherein the cost of each plan is derived from the global set of statistics; wherein at least one of the steps is carried out by a computer device.