Azure SQL DB causing connection time out for stored procedures

We have hosted our database in Azure and are running stored procedures on this DB. The stored procedures had been running fine till last week but suddenly started giving error connection timeout.

Our database size is 14 GB and the stored procedures in general return 2k to 20k records and we are using the S3 pricing tier (50 DTU) of Azure DB.

What I found interesting was the first time the stored procedure is executed, it takes a lot of time 2 - 3 mins and this is causing the timeout. The later executions are fast (maybe it caches the execution plan).

Also when I run on the same DB with the same number of records on a machine with the config of 8gb ram, Win10 it runs in 15 seconds.

This is my stored procedure:

CREATE PROCEDURE [dbo].[PRSP]
@CompanyID INT,
@fromDate DATETIME,
@toDate DATETIME,
@ListMailboxId as MailboxIds Readonly,
@ListConversationType as ConversationTypes Readonly
AS
BEGIN
SET NOCOUNT ON;

SELECT
C.ID,
C.MailboxID,
C.Status,
C.CustomerID,
Cust.FName,
Cust.LName,
C.ArrivalDate as ConversationArrivalDate,
C.[ClosureDate],
C.[ConversationType],
M.[From],
M.ArrivalDate as MessageArrivalDate,
M.ID as MessageID
FROM
[Conversation] as C
INNER JOIN
[ConversationHistory] AS CHis ON (CHis.ConversationID = C.ID)
INNER JOIN
[Message] AS M ON (M.ConversationID = C.ID)
INNER JOIN
[Mailbox] AS Mb ON (Mb.ID = C.MailboxID)
INNER JOIN
[Customer] AS Cust ON (Cust.ID = C.CustomerID)
JOIN
@ListConversationType AS convType ON convType.ID = C.[ConversationType]
JOIN
@ListMailboxId AS mailboxIds ON mailboxIds.ID = Mb.ID
WHERE
Mb.CompanyID = @CompanyID
AND ((CHis.CreatedOn > @fromDate
AND CHis.CreatedOn < @toDate
AND CHis.Activity = 1
AND CHis.TagData = '3')
OR (M.ArrivalDate > @fromDate
AND M.ArrivalDate < @toDate))
END


This is the execution plan :

Execution Plan

Please do give your suggestions as to what improvement is needed? Also do we need to upgrade my pricing tier?

Ideally for a 14GB DB what should be the Azure Pricing tier?

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.