Skip to content

Comments

refactor: change some hashbrown RawTable uses to HashTable (round 2)#13524

Merged
crepererum merged 3 commits intoapache:mainfrom
crepererum:crepererum/issue13256_b
Dec 4, 2024
Merged

refactor: change some hashbrown RawTable uses to HashTable (round 2)#13524
crepererum merged 3 commits intoapache:mainfrom
crepererum:crepererum/issue13256_b

Conversation

@crepererum
Copy link
Contributor

@crepererum crepererum commented Nov 22, 2024

Which issue does this PR close?

For #13433, but only parts of it.

Rationale for this change

Prepare hashbrown 0.15 upgrade.

What changes are included in this PR?

  • HashTableAllocExt
  • a few migrations

Are these changes tested?

Existing tests pass.

Are there any user-facing changes?

No.

@github-actions github-actions bot added the physical-expr Changes to the physical-expr crates label Nov 22, 2024
crepererum
crepererum commented Nov 22, 2024
View reviewed changes
datafusion/physical-plan/src/aggregates/group_values/row.rs
}
std::mem::swap(&mut new_group_values, &mut group_values);

// SAFETY: self.map outlives iterator and is not modified concurrently
Copy link
Contributor Author

@crepererum crepererum Nov 22, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Picking this one, but this pattern occurs multiple times:

That SAFETY statement is just plain wrong: while iterating over the map, we erase elements from it. That is THE prime example for "concurrent modification of containers" and why Rust's lifetimes/reference system prevents that. I'm kinda surprised that this hasn't exploded yet.

@crepererum
Copy link
Contributor Author

crepererum commented Nov 22, 2024

The test failure (full logs here):

2024-11-22T12:00:01.8774000Z External error: query result mismatch:
2024-11-22T12:00:01.8776864Z [SQL] select make_array(make_array(1)) x UNION ALL SELECT make_array(arrow_cast(make_array(-1), 'LargeList(Int8)')) x;
2024-11-22T12:00:01.8778565Z [Diff] (-expected|+actual)
2024-11-22T12:00:01.8778975Z -   [[-1]]
2024-11-22T12:00:01.8779248Z -   [[1]]
2024-11-22T12:00:01.8779488Z +   [[1]]
2024-11-22T12:00:01.8779735Z +   [[-1]]
2024-11-22T12:00:01.8780003Z at test_files/union.slt:775

Is the order of UNION ALL even defined?

@Dandandan
Copy link
Contributor

Dandandan commented Nov 22, 2024

The test failure (full logs here):

2024-11-22T12:00:01.8774000Z External error: query result mismatch:
2024-11-22T12:00:01.8776864Z [SQL] select make_array(make_array(1)) x UNION ALL SELECT make_array(arrow_cast(make_array(-1), 'LargeList(Int8)')) x;
2024-11-22T12:00:01.8778565Z [Diff] (-expected|+actual)
2024-11-22T12:00:01.8778975Z -   [[-1]]
2024-11-22T12:00:01.8779248Z -   [[1]]
2024-11-22T12:00:01.8779488Z +   [[1]]
2024-11-22T12:00:01.8779735Z +   [[-1]]
2024-11-22T12:00:01.8780003Z at test_files/union.slt:775

Is the order of UNION ALL even defined?

It isn't / shouldn't be AFAIK

@Dandandan
Copy link
Contributor

Dandandan commented Nov 25, 2024

Test was fixed in #13547

@Dandandan
Copy link
Contributor

Dandandan commented Nov 25, 2024 •
edited
Loading

Changes look good, can we run some benchmark?

@crepererum crepererum force-pushed the crepererum/issue13256_b branch from 8d3ca50 to 655bb3d Compare December 2, 2024 12:10
@alamb
Copy link
Contributor

alamb commented Dec 4, 2024

I will run benchmarks

alamb
alamb approved these changes Dec 4, 2024
View reviewed changes
Copy link
Contributor

