Ranges with NULLs 04: Pack, Merge

In this post, I’m going to treat two closely related but distinct requirements:

  1. “Pack”: in a SELECT, return contiguous or overlapping ranges as one range.
  2. “Merge”: modify a table to reduce contiguous or overlapping ranges to one range.

These operations should take into account other data associated with each range: ranges are packed or merged only when the other data is the same.

Current list of posts: 

What is the meaning of this?

This heading sounds like something a teacher would say when he discovers students breaking the rules. Actually, I’m not trying to break rules, I’m trying to make some – or at least tell you what rules I am following.

  • In my world, the rule is that ranges have exclusive end points: this is called the “closed-open” type. It allows ranges that “meet” without gaps or overlaps.
  • I classify ranges in three categories:
    1. Neither “To” nor “From” may be NULL
    2. “To” may be NULL, but not “From”
    3. Both “From” and “To” may be NULL.
  • My data consists of an object, a “from” and “to” range –
    and optional “attributes” that are valid for the object only within the range.
  • In this post, I’ll use “Pack” to mean a SELECT that returns contiguous or overlapping ranges as one big range (any “attributes” have to be the same).
  • In this post, I’ll use “Merge” to mean a MERGE statement that changes a table so that contiguous or overlapping ranges become one big range.
  • I propose solutions that require database version 12.1 or later.

Test data with no NULLs allowed

This isn’t a full test harness, just the minimum to illustrate the solution. This is the same data as in my previous post Ranges with NULLs 03: Gaps

create table t(
  obj_id varchar2(9), 
  f int, t int, af int, at int, bf int, bt int
);

Insert into T values ('1p    0',1,2,1,2,3,4);
Insert into T values ('1p    0',3,4,1,2,3,4);
Insert into T values ('2m    0',1,2,1,2,2,3);
Insert into T values ('2m    0',2,3,1,2,2,3);
Insert into T values ('3o    0',1,3,1,3,2,4);
Insert into T values ('3o    0',2,4,1,3,2,4);
Insert into T values ('4f    0',1,3,1,3,2,3);
Insert into T values ('4f    0',2,3,1,3,2,3);
Insert into T values ('5c    0',1,4,1,4,2,3);
Insert into T values ('5c    0',2,3,1,4,2,3);
Insert into T values ('6s    0',1,2,1,2,1,3);
Insert into T values ('6s    0',1,3,1,2,1,3);
Insert into T values ('7e    0',1,2,1,2,1,2);
Insert into T values ('7e    0',1,2,1,2,1,2);
  1. There are two rows = two ranges for each test case.
  2. OBJ_ID indicates the relation between the ranges: “precedes, meets, overlaps, finished by, contains, starts, equals”. The 0 at the end means there are no nulls.
  3. F is the “from” value.
  4. T is the “to” value (exclusive).
  5. So we can check our results more easily, each row contains the values for both ranges,
    1. AF and AT for the first range,
    2. BF and BT for the second range.

Pack non-null ranges

  • I partition by the object ID and also by any attributes I want to include. PARTITION BY, like GROUP BY, does a good job of comparing values when NULL might be involved: two NULLs are considered “the same”, and a NULL is considered different from a non-NULL value.
    For brevity, here the attributes for a given object are always the same.
  • In a DEFINE, the current row is assumed to belong to the condition being tested, so I cannot compare the current start date to the maximum prior end date. I can however compare the maximum end date to the next start date.
select obj_id, F, T, AF, AT, BF, BT
from t
match_recognize( 
  partition by obj_id, AF, AT, BF, BT
  order by F, T
  measures first(F) F, max(T) T 
  pattern(a* b)
  define a as max(T) >= next(F)
);
OBJ_ID F T AF AT BF BT
1p 0 1 2 1 2 3 4
1p 0 3 4 1 2 3 4
2m 0 1 3 1 2 2 3
3o 0 1 4 1 3 2 4
4f 0 1 3 1 3 2 3
5c 0 1 4 1 4 2 3
6s 0 1 3 1 2 1 3
7e 0 1 2 1 2 1 2

 

Pack ranges with “To” NULL

Insert into T values ('1p    1',1,2,1,2,3,null);
Insert into T values ('1p    1',3,null,1,2,3,null);
Insert into T values ('2m    1',1,2,1,2,2,null);
Insert into T values ('2m    1',2,null,1,2,2,null);
Insert into T values ('3o    1',1,3,1,3,2,null);
Insert into T values ('3o    1',2,null,1,3,2,null);
Insert into T values ('4f    1',1,null,1,null,2,null);
Insert into T values ('4f    1',2,null,1,null,2,null);
Insert into T values ('5c    1',1,null,1,null,2,3);
Insert into T values ('5c    1',2,3,1,null,2,3);
Insert into T values ('6s    1',1,2,1,2,1,null);
Insert into T values ('6s    1',1,null,1,2,1,null);
Insert into T values ('7e    1',1,null,1,null,1,null);
Insert into T values ('7e    1',1,null,1,null,1,null);
commit;

In the MEASURES and DEFINE lines, I find out whether there has been a NULL “to” by comparing COUNT(*) to COUNT(T).

