The query has been canceled because the estimated cost of this query exceeds the ....

I am getting this error while excuting my stored procedure from asp.net.
There are no any complex code. This is a very simple procedure to import XML.

Msg 8649, Level 17, State 1, Procedure prc_MailingList_INSERT_XML, Line 13
The query has been canceled because the estimated cost of this query (3258) exceeds the configured threshold of 2500. Contact the system administrator.

Code which is causing the error:

INSERT INTO @TempTable(FullName, FirstName, LastName, Email, DateOfBirth, CountryCode)
SELECT FullName = T.Item.query('fullname').value('.', 'VARCHAR(256)'),
FirstName = T.Item.query('firstname').value('.', 'VARCHAR(256)'),
LastName = T.Item.query('lastname').value('.', 'VARCHAR(256)'),
Email = T.Item.query('email').value('.', 'VARCHAR(256)'),
DOB = CASE
WHEN T.Item.query('dateofbirth').value('.', 'VARCHAR(10)') = '' THEN NULL
ELSE CONVERT(DATE, T.Item.query('dateofbirth').value('.', 'VARCHAR(10)'), 103)
END,
CC = T.Item.query('country').value('.', 'CHAR(2)')
FROM @xmlMailingListData.nodes('contacts/contact') AS T(Item)

I have contacted customer care but they are saying that I will have to implement indexing. How can I implement indexing in XML ?
They just see the error code & provide their feedback without checking the actual code.

can someone please help me.

 

Thanks Gropen,
But if you check above code, I have imported XML into a table variable. & after that I will insert this data into a table.

But how can I implement Indexing in XML?