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

ALLOW FILTERING gives wrong result when SELECT lists specific columns #4121

Closed
nyh opened this Issue Jan 21, 2019 · 11 comments

Comments

Projects
None yet
4 participants
@nyh
Copy link
Contributor

nyh commented Jan 21, 2019

This issue is similar to issue #3803, which was marked solved but apparently is still partly incorrect.

On the user mailing list, temple3x@gmail.com discovered that a query like

select block from cold where date='2019-01-22' and start <=150262 and end >=150262 ALLOW FILTERING

works incorrectly (returns rows which should have been filtered out), whereas the same thing with a "select *" works correctly.

I wrote a simple unit test to reproduce this:

SEASTAR_TEST_CASE(test_allow_filtering_two_clustering_columns) {
    return do_with_cql_env_thread([] (cql_test_env& e) {
        e.execute_cql("CREATE TABLE t (p int, c1 int, c2 int, data int, PRIMARY KEY (p, c1, c2));").get();

        e.execute_cql("INSERT INTO t (p, c1, c2, data) VALUES (1, 2, 3, 1)").get();
        e.execute_cql("INSERT INTO t (p, c1, c2, data) VALUES (1, 3, 4, 2)").get();
        e.execute_cql("INSERT INTO t (p, c1, c2, data) VALUES (1, 2, 5, 3)").get();
        e.execute_cql("INSERT INTO t (p, c1, c2, data) VALUES (2, 3, 4, 4)").get();

        auto res = e.execute_cql("SELECT * FROM t WHERE p = 1 and c1 < 3 and c2 > 3 ALLOW FILTERING").get0();
        assert_that(res).is_rows().with_rows({
            {
                int32_type->decompose(1),
                int32_type->decompose(2),
                int32_type->decompose(5),
                int32_type->decompose(3)
            }
        });
        res = e.execute_cql("SELECT data FROM t WHERE p = 1 and c1 < 3 and c2 > 3 ALLOW FILTERING").get0();
        std::cout << res << "\n";
        assert_that(res).is_rows().with_rows({
            {
                int32_type->decompose(3)
            }
        });
    });
}

The first request has "select *" with restrictions on two clustering columns, and correctly returns just one row: (1, 2, 5, 3). The second request does the same request, just with "select data" instead of "select *", and should have returned just one row with data=3. But it fails because it also returns the first row, with data=1, which doesn't match the second filtering criterion (c2 > 3 is false for it).

CC: @psarna

@nyh

This comment has been minimized.

Copy link
Contributor Author

nyh commented Jan 21, 2019

The above was a unit test (which we can use directly as a regression test), but here is a more interactive example of the same thing, in cqlsh, for the curious:

CREATE KEYSPACE ks WITH REPLICATION = { 'class' : 'SimpleStrategy', 'replication_factor' : 1 };
USE ks;
CREATE TABLE t (p int, c1 int, c2 int, data int, PRIMARY KEY (p, c1, c2));
INSERT INTO t (p, c1, c2, data) VALUES (1, 2, 3, 1);
INSERT INTO t (p, c1, c2, data) VALUES (1, 3, 4, 2);
INSERT INTO t (p, c1, c2, data) VALUES (1, 2, 5, 3);
INSERT INTO t (p, c1, c2, data) VALUES (2, 3, 4, 4);
SELECT * FROM t WHERE p = 1 and c1 < 3 and c2 > 3 ALLOW FILTERING;

 p | c1 | c2 | data
---+----+----+------
 1 |  2 |  5 |    3

(1 rows)

SELECT data FROM t WHERE p = 1 and c1 < 3 and c2 > 3 ALLOW FILTERING;
 
 data
------
    1
    3

(2 rows)

Note both queries have exactly the same filter, but the second request, differing only in the selected columns, returns too many rows. The broken filtering in the second request appears to be obeying the first partition key restriction (p=1) and the first clustering key restriction (c1 < 3) but not the second one (c2 > 3).

I forgot to mention this, but I reproduced this bug on today's master.

@tzach

This comment has been minimized.

Copy link
Contributor

tzach commented Jan 21, 2019

Just reproduce on Scylla 3.0 as well

@nyh

This comment has been minimized.

Copy link
Contributor Author

nyh commented Jan 22, 2019

I'll take a stab at solving this issue (very sad how github doesn't let me change the fields like "assigned to" myself).

@psarna

This comment has been minimized.

Copy link
Member

psarna commented Jan 22, 2019

