Repository navigation
Commit 33028d5
authored
Optimize NULL-containing string IN list pruning (apache#24954)
## Which issue does this PR close?
- Closes apache#24711.
## Rationale for this change
apache#24781 added compact pruning for non-NULL `NOT IN` lists. Issue apache#24711
still needs support for NULL-containing lists.
Large string lists can create expensive per-value pruning expressions.
The compact path reduces this cost when `max_in_list_size` permits the
rewrite.
NULL values require special handling. Filter pruning treats FALSE and
UNKNOWN equally, but full-match detection must keep these results
separate.
## What changes are included in this PR?
This PR makes these changes:
- Supports compact pruning for large string `IN` lists that contain
NULL.
- Treats `NOT IN` with NULL as unable to match rows.
- Treats all-NULL `IN` lists as unable to match rows.
- Records whether a pruning predicate is safe for full-match inversion.
- Uses the same configured list-size cap when it builds the inverse
predicate.
- Adds unit tests, Parquet integration tests, documentation, and
benchmarks.
## What is the testing strategy for this PR?
The tests cover positive and negative lists, all-NULL lists, nested `OR`
expressions, configured caps, and Parquet full-match detection.
These commands passed:
```shell
cargo test -p datafusion-pruning
cargo test -p datafusion-datasource-parquet
cargo test -p datafusion --test parquet_integration string_in_list_pruning
cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
```
Focused benchmarks also cover compact `IN` and constant-false `NOT IN`
expressions with NULL.
## Are there any user-facing changes?
Large string `IN` and `NOT IN` lists that contain NULL can now use
compact pruning when the cap permits it.
Query results and configuration defaults do not change.
This PR adds two non-breaking `PruningPredicate` accessors:
`max_in_list_size` and `can_be_inverted_for_full_match`.1 parent 565f933 commit 33028d5
7 files changed
Lines changed: 302 additions & 113 deletions
File tree
- datafusion
- common/src
- core/tests/parquet
- datasource-parquet/src
- pruning
- benches
- src
- sqllogictest/test_files
- docs/source/user-guide
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1373 | 1373 | | |
1374 | 1374 | | |
1375 | 1375 | | |
1376 | | - | |
1377 | | - | |
1378 | | - | |
1379 | | - | |
| 1376 | + | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
| 1380 | + | |
| 1381 | + | |
1380 | 1382 | | |
1381 | 1383 | | |
1382 | 1384 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
440 | 440 | | |
441 | 441 | | |
442 | 442 | | |
443 | | - | |
| 443 | + | |
444 | 444 | | |
445 | | - | |
| 445 | + | |
446 | 446 | | |
447 | 447 | | |
448 | 448 | | |
449 | 449 | | |
450 | 450 | | |
451 | | - | |
452 | | - | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
453 | 454 | | |
454 | 455 | | |
455 | 456 | | |
456 | 457 | | |
457 | 458 | | |
458 | | - | |
459 | 459 | | |
| 460 | + | |
460 | 461 | | |
461 | 462 | | |
462 | 463 | | |
| |||
475 | 476 | | |
476 | 477 | | |
477 | 478 | | |
478 | | - | |
| 479 | + | |
479 | 480 | | |
480 | 481 | | |
481 | 482 | | |
482 | 483 | | |
483 | | - | |
484 | | - | |
485 | 484 | | |
486 | 485 | | |
487 | 486 | | |
| |||
490 | 489 | | |
491 | 490 | | |
492 | 491 | | |
493 | | - | |
494 | | - | |
495 | | - | |
496 | | - | |
497 | | - | |
498 | | - | |
499 | | - | |
500 | | - | |
501 | | - | |
502 | | - | |
503 | | - | |
504 | | - | |
505 | | - | |
506 | | - | |
507 | | - | |
508 | | - | |
509 | | - | |
510 | | - | |
511 | | - | |
512 | | - | |
513 | | - | |
514 | | - | |
515 | | - | |
516 | | - | |
517 | | - | |
518 | | - | |
519 | | - | |
520 | | - | |
521 | | - | |
522 | | - | |
523 | | - | |
524 | | - | |
525 | | - | |
526 | | - | |
527 | | - | |
528 | | - | |
529 | | - | |
530 | | - | |
531 | | - | |
532 | | - | |
533 | | - | |
534 | | - | |
535 | | - | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
| 523 | + | |
| 524 | + | |
| 525 | + | |
| 526 | + | |
| 527 | + | |
| 528 | + | |
| 529 | + | |
| 530 | + | |
| 531 | + | |
| 532 | + | |
| 533 | + | |
| 534 | + | |
| 535 | + | |
| 536 | + | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
| 542 | + | |
| 543 | + | |
| 544 | + | |
| 545 | + | |
| 546 | + | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
| 552 | + | |
| 553 | + | |
| 554 | + | |
| 555 | + | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
536 | 566 | | |
537 | 567 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
395 | 395 | | |
396 | 396 | | |
397 | 397 | | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
| 402 | + | |
398 | 403 | | |
399 | 404 | | |
400 | 405 | | |
| |||
432 | 437 | | |
433 | 438 | | |
434 | 439 | | |
| 440 | + | |
435 | 441 | | |
436 | 442 | | |
437 | 443 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
24 | 24 | | |
25 | 25 | | |
26 | 26 | | |
27 | | - | |
28 | | - | |
29 | | - | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
30 | 31 | | |
31 | 32 | | |
32 | 33 | | |
| |||
188 | 189 | | |
189 | 190 | | |
190 | 191 | | |
| 192 | + | |
191 | 193 | | |
192 | 194 | | |
| 195 | + | |
193 | 196 | | |
194 | 197 | | |
| 198 | + | |
195 | 199 | | |
196 | 200 | | |
| 201 | + | |
197 | 202 | | |
198 | 203 | | |
199 | 204 | | |
| |||
209 | 214 | | |
210 | 215 | | |
211 | 216 | | |
| 217 | + | |
| 218 | + | |
212 | 219 | | |
213 | 220 | | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
214 | 230 | | |
215 | 231 | | |
216 | 232 | | |
217 | 233 | | |
218 | 234 | | |
| 235 | + | |
| 236 | + | |
219 | 237 | | |
220 | 238 | | |
| 239 | + | |
| 240 | + | |
221 | 241 | | |
222 | 242 | | |
223 | 243 | | |
| |||
239 | 259 | | |
240 | 260 | | |
241 | 261 | | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
242 | 266 | | |
243 | 267 | | |
244 | 268 | | |
| |||
248 | 272 | | |
249 | 273 | | |
250 | 274 | | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
251 | 282 | | |
252 | 283 | | |
253 | 284 | | |
254 | 285 | | |
255 | 286 | | |
| 287 | + | |
256 | 288 | | |
257 | 289 | | |
| 290 | + | |
258 | 291 | | |
259 | 292 | | |
| 293 | + | |
260 | 294 | | |
261 | 295 | | |
| 296 | + | |
262 | 297 | | |
263 | 298 | | |
264 | 299 | | |
| |||
269 | 304 | | |
270 | 305 | | |
271 | 306 | | |
272 | | - | |
273 | | - | |
274 | | - | |
275 | | - | |
276 | | - | |
277 | | - | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
278 | 318 | | |
| 319 | + | |
279 | 320 | | |
280 | | - | |
| 321 | + | |
281 | 322 | | |
282 | 323 | | |
283 | 324 | | |
284 | 325 | | |
285 | 326 | | |
286 | 327 | | |
287 | | - | |
| 328 | + | |
288 | 329 | | |
289 | 330 | | |
290 | 331 | | |
| |||
296 | 337 | | |
297 | 338 | | |
298 | 339 | | |
299 | | - | |
300 | | - | |
301 | | - | |
302 | | - | |
303 | | - | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
| 346 | + | |
| 347 | + | |
| 348 | + | |
| 349 | + | |
| 350 | + | |
| 351 | + | |
| 352 | + | |
| 353 | + | |
| 354 | + | |
304 | 355 | | |
305 | 356 | | |
306 | | - | |
| 357 | + | |
307 | 358 | | |
308 | 359 | | |
309 | 360 | | |
| |||
0 commit comments