select obj_id, F, T, AF, AT, BF, BT
from t
match_recognize(
  partition by obj_id, AF, AT, BF, BT
  order by F, T
  measures first(F) F, decode(count(*), count(T), max(T)) T
  pattern(a* b)
  define a as count(*) > count(T) or max(T) >= next(F)
)
order by 1, 2 nulls first, 3;
OBJ_ID F T AF AT BF BT
1p 0 1 2 1 2 3 4
1p 0 3 4 1 2 3 4
1p 1 1 2 1 2 3
1p 1 3 1 2 3
2m 0 1 3 1 2 2 3
2m 1 1 1 2 2
3o 0 1 4 1 3 2 4
3o 1 1 1 3 2
4f 0 1 3 1 3 2 3
4f 1 1 1 2
5c 0 1 4 1 4 2 3
5c 1 1 1 2 3
6s 0 1 3 1 2 1 3
6s 1 1 1 2 1
7e 0 1 2 1 2 1 2
7e 1 1 1 1

 

Pack with “From” and “To” NULLs

Insert into T values ('1p    2',3,null,null,2,3,null);
Insert into T values ('1p    2',null,2,null,2,3,null);
Insert into T values ('2m    2',2,null,null,2,2,null);
Insert into T values ('2m    2',null,2,null,2,2,null);
Insert into T values ('3o    2',2,null,null,3,2,null);
Insert into T values ('3o    2',null,3,null,3,2,null);
Insert into T values ('4f    2',2,null,null,null,2,null);
Insert into T values ('4f    2',null,null,null,null,2,null);
Insert into T values ('5c    2',2,3,null,null,2,3);
Insert into T values ('5c    2',null,null,null,null,2,3);
Insert into T values ('6s    2',null,2,null,2,null,null);
Insert into T values ('6s    2',null,null,null,2,null,null);
Insert into T values ('7e    2',null,null,null,null,null,null);
Insert into T values ('7e    2',null,null,null,null,null,null);
commit;

We just need to order by F nulls first, and in the DEFINE say nvl(next(F),T).

select obj_id, F, T, AF, AT, BF, BT
from t
match_recognize( 
  partition by obj_id, AF, AT, BF, BT
  order by F nulls first, T
  measures first(F) F, decode(count(*), count(T), max(T)) T 
  pattern(a* b)
  define a as count(*) > count(T) or max(T) >= nvl(next(F),T)
)
order by 1,2 nulls first, 3;
OBJ_ID F T AF AT BF BT
1p 0 1 2 1 2 3 4
1p 0 3 4 1 2 3 4
1p 1 1 2 1 2 3
1p 1 3 1 2 3
1p 2 2 2 3
1p 2 3 2 3
2m 0 1 3 1 2 2 3
2m 1 1 1 2 2
2m 2 2 2
3o 0 1 4 1 3 2 4
3o 1 1 1 3 2
3o 2 3 2
4f 0 1 3 1 3 2 3
4f 1 1 1 2
4f 2 2
5c 0 1 4 1 4 2 3
5c 1 1 1 2 3
5c 2 2 3
6s 0 1 3 1 2 1 3
6s 1 1 1 2 1
6s 2 2
7e 0 1 2 1 2 1 2
7e 1 1 1 1
7e 2

 

Merge with or without NULLs

Here I’ll use the same data.

  • I use the ROWID to identify each row and to allow direct access to the target rows in the MERGE step.
  • To take attributes into account, simply add them to the PARTITION BY list.
  • Since I use ALL ROWS PER MATCH, I must use the FINAL keyword to include the entire match in the aggregation functions.
  • I adjust the PATTERN (A+, not A*) to bypass rows that are already packed ranges.
  • I return all the rows to be packed, updating the first row to the new T and deleting the others.
merge into t o
using (
  select * from (
    select obj_id, f, t, rowid rid from t a
  )
  match_recognize( 
    partition by obj_id
    order by F nulls first, T
    measures count(*) cnt,
      decode(final count(*), final count(T), final max(T)) new_T 
    all rows per match
    pattern(a+ b)
    define a as count(*) > count(T) or max(T) >= nvl(next(F),T)
  )
) n
on (o.rowid = n.rid)
when matched then update set o.t = n.new_t
  delete where n.cnt > 1;

36 rows merged.

Next up: breaking down overlapping ranges into component segments.

Advertisements

Ranges with NULLs 03: Gaps

When I wrote “Gaps in Date Ranges: when are you free?“, I handled NULLs using “magic” values. This time I’ll try not to cheat.

[UPDATE 2018-11-08: I have never seen a situation where “from” could be NULL and “to” was NOT NULL, so I no longer test that. ]

Current list of posts: 

Test data with no NULLs allowed

This isn’t a full test harness, just the minimum to illustrate the solution.

create table t(
  obj_id varchar2(9), 
  f int, t int, af int, at int, bf int, bt int
);

Insert into T values ('1p    0',1,2,1,2,3,4);
Insert into T values ('1p    0',3,4,1,2,3,4);
Insert into T values ('2m    0',1,2,1,2,2,3);
Insert into T values ('2m    0',2,3,1,2,2,3);
Insert into T values ('3o    0',1,3,1,3,2,4);
Insert into T values ('3o    0',2,4,1,3,2,4);
Insert into T values ('4f    0',1,3,1,3,2,3);
Insert into T values ('4f    0',2,3,1,3,2,3);
Insert into T values ('5c    0',1,4,1,4,2,3);
Insert into T values ('5c    0',2,3,1,4,2,3);
Insert into T values ('6s    0',1,2,1,2,1,3);
Insert into T values ('6s    0',1,3,1,2,1,3);
Insert into T values ('7e    0',1,2,1,2,1,2);
Insert into T values ('7e    0',1,2,1,2,1,2);
  1. There are two rows = two ranges for each test case.
  2. OBJ_ID indicates the relation between the ranges: “precedes, meets, overlaps, finished by, contains, starts, equals”. The 0 at the end means there are no nulls.
  3. F is the “from” value.
  4. T is the “to” value (exclusive).
  5. So we can check our results more easily, each row contains the values for both ranges,
    1. AF and AT for the first range,
    2. BF and BT for the second range.