FYI: It's in statement_restrictions::get_column_defs_for_filtering. The code checks if there are any clustering columns that do not form a prefix, but it's not enough - prefix in a form of c1 = 3 and c2 > 3 is fine and doesn't need filtering, but c1 < 3 and c2 > 3 does, because inequality relation is only accepted as the last part of the prefix.
So, statement_restrictions::get_column_defs_for_filtering will qualify this set of restrictions as not needing filtering (when in fact they do), and will not add these columns as needed for post filtering.

@psarna

This comment has been minimized.

Copy link
Member

psarna commented Jan 22, 2019

Also, cql3/restrictions/single_column_primary_key_restrictions.hh has single_column_primary_key_restrictions<clustering_key>::needs_filtering which performs a very similar check correctly (that's one of the reasons it works fine with SELECT *).

@nyh

This comment has been minimized.

Copy link
Contributor Author

nyh commented Jan 22, 2019

@psarna yes, thanks, I know that get_column_defs_for_filtering is the bug, I just haven't yet figure out where the actual problem is. This function doesn't check any "prefix" as far as I can see, it calls _clustering_columns_restrictions->needs_filtering(), I guess that's where the code is wrong?

@psarna

This comment has been minimized.

Copy link
Member

psarna commented Jan 22, 2019

The clustering key part does:

        if (_clustering_columns_restrictions->needs_filtering(*_schema)) {
            column_id first_non_prefix_id = _schema->clustering_key_columns().begin()->id +
                    _clustering_columns_restrictions->prefix_size(_schema);
            for (auto&& cdef : _clustering_columns_restrictions->get_column_defs()) {
                if ((cdef->id >= first_non_prefix_id) && (!column_uses_indexing(cdef))) {
                    column_defs_for_filtering.emplace_back(cdef);
                }
            }
        }

and what is missing is more strict checking - not just a prefix, but whether it's a prefix without slicing (like in single_column_primary_key_restrictions<clustering_key>::needs_filtering)

@nyh

This comment has been minimized.

Copy link
Contributor Author

nyh commented Jan 22, 2019

Right. Thanks! I'll fix it.

@tzach tzach added this to the 3.1 milestone Jan 22, 2019

@tzach tzach added bug CQL labels Jan 22, 2019

@nyh

This comment has been minimized.

Copy link
Contributor Author

nyh commented Jan 22, 2019

@psarna what drives me crazy now is how to get through all the layers of templates and virtual functions to get to the information I need :-)

@psarna

This comment has been minimized.

Copy link
Member

psarna commented Jan 22, 2019

@nyh #3815 is all about that, unfortunately filtering was much higher priority than this, so it's still in the same sorry state of virtual functions and templates everywhere.

At the very least, single_column_primary_key_restrictions and primary_key_restrictions in general should be detemplatized, since they have lots of specifications for both partition key and clustering key anyway, so it pretty much only increases compilation time. I have all these improvements somewhere very deep in my backlog.

@psarna

This comment has been minimized.

Copy link
Member

psarna commented Jan 22, 2019

Actually, after I spend some more time on view building and hints, I'll have another go at this topic, prehaps just a small step of detemplatizing these key restrictions.

@slivne slivne added the Backport 3.0 label Jan 22, 2019

avikivity added a commit that referenced this issue Jan 23, 2019

cql3: really ensure retrieval of columns for filtering
Commit fd422c9 aimed to fix
issue #3803. In that issue, if a query SELECTed only certain columns but
did filtering (ALLOW FILTERING) over other unselected columns, the filtering
didn't work. The fix involved adding the columns being filtered to the set
of columns we read from disk, so they can be filtered.

But that commit included an optimization: If you have clustering keys
c1 and c2, and the query asks for a specific partition key and c1 < 3 and
c2 > 3, the "c1 < 3" part does NOT need to be filtered because it is already
done as a slice (a contiguous read from disk). The committed code erroneously
concluded that both c1 and c2 don't need to be filtered, which was wrong
(c2 *does* need to be read and filtered).

In this patch, we fix this optimization. Previously, we used the "prefix
length", which in the above example was 2 (both c1 and c2 were filtered)
but we need a new and more elaborate function,
num_prefix_columns_that_need_not_be_filtered(), to determine we can only
skip filtering of 1 (c1) and cannot skip the second.

Fixes #4121. This patch also adds a unit test to confirm this.

Signed-off-by: Nadav Har'El <nyh@scylladb.com>

Message-Id: <20190123131212.6269-1-nyh@scylladb.com>
(cherry picked from commit 76f1fcc)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment