Consideration for a little bit heavy database Environment information

OS : Windows Server 2012 R2 ( 64bit )
RAM : 16.00GB
CPU : Intel(R) Xeon(R) CPU E5-2609 @ 2.40GHz
SQL : Windows SQL Server 2012 Standard

Brief Database Data Information

Among more than 10 tables, one of them has varbinary(max) type column
The table has more than 1m records and each column has thumbnail data that takes up about 20k

Brief Table Spec

Table name : RegisteredThumbnail
Column name : UserId, ThumbData, Created, Updated
Column type : int, varbinarymax, datetime, datetime
Used space info : row : 1,034,300 | reserved : 34,092,160 KB | data : 34,054,872 KB | index_size : 31040 KB | unused : 6248 KB

Query
SELECT * FROM RegisteredThumbnail WHERE UserId = 512315

This query takes about 6:45 minutes to fetch the expected row.
To overcome this, is indexing the only option for me?
Changing the way image data is stored by replacing the binary data to image url as a string data will help a lot?
Since this is a currently operating system, changing the column is not a good idea though.
Any ideas would be greatly appreciated.
No indexes have been configured yet.
This table should have a clustered index on UserId. If there is no more than one thumbnail per user, then the clustered index can be the primary key.

Since you say you have a currently-running system on SQLServer 2012 standard edition, online index builds are not possible. You could wait for a low-activity period to create the index, or create a new table, migrate the data into it, then switch to using the new table.

The table should ideally look like this:

CREATE TABLE RegisteredThumbnail
(
    UserId       INT            NOT NULL,
    ThumbData    VARBINARY(MAX) NOT NULL,
    Created      DATETIME2(7)   NOT NULL,
    Updated      DATETIME2(7)   NULL,

    CONSTRAINT PK_RegisteredThumbnail PRIMARY KEY CLUSTERED (UserId ASC)
)


Since you cannot recreate the table, this is the index you need to create:

CREATE INDEX IX_RegisteredThumbnail_UserId
ON RegisteredThumbnail(UserID ASC)


As you're on 2012 Standard, this will be an "offline" operation - it'll block activity on this table while the index is being built. Given it's only a million rows, it should not take too long to build, however it does have to scan the table in order to do it, so you'll be limited by how fast it can read that data.