[ https://issues.apache.org/jira/browse/CASSANDRA-11500?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16082241#comment-16082241 ]
ZhaoYang edited comment on CASSANDRA-11500 at 7/25/17 9:24 AM: --------------------------------------------------------------- h3. Relation: base -> view First of all, I think all of us should agree on what cases view row should exists. IMO, there are two main cases: 1. base pk and view pk are the same (order doesn't matter) and view has no filter conditions or only conditions on base pk. (filter condition mean: {{c = 1}} in view's where clause. filter condition is not a concern here, since no previous view data to be cleared.) view row exists if any of following is true: * a. base row pk has live livenessInfo(timestamp) and base row pk satifies view's filter conditions if any. * b. or one of base row columns selected in view has live timestamp (via update) and base row pk satifies view's filter conditions if any. this is handled by existing mechanism of liveness and tombstone since all info are included in view row * c. or one of base row columns not selected in view has live timestamp (via update) and base row pk satifies view's filter conditions if any. Those unselected columns' timestamp/ttl/cell-deletion info are not currently stored on view row. 2. base column used in view pk or view has filter conditions on base non-key column which can also lead to entire view row being wiped. view row exists if any of following is true: * a. base row pk has live livenessInfo(timestamp) && base column used in view pk is not null but no timestamp && conditions are satisfied. ( pk having live livenesInfo means it is not deleted by tombstone) * b. or base row column in view pk has timestamp (via update) && conditions are satisfied. eg. if base column used in view pk is TTLed, entire view row should be wiped. Next thing is to model "view's tombstone and livenessInfo" to maintain view data based on above cases. h3. Previous known issues: (I might miss some issues, feel free to ping me..) ttl * view row is not wiped when TTLed on base column used in view pk or TTLed on base non-key column with filter condition * cells with same timestamp, merging ttls are not deterministic. partial update on base columns not selected in view * it results in no view data. because of current update semantics, no view updates are generated * corresponding view row' liveness is not depending on liveness of base columns filter conditions or base column used in view pk causes * view row is shadowed after a few modification on base column used in view pk if the base non-key column has TS greater than base pk's ts and view key column's ts. (as mentioned by sylvain: we need to be able to re-insert an entry when a prior one had been deleted need to be careful to hanlde timestamp tie) tombstone merging is not commutative * in current code, shadowable tombstone doesn't co-exist with regular tombstone sstabledump not supporting current shadowable tombstone h3. Model I can think of two ways to ship all required base column info to view: * make base columns that are not selected in view as "virtual cell" and store their imestamp/ttl to view without their actual values. so we can reuse current ts/tb/ttl mechanism with additional validation logic to check if a view row is alive. * or storing those info on view's livenessInfo/deletion with addition merge logic to make sure view liveness/deletion are ordered properly even in the case of timestamp tie. It's like a replacement stragy which uses inserted view row to replace old view row. (In regular table, reconciliation is at cell level. need to research more about the concurrent view update cases, fow now, it looks fine). It also implies that every modification on base, view row will get replaced entirely.. FIXME in one node, if multiple ViewLivenessInfo having same timestamp, we do replacement.. how about cross node merging? how about partial update on normal columns that are part of view normal column? always send entire row to do replacement.... I will go ahead with ~second way since there is an existing shadowable tombstone mechanism.~ View PrimaryKey LivenessInfo, its timestamp, payloads, merging {code} ColumnInfo: // generated from base column as it is. 0. timestamp 1. ttl 2. localDeletionTime: could be used to represent tombstone or TTLed depends on if there is ttl supersedes(): if timestamps are different, greater timestamp supersedes; if timestamps are same, greater localDeletionTime supersedes. Row: // keyOrConditions and unselected are always merged with another row's during row merging process // base column that are used in view pk or has filter condition on non-pk column. // if any column is not live, entire view row is wiped. // if a column in base is filtered and not selected, it's stored here. // during base modification, if a view row is removed due to base-column-in-view-pk or filter-contiions, then no deletion is issue, // the virtual cell tombstone is added to Row's keyOrConditions. 2. Map<ColumnIdentifier, ColumnInfo> keyOrConditions; // if any column is live // during base modification, if base columns not selected in view is modified, then no deletion is issue, // the virtual cell tombstone is added to Row's keyOrConditions. 3. Map<ColumnIdentifier, ColumnInfo> unselected; // to determina if a row is dead isAliveRow(): if any colummn in {{keyOrConditions}} is TTLed or tombstone(dead) or not existed, false if {{timestamp or ttl}} are alive, true if any column in {{unselected}} is alive, true otherwise check any columns in view row are alive merge(Row): // merge 3 parts separates a. for LivenessInfo/Deletion/Cells are merged as it is b. for keyOrConditions, merge by comparing ColumnInfo.supersedes() c. for unselected, same above ShadowableDeletion(now removed) Row.Deletion(now removed) {code} h3. Examples (*_TL;DR;_* validate the model using different tests in each issue) Reinserting previous deleted view row(11500) {code} CREATE TABLE t (k int PRIMARY KEY, a int, b int); CREATE MATERIALIZED VIEW mv AS SELECT * FROM t WHERE k IS NOT NULL AND a IS NOT NULL PRIMARY KEY (k, a); {{q1}} INSERT INTO t(k, a, b) VALUES (1, 1, 1) USING TIMESTAMP 0; {{q2}} UPDATE t USING TIMESTAMP 10 SET b = 2 WHERE k = 1; {{q3}} UPDATE t USING TIMESTAMP 2 SET a = 2 WHERE k = 1; {{q4}} UPDATE t USING TIMESTAMP 3 SET a = 1 WHERE k = 1; After {{q1}}: base: k=1@0, a=1@0, b=1@0 // 'k' is having value '1' with timestamp '0' view: sstable1: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=1@0 //VC-> virtualCells After {{q2}}: base(merged): (k=1@0, a=1@0, b=2@10) view: sstable1: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=1@0 sstable2: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(no_ts) b=2@10 // the VC here could be ommitted since it's not changed or merged: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=2@10 After {{q3}}: base(merged): (k=1@0, a=2@2, b=2@10) view: sstable1: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=1@0 sstable2: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(no_ts) b=2@10 sstable3: VC(keyOrConditions{a@tb0}, unselected:{}) (k=1&&a=1) // row deletion caused by switch_entry VC(keyOrConditions{a@2}, unselected:{}) (k=1&&a=2)@liveness(ts@0) b=2@10 or merged: VC(keyOrConditions{a@tb0}, unselected:{}) (k=1&&a=1) VC(keyOrConditions{a@2}, unselected:{}) (k=1&&a=2)@liveness(ts@0) b=2@10 After {{q4}}: base(merged): (k=1@0, a=1@3, b=2@10) view: sstable1: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=1@0 sstable2: VC(keyOrConditions{a@0}, unselected:{}) (k=1&&a=1)@liveness(no_ts) b=2@10 sstable3: VC(keyOrConditions{a@tb0}, unselected:{}) (k=1&&a=1) VC(keyOrConditions{a@2}, unselected:{}) (k=1&&a=2)@liveness(ts@0) b=2@10 sstable4: VC(keyOrConditions{a@3}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=2@10 VC(keyOrConditions{a@tb2}, unselected:{}) (k=1&&a=2) or merged: VC(keyOrConditions{a@3}, unselected:{}) (k=1&&a=1)@liveness(ts@0) b=2@10 VC(keyOrConditions{a@tb2}, unselected:{}) (k=1&&a=2) {code} based column used in view key is TTLed (13657) {code} CREATE TABLE t (k int, a int, b int, PRIMARY KEY (k)); CREATE MATERIALIZED VIEW mv AS SELECT * FROM t WHERE k IS NOT NULL AND a IS NOT NULL PRIMARY KEY (a, k); {{q1}} INSERT INTO t (k) VALUES (1); {{q2}} UPDATE t USING TTL 5 SET a = 10 WHERE k = 1; {{q3}} UPDATE t SET b = 100 WHERE k = 1; After q1: base: k=1@t1 view: no view updates generated because no existing view data After q2: base(merged): k=1@t1, a=10@(t2, ttl@5) view: VC(keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) (k=1&&a=10)@liveness(ts@t1) After q2: base(merged): k=1@t1, a=10@(t2, ttl@5), b=100@t3 view: sstable1: VC(keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) (k=1&&a=10)@liveness(ts@t1) sstable2: VC(keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) (k=1&&a=10) b=100@t3 or merged: VC(keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) (k=1&&a=10)@liveness(ts@t1) b=100@t3 5 seconds later, view row is considered removed becuase {{keyOrConditions-a}} is TTLed. {code} View row expires too fast with unselected base column (13127) {code} CREATE TABLE ks.base (p int, c int, v int, PRIMARY KEY (p, c)); CREATE MATERIALIZED VIEW ks.mv AS SELECT p, c FROM base WHERE p IS NOT NULL AND c IS NOT NULL PRIMARY KEY (c, p); {{q1}} INSERT INTO ks.base (p, c) VALUES (0, 0) USING TTL 3; {{q2}} UPDATE ks.base USING TTL 100 SET v = 0 WHERE p = 0 and c = 0; After q1: base: (p=0&&c=0)@(ts@t1, ttl@3) view: VC(keyOrConditions{}, unselected:{}) (c=p&&p=0)@liveness(ts@t1, ttl@3) After q2: base(merged): (p=0&&c=0)@(ts@t1, ttl@3) v=0@(ts@t2, ttl@100) view: sstable1: VC(keyOrConditions{}, unselected:{}) (c=p&&p=0)@liveness(ts@t1, ttl@3) sstable2: VC(keyOrConditions{}, unselected:{v@(ts@t2, ttl@100) }) (c=p&&p=0)@liveness(ts@t1, ttl@3) or merged: VC(keyOrConditions{}, unselected:{v@(ts@t2, ttl@100) }) (c=p&&p=0)@liveness(ts@t1, ttl@3) after 5 second, base: p,c,v-> 0,0,0 view: c,p -> 0,0 because {{unselected has not TTLed column v}} {code} Partial update unselected columns in base (13127) {code} CREATE TABLE base (k int, c int, a int, b int, PRIMARY KEY (k, c)); CREATE MATERIALIZED VIEW mv AS SELECT k,c FROM base WHERE k IS NOT NULL AND c IS NOT NULL PRIMARY KEY (k,c); {{q1}} UPDATE base USING TIMESTAMP 10 SET b=1 WHERE k=1 AND c=1; {{q2}} DELETE b FROM base USING TIMESTAMP 11 WHERE k=1 AND c=1; {{q3}} UPDATE base USING TIMESTAMP 1 SET a=1 WHERE k=1 AND c=1; After q1: base: (k=1&&c=1), b=1@10 view: VC(keyOrConditions{}, unselected:{b@(ts@10)}) (k=1&&c=1) After q2: base(merged): (k=1&&c=1), b@tombstone(ts@11) view: sstable1: VC(keyOrConditions{}, unselected:{b@(ts@10)}) (k=1&&c=1) sstable2: VC(keyOrConditions{}, unselected:{b@(tb@11)}) (k=1&&c=1) or merged: VC(keyOrConditions{}, unselected:{b@(tb@11)}) (k=1&&c=1) // no view row After q3: base(merged): (k=1&&c=1), b@tombstone(ts@11), c=1@1 view: sstable1: VC(keyOrConditions{}, unselected:{b@(ts@10)}) (k=1&&c=1) sstable2: VC(keyOrConditions{}, unselected:{b@(tb@11)}) (k=1&&c=1) sstable3: VC(keyOrConditions{}, unselected:{c@(ts@1)}) (k=1&&c=1) or merged: VC(keyOrConditions{}, unselected:{b@(tb@11), c@(ts@1)}) (k=1&&c=1) // view row a live since one of {{unselected}} is live {code} merging should be commutative (13409) {code} create table ks.base (p int primary key, v1 int, v2 int); create materialized view ks.my_view as select * from ks.base where p is not null and v1 is not null primary key (v1, p); {{q1}} insert into ks.base (p, v1, v2) values (3, 1, 3) using timestamp 1; {{q2}} delete from ks.base using timestamp 2 where p = 3; {{q3} insert into ks.base (p, v1) values (3, 1) using timestamp 3; at the end: base(merged): p=3@partition_deletion@2, livenesInfo@3, v1=1 view: sstable1: VC(keyOrConditions{v1:(ts@0) }, unselected:{}) (v1=3&&p=3)@livenes(ts@1), v2=3 sstable2: (v1=3&&p=3)@tombstone(ts@2) sstable3: VC(keyOrConditions{v1:(ts@3) }, unselected:{}) (v1=3&&p=3)@livenes(ts@3, keyOrConditions{v1:(ts@3) }, unselected:{}) or merged: VC(keyOrConditions{v1:(ts@3) }, unselected:{}) (v1=3&&p=3)@livenes(ts@3, keyOrConditions{v1:(ts@3) }, unselected:{}) @tombstone(ts@2) {code} {code} create table ks.base (p int primary key, v1 int, v2 int); create materialized view ks.my_view as select * from ks.base where p is not null and v1 is not null primary key (v1, p); {{q1}} insert into base (p, v1, v2) values (3, 1, 3) using timestamp 1 {{q2}} update base using timestamp 2 set v2 = null where p = 3 {{q3}} update base using timestamp 3 set v1 = 2 where p = 3 {{q4}} update base using timestamp 4 set v1 = 1 where p = 3 at the end: base(merged): p=3@1, v1=1@4, v2@tombstone(ts@3) view: sstable1: VC(keyOrConditions{v1:(ts@1) }, unselected:{}) (v1=1&&p=3)@livenes(ts@1), v2=3 sstable2: (v1=1&&p=3) v2@tombstone(ts@2) sstable3: VC(keyOrConditions{v1:(tb@1) }, unselected:{}) (v1=1&&p=3) VC(keyOrConditions{v1:(ts@3) }, unselected:{}) (v1=2&&p=3)@livenes(ts@1), v2@tombstone(ts@2) sstable4: VC(keyOrConditions{v1:(ts@4) }, unselected:{}) (v1=1&&p=3)@liveness(ts@1), v2@tombstone(ts@2) VC(keyOrConditions{v1: (tb@3)}, unselected:{}) (v1=2&&p=3) or merged 2&3: sstable1: VC(keyOrConditions{v1:(ts@1) }, unselected:{}) (v1=1&&p=3)@livenes(ts@1), v2=3 sstable5: VC(keyOrConditions{v1:(tb@1) }, unselected:{}) (v1=1&&p=3) v2@tombstone(ts@2) VC(keyOrConditions{v1:(ts@3) }, unselected:{}) (v1=2&&p=3)@livenes(ts@1), v2@tombstone(ts@2) sstable4: VC(keyOrConditions{v1:(ts@4) }, unselected:{}) (v1=1&&p=3)@liveness(ts@1), v2@tombstone(ts@2) VC(keyOrConditions{v1: (tb@3)}, unselected:{}) (v1=2&&p=3) or merged all: VC(keyOrConditions{v1:(ts@4) }, unselected:{}) (v1=1&&p=3)@liveness(ts@1), v2@tombstone(ts@2) VC(keyOrConditions{v1: (tb@3)}, unselected:{}) (v1=2&&p=3) v2@tombstone(ts@2) {code} {code} create table ks.base (p int primary key, v1 int, v2 int); create materialized view ks.my_view as select * from ks.base where p is not null and v1 is not null primary key (v1, p); {{q1}} insert into base (p, v1, v2) values (3, 1, 3) using timestamp 1 {{q2}} delete from base using timestamp 2 where p = 3 {{q3}} insert into base (p, v1) values (3, 1) using timestamp 3 {{q4}} update base using timestamp 4 set v1 = 2 where p = 3 // will create a shadowable row tombstone for (v1, p) = (1, 3) {{q5}} update base using timestamp 5 set v1 = 1 where p = 3 at the end: base(merged): p=3@partition_deletion(ts@2), livenesInfo@3, v1=1@5 view: sstable1: VC(keyOrConditions{v1:(ts@1) }, unselected:{}) (v=1&&p=3)@livenes(ts@1) v2=3 sstable2: (v=1&&p=3)@tombstone(ts@2) // normal deletion sstable3: VC(keyOrConditions{v1:(ts@3) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) sstable4: VC(keyOrConditions{v1:(tb@3) }, unselected:{}) (v=1&&p=3) VC(keyOrConditions{v1:(ts@4) }, unselected:{}) (v=2&&p=3)@liveness(ts@3) sstable5: VC(keyOrConditions{v1:(ts@5) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) VC(keyOrConditions{v1:(tb@4) }, unselected:{}) (v=2&&p=3) or merged 2&4: sstable1: VC(keyOrConditions{v1:(ts@1) }, unselected:{}) (v=1&&p=3)@livenes(ts@1) v2=3 sstable3: VC(keyOrConditions{v1:(ts@3) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) sstable6: VC(keyOrConditions{v1:(tb@3) }, unselected:{}) (v=1&&p=3)@tombstone(ts@2) VC(keyOrConditions{v1:(ts@4) }, unselected:{}) (v=2&&p=3)@liveness(ts@3) sstable5: VC(keyOrConditions{v1:(ts@5) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) VC(keyOrConditions{v1:(tb@4) }, unselected:{}) (v=2&&p=3) then merged 3&6&5: sstable1: VC(keyOrConditions{v1:(ts@1) }, unselected:{}) (v=1&&p=3)@livenes(ts@1) v2=3 sstable7: VC(keyOrConditions{v1:(ts@5) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) @tombstone(ts@2) VC(keyOrConditions{v1:(tb@4) }, unselected:{}) (v=2&&p=3)@liveness(ts@3) then merged 1&7: VC(keyOrConditions{v1:(ts@5) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) @tombstone(ts@2) VC(keyOrConditions{v1:(tb@4) }, unselected:{}) (v=2&&p=3)@liveness(ts@3) or merged all: VC(keyOrConditions{v1:(ts@5) }, unselected:{}) (v=1&&p=3)@liveness(ts@3) @tombstone(ts@2) VC(keyOrConditions{v1:(tb@4) }, unselected:{}) (v=2&&p=3) {code} with filter conditions (13547) {code} CREATE TABLE test.table1 ( id int, name text, enabled boolean, foo text, PRIMARY KEY (id, name)); CREATE MATERIALIZED VIEW view1 AS SELECT id, name, foo FROM test.table1 WHERE id IS NOT NULL AND name IS NOT NULL AND enabled = TRUE PRIMARY KEY ((name), id); CREATE MATERIALIZED VIEW view2 AS SELECT * FROM test.table1 WHERE id IS NOT NULL AND name IS NOT NULL AND enabled = TRUE PRIMARY KEY ((name), id); {{q1}} INSERT INTO test.table1 (id, name, enabled, foo) VALUES (1, 'One', TRUE, 'Bar'); // t1 {{q2}} UPDATE test.table1 SET enabled = FALSE WHERE id = 1 AND name = 'One'; // t2 {{q3}} UPDATE test.table1 SET enabled = TRUE WHERE id = 1 AND name = 'One'; // t3 At the end: base(merged): (id=1&&name='One')@t1, enabled=TRUE@t3, foo='Bar' View1: sstable1: VC(keyOrConditions{enabled:(ts@t1) }, unselected:{}) (id=1&&name='One')@liveness(ts@t1), foo='bar'@t1 sstable2: VC(keyOrConditions{enabled:(tb@t1) }, unselected:{}) (id=1&&name='One') sstable3: VC(keyOrConditions{enabled:(ts@t3) }, unselected:{}) (id=1&&name='One')@liveness(ts@t1), foo='bar'@t1 or merged: VC(keyOrConditions{enabled:(ts@t3) }, unselected:{}) (id=1&&name='One')@liveness(ts@t1), foo='bar'@t1 View2: sstable1: VC(keyOrConditions{enabled:(ts@t1) }, unselected:{}) (id=1&&name='One')@liveness(ts@t1), enabled=True@t1, foo='bar'@t1 sstable2: VC(keyOrConditions{enabled:(tb@t1) }, unselected:{}) (id=1&&name='One') sstable3: VC(keyOrConditions{enabled:(ts@t3) }, unselected:{}) (id=1&&name='One')@liveness(ts@t1), enabled=True@t3, foo='bar'@t1 or merged: VC(keyOrConditions{enabled:(ts@t3) }, unselected:{}) (id=1&&name='One')@liveness(ts@t1), enabled=True@t3, foo='bar'@t1 {code} was (Author: jasonstack): h3. Relation: base -> view First of all, I think all of us should agree on what cases view row should exists. IMO, there are two main cases: 1. base pk and view pk are the same (order doesn't matter) and view has no filter conditions or only conditions on base pk. (filter condition mean: {{c = 1}} in view's where clause. filter condition is not a concern here, since no previous view data to be cleared.) view row exists if any of following is true: * a. base row pk has live livenessInfo(timestamp) and base row pk satifies view's filter conditions if any. * b. or one of base row columns selected in view has live timestamp (via update) and base row pk satifies view's filter conditions if any. this is handled by existing mechanism of liveness and tombstone since all info are included in view row * c. or one of base row columns not selected in view has live timestamp (via update) and base row pk satifies view's filter conditions if any. Those unselected columns' timestamp/ttl/cell-deletion info are not currently stored on view row. 2. base column used in view pk or view has filter conditions on base non-key column which can also lead to entire view row being wiped. view row exists if any of following is true: * a. base row pk has live livenessInfo(timestamp) && base column used in view pk is not null but no timestamp && conditions are satisfied. ( pk having live livenesInfo means it is not deleted by tombstone) * b. or base row column in view pk has timestamp (via update) && conditions are satisfied. eg. if base column used in view pk is TTLed, entire view row should be wiped. Next thing is to model "view's tombstone and livenessInfo" to maintain view data based on above cases. h3. Previous known issues: (I might miss some issues, feel free to ping me..) ttl * view row is not wiped when TTLed on base column used in view pk or TTLed on base non-key column with filter condition * cells with same timestamp, merging ttls are not deterministic. partial update on base columns not selected in view * it results in no view data. because of current update semantics, no view updates are generated * corresponding view row' liveness is not depending on liveness of base columns filter conditions or base column used in view pk causes * view row is shadowed after a few modification on base column used in view pk if the base non-key column has TS greater than base pk's ts and view key column's ts. (as mentioned by sylvain: we need to be able to re-insert an entry when a prior one had been deleted need to be careful to hanlde timestamp tie) tombstone merging is not commutative * in current code, shadowable tombstone doesn't co-exist with regular tombstone sstabledump not supporting current shadowable tombstone h3. Model I can think of two ways to ship all required base column info to view: * make base columns that are not selected in view as "virtual cell" and store their imestamp/ttl to view without their actual values. so we can reuse current ts/tb/ttl mechanism with additional validation logic to check if a view row is alive. * or storing those info on view's livenessInfo/deletion with addition merge logic. I will go ahead with second way since there is an existing shadowable tombstone mechanism. View PrimaryKey LivenessInfo, its timestamp, payloads, merging {code} ColumnInfo: // generated from base column as it is. 0. timestamp 1. ttl 2. localDeletionTime: could be used to represent tombstone or TTLed depends on if there is ttl supersedes(): if timestamps are different, greater timestamp supersedes; if timestamps are same, greater localDeletionTime supersedes. // if a normal column in base row has no timestamp (aka. generated by Insert statement), when it is sent to view, it remains no timestamp. // it will implicitly inherit ViewLivenessInfo just like how it works with standard LivenessInfo in regular table, // unlike shadowable mechanism which will explicitly put base pk's timestamp into not-updated base columns into view data to keep "select writetime" correct in view. // (because in shaowable mechanism, view's pk timestamp is promoted to a bigger value which cannot be used for writetime in view) ViewLivenessInfo // corresponding to base pk livenessInfo 0. timestamp 1. ttl / localDeletionTime // base column that are used in view pk or has filter condition. // if any column is not live or doesn't exist, entire view row is wiped. // if a column in base is filtered and not selected, it's stored here. 2. Map<ColumnIdentifier, ColumnInfo> keyOrConditions; // if any column is live 3. Map<ColumnIdentifier, ColumnInfo> unselected; // to determina if a row is live isRowAlive(Deletion delete): get timestamp or columnInfo that is greater than those in Deletion if any colummn in {{keyOrConditions}} is TTLed or tombstone(dead) or not existed, false if {{timestamp or ttl}} are alive, true if any column in {{unselected}} is alive, true otherwise check any columns in view row are alive // cannot use supersedes, because timestamp can tie, we cannot compare keyOrConditions. need to merge merge(ViewLivenessInfo ): // merge 3 parts separates a. for timestamp/ttl/localDeletionTime merging: greater timestamp and its ttl/localDeletionTime remains, if timestamp ties, greate localDeletionTime and its ttl remains. b. for keyOrConditions, merge map if key is the same, compare ColumnInfo.supersedes() c. for unselected, same above {code} View Row Deletion, its timestamp, payloads, merging {code} // it could co-exists with ViewLivenessInfo, similar to regular Deletion. // in shadowable mechanism, shadowable tombstone is invalidated by a newer livenessInfo which will resurrect dead data. ViewDeletion: // base pk deletion time, same as current definition // the localDeletionTime is used for GC_GRACE_SECOND 1. DeletionTime // if view row deletion is caused by base column in view pk being changed or filter conditions failed // the column tombstone ts is existing column's timestamp 2. Map<ColumnIdentifier, ColumnInfo> keyOrConditions; // if base column not selected in view is deleted 3. Map<ColumnIdentifier, ColumnInfo> unselected; // if a deletion removes the livesnessInfo deletes(viewLivessInfo): similar to above checking if row is alive {code} h3. Examples (*_TL;DR;_* validate the model using different tests in each issue) Reinserting previous deleted view row(11500) {code} CREATE TABLE t (k int PRIMARY KEY, a int, b int); CREATE MATERIALIZED VIEW mv AS SELECT * FROM t WHERE k IS NOT NULL AND a IS NOT NULL PRIMARY KEY (k, a); {{q1}} INSERT INTO t(k, a, b) VALUES (1, 1, 1) USING TIMESTAMP 0; {{q2}} UPDATE t USING TIMESTAMP 10 SET b = 2 WHERE k = 1; {{q3}} UPDATE t USING TIMESTAMP 2 SET a = 2 WHERE k = 1; {{q4}} UPDATE t USING TIMESTAMP 3 SET a = 1 WHERE k = 1; After {{q1}}: base: k=1@0, a=1, b=1 // 'k' is having value '1' with timestamp '0' view: sstable1: (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:() }, unselected:{}) //column has no timestamp After {{q2}}: base(merged): (k=1@0, a=1, b=2@10) view: sstable1: (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:() }, unselected:{}) b=1 //column has no timestamp sstable2: (k=1&&a=1)@liveness(no_ts, keyOrConditions{}, unselected:{}) b=2@10 // only b is updated or merged: (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:() }, unselected:{})) b=2@10 After {{q3}}: base(merged): (k=1@0, a=2@2, b=2@10) view: sstable1: (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:() }, unselected:{}) b=1 //column has no timestamp sstable2: (k=1&&a=1)@liveness(no_ts, keyOrConditions{}, unselected:{}) b=2@10 // only b is updated sstable3: (k=1&&a=1)@tombstone(ts@0, keyOrConditions{a:() }, unselected:{}) // row deletion caused by switch_entry (k=1&&a=2)@liveness(ts@0, keyOrConditions{a:(ts@2) }, unselected:{}) b=2@10 or merged: (k=1&&a=1)@tombstone(ts@0, keyOrConditions{a:() }, unselected:{}) (k=1&&a=2)@liveness(ts@0, keyOrConditions{a:(ts@2) }, unselected:{})) b=2@10 After {{q4}}: base(merged): (k=1@0, a=1@3, b=2@10) view: sstable1: (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:() }, unselected:{}) b=1 //column has no timestamp sstable2: (k=1&&a=1)@liveness(no_ts, keyOrConditions{}, unselected:{}) b=2@10 // only b is updated sstable3: (k=1&&a=1)@tombstone(ts@0, keyOrConditions{a:() }, unselected:{}) // row deletion caused by switch_entry (k=1&&a=2)@liveness(ts@0, keyOrConditions{a:(ts@2) }, unselected:{}) b=2@10 sstable4: (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:(ts@3) }, unselected:{}) b=2@10 (k=1&&a=2)@tombstone(ts@0, keyOrConditions{a:(ts@2) }, unselected:{}) or merged: // co-existed liveness & deletion (k=1&&a=1)@liveness(ts@0, keyOrConditions{a:(ts@3) }, unselected:{})), tombstone(ts@0, keyOrConditions{a:() }, unselected:{}) b=2@10 (k=1&&a=2)@tombstone(ts@0, keyOrConditions{a:(ts@2) }, unselected:{}) {code} based column used in view key is TTLed (13657) {code} CREATE TABLE t (k int, a int, b int, PRIMARY KEY (k)); CREATE MATERIALIZED VIEW mv AS SELECT * FROM t WHERE k IS NOT NULL AND a IS NOT NULL PRIMARY KEY (a, k); {{q1}} INSERT INTO t (k) VALUES (1); {{q2}} UPDATE t USING TTL 5 SET a = 10 WHERE k = 1; {{q3}} UPDATE t SET b = 100 WHERE k = 1; After q1: base: k=1@t1 view: no view updates generated because no existing view data After q2: base(merged): k=1@t1, a=10@(t2, ttl@5) view: (k=1&&a=10)@liveness(ts@t1, keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) After q2: base(merged): k=1@t1, a=10@(t2, ttl@5), b@t3 view: sstable1: (k=1&&a=10)@liveness(ts@t1, keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) sstable2: (k=1&&a=10)@liveness(ts@t1, keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) b=100@t3 or merged: (k=1&&a=10)@liveness(ts@t1, keyOrConditions{a:(ts@t2, ttl@5) }, unselected:{}) b=100@t3 5 seconds later, view row is considered removed becuase {{keyOrConditions-a}} is TTLed. {code} View row expires too fast with unselected base column (13127) {code} CREATE TABLE ks.base (p int, c int, v int, PRIMARY KEY (p, c)); CREATE MATERIALIZED VIEW ks.mv AS SELECT p, c FROM base WHERE p IS NOT NULL AND c IS NOT NULL PRIMARY KEY (c, p); {{q1}} INSERT INTO ks.base (p, c) VALUES (0, 0) USING TTL 3; {{q2}} UPDATE ks.base USING TTL 100 SET v = 0 WHERE p = 0 and c = 0; After q1: base: (p=0&&c=0)@(ts@t1, ttl@3) view: (c=p&&p=0)@liveness(ts@t1, ttl@3, keyOrConditions{}, unselected:{}) After q2: base(merged): (p=0&&c=0)@(ts@t1, ttl@3) v=0@(ts@t2, ttl@100) view: sstable1: (c=0&&p=0)@liveness(ts@t1, ttl@3, keyOrConditions{}, unselected:{}) sstable2: (c=0&&p=0)@liveness(ts@t1, ttl@3, keyOrConditions{}, unselected:{v@(ts@t2, ttl@100) }) or merged: (c=0&&p=0)@liveness(ts@t1, ttl@3, keyOrConditions{}, unselected:{v@(ts@t2, ttl@100) }) after 5 second, base: p,c,v-> 0,0,0 view: c,p -> 0,0 because {{unselected has not TTLed column v}} {code} Partial update unselected columns in base (13127) {code} CREATE TABLE base (k int, c int, a int, b int, PRIMARY KEY (k, c)); CREATE MATERIALIZED VIEW mv AS SELECT k,c FROM base WHERE k IS NOT NULL AND c IS NOT NULL PRIMARY KEY (k,c); {{q1}} UPDATE base USING TIMESTAMP 10 SET b=1 WHERE k=1 AND c=1; {{q2}} DELETE b FROM base USING TIMESTAMP 11 WHERE k=1 AND c=1; {{q3}} UPDATE base USING TIMESTAMP 1 SET a=1 WHERE k=1 AND c=1; After q1: base: (k=1&&c=1), b=1@10 view: (k=1&&c=1)@liveness(no_ts, keyOrConditions{}, unselected:{b@(ts@10)}) After q2: base(merged): (k=1&&c=1), b@tombstone(ts@11) view: sstable1: (k=1&&c=1)@liveness(no_ts, keyOrConditions{}, unselected:{b@(ts@10)}) sstable2: (k=1&&c=1)@tombstone(no_ts, keyOrConditions{}, unselected:{b@(ts@11)}) or merged: (k=1&&c=1)@tombstone(no_ts, keyOrConditions{}, unselected:{b@(ts@11)}) // no view row After q3: base(merged): (k=1&&c=1), b@tombstone(ts@11), c=1@1 view: sstable1: (k=1&&c=1)@liveness(no_ts, keyOrConditions{}, unselected:{b@(ts@10)}) sstable2: (k=1&&c=1)@tombstone(no_ts, keyOrConditions{}, unselected:{b@(ts@11)}) sstable3: (k=1&&c=1)@liveness(no_ts, keyOrConditions{}, unselected:{c@(ts@1)}) or merged: (k=1&&c=1)@liveness(no_ts, keyOrConditions{}, unselected:{c@(ts@1), b@(deletion@11)}) // view row a live since one of {{unselected}} is live {code} merging should be commutative (13409) {code} create table ks.base (p int primary key, v1 int, v2 int); create materialized view ks.my_view as select * from ks.base where p is not null and v1 is not null primary key (v1, p); {{q1}} insert into ks.base (p, v1, v2) values (3, 1, 3) using timestamp 1; {{q2}} delete from ks.base using timestamp 2 where p = 3; {{q3} insert into ks.base (p, v1) values (3, 1) using timestamp 3; at the end: base(merged): p=3@partition_deletion@2, livenesInfo@3, v1=1 view: sstable1: (v1=3&&p=3)@livenes(ts@1, keyOrConditions{v1:() }, unselected:{}), v2=3 sstable2: (v1=3&&p=3)@tombstone(ts@2, keyOrConditions{}, unselected:{}) sstable3: (v1=3&&p=3)@livenes(ts@3, keyOrConditions{v1:(ts@3) }, unselected:{}) or merged: (v1=3&&p=3)@livenes(ts@3, keyOrConditions{v1:(ts@3) }, unselected:{}), tombstone(ts@2, keyOrConditions{}, unselected:{}) // liveness & deletion should be able to co-exist {code} {code} create table ks.base (p int primary key, v1 int, v2 int); create materialized view ks.my_view as select * from ks.base where p is not null and v1 is not null primary key (v1, p); {{q1}} insert into base (p, v1, v2) values (3, 1, 3) using timestamp 1 {{q2}} update base using timestamp 2 set v2 = null where p = 3 {{q3}} update base using timestamp 3 set v1 = 2 where p = 3 {{q4} }update base using timestamp 4 set v1 = 1 where p = 3 at the end: base(merged): p=3@1, v1=1@4, v2@tombstone(ts@3) view: sstable1: (v1=1&&p=3)@livenes(ts@1, keyOrConditions{v1:() }, unselected:{}), v2=3 sstable2: (v1=1&&p=3)@livenes(ts@1, keyOrConditions{v1:() }, unselected:{}), v2@tombstone(ts@2) sstable3: (v1=1&&p=3)@tombstone(ts@1, keyOrConditions{v1: () }, unselected:{}) (v1=2&&p=3)@livenes(ts@1, keyOrConditions{v1: (ts@3)}, unselected:{}), v2@tombstone(ts@2) sstable4: (v1=1&&p=3)@liveness(ts@1, keyOrConditions{v1: (ts@4) }, unselected:{}), v2@tombstone(ts@2) (v1=2&&p=3)@tombstone(ts@1, keyOrConditions{v1: (ts@3)}, unselected:{}) or merged 2&3: sstable1: (v1=1&&p=3)@livenes(ts@1, keyOrConditions{}, unselected:{}), v2=3 sstable5: (v1=1&&p=3)@tombstone(ts@1, keyOrConditions{v1: () }, unselected:{}) (v1=2&&p=3)@livenes(ts@1, keyOrConditions{v1: (ts@3)}, unselected:{}), v2@tombstone(ts@2) sstable4: (v1=1&&p=3)@liveness(ts@1, keyOrConditions{v1: (ts@4) }, unselected:{}), v2@tombstone(ts@2) (v1=2&&p=3)@tombstone(ts@1, keyOrConditions{v1: (ts@3)}, unselected:{}) or merged all: (v1=1&&p=3)@liveness(ts@1, keyOrConditions{v1: (ts@4) }, unselected:{}), tombstone(ts@1, keyOrConditions{v1: () }, unselected:{}), v2@tombstone(ts@2) (v1=2&&p=3)@tombstone(ts@1, keyOrConditions{v1: (ts@3)}, unselected:{}) {code} {code} create table ks.base (p int primary key, v1 int, v2 int); create materialized view ks.my_view as select * from ks.base where p is not null and v1 is not null primary key (v1, p); {{q1}} insert into base (p, v1, v2) values (3, 1, 3) using timestamp 1 {{q2}} delete from base using timestamp 2 where p = 3 {{q3}} insert into base (p, v1) values (3, 1) using timestamp 3 {{q4}} update base using timestamp 4 set v1 = 2 where p = 3 // will create a shadowable row tombstone for (v1, p) = (1, 3) {{q5}} update base using timestamp 5 set v1 = 1 where p = 3 at the end: base(merged): p=3@partition_deletion(ts@2), livenesInfo@3, v1=1@5 view: sstable1: (v=1&&p=3)@livenes(ts@1, keyOrConditions{v1:() }, unselected:{}) v2=3 sstable2: (v=1&&p=3)@tombstone(ts@2, keyOrConditions{}, unselected:{}) sstable3: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:() }, unselected:{}) sstable4: (v=1&&p=3)@tombstone(ts@3, keyOrConditions{v1:() }, unselected:{}) (v=2&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) sstable5: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@5) }, unselected:{}) (v=2&&p=3)@tombstone(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) or merged 2&4: sstable1: (v=1&&p=3)@livenes(ts@1, keyOrConditions{v1:() }, unselected:{}) v2=3 sstable3: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:() }, unselected:{}) sstable6: (v=1&&p=3)@tombstone(ts@3, keyOrConditions{v1:() }, unselected:{}) (v=2&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) sstable5: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@5) }, unselected:{}) (v=2&&p=3)@tombstone(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) then merged 3&6&5: sstable1: (v=1&&p=3)@livenes(ts@1, keyOrConditions{v1:() }, unselected:{}) v2=3 sstable7: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@5) }, unselected:{}), tombstone(ts@3, keyOrConditions{v1:() }, unselected:{}) (v=2&&p=3)@tombstone(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) then merged 1&7: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@5) }, unselected:{}), tombstone(ts@3, keyOrConditions{v1:() }, unselected:{}) (v=2&&p=3)@tombstone(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) or merged all: (v=1&&p=3)@liveness(ts@3, keyOrConditions{v1:(ts@5) }, unselected:{}), (v=1&&p=3)@tombstone(ts@3, keyOrConditions{v1:() }, unselected:{}) (v=2&&p=3)@tombstone(ts@3, keyOrConditions{v1:(ts@4) }, unselected:{}) {code} with filter conditions (13547) {code} CREATE TABLE test.table1 ( id int, name text, enabled boolean, foo text, PRIMARY KEY (id, name)); CREATE MATERIALIZED VIEW view1 AS SELECT id, name, foo FROM test.table1 WHERE id IS NOT NULL AND name IS NOT NULL AND enabled = TRUE PRIMARY KEY ((name), id); CREATE MATERIALIZED VIEW view2 AS SELECT * FROM test.table1 WHERE id IS NOT NULL AND name IS NOT NULL AND enabled = TRUE PRIMARY KEY ((name), id); {{q1}} INSERT INTO test.table1 (id, name, enabled, foo) VALUES (1, 'One', TRUE, 'Bar'); // t1 {{q2}} UPDATE test.table1 SET enabled = FALSE WHERE id = 1 AND name = 'One'; // t2 {{q3}} UPDATE test.table1 SET enabled = TRUE WHERE id = 1 AND name = 'One'; // t3 At the end: base(merged): (id=1&&name='One')@t1, enabled=TRUE@t3, foo='Bar' View1: sstable1: (id=1&&name='One')@liveness(ts@t1, keyOrConditions{enabled:() }, unselected:{}), foo='bar' sstable2: (id=1&&name='One')@tombstone(ts@t1, keyOrConditions{enabled:() }, unselected:{}) sstable3: (id=1&&name='One')@liveness(ts@t1, keyOrConditions{enabled:(ts@t2) }, unselected:{}), foo='bar' or merged: (id=1&&name='One')@liveness(ts@t1, keyOrConditions{enabled:(ts@t2) }, unselected:{}), foo='bar' View2: sstable1: (id=1&&name='One')@liveness(ts@t1, keyOrConditions{enabled:() }, unselected:{}), enabled=True, foo='bar' sstable2: (id=1&&name='One')@tombstone(ts@t1, keyOrConditions{enabled:() }, unselected:{}) sstable3: (id=1&&name='One')@liveness(ts@t1, keyOrConditions{enabled:(ts@t2) }, unselected:{}), enabled=True@t3, foo='bar' or merged: (id=1&&name='One')@liveness(ts@t1, keyOrConditions{enabled:(ts@t2) }, unselected:{}), enabled=True@t3, foo='bar' {code} > Obsolete MV entry may not be properly deleted > --------------------------------------------- > > Key: CASSANDRA-11500 > URL: https://issues.apache.org/jira/browse/CASSANDRA-11500 > Project: Cassandra > Issue Type: Bug > Components: Materialized Views > Reporter: Sylvain Lebresne > Assignee: ZhaoYang > > When a Materialized View uses a non-PK base table column in its PK, if an > update changes that column value, we add the new view entry and remove the > old one. When doing that removal, the current code uses the same timestamp > than for the liveness info of the new entry, which is the max timestamp for > any columns participating to the view PK. This is not correct for the > deletion as the old view entry could have other columns with higher timestamp > which won't be deleted as can easily shown by the failing of the following > test: > {noformat} > CREATE TABLE t (k int PRIMARY KEY, a int, b int); > CREATE MATERIALIZED VIEW mv AS SELECT * FROM t WHERE k IS NOT NULL AND a IS > NOT NULL PRIMARY KEY (k, a); > INSERT INTO t(k, a, b) VALUES (1, 1, 1) USING TIMESTAMP 0; > UPDATE t USING TIMESTAMP 4 SET b = 2 WHERE k = 1; > UPDATE t USING TIMESTAMP 2 SET a = 2 WHERE k = 1; > SELECT * FROM mv WHERE k = 1; // This currently return 2 entries, the old > (invalid) and the new one > {noformat} > So the correct timestamp to use for the deletion is the biggest timestamp in > the old view entry (which we know since we read the pre-existing base row), > and that is what CASSANDRA-11475 does (the test above thus doesn't fail on > that branch). > Unfortunately, even then we can still have problems if further updates > requires us to overide the old entry. Consider the following case: > {noformat} > CREATE TABLE t (k int PRIMARY KEY, a int, b int); > CREATE MATERIALIZED VIEW mv AS SELECT * FROM t WHERE k IS NOT NULL AND a IS > NOT NULL PRIMARY KEY (k, a); > INSERT INTO t(k, a, b) VALUES (1, 1, 1) USING TIMESTAMP 0; > UPDATE t USING TIMESTAMP 10 SET b = 2 WHERE k = 1; > UPDATE t USING TIMESTAMP 2 SET a = 2 WHERE k = 1; // This will delete the > entry for a=1 with timestamp 10 > UPDATE t USING TIMESTAMP 3 SET a = 1 WHERE k = 1; // This needs to re-insert > an entry for a=1 but shouldn't be deleted by the prior deletion > UPDATE t USING TIMESTAMP 4 SET a = 2 WHERE k = 1; // ... and we can play this > game more than once > UPDATE t USING TIMESTAMP 5 SET a = 1 WHERE k = 1; > ... > {noformat} > In a way, this is saying that the "shadowable" deletion mechanism is not > general enough: we need to be able to re-insert an entry when a prior one had > been deleted before, but we can't rely on timestamps being strictly bigger on > the re-insert. In that sense, this can be though as a similar problem than > CASSANDRA-10965, though the solution there of a single flag is not enough > since we can have to replace more than once. > I think the proper solution would be to ship enough information to always be > able to decide when a view deletion is shadowed. Which means that both > liveness info (for updates) and shadowable deletion would need to ship the > timestamp of any base table column that is part the view PK (so {{a}} in the > example below). It's doable (and not that hard really), but it does require > a change to the sstable and intra-node protocol, which makes this a bit > painful right now. > But I'll also note that as CASSANDRA-1096 shows, the timestamp is not even > enough since on equal timestamp the value can be the deciding factor. So in > theory we'd have to ship the value of those columns (in the case of a > deletion at least since we have it in the view PK for updates). That said, on > that last problem, my preference would be that we start prioritizing > CASSANDRA-6123 seriously so we don't have to care about conflicting timestamp > anymore, which would make this problem go away. -- This message was sent by Atlassian JIRA (v6.4.14#64029) --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org