Analytic solution

select * from (
  select OBJ_ID,
    max(t) over(partition by obj_id order by f) start_gap,
    lead(f) over(partition by obj_id order by f) end_gap,
    AF, AT, BF, BT
  from t
)
where start_gap < end_gap
order by obj_id, start_gap;
OBJ_ID START_GAP END_GAP AF AT BF BT
1p 0 2 3 1 2 3 4

 

The start of the gap is the biggest T so far, and the end of the gap is the next F – as long as MAX(T) is less than the next F.

Match_recognize solution

select OBJ_ID, START_GAP, END_GAP, AF, AT, BF, BT
from t
match_recognize(
  partition by obj_id
  order by F, T
  measures max(T) start_gap, next(F) end_gap
  all rows per match
  pattern((A|{-B-})+)
  define A as max(T) < next(F)
)
order by obj_id, start_gap;

 

When the “to” value can be null

The new test data is exactly the same as before, except that the highest “to” value in each test case has been replaced with NULL. The OBJ_ID of the test case ends in 1, not 0, to signal this.

Insert into T values ('1p    1',1,2,1,2,3,null);
Insert into T values ('1p    1',3,null,1,2,3,null);
Insert into T values ('2m    1',1,2,1,2,2,null);
Insert into T values ('2m    1',2,null,1,2,2,null);
Insert into T values ('3o    1',1,3,1,3,2,null);
Insert into T values ('3o    1',2,null,1,3,2,null);
Insert into T values ('4f    1',1,null,1,null,2,null);
Insert into T values ('4f    1',2,null,1,null,2,null);
Insert into T values ('5c    1',1,null,1,null,2,3);
Insert into T values ('5c    1',2,3,1,null,2,3);
Insert into T values ('6s    1',1,2,1,2,1,null);
Insert into T values ('6s    1',1,null,1,2,1,null);
Insert into T values ('7e    1',1,null,1,null,1,null);
Insert into T values ('7e    1',1,null,1,null,1,null);

The problem with “to” being null is that MAX(T) ignores NULL values. I have to know if there has been a NULL T along the way, because that means there can be no more gaps. I use SUM(DECODE(…)) in the analytic solution, and with MATCH_RECOGNIZE I compare COUNT(*) to COUNT(T): if they are not the same then there was a null value along the way.

select * from (
  select OBJ_ID,
    case sum(decode(t,null,1,0)) over(partition by obj_id order by f)
      when 0
        then max(t) over(partition by obj_id order by f)
    end start_gap,
    lead(f) over(partition by obj_id order by f) end_gap,
    AF, AT, BF, BT
  from t
)
where start_gap < end_gap;

select OBJ_ID, START_GAP, END_GAP, AF, AT, BF, BT
from t
match_recognize(
  partition by obj_id
  order by F, T
  measures max(T) start_gap, next(F) end_gap
  all rows per match
  pattern((A|{-B-})+)
  define A as max(T) < next(F) and count(t) = count(*)
)
order by obj_id, start_gap;
OBJ_ID START_GAP END_GAP AF AT BF BT
1p 0 2 3 1 2 3 4
1p 1 2 3 1 2 3

 

When “from” and “to” can both be null

In the new test data, OBJ_ID ends with 2 when the lowest F and the highest T are replaced by NULL.

The only additional change is to order by F NULLS FIRST.

Insert into T values ('1p    2',3,null,null,2,3,null);
Insert into T values ('1p    2',null,2,null,2,3,null);
Insert into T values ('2m    2',2,null,null,2,2,null);
Insert into T values ('2m    2',null,2,null,2,2,null);
Insert into T values ('3o    2',2,null,null,3,2,null);
Insert into T values ('3o    2',null,3,null,3,2,null);
Insert into T values ('4f    2',2,null,null,null,2,null);
Insert into T values ('4f    2',null,null,null,null,2,null);
Insert into T values ('5c    2',2,3,null,null,2,3);
Insert into T values ('5c    2',null,null,null,null,2,3);
Insert into T values ('6s    2',null,2,null,2,null,null);
Insert into T values ('6s    2',null,null,null,2,null,null);
Insert into T values ('7e    2',null,null,null,null,null,null);
Insert into T values ('7e    2',null,null,null,null,null,null);

select * from (
  select OBJ_ID,
    case sum(decode(t,null,1,0)) over(partition by obj_id order by f nulls first)
      when 0
        then max(t) over(partition by obj_id order by f nulls first)
    end start_gap,
    lead(f) over(partition by obj_id order by f nulls first) end_gap,
    AF, AT, BF, BT
  from t
)
where start_gap < end_gap;

select OBJ_ID, START_GAP, END_GAP, AF, AT, BF, BT
from t
match_recognize(
  partition by obj_id
  order by F nulls first, T
  measures max(T) start_gap, next(F) end_gap
  all rows per match
  pattern((A|{-B-})+)
  define A as max(T) < next(F) and count(t) = count(*)
)
order by obj_id, start_gap;
OBJ_ID START_GAP END_GAP AF AT BF BT
1p 0 2 3 1 2 3 4
1p 1 2 3 1 2 3
1p 2 2 3 2 3

 
Next up: merging or “packing” ranges.

Ranges with NULLs 02: test cases

When I write SQL there is a bit of trial and error (laughter), so I need as complete a set of test cases as possible. Here’s what I came up with.

Current list of posts: 

0: input with no rows

Would you believe that one of my solutions doesn’t work when the input has no rows? Well…let’s put it this way, I never said what “working” should mean with no input rows. Now that I’ve added that test case, I have to say what output I expect.

1: one range per test case

This is another situation I never bothered to think about – until now.

2: two ranges per test case

With two ranges to compare, it only takes 7 test cases to cover all the relations defined in Dr. Allen’s Time Interval Algebra.
Time Interval Relationships

The image mentions “day of month” but the logic would be identical with numbers instead of dates. The boundaries are starting and ending points: the starting point is included in the range, but the ending point is not. When A’s ending point is equal to B’s starting point, the ranges “meet” with no gap and no overlap.

3: three ranges per test case

In all the time I have looked at range-related problems on forums, every bug could be illustrated with at most three ranges. I decided to generate all the possible combinations of relations: range A to range B, A to C and B to C. It turns out there are 75 valid combinations, so 75 test cases at 3 rows per test case.

3: three combinations of NULL and NOT NULL

The whole point in this series is to deal with NULL starting and ending points, so I will test three variations:

  • No nulls
  • Start can be null, end not null
  • Start not null, end can be null
  • Start and end can both be null.

[UPDATE 2018-11-8: I now omit the variant “Start can be null, end not null” since I have never seen it in real life.]

6 / 26: comparing attributes

When ranges intersect in any way, there may be a requirement to compare additional attributes. For example, we may want to merge two rows together if they intersect and all the attributes are the same. Limiting myself to one attribute only, I’ve come up with six combinations:

  1. x=y: the attributes are identical
  2. x<y: the "earlier" range attribute is less than the "later" range attribute
  3. x>y: the earlier attribute is greater than the later one
  4. N-y: the earlier attribute is null
  5. x-N: the later attribute is null
  6. N-N: both attributes are null

For completeness, I’ll add case “0-n/a”: when there is no intersection, the attributes are not compared.

When there are three ranges, there are up to 26 different combinations of comparison.

Summary: 4373 test cases

Changing the number of ranges from 0 through 3, and adding attributes when there are two or three intersecting relations, I get a total of 4373 test cases in 6 different tables:

Table name                  RANGES0 RANGES1 RANGES2 RANGES2_ATTRS RANGES3 RANGES3_ATTR
Relations                   0       0       7       7             75      75
Relations with or w/o nulls 0       0       21      21            225     225
Combinations of attributes  0       0       0       6             0       26
Test cases                  1       4       21      96            225     4026
rows                        0       4       56      192           675     12078

Forgive me for not publishing the actual test data, and the convoluted code I used to generate it. I may show bits as needed in later posts.

Next up: finding gaps in ranges.

Ranges with NULLs 01: starting over

I have written a lot about ranges, mostly based on dates, and I have tried my best to avoid NULLs in “from” and “to” columns. I give up: NULLs are a fact of life and must be dealt with. This means revisiting all my previous work!

Current list of posts: 

What do I mean by “range”?

Let’s start with the SQL:2011 definition of PERIOD. A PERIOD identifies two datetime columns. The end datetime is greater than the start datetime. In the Oracle implementation, both start and end can be null.

A datetime value falls within the period if:

  • it is greater than or equal to the start datetime
    OR the start datetime is NULL
  • and it is less than the end datetime
    OR the end datetime is NULL.

A period that starts with NULL and ends with NULL will include any datetime value, including NULL!

My notion of “range” is basically an extension of this definition to more data types:

  • A range identifies a pair of values of the same data type.
  • The data type can be any scalar capable of equal, greater-than and less-than comparisons,
    though datetime types and numbers are by far the most common.
  • I tend to use “from” and “to” because “start” and “end” make me think of datetime ranges.
  • “From” is less than “to”
  • “From” and / or “to” can be NULL
  • A value falls within the range if:
    • it is greater than or equal to “from”
      OR “from” is NULL
    • and it is less than “to”
      OR “to” is NULL
  • In table definitions, I strongly recommend constraints
    • “from” < "to". This constraint should always be there.
    • “from” NOT NULL (unless a use case necessitates NULL).

Closed-Open ranges

When defining ranges, we always want to allow the possibility for two ranges to “meet”, meaning there is no gap between them yet they do not overlap.

The “closed-open” model allows this, because the “from” value belongs to the range but the “to” value does not.

If we have a range 1 to 2 and another range from 2 to 3:

  • The value 2 is not in the first range, but it is in the second.
  • There is no value from 1 to 3 that is in both ranges, so there is no overlap.
  • There is no value from 1 to 3 that is in neither range, so there is no gap.
  • In other words, every value from 1 to 3 is in exactly one of the two ranges.

This model will work will all types of range, and it makes some queries easier to write. It’s all good.

Objections to NULL in ranges

I once wrote SQL and date ranges: don’t make NULL mean something, where I gave five arguments against NULL. Here’s what I think as of today.

  1. “NULL should not mean anything”.
    I still agree with that, but what can you do?
  2. “We can use real values instead of NULL”.
    That may be the case for “from”, but not for “to” because there is no valid “to” value that is strictly greater than every valid “to” value!
  3. “Oracle doesn’t index NULLs”.
    Oracle does not index a row if all of the columns to be indexed are NULL. When this is a problem, it can be worked around.
  4. “Queries on NULLable ranges are hard”.
    We’ll see if I am up to the task…
  5. “Unique constraints don’t work with NULL”.
    Again, when this is a problem there are workarounds.

Next up: test data! If the queries are hard, I must try to test them thoroughly.

 

Optimistic Locking 9: proof of concept

To wind up this series about optimistic locking using the SCN, here is a sample API for querying and updating the DEPT table, using JSON as the format for exchanging data with the client application.

