Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[YCQL] Unable to use range query on a column which is clustered in the index but a partition column in the primary key #7069

Closed
kmuthukk opened this issue Feb 2, 2021 · 5 comments
Assignees
Labels
area/ycql Yugabyte CQL (YCQL) priority/high High Priority

Comments

@kmuthukk
Copy link
Collaborator

kmuthukk commented Feb 2, 2021

Test Case:

CREATE KEYSPACE k;
USE k;

CREATE TABLE test (
  id int,
  scope text,
  metadata map<text, text>,
  PRIMARY KEY (id)
) WITH default_time_to_live = 0
  AND transactions = {'enabled': 'true'};

CREATE INDEX test_index ON test (scope, id)
    WITH CLUSTERING ORDER BY (id ASC)
    AND transactions = {'enabled': 'true'};

INSERT into test (id, scope, metadata) VALUES (1, 'test', {'a' : '1', 'b' : '1'});
INSERT into test (id, scope, metadata) VALUES (2, 'test', {'a' : '2', 'b' : '2'});
INSERT into test (id, scope, metadata) VALUES (3, 'test', {'a' : '3', 'b' : '3'});
INSERT into test (id, scope, metadata) VALUES (4, 'test', {'a' : '4', 'b' : '4'});
INSERT into test (id, scope, metadata) VALUES (5, 'test', {'a' : '5', 'b' : '5'});

Now, a query of this form is expected to use the index because scope is provided, and we should be able to do a range scan on the id which is a clustering column in the index. However, we run into this error message:

ycqlsh:k> SELECT id FROM test WHERE scope = 'test' AND id > 2;
SyntaxException: Invalid CQL Statement. Partition column cannot be used in this expression
SELECT id FROM test WHERE scope = 'test' AND id > 2;
                                             ^^
 (ql error -12)
@kmuthukk kmuthukk added priority/high High Priority area/ycql Yugabyte CQL (YCQL) labels Feb 2, 2021
@kmuthukk
Copy link
Collaborator Author

kmuthukk commented Feb 2, 2021

A kludgy stop-gap workaround until we can roll out the fix/enhancement to support this, would be to have a duplicate column id2 whose contents are the same as id column. But the index is built on (scope, id2) instead of (scope, id).

CREATE TABLE test (
  id int,
  id2 int,
  scope text,
  metadata map<text, text>,
  PRIMARY KEY (id)
) WITH default_time_to_live = 0
  AND transactions = {'enabled': 'false'};

CREATE INDEX test_index ON test (scope, id2)
    WITH CLUSTERING ORDER BY (id2 ASC)
    AND transactions = {'enabled': 'false', 'consistency_level': 'user_enforced'};


INSERT into test (id, id2, scope, metadata) VALUES (1, 1, 'test', {'a' : '1', 'b' : '1'});
INSERT into test (id, id2, scope, metadata) VALUES (2, 2, 'test', {'a' : '2', 'b' : '2'});
INSERT into test (id, id2, scope, metadata) VALUES (3, 3, 'test', {'a' : '3', 'b' : '3'});
INSERT into test (id, id2, scope, metadata) VALUES (4, 4, 'test', {'a' : '4', 'b' : '4'});
INSERT into test (id, id2, scope, metadata) VALUES (5, 5, 'test', {'a' : '5', 'b' : '5'});

ycqlsh:k1> explain SELECT id FROM test WHERE scope = 'test' AND id2 > 2 limit 2;

QUERY PLAN
------------------------------------------------
 Index Only Scan using k1.test_index on k1.test
   Key Conditions: (scope = 'test')
   Filter: (id2 > 2)

ycqlsh:k1> SELECT id FROM test WHERE scope = 'test' AND id2 > 2 limit 2;

id
----
  3
  4 

@tedyu
Copy link
Contributor

tedyu commented Feb 2, 2021

Looks like the original query would work when "Partition column cannot be used in this expression" error is dropped from WhereExprState::AnalyzeColumnOp().

Maybe there is some consideration for prohibiting partition column from appearing in inequality conditions.

@tedyu
Copy link
Contributor

tedyu commented Feb 3, 2021

