Actual Number of Rows Significantly Lower than Estimated

Question

My Problem

I am having an issue with a update query, where the execution plan has a bad cardinality estimate. It is estimated way more rows (14000%) than there should be when it does an Index seek on one of the tables (ShInvoiceHeader). My understanding of why that's not good is that the plan won't be as optimized and it'll cause more memory to be requested than needed.

Here's a screenshot of what I'm seeing in the execution plan, and a link to the actual execution plan.

Here is the update query. We are finding all the records where a column is False, checking if a matching record exists in a table with records from an activity log and then updating them to True. The log table doesn't have the same uniqueness as the primary table ShInvoiceHeader, so we are using an EXISTS. However I also tested this out with a JOIN and saw the same issue.

UPDATE  HDR
SET PrintedBillTrustFlag = 1
FROM    dbo.ShInvoiceHeader                     HDR
WHERE   EXISTS(SELECT 1
                FROM USESIDW_FastAccess.dbo.LedgerLogEvent  LLE
                WHERE   HDR.LedgerID = LLE.LedgerID
                    AND HDR.GenID    = LLE.GenID
                    AND LLE.EventID IN (25,53,54)
                )
    AND HDR.PrintedBillTrustFlag = 0

What I've done to try and fix it

I right clicked the Analyze Actual Execution Plan and selected the node with the Index Seek on NonClustered ShInvoiceHeader.IX_ShInvoiceHeader_PrintedBillTrustFlag and it listed for findings details:

1. One of the common reasons for estimation differences is the use of different statistics. Check if the statistics for table [ShInvoiceHeader] are different or stale. Refer to here for more information

So then I updated the stastics for the column using: UPDATE STATISTICS ShInvoiceHeader [IX_ShInvoiceHeader_PrintedBillTrustFlag] WITH FULLSCAN

and I also tried:

ALTER INDEX [IX_ShInvoiceHeader_PrintedBillTrustFlag] ON ShInvoiceHeader REBUILD;

To no avail, the issue stayed the same. I read posts on StackExchange and most of them mentioned outdated statistics and one mentioned if the update had happened earlier that day it could cause an issue. So I tried to undo the update so the records looked like they would've the first time and then test again and still same issue.

I tried a few query hints for the heck of it like RECOMPILE and MAXDOP 1 and tried joining to an empty table with columnstore to induce Batch mode. I don't know a lot about those topics but tried them.

I also counted the number of rows in each part of the query. There are 5.3M records in ShInvoiceHeader with a PrintedBillTrustFlag = 0, so that number makes sense. There are 4.9M records from the LedgerLogEvent table that meet the criteria. There are 7,604 rows when you combine and do the EXISTS which matches the amount updated. But what doesn't make sense to me is the ACTUAL of 36881 in the Execution Plan.

Update:

I was asked to include the table definition and index definition.

• Here's ShInvoiceHeader, with some of the columns, the list goes on and on for a while, it's pretty wide.

• Here's LedgerLogEvent. Note uniqueness is different that's why I'm doing the exists instead of a join.

• Here is the index being used