I just started working with databases and have a problem with queries taking very long.

My table has the following form

    CREATE TABLE table (column1 INT(10) AUTO_INCREMENT PRIMARY KEY, 
    column2 VARCHAR(255) NOT NULL, 
    column3 VARCHAR(255) NOT NULL, 
    column4 VARCHAR(255) NOT NULL, 
    column5 VARCHAR(255) NOT NULL, 
    column6 VARCHAR(255) NOT NULL);

    ALTER TABLE table ADD UNIQUE entry (column2, column3, column4, column5); 
    ALTER TABLE table CONVERT TO CHARACTER SET utf8 COLLATE utf8_unicode_ci;

I have inserted about 10 million rows.

Simple queries including a cartesian product like
    
    SELECT a.column1, b.column1
    FROM table AS a, table AS b
    WHERE a.column2 = ''
	AND NOT a.column3 = b.column3

take about five minutes before the results start showing.
A more complex one which includes ordering by multiple columns runs about half an hour before it eventually causes my system to freeze. There are no other concurrent database operations.

I'm running MySQL 5.6.25 on Ubuntu Vivid and didn't change any settings. My machine is a 6x3GHz Phenom II with 8 GB RAM.

Is there a problem with my table/query? Are there any default setting I should change?