Graph decomposition methods are at the core of algorithmic graph theory. Tree-width and clique-width are central notions in the theory of graph decomposition, and it has been shown that a multitude of problems enjoy fast algorithms when the input is restricted to graphs whose tree-width or clique-width is small. Most such algorithms are based on dynamic programming over the decomposition, and up until just a few years ago there were basically no improvements over the ``naive'' dynamic programming algorithms for graphs of bounded clique-width or tree-width. Over the recent years we have seen a number of results showing that many of the naive dynamic programming algorithms for graphs of bounded tree-width and clique-width are optimal, under reasonable complexity theory assumptions. These lower bound results were subsequently complemented by surprising and elegant improvements over the ``naive'' dynamic programs. In this talk i will survey the state of the art of lower- and upper-bounds on the running time of algorithms on decomposable graphs.