Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-35897

Questions about memory allocation done for vector index search

Details

    • Bug
    • Status: Open (View Workflow)
    • Major
    • Resolution: Unresolved
    • 11.7.1
    • 11.8
    • Vector search
    • None

    Description

      I started to look at PMP and perf profiles while running ann-benchmarks and when ef_search is large I see much time in memory allocation functions, most from VisitedSet code, during search_layer.

      I am curious about two things:
      1) Why is such a large value for est_size passed to the VisitedSet ctor here? This creates huge bloom filters as each uses about 2*est_size bytes, and with ef_search=400 (see example below) that is ~32MB. Such large alloc / dealloc cycles are slow when frequent.

      2) Why does "bv" use longlong which is 8 bytes while (see here) while the num_blocks math (see here) appears to assume the bv vector is 4 bytes per entry. For one example:

      • n = 15,044,334
      • m = 143,931,441 (~= 10 * n)
      • log_num_blocks = 22
      • num_blocks = 4,194,304
      • bv.resize(4194304) is called, which provides about 33,554,432 bits

      The est_size variable is: est_heuristic * (ef ^ ef_power), from here. This ends up creating huge bloom filters when used by the VisitedSet ctor.

      All of these are from queries with LIMIT 10

      With ef_search=120 the math is: 39.x * (120 ^ 2) = 1135647 and visited.count is <= 2000 at the end of search_layer

      With ef_search=200 the math is: 39.x * (200 ^ 2) = 3398947 and visited.count is <= 2000 at the end of search_layer()

      With ef_search=300 the math is: 39.x * (300 ^ 2) = 8114222 and visited.count is <= 3000 at the end of search_layer()

      With ef_search=400 the math is: 39.x * (400 ^ 2) = 15044334 and visited.count is <= 3000 at the end of search_layer()

      Attachments

        Issue Links

          is duplicated by

          Bug - A problem which impairs or prevents the functions of the product. MDEV-36338 vector search with Cosine Distance is slow

          • Major - Major loss of function.
          • Closed

          Activity

            Ascending order - Click to sort in descending order
            mdcallag Mark Callaghan added a comment - - edited

            After hacking MariaDB so that est_size is always <= 64000 when the VisitedSet constructor is called, I repeated tests and the hack makes QPS for ef_search=200, =300 and =400 much faster.

            The numbers I pasted below are also here in case I can't get fixed-width fonts 

                                                                    recall  QPS
            		 
            PGVector(m=16, ef_construction=96, ef_search=20)        0.990   2126
            		 
            PGVector(m=16, ef_construction=96, ef_search=10)        0.970   2662
            		 
            PGVector(m=16, ef_construction=96, ef_search=30)        0.995   1803
            		 
            PGVector(m=16, ef_construction=96, ef_search=40)        0.997   1581
            		 
            PGVector(m=16, ef_construction=96, ef_search=80)        0.999   1109
            		 
            PGVector(m=16, ef_construction=96, ef_search=120)       0.999    874
            		 
            PGVector(m=16, ef_construction=96, ef_search=200)       1.000    606
            		 
            PGVector(m=16, ef_construction=96, ef_search=300)       1.000    462
            		 
            PGVector(m=16, ef_construction=96, ef_search=400)       1.000    383
            		 
            PGVector(m=16, ef_construction=96, ef_search=800)       1.000    236
            		 
             
            		 
                                                                       recall    QPS
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=10)   0.968     2803
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=20)   0.989     2294
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=30)   0.994     1991
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=40)   0.996     1767
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=80)   0.999     1260
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=120)  0.999      998
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=200)  1.000      731
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=300)  1.000      527
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=400)  1.000      439
            		 
            PGVector_halfvec(m=16, ef_construction=96, ef_search=800)  1.000      269
            		 
             
            		 
            MariaDB 11.7.1, as-is
            		 
                                            recall    QPS
            		 
            MariaDB(m=8, ef_search=10)      0.984     4400
            		 
            MariaDB(m=8, ef_search=20)      0.995     3791
            		 
            MariaDB(m=8, ef_search=30)      0.997     3391
            		 
            MariaDB(m=8, ef_search=40)      0.998     3105
            		 
            MariaDB(m=8, ef_search=80)      0.999     2321
            		 
            MariaDB(m=8, ef_search=120)     0.999     1913
            		 
            MariaDB(m=8, ef_search=200)     0.999     1356
            		 
            MariaDB(m=8, ef_search=300)     1.000      189
            		 
            MariaDB(m=8, ef_search=400)     1.000      100
            		 
            MariaDB(m=8, ef_search=800)     1.000       13
            		 
             
            		 
            MariaDB 11.7.1, hacked so that est_size is <= 64000 in call to VisitedSet
            		 
                                            recall    QPS
            		 
            MariaDB(m=8, ef_search=10)      0.984     4391
            		 
            MariaDB(m=8, ef_search=20)      0.995     3797
            		 
            MariaDB(m=8, ef_search=30)      0.997     3378
            		 
            MariaDB(m=8, ef_search=40)      0.998     3094
            		 
            MariaDB(m=8, ef_search=80)      0.999     2383
            		 
            MariaDB(m=8, ef_search=120)     0.999     1977
            		 
            MariaDB(m=8, ef_search=200)     0.999     1510 -> vs 1356 above for MariaDB without fix
            		 
            MariaDB(m=8, ef_search=300)     1.000     1190 -> vs  189 above for MariaDB without fix
            		 
            MariaDB(m=8, ef_search=400)     1.000      993 -> vs  100 above for MariaDB without fix
            		 
            MariaDB(m=8, ef_search=800)     1.000      625 -> vs   13 above for MariaDB without fix

            mdcallag Mark Callaghan added a comment - - edited After hacking MariaDB so that est_size is always <= 64000 when the VisitedSet constructor is called, I repeated tests and the hack makes QPS for ef_search=200, =300 and =400 much faster. The numbers I pasted below are also here in case I can't get fixed-width fonts recall QPS PGVector(m=16, ef_construction=96, ef_search=20) 0.990 2126 PGVector(m=16, ef_construction=96, ef_search=10) 0.970 2662 PGVector(m=16, ef_construction=96, ef_search=30) 0.995 1803 PGVector(m=16, ef_construction=96, ef_search=40) 0.997 1581 PGVector(m=16, ef_construction=96, ef_search=80) 0.999 1109 PGVector(m=16, ef_construction=96, ef_search=120) 0.999 874 PGVector(m=16, ef_construction=96, ef_search=200) 1.000 606 PGVector(m=16, ef_construction=96, ef_search=300) 1.000 462 PGVector(m=16, ef_construction=96, ef_search=400) 1.000 383 PGVector(m=16, ef_construction=96, ef_search=800) 1.000 236   recall QPS PGVector_halfvec(m=16, ef_construction=96, ef_search=10) 0.968 2803 PGVector_halfvec(m=16, ef_construction=96, ef_search=20) 0.989 2294 PGVector_halfvec(m=16, ef_construction=96, ef_search=30) 0.994 1991 PGVector_halfvec(m=16, ef_construction=96, ef_search=40) 0.996 1767 PGVector_halfvec(m=16, ef_construction=96, ef_search=80) 0.999 1260 PGVector_halfvec(m=16, ef_construction=96, ef_search=120) 0.999 998 PGVector_halfvec(m=16, ef_construction=96, ef_search=200) 1.000 731 PGVector_halfvec(m=16, ef_construction=96, ef_search=300) 1.000 527 PGVector_halfvec(m=16, ef_construction=96, ef_search=400) 1.000 439 PGVector_halfvec(m=16, ef_construction=96, ef_search=800) 1.000 269   MariaDB 11.7.1, as-is recall QPS MariaDB(m=8, ef_search=10) 0.984 4400 MariaDB(m=8, ef_search=20) 0.995 3791 MariaDB(m=8, ef_search=30) 0.997 3391 MariaDB(m=8, ef_search=40) 0.998 3105 MariaDB(m=8, ef_search=80) 0.999 2321 MariaDB(m=8, ef_search=120) 0.999 1913 MariaDB(m=8, ef_search=200) 0.999 1356 MariaDB(m=8, ef_search=300) 1.000 189 MariaDB(m=8, ef_search=400) 1.000 100 MariaDB(m=8, ef_search=800) 1.000 13   MariaDB 11.7.1, hacked so that est_size is <= 64000 in call to VisitedSet recall QPS MariaDB(m=8, ef_search=10) 0.984 4391 MariaDB(m=8, ef_search=20) 0.995 3797 MariaDB(m=8, ef_search=30) 0.997 3378 MariaDB(m=8, ef_search=40) 0.998 3094 MariaDB(m=8, ef_search=80) 0.999 2383 MariaDB(m=8, ef_search=120) 0.999 1977 MariaDB(m=8, ef_search=200) 0.999 1510 -> vs 1356 above for MariaDB without fix MariaDB(m=8, ef_search=300) 1.000 1190 -> vs 189 above for MariaDB without fix MariaDB(m=8, ef_search=400) 1.000 993 -> vs 100 above for MariaDB without fix MariaDB(m=8, ef_search=800) 1.000 625 -> vs 13 above for MariaDB without fix
            serg Sergei Golubchik added a comment -

            I've tuned bloom filter at the very early phase of the vector search development, not surprising it might need re-tuning now. The problem here is that the smaller bloom filter is, the more false positives it'll have, which directly affects recall. It's the same tradeoff — improving the speed reduces the recall.

            But I definitely need to re-tune it. I didn't expect it to have that big effect on qps

            serg Sergei Golubchik added a comment - I've tuned bloom filter at the very early phase of the vector search development, not surprising it might need re-tuning now. The problem here is that the smaller bloom filter is, the more false positives it'll have, which directly affects recall. It's the same tradeoff — improving the speed reduces the recall. But I definitely need to re-tune it. I didn't expect it to have that big effect on qps

            People

              serg Sergei Golubchik
              mdcallag Mark Callaghan
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.