How they work…
“I have a transactions table (~10M rows) and a card_banlist table (~1M rows).
I want every transaction that happened on a banned card after that card’s ban date.”
Setup some objects.
CREATE TABLE dbo.card_banlist
(
ban_id BIGINT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
card_no CHAR(16) NOT NULL,
denied_date DATETIME2(0) NOT NULL,
reason VARCHAR(50) NOT NULL
);
CREATE TABLE dbo.transactions
(
transaction_id BIGINT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
card_no CHAR(16) NOT NULL,
transaction_date DATETIME2(0) NOT NULL,
amount DECIMAL(10,2) NOT NULL,
status VARCHAR(20) NOT NULL
);
CREATE NONCLUSTERED INDEX IX_transactions_cardno_date
ON dbo.transactions (card_no, transaction_date);
CREATE NONCLUSTERED INDEX IX_banlist_cardno_date
ON dbo.card_banlist (card_no, denied_date);
The query we are using.
SELECT t.card_no, b.denied_date, t.transaction_date
FROM dbo.transactions t
JOIN dbo.card_banlist b ON t.card_no = b.card_no
WHERE t.transaction_date > b.denied_dateThe Execution Plan supplied by Erik Darling ( erikdarlingdata/PerformanceStudio: Free, open-source SQL Server execution plan analyzer — cross-platform GUI + CLI with 30 analysis rules, missing index detection, SSMS extension. Built-in MCP server for AI-assisted plan review. )
The way the operators flow and the decision to go left or right (Nested Loop or Hash Join).
Bitmap Arrays, why they are so handy to have and how the look.
Show me a bitmap! SQL Server gives no way to look inside its own bitmaps: no DMV, no trace flag. So I built a small one in T-SQL from your data: 32 bits, from the first 8 banned cards. The idea is the same as Opt_Bitmap1003, but it’s small enough to read, and SQL Server uses a different hash function.
1. Build side: each banned card sets one bit
The bit position is ABS(CHECKSUM(card_no)) % 32:
card_no bit
4000000000431757 1
4000000001337565 19
4000000000909369 23
4000000000704448 24 ┐
4000000000425988 24 ├ three cards land on the same bit
4000000001183068 24 ┘
4000000002133303 29
4000000001812762 302. The bitmap itself
position 00000000001111111111222222222233
01234567890123456789012345678901
bitmap 01000000000000000001000110000110That’s the whole thing: 32 bits (4 bytes), with 6 bits set by 8 cards. It holds no card numbers, only “something hashed here”.
3. Probe side: each transaction checks one bit
card_no bit outcome
4000000000000012 14 bit 0: dropped
4000000000000031 15 bit 0: dropped
4000000000425988 24 bit 1: passes, real match
4000000000431757 1 bit 1: passes, real match
4000000000000108 24 bit 1: passes, FALSE POSITIVE (shares bit 24)
4000000000000163 29 bit 1: passes, FALSE POSITIVE (shares bit 29)Across 200,020 transactions (the first 200,000, plus the 20 that belong to the 8 banned cards):
| Checked | Dropped | Passed | Real matches | False positives |
|---|---|---|---|---|
| 200,020 | 140,278 (70%) | 59,742 | 20 | 59,722 |
With only 32 bits, almost everything that passes is a false positive. The hash join would then reject those 59,722 rows with a real card_no comparison, so the result is still correct, just with less work saved.
Size matters: compared with q1
- Build keys: 1,000,000 banned cards.
- False positives: 1,860 out of about 6,669,361 transactions on cards that aren’t banned, a rate of 0.028%. That’s the rows passing the Filter minus the 3,330,639 transactions on banned cards.
- With my toy method: one hash and one bit per card would need about 3.6 billion bits (≈450 MB) to get that low. That’s more than the whole 362 MB memory grant.
So SQL Server’s bitmap must be built more cleverly than this demo. For example, a Bloom filter sets several bits per key and needs roughly 17 bits per key (≈2 MB) for that rate. I don’t know SQL Server’s exact internal design, so treat that as an explanation of why the rate is possible, not as how SQL Server does it.
Generate some sample data for both Tables.
/* Sample data for the hash-vs-merge join repro in database [issues].
Deterministic (MD5 of a row number), so a reload gives identical data.
- 3,000,000 distinct cards : '4000' + 12-digit card id
- dbo.transactions 10,000,000 rows, random card, random time 2024-09-01 .. 2026-09-01,
transaction_id assigned in date order
- dbo.card_banlist 1,000,000 rows, every 3rd card (card_no unique BY DATA, not declared),
random denied_date in the same window
*/
SET NOCOUNT ON;
SET QUOTED_IDENTIFIER ON;
USE issues;
IF EXISTS (SELECT 1 FROM dbo.transactions) OR EXISTS (SELECT 1 FROM dbo.card_banlist)
BEGIN
RAISERROR('Tables are not empty - load skipped.', 16, 1);
RETURN;
END;
ALTER INDEX IX_transactions_cardno_date ON dbo.transactions DISABLE;
ALTER INDEX IX_banlist_cardno_date ON dbo.card_banlist DISABLE;
DECLARE @t0 datetime2 = SYSDATETIME();
INSERT dbo.transactions WITH (TABLOCK) (card_no, transaction_date, amount, status)
SELECT card_no, transaction_date, amount, status
FROM (
SELECT
card_no = CAST('4000' + RIGHT(CONCAT('000000000000',
(CAST(SUBSTRING(h, 1, 4) AS int) & 2147483647) % 3000000 + 1), 12) AS char(16)),
transaction_date = DATEADD(SECOND,
(CAST(SUBSTRING(h, 5, 4) AS int) & 2147483647) % 63072000,
CAST('2024-09-01' AS datetime2(0))),
amount = CAST(((CAST(SUBSTRING(h, 9, 4) AS int) & 2147483647) % 50000) / 100.0 + 1 AS decimal(10,2)),
status = CASE WHEN CAST(SUBSTRING(h, 13, 1) AS int) % 100 < 90 THEN 'approved'
WHEN CAST(SUBSTRING(h, 13, 1) AS int) % 100 < 98 THEN 'declined'
ELSE 'reversed' END
FROM (SELECT h = HASHBYTES('MD5', CAST(value AS binary(8)))
FROM GENERATE_SERIES(CAST(1 AS bigint), CAST(10000000 AS bigint))) s
) x
ORDER BY transaction_date;
PRINT CONCAT('transactions loaded in ', DATEDIFF(SECOND, @t0, SYSDATETIME()), ' s');
SET @t0 = SYSDATETIME();
INSERT dbo.card_banlist WITH (TABLOCK) (card_no, denied_date, reason)
SELECT card_no, denied_date, reason
FROM (
SELECT
card_no = CAST('4000' + RIGHT(CONCAT('000000000000', value), 12) AS char(16)),
denied_date = DATEADD(SECOND,
(CAST(SUBSTRING(h, 1, 4) AS int) & 2147483647) % 63072000,
CAST('2024-09-01' AS datetime2(0))),
reason = CASE CAST(SUBSTRING(h, 5, 1) AS int) % 4
WHEN 0 THEN 'reported stolen'
WHEN 1 THEN 'reported lost'
WHEN 2 THEN 'suspected fraud'
ELSE 'chargeback limit exceeded' END
FROM (SELECT value, h = HASHBYTES('MD5', CAST(value AS binary(8)) + 0x01)
FROM GENERATE_SERIES(CAST(3 AS bigint), CAST(3000000 AS bigint), CAST(3 AS bigint))) s
) x
ORDER BY denied_date;
PRINT CONCAT('card_banlist loaded in ', DATEDIFF(SECOND, @t0, SYSDATETIME()), ' s');
SET @t0 = SYSDATETIME();
ALTER INDEX IX_transactions_cardno_date ON dbo.transactions REBUILD;
ALTER INDEX IX_banlist_cardno_date ON dbo.card_banlist REBUILD;
PRINT CONCAT('indexes rebuilt in ', DATEDIFF(SECOND, @t0, SYSDATETIME()), ' s');
SET NOCOUNT ON;
SET QUOTED_IDENTIFIER ON;
USE issues;
SELECT tbl = 'transactions', rows = COUNT_BIG(*), cards = COUNT(DISTINCT card_no),
min_date = MIN(transaction_date), max_date = MAX(transaction_date)
FROM dbo.transactions
UNION ALL
SELECT 'card_banlist', COUNT_BIG(*), COUNT(DISTINCT card_no), MIN(denied_date), MAX(denied_date)
FROM dbo.card_banlist;
SELECT status, n = COUNT_BIG(*) FROM dbo.transactions GROUP BY status ORDER BY status;
SELECT reason, n = COUNT_BIG(*) FROM dbo.card_banlist GROUP BY reason ORDER BY reason;
SELECT txns_on_banned_cards = COUNT_BIG(*),
txns_after_ban = SUM(CASE WHEN t.transaction_date > b.denied_date THEN 1 ELSE 0 END)
FROM dbo.transactions t JOIN dbo.card_banlist b ON t.card_no = b.card_no;
SELECT TOP (3) * FROM dbo.transactions ORDER BY transaction_id;
SELECT TOP (3) * FROM dbo.card_banlist ORDER BY ban_id;
SELECT tbl = OBJECT_NAME(ps.object_id), idx = i.name, ps.row_count,
used_mb = ps.used_page_count * 8 / 1024
FROM sys.dm_db_partition_stats ps
JOIN sys.indexes i ON i.object_id = ps.object_id AND i.index_id = ps.index_id
WHERE ps.object_id IN (OBJECT_ID('dbo.transactions'), OBJECT_ID('dbo.card_banlist'))
ORDER BY 1, i.index_id;
SELECT file_name = name, size_mb = size * 8 / 1024 FROM sys.database_files;
Over en sluiten..