I want to make optimistic locking as unobtrusive as possible, even if it means more code for me:

  • the DEPT table does not have to be created with ROWDEPENDENCIES. The ORA_ROWSCN pseudocolumn reflects the latest change to the data block, not to one specific row.
  • the client application receives just one SCN when it queries data. Its only responsibility is to return the same SCN when it wants to update the data.
  • Being “optimistic”, I assume that most of the time the data block will not have changed, so the update will succeed directly.
  • If and only if the data block has changed, I check to see if the actual column values have changed.

The API

(Sorry about the lack of line numbers, there is a problem with the [ code ] tag at one point in the package body.)

create or replace package dept_json as
  function get_depts return varchar2;
  procedure update_depts(p_json in varchar2);
end dept_json;

The GET_DEPTS function returns one VARCHAR2 containing all the departments in JSON format, together with the SCN:

{
  "data_version_num" : 56781167,
  "depts" :
  [
    {
      "deptno" : 10,
      "dname" : "ACCOUNTING",
      "loc" : "NEW YORK"
    },
    {
      "deptno" : 20,
      "dname" : "RESEARCH",
      "loc" : "DALLAS"
    },
    {
      "deptno" : 30,
      "dname" : "SALES",
      "loc" : "CHICAGO"
    },
    {
      "deptno" : 40,
      "dname" : "OPERATIONS",
      "loc" : "BOSTON"
    }
  ]
}

In this simplistic proof of concept, the UPDATE_DEPTS API sends back JSON in exactly the same format with the same “data_version_num” and the changed data:

{
  "data_version_num" : 56781167,
  "depts" :
  [
    {
      "deptno" : 10,
      "dname" : "ACCOUNTING",
      "loc" : "NEW LOC"
    }
  ]
}

Getting the data

create or replace package body dept_json as
  ...
  function get_depts return varchar2 is
    l_json varchar2(4000 byte);
    l_scn number;
  begin
    l_scn := dbms_flashback.get_system_change_number;
    select json_object(
      'data_version_num' value l_scn,
      'depts' value json_arrayagg(
        json_object(
          'deptno' value deptno,
          'dname' value dname,
          'loc' value loc  
        ) order by deptno
      )
    )
    into l_json
    from dept;
    return l_json;
  end get_depts;
  ...
end dept_json;

Using the 12c SQL/JSON functions, I can query the data and convert it to JSON format immediately. I get an SCN just before querying the data. In a busy database, the actual “read SCN” may be slightly higher. See Optimistic Locking 5: “Read-consistent” SCN for a discussion.

Updating the data

create or replace package body dept_json as

  type tt_dept is table of dept%rowtype;  
  cursor c_request is select 0 read_scn, d.* from dept d;
  type tt_request is table of c_request%rowtype;
  ...
  procedure update_depts(p_json in varchar2) is
    lt_request tt_request;
    lt_try_again tt_request := new tt_request();
    c_char constant varchar2(1) := '*';
    lt_dept tt_dept := new tt_dept();
  begin
    select * bulk collect into lt_request
    from json_table(p_json, '$' columns
      read_scn number path '$.data_version_num',
      nested path '$.depts[*]' columns (
        deptno number path '$.deptno',
        dname varchar2(40) path '$.dname',
        loc varchar2(40) path '$.loc'
      )
    )
    order by deptno;

    forall i in 1..lt_request.count
      update dept set dname = lt_request(i).dname, loc = lt_request(i).loc
      where deptno = lt_request(i).deptno
      and coalesce(c_char, dname||loc) is not null
      and ora_rowscn <= lt_request(i).read_scn;
  ...
  end update_depts;
end dept_json;

This is the first part of the update procedure. I convert the JSON input to SQL format, then I do a conditional update: the update will succeed only if ORA_ROWSCN remains less that the SCN supplied by the GET_DEPTS function. The line in italics is necessary to ensure “restartability” of the update: see Optimistic Locking 7: Restartability for details.

Double-checking

After the first UPDATE, I gather the rows that were not updated into a new collection.

  procedure update_depts(p_json in varchar2) is
    lt_request tt_request;
    lt_try_again tt_request := new tt_request();
    c_char constant varchar2(1) := '*';
    lt_dept tt_dept := new tt_dept();
  begin
    -- I have removed the code for the first UPDATE
    for i in 1..lt_request.count loop
      if sql%bulk_rowcount(i) = 0 then
        lt_try_again.extend;
        lt_try_again(lt_try_again.last) := lt_request(i);
        dbms_output.put_line('deptno '||lt_request(i).deptno||': SCN too recent');
      else
        dbms_output.put_line('deptno '||lt_request(i).deptno||': first update succeeded');
      end if;
    end loop;

Now I use a flashback query to get the actual column values I sent to the client application in the first place.

    if lt_try_again.count > 0 then
      lt_dept := select_depts_flashback(lt_try_again);
  function select_depts_flashback(
    pt_request in tt_request
  ) return tt_dept is
    pragma autonomous_transaction;
    lt_dept tt_dept;
    lt_deptno sys.odcinumberlist := new sys.odcinumberlist();
  begin
    lt_deptno.extend(pt_request.count);
    for i in 1..pt_request.count loop
      lt_deptno(i) := pt_request(i).deptno;
    end loop;
    dbms_flashback.enable_at_system_change_number(pt_request(1).read_scn);
    select * bulk collect into lt_dept
    from dept where deptno in (select * from table(lt_deptno))
    order by deptno;
    dbms_flashback.disable;
    return lt_dept;
  end select_depts_flashback;

