flow-php / flow

Flow PHP - data processing framework
https://flow-php.com
MIT License
483 stars 28 forks source link

Replaced nested loop join with hash join algorithm #1055

Closed norberttech closed 6 months ago

norberttech commented 6 months ago

Change Log

Added

Fixed

  • Right Join before duplicating right side rows in each batch from the left side dataset

Changed

  • NestedLoop join algorithm was replaced with HashJoin algorithm

Removed

  • Join expression comparison types other than equal/identical/any/all

Deprecated

Security


Description

This is just the first step to significantly improve join operation performance. Now flow join mechanism is using hash join algorithm, next one will be the sort-merge join.

github-actions[bot] commented 6 months ago

Flow PHP - Benchmarks

Results of the benchmarks from this PR are compared with the results from 1.x branch.

Extractors ```shell +-----------------------+-------------------+------+-----+------------------+------------------+-----------------+ | benchmark | subject | revs | its | mem_peak | mode | rstdev | +-----------------------+-------------------+------+-----+------------------+------------------+-----------------+ | AvroExtractorBench | bench_extract_10k | 1 | 3 | 35.299mb -0.03% | 852.279ms +0.12% | ±1.12% +189.56% | | CSVExtractorBench | bench_extract_10k | 1 | 3 | 5.020mb -0.18% | 348.072ms +1.17% | ±0.66% -24.71% | | JsonExtractorBench | bench_extract_10k | 1 | 3 | 5.174mb -0.17% | 1.065s -1.17% | ±0.55% -81.68% | | ParquetExtractorBench | bench_extract_10k | 1 | 3 | 135.846mb -0.01% | 918.670ms +0.68% | ±0.76% +227.45% | | TextExtractorBench | bench_extract_10k | 1 | 3 | 4.929mb -0.08% | 35.715ms -0.31% | ±0.52% -56.57% | | XmlExtractorBench | bench_extract_10k | 1 | 3 | 4.935mb -0.08% | 433.850ms -1.05% | ±0.45% -87.55% | +-----------------------+-------------------+------+-----+------------------+------------------+-----------------+ ```
Transformers ```shell +-----------------------------+--------------------------+------+-----+------------------+-----------------+----------------+ | benchmark | subject | revs | its | mem_peak | mode | rstdev | +-----------------------------+--------------------------+------+-----+------------------+-----------------+----------------+ | RenameEntryTransformerBench | bench_transform_10k_rows | 1 | 3 | 116.240mb -0.01% | 60.304ms -0.41% | ±1.75% +96.84% | +-----------------------------+--------------------------+------+-----+------------------+-----------------+----------------+ ```
Loaders ```shell +--------------------+----------------+------+-----+------------------+------------------+------------------+ | benchmark | subject | revs | its | mem_peak | mode | rstdev | +--------------------+----------------+------+-----+------------------+------------------+------------------+ | AvroLoaderBench | bench_load_10k | 1 | 3 | 96.685mb -0.01% | 466.595ms +1.11% | ±0.96% +532.89% | | CSVLoaderBench | bench_load_10k | 1 | 3 | 55.164mb -0.02% | 68.830ms +0.93% | ±0.42% -62.06% | | JsonLoaderBench | bench_load_10k | 1 | 3 | 107.594mb -0.01% | 52.054ms +1.68% | ±2.74% +1572.23% | | ParquetLoaderBench | bench_load_10k | 1 | 3 | 227.014mb -0.00% | 1.421s +0.57% | ±0.35% +220.52% | | TextLoaderBench | bench_load_10k | 1 | 3 | 17.977mb -0.05% | 38.829ms -0.06% | ±0.55% -38.73% | +--------------------+----------------+------+-----+------------------+------------------+------------------+ ```
Building Blocks ```shell +-------------------------+----------------------------+------+-----+------------------+------------------+------------------+ | benchmark | subject | revs | its | mem_peak | mode | rstdev | +-------------------------+----------------------------+------+-----+------------------+------------------+------------------+ | RowsBench | bench_chunk_10_on_10k | 2 | 3 | 87.061mb -0.01% | 3.684ms +7.61% | ±2.07% +26.82% | | RowsBench | bench_diff_left_1k_on_10k | 2 | 3 | 102.659mb -0.01% | 188.652ms +0.83% | ±1.55% +581.30% | | RowsBench | bench_diff_right_1k_on_10k | 2 | 3 | 85.379mb -0.01% | 19.152ms +1.98% | ±2.81% +1103.51% | | RowsBench | bench_drop_1k_on_10k | 2 | 3 | 88.301mb -0.01% | 1.935ms +17.83% | ±1.37% -60.89% | | RowsBench | bench_drop_right_1k_on_10k | 2 | 3 | 88.301mb -0.01% | 1.814ms +10.46% | ±1.36% -53.70% | | RowsBench | bench_entries_on_10k | 2 | 3 | 85.413mb -0.01% | 2.793ms +10.76% | ±0.66% -32.24% | | RowsBench | bench_filter_on_10k | 2 | 3 | 85.942mb -0.01% | 19.003ms +15.57% | ±1.72% -11.36% | | RowsBench | bench_find_on_10k | 2 | 3 | 85.942mb -0.01% | 19.001ms +15.98% | ±1.01% -58.89% | | RowsBench | bench_find_one_on_10k | 10 | 3 | 83.846mb -0.01% | 1.806μs +0.68% | ±2.57% -3.64% | | RowsBench | bench_first_on_10k | 10 | 3 | 83.846mb -0.01% | 0.400μs 0.00% | ±0.00% 0.00% | | RowsBench | bench_flat_map_on_1k | 2 | 3 | 93.196mb -0.01% | 12.556ms -0.35% | ±0.64% -36.79% | | RowsBench | bench_map_on_10k | 2 | 3 | 122.567mb -0.01% | 61.155ms -2.52% | ±1.18% -51.12% | | RowsBench | bench_merge_1k_on_10k | 2 | 3 | 86.462mb -0.01% | 1.189ms -5.27% | ±3.16% +783.84% | | RowsBench | bench_partition_by_on_10k | 2 | 3 | 89.808mb -0.01% | 62.805ms +2.99% | ±0.68% -42.49% | | RowsBench | bench_remove_on_10k | 2 | 3 | 88.563mb -0.01% | 3.832ms -0.87% | ±0.67% -49.78% | | RowsBench | bench_sort_asc_on_1k | 2 | 3 | 83.989mb -0.09% | 40.751ms +2.08% | ±1.88% +204.51% | | RowsBench | bench_sort_by_on_1k | 2 | 3 | 83.990mb -0.09% | 40.889ms +1.62% | ±3.39% +112.58% | | RowsBench | bench_sort_desc_on_1k | 2 | 3 | 83.989mb -0.09% | 41.098ms +2.50% | ±0.53% -39.12% | | RowsBench | bench_sort_entries_on_1k | 2 | 3 | 86.287mb -0.01% | 7.370ms -0.35% | ±0.86% -27.65% | | RowsBench | bench_sort_on_1k | 2 | 3 | 83.846mb -0.01% | 28.899ms +0.48% | ±0.67% -63.12% | | RowsBench | bench_take_1k_on_10k | 10 | 3 | 83.846mb -0.01% | 13.294μs -0.64% | ±0.36% -61.73% | | RowsBench | bench_take_right_1k_on_10k | 10 | 3 | 83.846mb -0.01% | 15.900μs +0.15% | ±0.00% -100.00% | | RowsBench | bench_unique_on_1k | 2 | 3 | 102.660mb -0.01% | 193.802ms +0.64% | ±1.60% +77.28% | | NativeEntryFactoryBench | bench_entry_factory | 1 | 3 | 116.738mb -0.01% | 520.633ms -0.52% | ±0.22% -73.29% | | NativeEntryFactoryBench | bench_entry_factory | 1 | 3 | 60.216mb -0.01% | 258.004ms -1.49% | ±1.82% +33.26% | | NativeEntryFactoryBench | bench_entry_factory | 1 | 3 | 15.151mb -0.07% | 55.540ms -1.08% | ±0.57% -65.65% | | TypeDetectorBench | bench_type_detector | 1 | 3 | 59.970mb -0.01% | 435.424ms +0.36% | ±0.15% -82.78% | | TypeDetectorBench | bench_type_detector | 1 | 3 | 14.510mb -0.03% | 87.532ms +2.14% | ±0.83% +120.59% | +-------------------------+----------------------------+------+-----+------------------+------------------+------------------+ ```