Mysql performance for a nullable unique id column in a large table that references a record in another table

Having a VARCHAR as a part of an index would be cumbersome to manage although doable.

I would design the tables as follows

CREATE TABLE folderkeys
(
    id INT NOT NULL AUTO_INCREMENT,
    userid INT NOT NULL,
    foldername VARCHAR(260),
    PRIMARY KEY (id),
    UNIQUE KEY (userid,foldername)
) ENGINE=MyISAM;
CREATE TABLE datatable
(
    id INT NOT NULL AUTO_INCREMENT,
    folderkey_id INT NOT NULL,
    filename VARCHAR(1024),
    PRIMARY KEY (id),
    KEY (folderkey_id)
) ENGINE=MyISAM;

This will make the datatables indexes as character-compacted as possible

This will make it as easy doing queries like

INSERT IGNORE INTO folderkeys (userid,foldername) VALUES (1,'first');
SELECT id INTO @fldrkey FROM folderkeys WHERE userid=1 AND foldername='first';
INSERT INTO datatable (folderkey_id,filename) VALUES (@fldrkey,'...');

If you want the filename from userid 1 foldername 'first', you would do queries like this

SET @GivenUserID = 1;
SET @GivenFolder = 'first';
SELECT A.userid,A.foldername,B.filename FROM
(SELECT id FROM folderkeys WHERE userid = @GivenUserID AND foldername=@GivenFolder) A
INNER JOIN datatable B ON A.id = B.folderkey_id;

If you want filenames from all folders for userid 27, you would do queries like this

SET @GivenUserID = 27;
SELECT A.userid,A.foldername,B.filename FROM
(SELECT id FROM folderkeys WHERE userid = @GivenUserID) A
INNER JOIN datatable B ON A.id = B.folderkey_id;

Give it a Try !!!

I would normally recommend using InnoDB. Since you have lots of BLOB data, I'd rather not spend time trying to tune your log buffer and log files sizes. I would go with MyISAM for now.

BTW I gave you the tables with Option A in mind

Since the alias column is nullable, if you add a unique constraint on the composite (last_name, first_name, birth_date, alias), there will still be duplicates allowed, with the same values in the first 3 columns and NULL in the alias. The constraint is skipped / accepted when at least one value is null. MySQL documentation on CREATE TABLE is not very clear but you can test the behaviour:

• A UNIQUE index creates a constraint such that all values in the index must be distinct. An error occurs if you try to add a new row with a key value that matches an existing row. For all engines, a UNIQUE index permits multiple NULL values for columns that can contain NULL.

What you could do is to define the alias as not null and add a default value, (say 'NONE' or 'DEFAULT' or the empty string ''). You (or the user) will not have to provide that value, it will be automatically saved in all rows. Once someone tries to add a new row with same last name, first name and birth date as an existing row, the unique constraint will forbid it. I guess you could add some procedure at that point, that asks for a different value for the alias and adds the new row with it.