Finally, I do a second update that will only succeed if the actual column values have not changed. If there has been a change, I raise an exception. That will cause all of the updates to be rolled back automatically, thanks to Statement-Level Atomicity.

      forall i in 1..lt_try_again.count
        update dept set dname = lt_try_again(i).dname, loc = lt_try_again(i).loc
        where deptno = lt_try_again(i).deptno
        and decode(lt_dept(i).dname, dname, 0, 1)
          + decode(lt_dept(i).loc,   loc,   0, 1)
          = 0;

      for i in 1..lt_try_again.count loop
        if sql%bulk_rowcount(i) = 0 then raise_application_error(
          -20001,
          'DEPT row with DEPTNO = ' 
          || lt_dept(i).deptno 
          ||' already changed by another user. No updates have been made.'
          );
        else
          dbms_output.put_line('deptno '||lt_request(i).deptno||': second update succeeded');
        end if;
      end loop;
    end if;

  end update_depts;
end dept_json;

 

A few tests

I’m going to create a DEPT table with the data in three different blocks.

drop table dept cascade constraints purge;
CREATE TABLE DEPT(
  DEPTNO NUMBER(2) CONSTRAINT PK_DEPT PRIMARY KEY,
	DNAME VARCHAR2(14),
	LOC VARCHAR2(13) 
);
INSERT INTO DEPT VALUES	(10,'ACCOUNTING','NEW YORK');
commit;
INSERT /*+ append */ INTO DEPT 
select 20,'RESEARCH','DALLAS' from dual
union all
select 30,'SALES','CHICAGO' from dual;
commit;
INSERT /*+ append_values */ INTO DEPT VALUES (40,'OPERATIONS','BOSTON');
commit;

select d.*,
DBMS_ROWID.ROWID_BLOCK_NUMBER(rowid) block_num,
ora_rowscn
from dept d;

    DEPTNO DNAME          LOC            BLOCK_NUM ORA_ROWSCN
---------- -------------- ------------- ---------- ----------
        10 ACCOUNTING     NEW YORK           80742   56026114
        20 RESEARCH       DALLAS             85848   56026119
        30 SALES          CHICAGO            85848   56026119
        40 OPERATIONS     BOSTON             85849   56026122

>> Test 1: update with no intervening update
SQL> begin
  2  dept_json.update_depts(
  3  '{"data_version_num":56781167,"depts":[{"deptno":10,"dname":"ACCOUNTING","loc":"Test 1"}]}'
  4  );
  5  end;
  6  /
deptno 10: first update succeeded

PL/SQL procedure successfully completed.

>> Test 2: update with intervening select for update
SQL> select * from dept where deptno = 20 for update;

    DEPTNO DNAME          LOC          
---------- -------------- -------------
        20 RESEARCH       DALLAS       

SQL> commit;

Commit complete.

SQL> begin
  2  dept_json.update_depts(
  3  '{"data_version_num":56781167,"depts":[
  4  {"deptno":20,"dname":"RESEARCH","loc":"Test 2"},
  5  {"deptno":30,"dname":"SALES","loc":"CHICAGO"}
  6  ]}'
  7  );
  8  end;
  9  /
deptno 20: SCN too recent
deptno 30: SCN too recent
deptno 20: second update succeeded
deptno 30: second update succeeded

PL/SQL procedure successfully completed.

>> Test 3: update refused, intervening update
SQL> update dept set loc = 'Test 3a' where deptno = 30;

1 row updated.

SQL> commit;

Commit complete.

SQL> begin
  2  dept_json.update_depts(
  3  '{"data_version_num":56781167,"depts":[
  4  {"deptno":20,"dname":"RESEARCH","loc":"Test 2"},
  5  {"deptno":30,"dname":"SALES","loc":"Test 3b"}
  6  ]}
  7  ');
  8  end;
  9  /
deptno 20: SCN too recent
deptno 30: SCN too recent
...
Error report -
ORA-20001: DEPT row with DEPTNO = 20 already changed by another user. No updates have been made.

>> Test 4: update refused, intervening update with restart
/* In another session
update dept set loc = 'Test 4a' where deptno = 40;
*/
SQL> begin
  2  dept_json.update_depts(
  3  '{"data_version_num":56781167,"depts":[
  4  {"deptno":40,"dname":"OPERATIONS","loc":"Test 4b"}
  5  ]}'
  6  );
  7  end;
  8  /
  
/* In another session
commit;
*/
deptno 40: SCN too recent
...
Error report -
ORA-20001: DEPT row with DEPTNO = 40 already changed by another user. No updates have been made.

Conclusion

To repeat a bit of what I said in Optimistic Locking 4: the Good :

If you base optimistic locking on row version numbers, row timestamps, or checksums of row columns, then the client code has to keep track of that data and send it back with the updates. With the SCN, the data from each row is just user data, not technical data. It can be pivoted, unpivoted, aggregated or denormalized. With JSON, it is trivial to separate the SCN from all the user data.

All the client code has to do is keep the SCN somewhere and include it in the call to the update API.

P.S. the package body

