  The o-minimal structure generated by the restricted Pfaffian functions, known
as restricted sub-Pfaffian sets, admits a natural measure of complexity in
terms of a format $\mathcal{F}$, recording information like the number of
variables and quantifiers involved in the definition of the set, and a degree
$D$ recording the degrees of the equations involved. Khovanskii and later
Gabrielov and Vorobjov have established many effective estimates for the
geometric complexity of sub-Pfaffian sets in terms of these parameters. It is
often important in applications that these estimates are polynomial in $D$.
  Despite much research done in this area, it is still not known whether cell
decomposition, the foundational operation of o-minimal geometry, preserves
polynomial dependence on $D$. We slightly modify the usual notions of format
and degree and prove that with these revised notions this does in fact hold. As
one consequence we also obtain the first polynomial (in $D$) upper bounds for
the sum of Betti numbers of sets defined using quantified formulas in the
restricted sub-Pfaffian structure.
