Speed up `uuid` UDF (40x faster) #14675

simonvandel · 2025-02-14T23:09:46Z

Which issue does this PR close?

N/A

Rationale for this change

It seems to be faster to generate random u128's in bulk, and then converting them to Uuids.

However, we are not exactly using the same random number generator. Uuid::new_v4() is using getrandom. In this PR, we are using rand.

$ cargo bench -p datafusion-functions --bench uuid
uuid                    time:   [19.516 µs 19.541 µs 19.565 µs]
                        change: [-97.652% -97.648% -97.643%] (p = 0.00 < 0.05)
                        Performance has improved.

What changes are included in this PR?

Are these changes tested?

Yes, existing tests. And added a new test for UUIDv4 format.

Are there any user-facing changes?

Yes, faster uuid() UDF.

simonvandel · 2025-02-14T23:38:28Z

Oops, need to generate valid uuidv4

comphead · 2025-02-14T23:43:05Z

datafusion/functions/src/string/uuid.rs

+        let mut randoms = vec![0u128; num_rows];
+        rng.fill(&mut randoms[..]);
+
+        let values = randoms.into_iter().map(|x| Uuid::from_u128(x).to_string());


Thanks @simonvandel
I'm just curious how this is faster as under the hood it uses the same approach

pub fn new_v4() -> Uuid { // This is an optimized method for generating random UUIDs that just masks // out the bits for the version and variant and sets them both together Uuid::from_u128( crate::rng::u128() & 0xFFFFFFFFFFFF4FFFBFFFFFFFFFFFFFFF | 0x40008000000000000000, ) }

probably repeat_with().take() is slow

I tried calling Uuid::new_v4() instead of Uuid::from_u128 with thread_rng. The performance was the same as before this PR.

I think the performance comes from not having to repeatedly call the rng for bytes. Instead, num_rows*36 bytes can be rng'ed at once.

comphead · 2025-02-15T00:15:53Z

@simonvandel I'd like to ask you to create a slt test for UUID(), I know it is non guaranteed output, but we can check the v4 validity format I suppose.

UPD: something like

> SELECT REGEXP_LIKE(uuid(), 
       '^[0-9a-f]{8}-[0-9a-f]{4}-4[0-9a-f]{3}-[89ab][0-9a-f]{3}-[0-9a-f]{12}$') 
       AS is_valid;
+----------+
| is_valid |
+----------+
| true     |
+----------+

Dandandan · 2025-02-15T05:04:47Z

datafusion/functions/src/string/uuid.rs

+        let mut randoms = vec![0u128; num_rows];
+        rng.fill(&mut randoms[..]);
+
+        let values = randoms.into_iter().map(|x| Uuid::from_u128(x).to_string());


it would be nice to avoid a to_string here as well

Resolved in f4f87c8

It doubled performance :)

alamb

Thank you @simonvandel and @Dandandan and @comphead

I think this optimization makes sense

I also tested it out locally and it seems to work well 👍 -- thanks also for the additional test @simonvandel (and the idea @comphead )

DataFusion CLI v45.0.0
> select uuid() from generate_series(1, 10);
+--------------------------------------+
| uuid()                               |
+--------------------------------------+
| 40e9df43-5fb8-4159-8ce9-1ce8313983b2 |
| 1a386033-ff17-4c6d-af0a-e4a09bb7dfc9 |
| cf410b99-6fb4-40ba-ad15-caf2a832a966 |
| 7c38582c-e7d2-4881-8ace-a1acc94734b3 |
| 4d708c96-1cfd-4b28-8f76-1f72762575cf |
| dce47ffd-6522-49d0-bf76-9bb9127ef948 |
| a61dbb63-b849-49a4-99eb-eb6e614beec8 |
| 9177acdb-3cb6-4ed4-a9b8-02f6070e26c5 |
| 4f904c21-f463-40b9-b38d-3c20db7aef8a |
| 3caec5d3-cf81-4888-bc66-92487b8bb539 |
+--------------------------------------+
10 row(s) fetched.
Elapsed 0.026 seconds.