I tried to refine the condition where the error is raised.

      if (col_desc->is_hash() && !sem_context->selecting_from_index()) {
        return sem_context->Error(expr, "Partition column cannot be used in this expression",
            ErrorCode::CQL_STATEMENT_INVALID);

For the given example, sem_context->selecting_from_index() is false and the error is still raised.

I will keep investigating.

@tedyu
Copy link
Contributor

tedyu commented Feb 3, 2021

Looking at PTSelectStmt::Analyze(), this is the current order:

  RETURN_NOT_OK(AnalyzeWhereClause(sem_context));
...
    RETURN_NOT_OK(AnalyzeIndexes(sem_context));
    if (child_select_ && child_select_->covers_fully_) {
      return Status::OK();

Effort so far has been on AnalyzeWhereClause(). However, the child select is determined later, in AnalyzeIndexes().
One possibility is to extract hash column check to after AnalyzeIndexes() returns.

@m-iancu m-iancu assigned tedyu and unassigned m-iancu Feb 3, 2021
@tedyu
Copy link
Contributor

tedyu commented Feb 16, 2021

cql-clustered-child.txt

@nocaway nocaway self-assigned this Feb 25, 2021
nocaway added a commit that referenced this issue Apr 1, 2021
Summary:
There are several issues with choosing the right INDEX scan when processing query.

**(A) Issue Background**
When analyzing SELECT, there should be three clear steps.
1. Analyze references: This step collect and validate the references to tables, columns, and operators.
2. Analyze scan plan: This step chooses an index to scan and save the scan-spec.
3. Analyze clauses: This step analyze clauses according to the chosen scan spec and prepare for protobuf-code generation.

It is common practice in compiler to decorate the parse tree when processing step (1) and use the decorated structures to process steps (2) and (3).  Unfortunately, YugaByte's existing implementation did not follow this design. It duplicates the parse tree for SELECT. One parse tree represents the outer select, and the other, the nested select. Then the two parse-trees are compiled together under the same context for the same SELECT command. This adds complexity and is the source of lots of bugs.

Additionally, existing code chose not to process LIMIT and OFFSET clause for SELECT if it has nested INDEX query.  This is a bug which is fixed in a different diff.
#7055

**(B) Pseudo Code**
The following pseudo code shows how the existing code is fixed with the two steps (1) and (2) above. We traverse the given tree to choose SCAN path first and then use the parse-tree duo structure for step (3).
```
Analyze(SelectNode) {
  // Traverse the entire SELECT node to collect references for table, column, clauses, expressions, operators.
  // Collect all necessary INDEX information into SelectScanInfo
  AnalyzeReferences (SelectNode, SelectScanInfo);

  // Analyze SelectScanInfo against the created indexes.
  for (each table_index) {
    scan_path = Analyze(SelectScanInfo, table_index)
    Append(scan_list, scan_path);
  }
  scan_spec = BestIndex(scan_list);

  // Duplicate SelectNode to create a nested node to query from chosen index.
  child_node = Duplicate(SelectNode);

  // Prepare for protobuf-code generation.
  FurtherAnalysis(child_node, nested_scan_path);
  FurtherAnalysis(parent_node, primary_read_path);
}
```
**(C) Solution Notes**
- This diff does not fix the duo of parse-tree issue because it'd be a lot of code changes. If CQL is extended to support more advance features, we will have to change the design.
- This diff only fixed INDEX-selection step. That is, it analyzes just ONE parse-tree for index selection, chooses the correct INDEX, and then uses the existing code with the parse-tree-duo for the rest of the analysis.
- Although the index-selection-process now traverses only ONE parse-tree, it continues to use the existing code for ORDER_BY analysis. To do so, the diff traverses the same ORDER_BY tree node one time for each  INDEX (PRIMARY and SECONDARY) and check if that index can be a match. That is, it does not create extra structures to analyze ORDER BY clause as a normal compiler would do, it just uses YugaByte's existing code but in a different way.

**(D) Notes on Implementation and Coding**
The general idea is that the user's query
```SELECT <select_list> FROM <table> WHERE <user's primary key cond> AND <user's regular column cond>```
will be executed as
```SELECT <select-list> FROM <table> WHERE primary_key IN (SELECT primary_key FROM <index> WHERE <user's primary key cond>) AND <user's regular column cond>```
The nested index query will seek a PRIMARY KEY value, and for each PRIMARY KEY, the outer select will read one row from PRIMARY table.

Coding
- First, we analyze WHERE, IF, ORDER BY clauses to find the right INDEX and write the result to a scan-spec variable.
- Later, we uses the chosen scan-spec to create a parse-tree duplicate as the existing code.
- The rest of the code is kept the same.

Some notes on coding
- Class SelectScanInfo is added.  It is used to collect all information that is needed for choosing an INDEX.
- Class SelectScanSpec is added to represent the chosen scan path.
- Filter-condition on PRIMARY KEY(hash, range) is voided in the outer SELECT because its condition is moved to the nested SELECT as described above.
- Move "filtering_exprs_" attribute from PTDmlStmt to PTSelectStmt class because we only need this for processing SELECT. Therefore, class IfExprState is removed as its work is now in SELECT.

Test Plan: Add TestIndexSelection.java

Reviewers: zyu, oleg, mihnea, pjain

Reviewed By: pjain

Subscribers: yql

Differential Revision: https://phabricator.dev.yugabyte.com/D10912
@nocaway nocaway closed this as completed May 7, 2021
YintongMa pushed a commit to YintongMa/yugabyte-db that referenced this issue May 26, 2021
…lecting optimal scan path

Summary:
There are several issues with choosing the right INDEX scan when processing query.

**(A) Issue Background**
When analyzing SELECT, there should be three clear steps.
1. Analyze references: This step collect and validate the references to tables, columns, and operators.
2. Analyze scan plan: This step chooses an index to scan and save the scan-spec.
3. Analyze clauses: This step analyze clauses according to the chosen scan spec and prepare for protobuf-code generation.

It is common practice in compiler to decorate the parse tree when processing step (1) and use the decorated structures to process steps (2) and (3).  Unfortunately, YugaByte's existing implementation did not follow this design. It duplicates the parse tree for SELECT. One parse tree represents the outer select, and the other, the nested select. Then the two parse-trees are compiled together under the same context for the same SELECT command. This adds complexity and is the source of lots of bugs.

Additionally, existing code chose not to process LIMIT and OFFSET clause for SELECT if it has nested INDEX query.  This is a bug which is fixed in a different diff.
yugabyte#7055

**(B) Pseudo Code**
The following pseudo code shows how the existing code is fixed with the two steps (1) and (2) above. We traverse the given tree to choose SCAN path first and then use the parse-tree duo structure for step (3).
```
Analyze(SelectNode) {
  // Traverse the entire SELECT node to collect references for table, column, clauses, expressions, operators.
  // Collect all necessary INDEX information into SelectScanInfo
  AnalyzeReferences (SelectNode, SelectScanInfo);

  // Analyze SelectScanInfo against the created indexes.
  for (each table_index) {
    scan_path = Analyze(SelectScanInfo, table_index)
    Append(scan_list, scan_path);
  }
  scan_spec = BestIndex(scan_list);

  // Duplicate SelectNode to create a nested node to query from chosen index.
  child_node = Duplicate(SelectNode);

  // Prepare for protobuf-code generation.
  FurtherAnalysis(child_node, nested_scan_path);
  FurtherAnalysis(parent_node, primary_read_path);
}
```
**(C) Solution Notes**
- This diff does not fix the duo of parse-tree issue because it'd be a lot of code changes. If CQL is extended to support more advance features, we will have to change the design.
- This diff only fixed INDEX-selection step. That is, it analyzes just ONE parse-tree for index selection, chooses the correct INDEX, and then uses the existing code with the parse-tree-duo for the rest of the analysis.
- Although the index-selection-process now traverses only ONE parse-tree, it continues to use the existing code for ORDER_BY analysis. To do so, the diff traverses the same ORDER_BY tree node one time for each  INDEX (PRIMARY and SECONDARY) and check if that index can be a match. That is, it does not create extra structures to analyze ORDER BY clause as a normal compiler would do, it just uses YugaByte's existing code but in a different way.

**(D) Notes on Implementation and Coding**
The general idea is that the user's query
```SELECT <select_list> FROM <table> WHERE <user's primary key cond> AND <user's regular column cond>```
will be executed as
```SELECT <select-list> FROM <table> WHERE primary_key IN (SELECT primary_key FROM <index> WHERE <user's primary key cond>) AND <user's regular column cond>```
The nested index query will seek a PRIMARY KEY value, and for each PRIMARY KEY, the outer select will read one row from PRIMARY table.

Coding
- First, we analyze WHERE, IF, ORDER BY clauses to find the right INDEX and write the result to a scan-spec variable.
- Later, we uses the chosen scan-spec to create a parse-tree duplicate as the existing code.
- The rest of the code is kept the same.

Some notes on coding
- Class SelectScanInfo is added.  It is used to collect all information that is needed for choosing an INDEX.
- Class SelectScanSpec is added to represent the chosen scan path.
- Filter-condition on PRIMARY KEY(hash, range) is voided in the outer SELECT because its condition is moved to the nested SELECT as described above.
- Move "filtering_exprs_" attribute from PTDmlStmt to PTSelectStmt class because we only need this for processing SELECT. Therefore, class IfExprState is removed as its work is now in SELECT.

Test Plan: Add TestIndexSelection.java

Reviewers: zyu, oleg, mihnea, pjain

Reviewed By: pjain

Subscribers: yql

Differential Revision: https://phabricator.dev.yugabyte.com/D10912
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area/ycql Yugabyte CQL (YCQL) priority/high High Priority
Projects
None yet
Development

No branches or pull requests

4 participants