create or replace package body dept_json as

  type tt_dept is table of dept%rowtype;  
  cursor c_request is select 0 read_scn, d.* from dept d;
  type tt_request is table of c_request%rowtype;

  function get_depts return varchar2 is
    l_json varchar2(4000 byte);
    l_scn number;
  begin
    l_scn := dbms_flashback.get_system_change_number;
    select json_object(
      'data_version_num' value l_scn,
      'depts' value json_arrayagg(
        json_object(
          'deptno' value deptno,
          'dname' value dname,
          'loc' value loc  
        ) order by deptno
      )
    )
    into l_json
    from dept;
    return l_json;
  end get_depts;

  function select_depts_flashback(
    pt_request in tt_request
  ) return tt_dept is
    pragma autonomous_transaction;
    lt_dept tt_dept;
    lt_deptno sys.odcinumberlist := new sys.odcinumberlist();
  begin
    lt_deptno.extend(pt_request.count);
    for i in 1..pt_request.count loop
      lt_deptno(i) := pt_request(i).deptno;
    end loop;
    dbms_flashback.enable_at_system_change_number(pt_request(1).read_scn);
    select * bulk collect into lt_dept
    from dept where deptno in (select * from table(lt_deptno))
    order by deptno;
    dbms_flashback.disable;
    return lt_dept;
  end select_depts_flashback;

  procedure update_depts(p_json in varchar2) is
    lt_request tt_request;
    lt_try_again tt_request := new tt_request();
    c_char constant varchar2(1) := '*';
    lt_dept tt_dept := new tt_dept();
  begin
    select * bulk collect into lt_request
    from json_table(p_json, '$' columns
      read_scn number path '$.data_version_num',
      nested path '$.depts[*]' columns (
        deptno number path '$.deptno',
        dname varchar2(40) path '$.dname',
        loc varchar2(40) path '$.loc'
      )
    )
    order by deptno;
    
    if lt_request.count = 0 then
      dbms_output.put_line('No depts found, so nothing to update.');
      return;
    end if;

    forall i in 1..lt_request.count
      update dept set dname = lt_request(i).dname, loc = lt_request(i).loc
      where deptno = lt_request(i).deptno
      and coalesce(c_char, dname||loc) is not null
      and ora_rowscn  0 then
      lt_dept := select_depts_flashback(lt_try_again);

      forall i in 1..lt_try_again.count
        update dept set dname = lt_try_again(i).dname, loc = lt_try_again(i).loc
        where deptno = lt_try_again(i).deptno
        and decode(lt_dept(i).dname, dname, 0, 1)
          + decode(lt_dept(i).loc,   loc,   0, 1)
          = 0;

      for i in 1..lt_try_again.count loop
        if sql%bulk_rowcount(i) = 0 then raise_application_error(
          -20001,
          'DEPT row with DEPTNO = ' 
          || lt_dept(i).deptno 
          ||' already changed by another user. No updates have been made.'
          );
        else
          dbms_output.put_line('deptno '||lt_request(i).deptno||': second update succeeded');
        end if;
      end loop;
    end if;

  end update_depts;
end dept_json;

Optimistic Locking 8: double-checking with flashback

Some optimistic locking methods, including the SCN method, can detect intervening updates even when column values have not really changed. With the SCN method, we can use flashback queries to confirm that real changes occurred.

Flashback queries are evil

As soon as we mention flashback queries, some wise DBAs will immediately object that such queries harm the “shared pool”. This is a serious objection; let me explain why.

Before executing a SQL statement, Oracle must parse it and establish an execution plan: this is called the “hard parse”. Hard parsing can be an expensive operation, and it can be a bottleneck since it uses resources that must be serialized. To avoid constant parsing, Oracle stores executable forms of SQL cursors and PL/SQL programs in the “library cache”, which is part of the shared pool. This enables “parse once, execute many”, a prerequisite for good performance in OLTP databases.

Imagine a SQL statement that must be hard parsed before every execution. That one statement will use up resources and slow down parsing of other new statements. Not good. Now imagine that the “cursor” resulting from that parse goes into the library cache: the cache will get bigger and bigger and slower to navigate, until finally other cursors start getting aged out. We now have a dysfunctional database that spends its time hard parsing instead of executing statements.

