If you have a look at the Action Reference, you’ll see all of the actions executed before pre_get_posts. The two you’ll probably want to investigate are parse_request and parse_query (yes, those are lacking in documentation).
The part you’re probably most interested in is parse_request, where rewrite rules are matched against the requested URI. You can see it in source here.
When a front end request happens, the file wp-blog-header.php is loaded, which calls wp(), which calls the main() method of the WP class, which calls the parse_request() method. At the bottom of that function, you’ll see where the parse_request action is executed.
EDIT
Also see this page in Codex for some more in-depth info: Query Overview