@alamb alamb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for working on this @crepererum 🙏 and for the review @Dandandan

My benchmark run show no significant difference in my measurements

--------------------
Benchmark clickbench_1.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query        ┃  main_base ┃ crepererum_issue13256_b ┃        Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 0     │     0.69ms │                  0.70ms │     no change │
│ QQuery 1     │    74.34ms │                 74.80ms │     no change │
│ QQuery 2     │   128.56ms │                129.12ms │     no change │
│ QQuery 3     │   137.65ms │                137.99ms │     no change │
│ QQuery 4     │   983.51ms │               1008.79ms │     no change │
│ QQuery 5     │  1077.25ms │               1092.78ms │     no change │
│ QQuery 6     │    66.04ms │                 66.01ms │     no change │
│ QQuery 7     │    84.05ms │                 81.62ms │     no change │
│ QQuery 8     │  1055.63ms │               1088.56ms │     no change │
│ QQuery 9     │  1389.05ms │               1366.73ms │     no change │
│ QQuery 10    │   315.62ms │                315.54ms │     no change │
│ QQuery 11    │   350.14ms │                349.13ms │     no change │
│ QQuery 12    │  1085.67ms │               1104.52ms │     no change │
│ QQuery 13    │  1559.67ms │               1529.49ms │     no change │
│ QQuery 14    │  1013.55ms │               1037.34ms │     no change │
│ QQuery 15    │  1131.21ms │               1137.18ms │     no change │
│ QQuery 16    │  2108.99ms │               2146.87ms │     no change │
│ QQuery 17    │  1927.83ms │               2000.34ms │     no change │
│ QQuery 18    │  4072.99ms │               4220.87ms │     no change │
│ QQuery 19    │   125.13ms │                125.87ms │     no change │
│ QQuery 20    │  1384.71ms │               1351.71ms │     no change │
│ QQuery 21    │  1725.11ms │               1731.10ms │     no change │
│ QQuery 22    │  4297.71ms │               4219.14ms │     no change │
│ QQuery 23    │ 10051.68ms │               9978.79ms │     no change │
│ QQuery 24    │   676.04ms │                662.25ms │     no change │
│ QQuery 25    │   592.05ms │                579.24ms │     no change │
│ QQuery 26    │   750.21ms │                740.54ms │     no change │
│ QQuery 27    │  2085.26ms │               2066.92ms │     no change │
│ QQuery 28    │ 13592.24ms │              13758.34ms │     no change │
│ QQuery 29    │   589.33ms │                575.83ms │     no change │
│ QQuery 30    │  1058.22ms │               1072.75ms │     no change │
│ QQuery 31    │  1116.99ms │               1123.70ms │     no change │
│ QQuery 32    │  3966.33ms │               3958.08ms │     no change │
│ QQuery 33    │  4118.32ms │               4251.35ms │     no change │
│ QQuery 34    │  4127.26ms │               4284.10ms │     no change │
│ QQuery 35    │  1335.66ms │               1401.46ms │     no change │
│ QQuery 36    │   279.13ms │                280.80ms │     no change │
│ QQuery 37    │   179.19ms │                191.29ms │  1.07x slower │
│ QQuery 38    │   189.74ms │                188.54ms │     no change │
│ QQuery 39    │   507.36ms │                496.50ms │     no change │
│ QQuery 40    │    86.52ms │                 86.86ms │     no change │
│ QQuery 41    │    82.57ms │                 78.23ms │ +1.06x faster │
│ QQuery 42    │    96.37ms │                 93.43ms │     no change │
└──────────────┴────────────┴─────────────────────────┴───────────────┘
--------------------
Benchmark clickbench_extended.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┓
┃ Query        ┃  main_base ┃ crepererum_issue13256_b ┃    Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━┩
│ QQuery 0     │  2616.05ms │               2656.28ms │ no change │
│ QQuery 1     │   768.66ms │                759.74ms │ no change │
│ QQuery 2     │  1520.15ms │               1525.95ms │ no change │
│ QQuery 3     │   736.90ms │                716.34ms │ no change │
│ QQuery 4     │ 12290.21ms │              12253.70ms │ no change │
│ QQuery 5     │ 18882.98ms │              19339.49ms │ no change │
└──────────────┴────────────┴─────────────────────────┴───────────┘
--------------------
Benchmark clickbench_partitioned.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━┓
┃ Query        ┃  main_base ┃ crepererum_issue13256_b ┃       Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━┩
│ QQuery 0     │     2.27ms │                  2.31ms │    no change │
│ QQuery 1     │    40.86ms │                 42.68ms │    no change │
│ QQuery 2     │    99.41ms │                101.10ms │    no change │
│ QQuery 3     │   105.82ms │                107.33ms │    no change │
│ QQuery 4     │   912.48ms │                932.39ms │    no change │
│ QQuery 5     │   932.55ms │                946.37ms │    no change │
│ QQuery 6     │    35.68ms │                 36.18ms │    no change │
│ QQuery 7     │    44.92ms │                 45.18ms │    no change │
│ QQuery 8     │   992.36ms │               1047.04ms │ 1.06x slower │
│ QQuery 9     │  1332.22ms │               1352.60ms │    no change │
│ QQuery 10    │   286.57ms │                291.61ms │    no change │
│ QQuery 11    │   329.27ms │                325.90ms │    no change │
│ QQuery 12    │   977.72ms │                964.00ms │    no change │
│ QQuery 13    │  1433.26ms │               1455.66ms │    no change │
│ QQuery 14    │   871.22ms │                883.98ms │    no change │
│ QQuery 15    │  1118.00ms │               1084.07ms │    no change │
│ QQuery 16    │  1985.56ms │               1997.37ms │    no change │
│ QQuery 17    │  1808.17ms │               1837.13ms │    no change │
│ QQuery 18    │  3932.35ms │               4008.86ms │    no change │
│ QQuery 19    │    93.24ms │                 96.37ms │    no change │
│ QQuery 20    │  1247.59ms │               1233.37ms │    no change │
│ QQuery 21    │  1487.30ms │               1467.18ms │    no change │
│ QQuery 22    │  2625.24ms │               2635.53ms │    no change │
│ QQuery 23    │  8641.57ms │               8514.93ms │    no change │
│ QQuery 24    │   518.85ms │                497.01ms │    no change │
│ QQuery 25    │   424.50ms │                422.18ms │    no change │
│ QQuery 26    │   578.49ms │                572.19ms │    no change │
│ QQuery 27    │  1827.42ms │               1830.38ms │    no change │
│ QQuery 28    │ 12999.73ms │              13048.48ms │    no change │
│ QQuery 29    │   525.24ms │                534.30ms │    no change │
│ QQuery 30    │   891.65ms │                901.06ms │    no change │
│ QQuery 31    │   939.15ms │                955.63ms │    no change │
│ QQuery 32    │  3878.81ms │               3787.85ms │    no change │
│ QQuery 33    │  3892.96ms │               3955.76ms │    no change │
│ QQuery 34    │  3901.67ms │               3960.14ms │    no change │
│ QQuery 35    │  1282.81ms │               1317.85ms │    no change │
│ QQuery 36    │   229.45ms │                236.91ms │    no change │
│ QQuery 37    │    95.41ms │                 94.21ms │    no change │
│ QQuery 38    │   130.10ms │                132.25ms │    no change │
│ QQuery 39    │   432.79ms │                443.89ms │    no change │
│ QQuery 40    │    58.16ms │                 56.40ms │    no change │
│ QQuery 41    │    47.15ms │                 48.55ms │    no change │
│ QQuery 42    │    62.84ms │                 65.08ms │    no change │
└──────────────┴────────────┴─────────────────────────┴──────────────┘
--------------------
Benchmark tpch_sf1.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query        ┃ main_base ┃ crepererum_issue13256_b ┃        Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1     │  228.38ms │                227.79ms │     no change │
│ QQuery 2     │  112.54ms │                115.45ms │     no change │
│ QQuery 3     │  127.05ms │                126.53ms │     no change │
│ QQuery 4     │   80.58ms │                 82.23ms │     no change │
│ QQuery 5     │  162.71ms │                160.40ms │     no change │
│ QQuery 6     │   42.19ms │                 58.91ms │  1.40x slower │
│ QQuery 7     │  210.22ms │                206.61ms │     no change │
│ QQuery 8     │  162.94ms │                152.35ms │ +1.07x faster │
│ QQuery 9     │  230.90ms │                244.31ms │  1.06x slower │
│ QQuery 10    │  212.76ms │                205.23ms │     no change │
│ QQuery 11    │   96.69ms │                 95.20ms │     no change │
│ QQuery 12    │  111.59ms │                115.83ms │     no change │
│ QQuery 13    │  207.61ms │                208.17ms │     no change │
│ QQuery 14    │   72.29ms │                 71.52ms │     no change │
│ QQuery 15    │  121.95ms │                126.59ms │     no change │
│ QQuery 16    │   72.63ms │                 69.59ms │     no change │
│ QQuery 17    │  221.69ms │                215.65ms │     no change │
│ QQuery 18    │  350.26ms │                298.38ms │ +1.17x faster │
│ QQuery 19    │  114.20ms │                112.13ms │     no change │
│ QQuery 20    │  125.56ms │                132.27ms │  1.05x slower │
│ QQuery 21    │  259.30ms │                263.83ms │     no change │
│ QQuery 22    │   64.92ms │                 69.56ms │  1.07x slower │
└──────────────┴───────────┴─────────────────────────┴───────────────┘

datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
if let Some(remaining) = group_index.checked_sub(n) {
self.emit_group_index_list_buffer.push(remaining);
}
self.map.retain(|(_exist_hash, group_idx_view)| {
Copy link
Contributor

@alamb alamb Dec 4, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

💯 for removing the unsafe

@crepererum crepererum merged commit dd242b9 into apache:main Dec 4, 2024
@crepererum
Copy link
Contributor Author

crepererum commented Dec 4, 2024

thanks for the reviews and tests 🙂

@Dandandan
Copy link
Contributor

Dandandan commented Dec 5, 2024 •
edited
Loading

│ QQuery 6 │ 42.19ms │ 58.91ms │ 1.40x slower │

This seems quite big, is this reproducible?

@Dandandan
Copy link
Contributor

Dandandan commented Dec 5, 2024

FYI @alamb

@alamb
Copy link
Contributor

alamb commented Dec 6, 2024

│ QQuery 6 │ 42.19ms │ 58.91ms │ 1.40x slower │

This seems quite big, is this reproducible?

I'll re-run

In general, I found the timing accuracy of my test machine (GCP VM) is not great for <100ms queries.

@alamb alamb mentioned this pull request Dec 6, 2024
Closed
4 tasks
@Dandandan
Copy link
Contributor

Dandandan commented Dec 6, 2024

1.40x

Hm, that's interesting! The results are not super reliable for me but mostly the noise is in the 5-7% range (running locally).

@alamb
Copy link
Contributor

alamb commented Dec 6, 2024

Here is my next run (this time it seems to be faster)

--------------------
Benchmark tpch_sf1.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query        ┃ main_base ┃ crepererum_issue13256_b ┃        Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1     │  212.59ms │                211.28ms │     no change │
│ QQuery 2     │  114.88ms │                110.85ms │     no change │
│ QQuery 3     │  128.11ms │                129.03ms │     no change │
│ QQuery 4     │   82.16ms │                 80.01ms │     no change │
│ QQuery 5     │  156.43ms │                158.55ms │     no change │
│ QQuery 6     │   58.67ms │                 41.48ms │ +1.41x faster │
│ QQuery 7     │  215.74ms │                207.64ms │     no change │
│ QQuery 8     │  161.71ms │                145.80ms │ +1.11x faster │
│ QQuery 9     │  232.17ms │                244.68ms │  1.05x slower │
│ QQuery 10    │  208.44ms │                202.66ms │     no change │
│ QQuery 11    │   92.92ms │                 96.30ms │     no change │
│ QQuery 12    │  100.40ms │                102.16ms │     no change │
│ QQuery 13    │  208.88ms │                205.97ms │     no change │
│ QQuery 14    │   70.13ms │                 70.42ms │     no change │
│ QQuery 15    │  106.56ms │                112.44ms │  1.06x slower │
│ QQuery 16    │   68.22ms │                 69.56ms │     no change │
│ QQuery 17    │  213.89ms │                212.62ms │     no change │
│ QQuery 18    │  315.85ms │                317.30ms │     no change │
│ QQuery 19    │  111.47ms │                105.21ms │ +1.06x faster │
│ QQuery 20    │  123.67ms │                139.11ms │  1.12x slower │
│ QQuery 21    │  270.95ms │                268.65ms │     no change │
│ QQuery 22    │   67.97ms │                 65.32ms │     no change │
└──────────────┴───────────┴─────────────────────────┴───────────────┘

@Dandandan
Copy link
Contributor

Dandandan commented Dec 6, 2024

It's as if it pingpongs between two machine "versions".
I'm running it myself as well locally

@Dandandan
Copy link
Contributor

Dandandan commented Dec 6, 2024

I found no real changes:

Comparing old_version and new
--------------------
Benchmark tpch_sf1.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query        ┃ old_version ┃      new ┃        Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1     │    126.64ms │ 126.31ms │     no change │
│ QQuery 2     │     55.58ms │  57.52ms │     no change │
│ QQuery 3     │     57.28ms │  57.43ms │     no change │
│ QQuery 4     │     41.79ms │  41.65ms │     no change │
│ QQuery 5     │     80.09ms │  78.55ms │     no change │
│ QQuery 6     │     21.41ms │  21.35ms │     no change │
│ QQuery 7     │     99.77ms │  94.68ms │ +1.05x faster │
│ QQuery 8     │     78.80ms │  79.46ms │     no change │
│ QQuery 9     │    117.79ms │ 116.57ms │     no change │
│ QQuery 10    │    104.93ms │ 107.49ms │     no change │
│ QQuery 11    │     42.57ms │  42.55ms │     no change │
│ QQuery 12    │     56.13ms │  54.79ms │     no change │
│ QQuery 13    │    119.79ms │ 122.90ms │     no change │
│ QQuery 14    │     39.99ms │  39.66ms │     no change │
│ QQuery 15    │     48.21ms │  48.11ms │     no change │
│ QQuery 16    │     37.15ms │  36.31ms │     no change │
│ QQuery 17    │     99.31ms │ 102.42ms │     no change │
│ QQuery 18    │    166.78ms │ 161.30ms │     no change │
│ QQuery 19    │     66.80ms │  66.67ms │     no change │
│ QQuery 20    │     62.38ms │  62.50ms │     no change │
│ QQuery 21    │    127.97ms │ 130.89ms │     no change │
│ QQuery 22    │     36.35ms │  34.54ms │     no change │
└──────────────┴─────────────┴──────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┓
┃ Benchmark Summary          ┃           ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━┩
│ Total Time (old_version)   │ 1687.51ms │
│ Total Time (new)           │ 1683.64ms │
│ Average Time (old_version) │   76.70ms │
│ Average Time (new)         │   76.53ms │
│ Queries Faster             │         1 │
│ Queries Slower             │         0 │
│ Queries with No Change     │        21 │
└────────────────────────────┴───────────┘

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@alamb alamb alamb approved these changes

Assignees

No one assigned

Labels

physical-expr Changes to the physical-expr crates

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@crepererum @Dandandan @alamb