[MDEV-34665] Simplify IN predicate processing for NULL-aware materialization involving only one column - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Major
Resolution: Fixed
Affects Version/s: 10.5
Fix Version/s: 10.5.28, 10.6.21, 10.11.11, 11.4.5
Component/s: Optimizer
Labels:
None

Description

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

We have predicate

left_expr IN (SELECT <subq1>)

where left_expr is a scalar (not a tuple). The logic in this case looks as follows:

if (left_expr is NULL) {

  if (subq1 produced any rows) {

    // note that we don't care if subq1 has produced

    // NULLs or not.

    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.

  } else {

    NULL IN ({empty-set}) -> FALSE.

} else {

  // left_expr is a non-NULL value

  if (subq1 output has a match for left_expr) {

    left_expr IN (..., left_expr ...) -> TRUE

  } else {

    // no "known" matches.

    if (subq1 output has a NULL) {

      left_expr IN ( ... NULL ...) ->

       (NULL could have been a match or not)

       -> NULL.

    } else {

      // subq1 didn't produce any "UNKNOWNs" so

      // we're positive there weren't any matches

      -> FALSE.

Attachments

Issue Links

relates to

MDEV-34041 Additional information for materialized subqueries must be displayed in EXPLAIN/ANALYZE FORMAT=JSON

Closed

Activity

Ascending order - Click to sort in descending order

Oleg Smirnov created issue - 2024-07-29 10:54

Oleg Smirnov made changes - 2024-07-29 11:00

Field	Original Value	New Value
Description	Looks like it is possible to skip complex logic of building sorted Ordered_key structures of subselect_rowid_merge_engine when there is only one key in the materialized subquery. In this scenario subselect_partial_match_engine::exec() can choose: - index lookup when left_expr of the IN predicate is not NULL - return NULL (unknown) when left_expr is NULL and the materialized table has at least one NULL value - return FALSE otherwise (todo: is it correct if there are no rows at all?)	Looks like it is possible to skip complex logic of building sorted Ordered_key structures of subselect_rowid_merge_engine when there is only one key in the materialized subquery. In this scenario subselect_partial_match_engine::exec() can choose: - index lookup when left_expr of the IN predicate is not NULL - return NULL (unknown) when left_expr is NULL and the materialized table has at least one NULL value - return TRUE otherwise (todo: is it correct when there are no rows in the table?)

Oleg Smirnov made changes - 2024-07-29 11:48

Description

Looks like it is possible to skip complex logic of building sorted Ordered_key structures of subselect_rowid_merge_engine when there is only one key in the materialized subquery.
In this scenario subselect_partial_match_engine::exec() can choose:
- index lookup when left_expr of the IN predicate is not NULL
- return NULL (unknown) when left_expr is NULL and the materialized table has at least one NULL value
- return TRUE otherwise (todo: is it correct when there are no rows in the table?)

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

The logic in this case looks as follows:

if (left_expr is NULL) {
  if (subq1 produced any rows) {
    // note that we don't care if subq1 has produced
    // NULLs or not.
    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.
  } else {
    NULL IN ({empty-set}) -> FALSE.
  }
} else {
  // left_expr is a non-NULL value
  if (subq1 output has a match for left_expr) {
    left_expr IN (..., left_expr ...) -> TRUE
  } else {
    // no "known" matches.
    if (subq1 output has a NULL) {
      left_expr IN ( ... NULL ...) ->
       (NULL could have been a match or not)
       -> NULL.
    } else {
      // subq1 didn't produce any "UNKNOWNs" so
      // we're positive there weren't any matches
      -> FALSE.
    }
  }
}

Oleg Smirnov made changes - 2024-07-29 11:48

Description

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

The logic in this case looks as follows:
{code}
if (left_expr is NULL) {
  if (subq1 produced any rows) {
    // note that we don't care if subq1 has produced
    // NULLs or not.
    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.
  } else {
    NULL IN ({empty-set}) -> FALSE.
  }
} else {
  // left_expr is a non-NULL value
  if (subq1 output has a match for left_expr) {
    left_expr IN (..., left_expr ...) -> TRUE
  } else {
    // no "known" matches.
    if (subq1 output has a NULL) {
      left_expr IN ( ... NULL ...) ->
       (NULL could have been a match or not)
       -> NULL.
    } else {
      // subq1 didn't produce any "UNKNOWNs" so
      // we're positive there weren't any matches
      -> FALSE.
    }
  }
}
{code}

Oleg Smirnov made changes - 2024-07-29 11:55

Description

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

The logic in this case looks as follows:
{code}
if (left_expr is NULL) {
  if (subq1 produced any rows) {
    // note that we don't care if subq1 has produced
    // NULLs or not.
    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.
  } else {
    NULL IN ({empty-set}) -> FALSE.
  }
} else {
  // left_expr is a non-NULL value
  if (subq1 output has a match for left_expr) {
    left_expr IN (..., left_expr ...) -> TRUE
  } else {
    // no "known" matches.
    if (subq1 output has a NULL) {
      left_expr IN ( ... NULL ...) ->
       (NULL could have been a match or not)
       -> NULL.
    } else {
      // subq1 didn't produce any "UNKNOWNs" so
      // we're positive there weren't any matches
      -> FALSE.
    }
  }
}
{code}

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

The logic in this case looks as follows.
We have predicate
{code}
left_expr IN (SELECT <subq1>)
{code}
where left_expr is a scalar (not a tuple)

{code}
if (left_expr is NULL) {
  if (subq1 produced any rows) {
    // note that we don't care if subq1 has produced
    // NULLs or not.
    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.
  } else {
    NULL IN ({empty-set}) -> FALSE.
  }
} else {
  // left_expr is a non-NULL value
  if (subq1 output has a match for left_expr) {
    left_expr IN (..., left_expr ...) -> TRUE
  } else {
    // no "known" matches.
    if (subq1 output has a NULL) {
      left_expr IN ( ... NULL ...) ->
       (NULL could have been a match or not)
       -> NULL.
    } else {
      // subq1 didn't produce any "UNKNOWNs" so
      // we're positive there weren't any matches
      -> FALSE.
    }
  }
}
{code}

Oleg Smirnov made changes - 2024-07-29 11:55

Summary

NULL-aware materialization: implement short-curcuit for the case of only one key

NULL-aware materialization: implement short-curcuit for scalar left_expr in IN-predicate

Oleg Smirnov made changes - 2024-07-29 11:55

Description

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

The logic in this case looks as follows.
We have predicate
{code}
left_expr IN (SELECT <subq1>)
{code}
where left_expr is a scalar (not a tuple)

{code}
if (left_expr is NULL) {
  if (subq1 produced any rows) {
    // note that we don't care if subq1 has produced
    // NULLs or not.
    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.
  } else {
    NULL IN ({empty-set}) -> FALSE.
  }
} else {
  // left_expr is a non-NULL value
  if (subq1 output has a match for left_expr) {
    left_expr IN (..., left_expr ...) -> TRUE
  } else {
    // no "known" matches.
    if (subq1 output has a NULL) {
      left_expr IN ( ... NULL ...) ->
       (NULL could have been a match or not)
       -> NULL.
    } else {
      // subq1 didn't produce any "UNKNOWNs" so
      // we're positive there weren't any matches
      -> FALSE.
    }
  }
}
{code}

Looks like it is possible to skip the building sorted Ordered_key structures for subselect_rowid_merge_engine when there is only one key in the materialized subquery.

We have predicate
{code}
left_expr IN (SELECT <subq1>)
{code}
where left_expr is a scalar (not a tuple). The logic in this case looks as follows:
{code}
if (left_expr is NULL) {
  if (subq1 produced any rows) {
    // note that we don't care if subq1 has produced
    // NULLs or not.
    NULL IN (<some values>) -> UNKNOWN, i.e. NULL.
  } else {
    NULL IN ({empty-set}) -> FALSE.
  }
} else {
  // left_expr is a non-NULL value
  if (subq1 output has a match for left_expr) {
    left_expr IN (..., left_expr ...) -> TRUE
  } else {
    // no "known" matches.
    if (subq1 output has a NULL) {
      left_expr IN ( ... NULL ...) ->
       (NULL could have been a match or not)
       -> NULL.
    } else {
      // subq1 didn't produce any "UNKNOWNs" so
      // we're positive there weren't any matches
      -> FALSE.
    }
  }
}
{code}

Oleg Smirnov made changes - 2024-08-01 12:13

Fix Version/s

10.5 [ 23123 ]

Oleg Smirnov made changes - 2024-08-01 12:31

Summary

NULL-aware materialization: implement short-curcuit for scalar left_expr in IN-predicate

Simplify IN predicate processing for materialization involving only one column

Oleg Smirnov made changes - 2024-08-01 12:34

Summary

Simplify IN predicate processing for materialization involving only one column

Simplify IN predicate processing for NULL-aware materialization involving only one column

Oleg Smirnov made changes - 2024-08-01 12:36

Status

Open [ 1 ]

In Progress [ 3 ]

Oleg Smirnov added a comment - 2024-08-01 15:13

psergei, can you please review the PR?

Oleg Smirnov added a comment - 2024-08-01 15:13 psergei , can you please review the PR ?

Oleg Smirnov made changes - 2024-08-01 15:13

Assignee	Oleg Smirnov [ JIRAUSER50405 ]	Sergei Petrunia [ psergey ]
Status	In Progress [ 3 ]	In Review [ 10002 ]

Sergei Petrunia made changes - 2024-08-30 07:35

Link

This issue relates to ~~MDEV-34041~~ [ ~~MDEV-34041~~ ]

Sergei Petrunia made changes - 2024-10-02 11:51

Link

This issue relates to TODO-4513 [ TODO-4513 ]

Sergei Petrunia added a comment - 2024-10-04 10:42

Reviewing...

Checking what would subselect_table_scan_engine do when computing

/*col1=*/NULL  IN  (SELECT ... FROM non_empty_select_without_nulls)

It would get into subselect_table_scan_engine::partial_match; would start a table scan and then would find it has a match after reading just one row.

Sergei Petrunia added a comment - 2024-10-04 10:42 Reviewing... Checking what would subselect_table_scan_engine do when computing /*col1=*/NULL IN (SELECT ... FROM non_empty_select_without_nulls) It would get into subselect_table_scan_engine::partial_match ; would start a table scan and then would find it has a match after reading just one row.

Sergei Petrunia added a comment - 2024-10-04 14:17

Review input provided in the PR.

Sergei Petrunia added a comment - 2024-10-04 14:17 Review input provided in the PR.

Sergei Petrunia made changes - 2024-10-04 14:17

Assignee	Sergei Petrunia [ psergey ]	Oleg Smirnov [ JIRAUSER50405 ]
Status	In Review [ 10002 ]	Stalled [ 10000 ]

Oleg Smirnov made changes - 2024-10-07 10:36

Status

Stalled [ 10000 ]

In Progress [ 3 ]

Oleg Smirnov added a comment - 2024-10-07 10:36

Code review fixes are pushed.

Oleg Smirnov added a comment - 2024-10-07 10:36 Code review fixes are pushed.

Oleg Smirnov made changes - 2024-10-07 10:36

Assignee	Oleg Smirnov [ JIRAUSER50405 ]	Sergei Petrunia [ psergey ]
Status	In Progress [ 3 ]	In Review [ 10002 ]

Sergei Petrunia added a comment - 2024-10-18 15:21

Review input provided

Sergei Petrunia added a comment - 2024-10-18 15:21 Review input provided

Sergei Petrunia made changes - 2024-10-18 15:21

Assignee	Sergei Petrunia [ psergey ]	Oleg Smirnov [ JIRAUSER50405 ]
Status	In Review [ 10002 ]	Stalled [ 10000 ]

Oleg Smirnov made changes - 2024-10-23 13:26

Status

Stalled [ 10000 ]

In Testing [ 10301 ]

Oleg Smirnov made changes - 2024-10-23 13:26

Assignee

Oleg Smirnov [ JIRAUSER50405 ]

Lena Startseva [ JIRAUSER50478 ]

Oleg Smirnov added a comment - 2024-10-23 13:28

lstartseva, could you please test the branch bb-10.5-~~MDEV-34665~~? psergei has already approved the pull request.

Oleg Smirnov added a comment - 2024-10-23 13:28 lstartseva , could you please test the branch bb-10.5- MDEV-34665 ? psergei has already approved the pull request.

Lena Startseva added a comment - 2024-10-30 05:44

Testinп done. Ok to push. But, before pushing it will be better to add some cases for "update" and "delete". This will allow you to check that everything is fine after merging in later versions.

Lena Startseva added a comment - 2024-10-30 05:44 Testinп done. Ok to push. But, before pushing it will be better to add some cases for "update" and "delete". This will allow you to check that everything is fine after merging in later versions.

Lena Startseva made changes - 2024-10-30 05:44

Assignee	Lena Startseva [ JIRAUSER50478 ]	Oleg Smirnov [ JIRAUSER50405 ]
Status	In Testing [ 10301 ]	Stalled [ 10000 ]

Oleg Smirnov added a comment - 2024-10-30 11:54

OK, added tests for UPDATE and DELETE and pushed to 10.5.

Oleg Smirnov added a comment - 2024-10-30 11:54 OK, added tests for UPDATE and DELETE and pushed to 10.5.

Oleg Smirnov made changes - 2024-10-30 11:54

Fix Version/s		10.5.27 [ 29902 ]
Fix Version/s	10.5 [ 23123 ]
Resolution		Fixed [ 1 ]
Status	Stalled [ 10000 ]	Closed [ 6 ]

JiraAutomate made changes - 2024-10-30 11:54

Fix Version/s		10.6.20 [ 29903 ]
Fix Version/s		10.11.10 [ 29904 ]
Fix Version/s		11.2.6 [ 29906 ]
Fix Version/s		11.4.4 [ 29907 ]

Oleg Smirnov added a comment - 2024-11-01 03:18

ralf.gebhardt, do you mean this commit won't make it into the upcoming releases? No problem for me to update the version but I don't know where the cut off point is. Who may know it for sure?

Oleg Smirnov added a comment - 2024-11-01 03:18 ralf.gebhardt , do you mean this commit won't make it into the upcoming releases? No problem for me to update the version but I don't know where the cut off point is. Who may know it for sure?

Daniel Bartholomew made changes - 2024-11-01 18:34

Fix Version/s		10.5.28 [ 29952 ]
Fix Version/s		10.6.21 [ 29953 ]
Fix Version/s		10.11.11 [ 29954 ]
Fix Version/s		11.4.5 [ 29956 ]
Fix Version/s	10.5.27 [ 29902 ]
Fix Version/s	10.6.20 [ 29903 ]
Fix Version/s	10.11.10 [ 29904 ]
Fix Version/s	11.2.6 [ 29906 ]
Fix Version/s	11.4.4 [ 29907 ]

People

Assignee:: Oleg Smirnov

Reporter:: Oleg Smirnov

Votes:: 0 Vote for this issue

Watchers:: 5 Start watching this issue

Dates

Created:: 2024-07-29 10:54

Updated:: 2024-11-06 00:15

Resolved:: 2024-10-30 11:54

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server

Details

Description

Attachments

Issue Links

Activity

People

Dates

Git Integration