How do you approach refactoring an ugly procedure/query?

Yes, create unit tests. This is really the only way to ensure that a modified version meets the same requirements as the original.

To refactor the procedures look for any repeating patterns of code that could be extracted into separate procedures or nested procedures. If the procedures are still too long break parts of it into separate procedures that each complete one task. As you break off new procedures you should add unit tests for it.

Seven or eight levels of sub-selects does sound excessive, but you may find that some or even most of these are necessary to produce the data required. I would focus on the procedure initially and then tackle the SQL.

To do unit testing in Oracle, the foremost commercial product for testing is Quest's Code Tester. Oracle has Unit Testing built into it's free SQL Developer product. The question Unit testing for PL/SQL on StackOverflow has some other options or you can just write your own tests.

maybe you could find good advice in here:

• How to dive into an ugly database?

In the meantime, try to identify nasty-looking queries, like the ones that use where instead of joins.

As for my two cents here, I generally run it through a reformatter if I can, to get things to a traceable level, because anything that's 1500 lines unless already reformattered is going to be a little rough to trace by hand.

Then I try and put deeply nested selects into temp tables to reduce the nesting.

Then I try and figure out if it can be split into contiguous chunks of code, that can be extracted to run by themselves (think like making smaller functions out of a single long method of C#) and encapsulated to prevent too much information being presented in one long stretch.

Those are my basics that I toss at the problem before getting too far off topic