I have this table on Microsoft SQL Server 2012:

```
CREATE TABLE [dbo].[Addresses_line_format]
(
    address_id UNIQUEIDENTIFIER NOT NULL
        CONSTRAINT pk_addresses_line_format PRIMARY KEY NONCLUSTERED,

    country_id UNIQUEIDENTIFIER NOT NULL
        CONSTRAINT fk_address_single_line_country FOREIGN KEY REFERENCES Countries (country_id)
            ON UPDATE NO ACTION
            ON DELETE NO ACTION,

    address_line NVARCHAR(255) NOT NULL,
    district_line NVARCHAR(255) NOT NULL
)

```

With 3.362.817 records in it.

Our application consumes messages from a queue, with 10 concurrent consumers. Each consumer inserts a line into this table, using the following statement:

```
INSERT [dbo].[Addresses_line_format] ([address_id], [country_id], [address_line], [district_line])
VALUES (@0, @1, @2, @3)

```

Looking at statistics, the average elapsed time for this query is 16 seconds, which is obviously way too much.

I'm wondering if this is because of how heap tables are handling inserts like described [here](http://sqlblog.com/blogs/tibor_karaszi/archive/2008/08/14/are-inserts-quicker-to-heap-or-clustered-tables.aspx), or do you have any ideas what is causing this?

I tried changing the PK to be clustered, but without any noticeable performance improvements.

Queries against the table are always performed using the following:

```
SELECT country_id, address_line, district_line
FROM Addresses_line_format
WHERE address_id = @1

```