I think Ciprian Popescu his solution is incomplete because it does not remove custom attributes that are added to products. Such attributes are stored in two places in the database:
1. As an attribute of the product, stored in wp_postmeta under the key '_produce_attributes'. Ciprian Popescu his solutions will remove these.
2. As terms in taxonomies that are linked to your products. Ciprian Popescu his solution will not remove these occurrences but only the links with the taxonomies which are stored in wp_term_relationships. To remove the taxonomies (which store the name of the attribute) and the terms (which store the values) as well, you can use the following query:
DELETE relations.*, taxes.*, terms.*
FROM wp_term_relationships AS relations
INNER JOIN wp_term_taxonomy AS taxes
INNER JOIN wp_terms AS terms
WHERE object_id IN (SELECT ID FROM wp_posts WHERE post_type='product')
The idea is that you join the table that contains the relationships between posts and taxonomies (wp_term_relationships) with the table containing the taxonomies (wp_term_taxonomy). Then you join this with the table that contains the terms (wp_terms). This results in all terms and taxonomies that are used by posts. The WHERE clause makes sure that you will only remove the taxonomies and terms of products. Beware that this query might also remove taxonomies and terms that are used by pages that are not products as well, so if you want to filter this out you need an additional query.