title: How to speed up the deletion of entries from a table with a large number of entries
body: <p>I have a table that currently has over 150 million records. The table has no foreign keys.</p>
  <p><a href="https://i.stack.imgur.com/s7VOR.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/s7VOR.png" alt="[TABLE]" /></a></p>
  <p>The database was previously based on MySQL and was migrated to SQL Server.
  Since then, one specific query on that table has taken much, much longer.
  On MySQL, the query counterpart took less than 3 seconds to execute. On SQL Server, the query can be executed even for more than 1 minute.</p>
  <p>There is no problem with any other table or query at the moment - just this one on this one table.</p>
  <p>[EXAMPLE] : I CAN'T CHANGE A QUERY.</p>
  <pre><code>delete from Features WITH(ROWLOCK)
  where ParentType=N'DokHandlowe' and Parent=3023658
     or ParentType=N'PozycjeDokHan' and Parent in (25302311, 25302312, 
  25302313, 25302314, 25302315, 25302316, 25302317, 25302318, 25302319, 
  25302320, 25302321, 25302322, 25302323, 25302324, 25302325, 25302326, 
  25302327, 25302328, 25302329, 25302330, 25302331, 25302332, 25302333, 
  25302334, 25302335, 25302336, 25302337, 25302338, 25302339, 25302340, 
  25302341, 25302342, 25302343, 25302344, 25302345, 25302346, 25302347, 
  25302348, 25302349, 25302350, 25302351, 25302352, 25302353, 25302354, 
  25302355, 25302356, 25302357, 25302358, 25302359, 25302360, 25302361, 
  25302362, 25302363, 25302364, 25302365, 25302366, 25302367, 25302368, 
  25302369, 25302370, 25302371, 25302372, 25302373, 25302374, 25302375, 
  25302376, 25302377, 25302378, 25302379, 25302380, 25302381, 25302382, 
  25302383, 25302384, 25302385, 25302386, 25302387, 25302388, 25302389, 
  25302390, 25302391, 25302392, 25302393, 25302394, 25302395, 25302396, 
  25302397, 25302398, 25302399, 25302400, 25302401, 25302402, 25302403, 
  25302404, 25302405, 25302406, 25302407, 25302408, 25302409, 25302410, 
  25302411, 25302412, 25302413, 25302414, 25302415, 25302416, 25302417, 
  25302418, 25302419, 25302420, 25302421, 25302422, 25302423, 25302424, 
  25302425, 25302426, 25302427, 25302428, 25302429, 25302430, 25302431, 
  25302432, 25302433, 25302434, 25302435, 25302436, 25302437, 25302438, 
  25302439, 25302440, 25302441, 25302442, 25302443, 25302444, 25302445, 
  25302446, 25302447, 25302448, 25302449, 25302450, 25302451, 25302452, 
  25302453, 25302454, 25302455, 25302456, 25302457, 25302458, 25302459, 
  25302460, 25302461, 25302462, 25302463, 25302464, 25302465, 25302466, 
  25302467, 25302468, 25302469, 25302470, 25302471, 25302472, 25302473, 
  25302474, 25302475, 25302476, 25302477, 25302478, 25302479, 25302480, 
  25302481, 25302482, 25302483, 25302484, 25302485, 25302486, 25302487, 
  25302488, 25302489, 25302490, 25302491, 25302492, 25302493, 25302494, 
  25302495, 25302496, 25302497, 25302498, 25302499, 25302500, 25302501, 
  25302502, 25302503, 25302504, 25302505, 25302506, 25302507, 25302508, 
  25302509, 25302510, 25302511, 25302512, 25302513, 25302514, 25302515, 
  25302516, 25302517, 25302518, 25302519, 25302520, 25302521, 25302522, 
  25302523, 25302524, 25302525, 25302526, 25302527, 25302528, 25302529, 
  25302530, 25302531, 25302532, 25302533, 25302534, 25302535, 25302536, 
  25302537, 25302538, 25302539, 25302540, 25302541, 25302542, 25302543, 
  25302544, 25302545, 25302546, 25302547, 25302548, 25302549, 25302550)
  </code></pre>
  <p>Tried doing indexes but either I've created them incorected or it didn't help.</p>
  <p>Indexes :</p>
  <p><a href="https://i.stack.imgur.com/8JCic.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8JCic.png" alt="enter image description here" /></a></p>
  <p>[EDIT#1]</p>
  <pre><code>/****** Object:  Index [Features_Data_INDEX]    Script Date: 2021-09-01 10:51:34 ******/
  CREATE NONCLUSTERED INDEX [Features_Data_INDEX] ON [dbo].[Features]
  (
      [ParentType] ASC,
      [Name] ASC,
      [DataKey] ASC,
      [Lp] ASC
  )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
  GO
  
  SET ANSI_PADDING ON
  GO
  
  /****** Object:  Index [NCI_Features_Parent_ParentType]    Script Date: 2021-09-01 10:59:29 ******/
  CREATE NONCLUSTERED INDEX [NCI_Features_Parent_ParentType] ON [dbo].[Features]
  (
      [ParentType] ASC,
      [Parent] ASC
  )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
  GO
  
  SET ANSI_PADDING ON
  GO
  
  /****** Object:  Index [NCI_Features_ParentType_Parent]    Script Date: 2021-09-01 10:59:55 ******/
  CREATE NONCLUSTERED INDEX [NCI_Features_ParentType_Parent] ON [dbo].[Features]
  (
      [Parent] ASC,
      [ParentType] ASC
  )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
  GO
  
  SET ANSI_PADDING ON
  GO
  
  /****** Object:  Index [PK_Feature]    Script Date: 2021-09-01 11:00:13 ******/
  ALTER TABLE [dbo].[Features] ADD  CONSTRAINT [PK_Feature] PRIMARY KEY CLUSTERED 
  (
      [Parent] ASC,
      [ParentType] ASC,
      [Name] ASC,
      [Lp] ASC
  )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
  GO
  </code></pre>
  <p>[EDIT#2]
  (Estimated) Query plan : <a href="https://www.brentozar.com/pastetheplan/?id=HkyJqphbt" rel="nofollow noreferrer">https://www.brentozar.com/pastetheplan/?id=HkyJqphbt</a></p>
  <p>[EDIT#3]
  (Actual) Query plan : <a href="https://www.brentozar.com/pastetheplan/?id=ryVNnC2ZY" rel="nofollow noreferrer">https://www.brentozar.com/pastetheplan/?id=ryVNnC2ZY</a></p>