How to find all posts without category and assign the “Uncategorized”?

Hi is there anybody who can help me how to find all posts without category and assign the “Uncategorized”? I have more than 7000 posts and 300 of them are without category, how I could assing one?

And another question, how I can assign category to all posts (except bulk edit which doesnt work well with this amount of posts)?

The current accepted takes posts out of range too. Since it LEFT JOIN on wp_term_relationships without knowing that the first join might be a Category or a Post_tag, it gives false-positive, hence affecting posts that might not be without category.

Inspired from the current accepted answer, change the “37” for your actual wanted category:

INSERT IGNORE INTO wp_term_relationships
(object_id, term_taxonomy_id, term_order)
SELECT p.ID as `object_id`, 37 as `term_taxonomy_id`, 0 as `term_order`
    FROM wp_posts p 
    WHERE p.post_type="post" 
        AND p.post_status="publish"
        AND NOT EXISTS
        (
        SELECT  *
        FROM    wp_term_relationships rel
        JOIN    wp_term_taxonomy tax
        ON      tax.term_taxonomy_id = rel.term_taxonomy_id 
                AND tax.taxonomy = 'category' 
        JOIN    wp_terms term
        ON      term.term_id = tax.term_id
        WHERE   p.ID = rel.object_id 
        )