[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 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 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 made changes - 2024-10-07 10:36

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

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 ]

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

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

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 ]

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