Skip to content
  • Evgeny Potemkin's avatar
    db6c93b7
    WL #2771: Batched Key Access Join. · db6c93b7
    Evgeny Potemkin authored
    Version for Feature Preview. 
    This patch contains the following: 
    
    1. Upgrade of the JOIN_CACHE structure to a class.
    
    2. Optimization of the function that writes into the cache buffer:
        - null fields are not copied into the cache anymore
        - varchar values are packed with their lengths prepended,
        - if the first match is needed all records in the cache are,
          prepended with their length that allows to skip them easily.
    
    3. The class JOIN_CACHE_BNL derived from the class JOIN_CACHE 
       that implements the Block-based Nested Loops Join algorithm.
       This algorithm was implemented earlier but unlike the existing
       implementation of the Nested Loops Join algorithm it did not
       support outer joins and first match joins. This implementation
       supports all such joins including nested outer joins.
    
    4. The class JOIN_CACHE_BKA derived also from the class JOIN_CACHE.
       The class implements the Batched Key Access Join algorithm.
       The implementation uses the existing implementations of the
       Multi-Range Read Interface for MyISAM/InnoDb and for NDB Cluster.
    
    Two varieties of join caches are supported: plain caches and linked
    caches. Records in a linked cache can refer to the records in other
    caches. So if two partially joined records were generated from the same
    initial records they just refer to their common beginning. It allows to
    save space in join buffers.
    
    Although this is already the result of refactoring of the first prototype
    implementation the code is still rather fragile. Hopefully the comments that
    were added in abundance will help you to navigate through it. Any improvements
    are welcome.  
    
    Original revid:sp1r-igor@olga.mysql.com-20080401061749-11032
    db6c93b7
    WL #2771: Batched Key Access Join.
    Evgeny Potemkin authored
    Version for Feature Preview. 
    This patch contains the following: 
    
    1. Upgrade of the JOIN_CACHE structure to a class.
    
    2. Optimization of the function that writes into the cache buffer:
        - null fields are not copied into the cache anymore
        - varchar values are packed with their lengths prepended,
        - if the first match is needed all records in the cache are,
          prepended with their length that allows to skip them easily.
    
    3. The class JOIN_CACHE_BNL derived from the class JOIN_CACHE 
       that implements the Block-based Nested Loops Join algorithm.
       This algorithm was implemented earlier but unlike the existing
       implementation of the Nested Loops Join algorithm it did not
       support outer joins and first match joins. This implementation
       supports all such joins including nested outer joins.
    
    4. The class JOIN_CACHE_BKA derived also from the class JOIN_CACHE.
       The class implements the Batched Key Access Join algorithm.
       The implementation uses the existing implementations of the
       Multi-Range Read Interface for MyISAM/InnoDb and for NDB Cluster.
    
    Two varieties of join caches are supported: plain caches and linked
    caches. Records in a linked cache can refer to the records in other
    caches. So if two partially joined records were generated from the same
    initial records they just refer to their common beginning. It allows to
    save space in join buffers.
    
    Although this is already the result of refactoring of the first prototype
    implementation the code is still rather fragile. Hopefully the comments that
    were added in abundance will help you to navigate through it. Any improvements
    are welcome.  
    
    Original revid:sp1r-igor@olga.mysql.com-20080401061749-11032
Loading