Unfortunately, one of those statements that gets hard parsed every time is the AS OF flashback query :-(

To demonstrate this, I’ll run a simple AS OF query in a PL/SQL block, using the same SCN every time. Note that I flush the shared pool beforehand, so there will always be a first hard parse.

declare 
  l_scn number;
  l_cnt number;
begin
  dbms_flashback.disable;
  execute immediate 'alter system flush shared_pool';
  l_scn := dbms_flashback.get_system_change_number;
  for i in 1..10 loop
    select count(*) into l_cnt from T as of scn l_scn;
  end loop;
end;
/

Now I’ll query V$SQL_SHARED_CURSOR to see what cursors could not be “shared” and had to be hard parsed over and over again.

select child_number, parse_calls, executions, reason "Reason: AS OF SCN"
from v$sql
left join V$SQL_SHARED_CURSOR using(sql_id, child_number)
where sql_text like 'SELECT COUNT(*) FROM T%';

CHILD_NUMBER PARSE_CALLS EXECUTIONS Reason: AS OF SCN                                                               
------------ ----------- ---------- --------------------------------------------------------------------------------
           0           1          1 <ChildNode><ChildNumber>0</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           1           1          1 <ChildNode><ChildNumber>1</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           2           1          1 <ChildNode><ChildNumber>2</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           3           1          1 <ChildNode><ChildNumber>3</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           4           1          1 <ChildNode><ChildNumber>4</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           5           1          1 <ChildNode><ChildNumber>5</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           6           1          1 <ChildNode><ChildNumber>6</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           7           1          1 <ChildNode><ChildNumber>7</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           8           1          1 <ChildNode><ChildNumber>8</ChildNumber><ID>21</ID><reason>Flashback cursor(1)</r
           9           1          1 

Formatted content of first Reason:
<ChildNode>
  <ChildNumber>0</ChildNumber>
  <ID>21</ID>
  <reason>Flashback cursor(1)</reason>
  <size>3x4</size>
  <Flashback_cursor>0</Flashback_cursor>
  <As_of_cursor>1</As_of_cursor>
  <Flashback_session>0</Flashback_session>
</ChildNode>

Compare this to a normal query:

declare 
  l_cnt number;
begin
  execute immediate 'alter system flush shared_pool';
  for i in 1..10 loop
    select count(*) into l_cnt from T;
  end loop;
end;
/
select child_number, parse_calls, executions, reason "Reason: no flashback"
from v$sql
left join V$SQL_SHARED_CURSOR using(sql_id, child_number)
where sql_text like 'SELECT COUNT(*) FROM T%';

CHILD_NUMBER PARSE_CALLS EXECUTIONS Reason: no flashback
------------ ----------- ---------- --------------------
           0           1         10

Flashback queries are evil – not all the time

Instead of adding AS OF SCN to every table in my query, I can use DBMS_FLASHBACK.ENABLE_AT_SYSTEM_CHANGE_NUMBER to set the “consistent read” SCN for every table in every query. Let’s see what happens with this technique:

declare 
  l_scn number;
  l_cnt number;
begin
  dbms_flashback.disable;
  execute immediate 'alter system flush shared_pool';
  l_scn := dbms_flashback.get_system_change_number - 1001;
  for i in 1..10 loop
    dbms_flashback.enable_at_system_change_number(l_scn+i);
    select count(*) into l_cnt from T;
    dbms_flashback.disable;
  end loop;
end;
/
select child_number, parse_calls, executions, reason "DBMS_FLASHBACK, increasing SCN"
from v$sql
left join V$SQL_SHARED_CURSOR using(sql_id, child_number)
where sql_text like 'SELECT COUNT(*) FROM T%';

CHILD_NUMBER PARSE_CALLS EXECUTIONS DBMS_FLASHBACK, increasing SCN
------------ ----------- ---------- ------------------------------
           0          10         10

Notice that there are 10 “parse calls” here. Oracle did a “soft parse”, that is it looked in the library cache for a cursor that could be reused, and it found one. This is extra work as compared to a normal query, but not nearly as much as a hard parse. More importantly, the library cache is not flooded with useless child cursors.

Conclusion

It turns out that we can safely use this technique under certain conditions:

  • The FLASHBACK and SELECT privileges must be granted on whatever tables we want to query;
  • The EXECUTE privilege must be granted on DBMS_FLASHBACK;
  • The SCN parameter of ENABLE_AT_SYSTEM_CHANGE_NUMBER must be increasing! If it decreases, we get hard parses and extra child cursors.
    This should never be a problem in the “optimistic locking” use case.

Optimistic Locking 7: Restartability

When we UPDATE, Oracle may find a discrepancy between the read-consistent and “current” versions of the data. If so, Oracle “restarts” the process. Our optimistic locking solution must make that happen when appropriate.

(It’s been a long time since my last post on this subject: see Optimistic Locking 4: the Good for context.)

What happens when we UPDATE?

(To simplify, I will only talk about the default READ COMMITTED isolation level.)

If we do an UPDATE without a prior SELECT FOR UPDATE,

  • Oracle will start by doing “consistent gets” of the target rows. This produces a result set that is read-consistent.
  • Next, Oracle will do “current gets” to lock and update the target rows.
    • If there is a predicate in the WHERE clause, such as WHERE HIREDATE > TRUNC(SYSDATE, 'YY'), and the column has been changed in the meantime, then Oracle will check whether the WHERE clause is still satisfied,
    • and if not then Oracle will “restart” the update processing.

Oracle will not stop until it has gotten and locked current versions of all the rows that meet the WHERE clause criteria in a read-consistent manner.

Re-evaluate, then (maybe) Restart

To make sure restarts happen when they should, we need to know:

  1. What columns set off the re-evaluation? To set off the re-evaluation, a changed column must be referenced in the WHERE clause or in a BEFORE UPDATE...FOR EACH ROW trigger. The ORA_ROWSCN pseudocolumn does not set off a re-evaluation.
  2. Once the re-evaluation is under way, what additional data is evaluated to decide whether to restart?
    If the re-evaluation takes place, the entire WHERE clause is evaluated.
    If ORA_ROWSCN is included in the WHERE clause, its “current” value is used in any comparison.

If we want to use ORA_ROWSCN for optimistic locking, we need to reference in the WHERE clause any columns we ourselves change. That will set off the re-evaluation, which will then use ORA_ROWSCN to determine whether some other process has changed the row since we last queried it.

See Avoiding Lost Updates with ORA_ROWSCN for a demonstration. Here is an example of an UPDATE that will restart when necessary:

update emp set sal = 800, deptno = 30
where empno = 7369
and ora_rowscn <= 13865770
and coalesce('*',sal || deptno) is not null;

I decided to use COALESCE to refer to the column values because it uses short-circuit evaluation. Once it determines that ‘*’ is not null, it doesn’t bother evaluating the concatenation of the columns. Also, concatenation implicitly converts every datatype to VARCHAR2 so I can list strings, dates, timestamps, numbers and intervals without worry. To prevent the Optimizer from removing that condition someday, I could replace ‘*’ by a bind variable with a non-null value.

Conclusion

ORA_ROWSCN can indeed be used as a “version number” that can be checked to avoid lost updates. The UPDATE statement just has to list the appropriate columns in the WHERE clause, but it doesn’t have to check them against values from a prior SELECT statement. The only real value that needs to be checked is ORA_ROWSCN.

In the next post I’ll address the problem of “false alarms”: ORA_ROWSCN will tell us that a row has previously been updated, but it will not say whether the values have really changed in the columns we care about.