search

btcsuite / btcutil

Provides bitcoin-specific convenience functions and types
479 stars 409 forks source link

[gcs] HashMatchAny: faster filter matches for large queries #122

Closed cfromknecht closed 5 years ago

cfromknecht commented 6 years ago

This PR proposes a different gcs filter querying mechanism, intended for having better performance as the number of query entries surpasses the number of elements in the filter.

As the number of elements in the query grows, allocating and sorting the elements begins to dominate the runtime. The solution then for large queries is inspired by a hash join, which makes no assumptions on the input ordering of either set. Since the number of filters is ultimately bounded by the block size, the filter entries are chosen as the hash index so that the setup latency is minimized.

Complexity

Number of filter entries: F Number of query entries: Q Assumption: Q > F

Setup

Regular Hash
Keying Theta (Q) 0
Cmp O(Q log Q) Theta(F)
Read 0 Theta(F)
Memory Theta(Q) Theta(F)

Online

Regular Hash
Keying 0 O(Q)
Cmp O(F+Q) O(Q)
Read O(F) 0
Memory O(1) O(1)

Benchmarks

Zip w/ 5K Filter Elements

BenchmarkGCSFilterZipMatchAny/q100-f5K-8                   10000            214745 ns/op           14496 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q1K-f5K-8                     5000            365375 ns/op           21792 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q10K-f5K-8                    1000           1997457 ns/op           95520 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q100K-f5K-8                    100          20662820 ns/op          816416 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q1M-f5K-8                        5         243683419 ns/op         8017184 B/op          3 allocs/op

Zip w/ 10K Filter Elements

BenchmarkGCSFilterZipMatchAny/q100-f10K-8                   3000            674189 ns/op           28192 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q1K-f10K-8                    2000            716604 ns/op           35488 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q10K-f10K-8                   1000           2414061 ns/op          109216 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q100K-f10K-8                   100          23639724 ns/op          830112 B/op          3 allocs/op
BenchmarkGCSFilterZipMatchAny/q1M-f10K-8                       5         246618280 ns/op         8030880 B/op          3 allocs/op

Hash-Join w/ 5K Filter Elements

BenchmarkGCSFilterHashMatchAny/q100-f5K-8                   3000            424421 ns/op           72351 B/op         11 allocs/op      
BenchmarkGCSFilterHashMatchAny/q1K-f5K-8                    3000            450057 ns/op           72348 B/op         11 allocs/op      
BenchmarkGCSFilterHashMatchAny/q10K-f5K-8                   2000            936740 ns/op           72347 B/op         11 allocs/op      
BenchmarkGCSFilterHashMatchAny/q100K-f5K-8                   200           6184445 ns/op           72340 B/op         11 allocs/op      
BenchmarkGCSFilterHashMatchAny/q1M-f5K-8                      50          31261020 ns/op           72422 B/op         11 allocs/op

Hash-Join w/ 10K Filter Elements

BenchmarkGCSFilterHashMatchAny/q100-f10K-8                  2000            890682 ns/op          136545 B/op         12 allocs/op
BenchmarkGCSFilterHashMatchAny/q1K-f10K-8                   2000            976564 ns/op          136513 B/op         12 allocs/op
BenchmarkGCSFilterHashMatchAny/q10K-f10K-8                  1000           1480180 ns/op          136564 B/op         12 allocs/op
BenchmarkGCSFilterHashMatchAny/q100K-f10K-8                  200           6389050 ns/op          136570 B/op         12 allocs/op
BenchmarkGCSFilterHashMatchAny/q1M-f10K-8                    300           5701372 ns/op          136512 B/op         12 allocs/op

Hybrid w/ 5k Filter Elements

BenchmarkGCSFilterMatchAny/q100-f5K-8                      10000            211485 ns/op           14496 B/op          3 allocs/op      
BenchmarkGCSFilterMatchAny/q1K-f5K-8                        5000            359744 ns/op           21792 B/op          3 allocs/op      
BenchmarkGCSFilterMatchAny/q10K-f5K-8                       2000            966623 ns/op           72346 B/op         11 allocs/op      
BenchmarkGCSFilterMatchAny/q100K-f5K-8                       200           6057262 ns/op           72340 B/op         11 allocs/op      
BenchmarkGCSFilterMatchAny/q1M-f5K-8                          50          31490692 ns/op           72319 B/op         11 allocs/op

Hybrid w/ 10k Filter Elements

BenchmarkGCSFilterMatchAny/q100-f10K-8                      3000            561779 ns/op           28192 B/op          3 allocs/op
BenchmarkGCSFilterMatchAny/q1K-f10K-8                       2000            725211 ns/op           35488 B/op          3 allocs/op
BenchmarkGCSFilterMatchAny/q10K-f10K-8                      1000           1431762 ns/op          136531 B/op         12 allocs/op
BenchmarkGCSFilterMatchAny/q100K-f10K-8                      200           6382231 ns/op          136457 B/op         12 allocs/op
BenchmarkGCSFilterMatchAny/q1M-f10K-8                        300           5611058 ns/op          136553 B/op         12 allocs/op

Ratio Zip/Hash

Latency Memory
q10K-f5K 2.13x 1.32x
q10K-f10K 1.63x 0.8x
q1M-f5K 7.80x 110.7x
q1M-f10K 43.3x 58.8x