> select uuid() from generate_series(1, 10);
+--------------------------------------+
| uuid()                               |
+--------------------------------------+
| 5252b5a1-cc7b-4f2a-b7fc-8f02274ef12e |
| 6c752c96-df99-420d-a1c2-73e2f21e4383 |
| a7b8c7bf-0a15-4522-bb6a-67f2a22fb73a |
| c284478e-cf24-4d14-9427-246c144fc481 |
| d13bcef0-d008-480b-8d16-e02b10ceeaca |
| 6667939e-900f-4e56-a3a9-8dbb6259b633 |
| d21f6b5c-4579-490a-acdb-06f448fc73f3 |
| 261e6621-aaac-4e86-81c3-a5c2fabf96f8 |
| 32a6c5b4-16c5-4e78-a613-a55cec48a391 |
| 0448bbf5-39f6-4cef-9dbc-1d6a7dd2dd08 |
+--------------------------------------+
10 row(s) fetched.
Elapsed 0.007 seconds.

Looks random to me 🤷

alamb · 2025-02-15T11:10:36Z

datafusion/functions/src/string/uuid.rs

@@ -87,9 +88,25 @@ impl ScalarUDFImpl for UuidFunc {
        if !args.is_empty() {
            return internal_err!("{} function does not accept arguments", self.name());
        }
-        let values = std::iter::repeat_with(|| Uuid::new_v4().to_string()).take(num_rows);


This old code will allocate a new string, create uuid, then copy that string into the output.

Removing that allocation alone is likely to make a big difference

alamb · 2025-02-15T11:16:30Z

datafusion/functions/src/string/uuid.rs

+
+        let mut buffer = [0u8; 36];
+        for x in &mut randoms {
+            // From Uuid::new_v4(): Mask out the version and variant bits


I double checked this is the case:
https://docs.rs/uuid/latest/src/uuid/v4.rs.html#33-39

alamb · 2025-02-15T11:16:37Z

datafusion/sqllogictest/test_files/functions.slt

@@ -720,6 +720,14 @@ select count(distinct u) from uuid_table;
 ----
 2

+# must be valid uuidv4 format
+query B
+SELECT REGEXP_LIKE(uuid(),


comphead

lgtm thanks @simonvandel

comphead · 2025-02-15T19:50:31Z

Thanks everyone

github-actions bot added the functions label Feb 14, 2025

simonvandel force-pushed the uuid-speedup branch from 231ec9c to 376e960 Compare February 14, 2025 23:17

Add benchmark for uuid

00e1c9d

simonvandel force-pushed the uuid-speedup branch from 376e960 to 00e1c9d Compare February 14, 2025 23:25

comphead reviewed Feb 14, 2025

View reviewed changes

Dandandan reviewed Feb 15, 2025

View reviewed changes

simonvandel added 3 commits February 15, 2025 10:22

add test for valid v4 format

8e5928f

Speed

fde30f8

avoid to_string

f4f87c8

simonvandel force-pushed the uuid-speedup branch from a303d41 to f4f87c8 Compare February 15, 2025 10:03

github-actions bot added the sqllogictest SQL Logic Tests (.slt) label Feb 15, 2025

simonvandel changed the title ~~Speed up uuid UDF (20x faster)~~ Speed up uuid UDF (40x faster) Feb 15, 2025

alamb approved these changes Feb 15, 2025

View reviewed changes

alamb added the performance Make DataFusion faster label Feb 15, 2025

comphead approved these changes Feb 15, 2025

View reviewed changes

comphead merged commit 40bb75f into apache:main Feb 15, 2025
29 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Speed up `uuid` UDF (40x faster) #14675

Speed up `uuid` UDF (40x faster) #14675

simonvandel commented Feb 14, 2025 •

edited

Loading

simonvandel commented Feb 14, 2025

comphead Feb 14, 2025

simonvandel Feb 15, 2025

comphead commented Feb 15, 2025 •

edited

Loading

Dandandan Feb 15, 2025

simonvandel Feb 15, 2025

simonvandel Feb 15, 2025

alamb left a comment •

edited

Loading

alamb Feb 15, 2025

alamb Feb 15, 2025

alamb Feb 15, 2025

comphead left a comment

comphead commented Feb 15, 2025

Speed up uuid UDF (40x faster) #14675

Speed up uuid UDF (40x faster) #14675

Conversation

simonvandel commented Feb 14, 2025 • edited Loading

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Are these changes tested?

Are there any user-facing changes?

simonvandel commented Feb 14, 2025

Choose a reason for hiding this comment

Choose a reason for hiding this comment

comphead commented Feb 15, 2025 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alamb left a comment • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

comphead left a comment

Choose a reason for hiding this comment

comphead commented Feb 15, 2025

Speed up `uuid` UDF (40x faster) #14675

Speed up `uuid` UDF (40x faster) #14675

simonvandel commented Feb 14, 2025 •

edited

Loading

comphead commented Feb 15, 2025 •

edited

Loading

alamb left a comment •

edited

Loading