Chunking tables 6: JOIN solution

At last, here is the first complete solution to the problem of dividing a table into 12 chunks with equal numbers of blocks. James Su and I proposed this solution on OTN, but without the “filtered_extents” optimisation.

The OTN solution is the basis for what Bryn Llewellyn calls “Approx_Method_Sql_Ashton_1” in his white paper.

Current list of posts: 

Preparation

drop table t purge;

create table t as
select rpad('x', 4000, 'x') x
from dual
connect by level <= 130;

var owner varchar2(128);
var table_name varchar2(128);
var num_chunks number;
begin
  :owner := user;
  :table_name := 'T';
  :num_chunks := 12;
end;
/

Up to now I have been hard-coding the owner name, the table name and the number of chunks (12). I hoped this would make the explanation a bit more concrete and therefore easier to follow. Now it’s time to remember that such values should be held in variables, both as a good programming practice and to allow Oracle to reuse the SQL statement without having to parse it every time. Here I am using “host variables”, because it is easier to test the query bit by bit when it is not wrapped in PL/SQL. Ultimately this SQL should live inside a PL/SQL function with formal parameters.

Overview

  1. extents_data: get all extents and data object ids for the table
  2. extents_with_sums:
    1. treat all the table blocks as if they were one contiguous set;
    2. number all the blocks in ascending sequence
    3. calculate total number of blocks
  3. filtered_extents: filter out the extents that do not contain a chunk boundary
  4. chunk_boundaries: calculate the chunk boundaries
  5. rowids:
    1. Use JOIN to map chunk boundaries to extents;
    2. calculate each ROWID
    3. group by chunk

extents_data

with extents_data as (
  select /*+ qb_name(extents_data) */
    o.data_object_id, e.file_id, e.block_id, e.blocks
  from dba_extents e
  join all_objects o
  on e.owner = o.owner
    and e.segment_name = o.object_name
    and e.segment_type = o.object_type
    and decode(e.partition_name, o.subobject_name, 0, 1) = 0
  where e.segment_type like 'TABLE%'
    and e.owner = :owner
    and e.segment_name = :table_name
)

I wrote a series of named subqueries using the WITH() clause, and gave a “query block name” (qb_name) equal to the subquery name in order to better understand the execution plan. It turns out that the optimizer rewrites the query in such a way that some of the qb_names disappear.

This first clause provides the raw material for calculating the ROWIDs we need: the data object ids, the file ids, the block ids and the number of blocks per chunk.

extents_with_sums

, extents_with_sums as (
  select /*+ qb_name(extents_with_sums) */
    sum(blocks) over() as total_blocks,
    sum(blocks) over(
      order by data_object_id, file_id, block_id
    ) - blocks as first_extent_block,
    sum(blocks) over(
      order by data_object_id, file_id, block_id
    ) - 1 as last_extent_block,
    e.*
  from extents_data e
) 

This subquery gets the total number of blocks (available in each row of the output), plus two running totals:

  • The number of blocks up to but not including the current extent.
    Since I am numbering the blocks consecutively starting from zero, this is the number assigned to the first block of the current extent.
  • The number of blocks up to and including the current extent, minus one.
    This is the number assigned to the last block of the current extent.

filtered_extents

, filtered_extents as (
  select /*+ qb_name(filtered_extents) */ * from (
    select
      width_bucket(first_extent_block-1, 0, total_blocks, :num_chunks)
        as prev_chunk,
      width_bucket(last_extent_block+1, 0, total_blocks, :num_chunks)
        as next_chunk,
      e.*
    from extents_with_sums e
  )
  where prev_chunk < next_chunk
)

Here I eliminate extents that do not contain any chunk boundaries.

  • WIDTH_BUCKET() tells me to which chunk a block belongs.
  • PREV_CHUNK is the chunk to which the end of the previous extent belongs.
  • NEXT_CHUNK is the chunk to which the start of the next extent belongs.
  • If they are the same, then the current extent is in the middle of a chunk and I can safely eliminate it.

For details on how I use WIDTH_BUCKET() here, and CEIL() in the next section, click here: https://stewashton.wordpress.com/2016/02/04/chunking-tables-4-histograms/

chunk_boundaries

, chunk_boundaries as (
  select  /*+qb_name(chunk_boundaries) */
    level chunk,
    CEIL( (level-1) * total_blocks / :num_chunks - 1 ) + 1 first_chunk_block,
    CEIL(  level    * total_blocks / :num_chunks - 1 )     last_chunk_block
  from (select total_blocks from extents_with_sums where rownum = 1)
  connect by level <= least(:num_chunks, total_blocks)
)

Having the extents and the extent boundaries, I now need the chunk boundaries.

  • I get TOTAL_BLOCKS by querying the first row from the EXTENTS_WITH_SUMS subquery.
  • Each chunk has a range equal to TOTAL_BLOCKS / :NUM_CHUNKS
  • The upper boundary of each chunk is LEVEL times that range
  • I need the last block that is less than the upper boundary, so I subtract 1 and then use CEIL().
  • least(:num_chunks, total_blocks) ensures that the number of chunks cannot be more than the total number of blocks. This is an alternative to raising an exception.

rowids

, rowids as (
  select  /*+qb_name(rowids) */ chunk,
    case when b.first_chunk_block
      between e.first_extent_block and e.last_extent_block then
        dbms_rowid.rowid_create(
          1, data_object_id, file_id,
          block_id + first_chunk_block - first_extent_block, 0
        )
    end as start_rowid,
    case when b.last_chunk_block
      between e.first_extent_block and e.last_extent_block then
        dbms_rowid.rowid_create(
          1, data_object_id, file_id,
          block_id + last_chunk_block - first_extent_block, 32767
        )
    end as end_rowid
  from chunk_boundaries b
  join filtered_extents e
  on b.first_chunk_block between e.first_extent_block and e.last_extent_block
   or b.last_chunk_block between e.first_extent_block and e.last_extent_block
)
select chunk, max(start_rowid) start_rowid, max(end_rowid) end_rowid
from rowids
group by chunk;

This is the heart of the solution. By joining the extents to the chunk boundaries, I automatically expand any extent that spans more than one chunk. If I ask for 12 chunks, the JOIN will return between 12 and 24 rows. I calculate START_ROWID only when appropriate, otherwise it is null – and the same goes for END_ROWID.

Finally, I condense the result into 12 rows using GROUP BY.

Evolution

My version of this solution has changed over time.

  • On OTN and in Bryn Llewellyn’s white paper, I did not filter the extents.
  • I now make sure my numbering scheme always starts with zero.
  • I have also incorporated WIDTH_BUCKET() and changed the way I calculate chunk boundaries to be coherent.

Next, another solution, this time without a join.

By the way, here is the code all together if anyone wants to copy and paste.

with extents_data as (
  select /*+ qb_name(extents_data) */
    o.data_object_id, e.file_id, e.block_id, e.blocks
  from dba_extents e
  join all_objects o
  on e.owner = o.owner
    and e.segment_name = o.object_name
    and e.segment_type = o.object_type
    and decode(e.partition_name, o.subobject_name, 0, 1) = 0
  where e.segment_type like 'TABLE%'
    and e.owner = :owner
    and e.segment_name = :table_name
)
, extents_with_sums as (
  select /*+ qb_name(extents_with_sums) */
    sum(blocks) over() as total_blocks,
    sum(blocks) over(
      order by data_object_id, file_id, block_id
    ) - blocks as first_extent_block,
    sum(blocks) over(
      order by data_object_id, file_id, block_id
    ) - 1 as last_extent_block,
    e.*
  from extents_data e
)
, filtered_extents as (
  select /*+ qb_name(filtered_extents) */ * from (
    select
      width_bucket(first_extent_block-1, 0, total_blocks, :num_chunks)
        as prev_chunk,
      width_bucket(last_extent_block+1, 0, total_blocks, :num_chunks)
        as next_chunk,
      e.*
    from extents_with_sums e
  )
  where prev_chunk < next_chunk
)
, chunk_boundaries as (
  select  /*+qb_name(chunk_boundaries) */
    level chunk,
    CEIL( (level-1) * total_blocks / :num_chunks - 1 ) + 1 first_chunk_block,
    CEIL(  level    * total_blocks / :num_chunks - 1 )     last_chunk_block
  from (select total_blocks from extents_with_sums where rownum = 1)
  connect by level <= least(:num_chunks, total_blocks)
)
, rowids as (
  select  /*+qb_name(rowids) */ chunk,
    case when b.first_chunk_block
      between e.first_extent_block and e.last_extent_block then
        dbms_rowid.rowid_create(
          1, data_object_id, file_id,
          block_id + first_chunk_block - first_extent_block, 0
        )
    end as start_rowid,
    case when b.last_chunk_block
      between e.first_extent_block and e.last_extent_block then
        dbms_rowid.rowid_create(
          1, data_object_id, file_id,
          block_id + last_chunk_block - first_extent_block, 32767
        )
    end as end_rowid
  from chunk_boundaries b
  join filtered_extents e
  on b.first_chunk_block between e.first_extent_block and e.last_extent_block
   or b.last_chunk_block between e.first_extent_block and e.last_extent_block
)
select chunk, max(start_rowid) start_rowid, max(end_rowid) end_rowid
from rowids
group by chunk;

Chunking tables 5: chunk boundaries

We still want to split a table into 12 chunks with equal numbers of blocks, so we can access each chunk using a rowid range. We have the extents we need and now we need to calculate the exact chunk boundaries.

Current list of posts: 

Histograms and WIDTH_BUCKET

I explained in my previous post that WIDTH_BUCKET is based on a histogram having identical intervals in a range.

  • The minimum range value is included in the range but the maximum range value is not.
  • The same thing is true for each interval: the minimum value is included in the interval, but not the maximum value.

We have already used WIDTH_BUCKET to answer the question: “what chunk is this block in?” Now we are asking the opposite question: “what blocks start and end this chunk?” We need to make absolutely sure the answers are coherent!

Getting the upper chunk boundary

Using our test table from the previous post, let’s compare what WIDTH_BUCKET tells us with a wrong answer and a right answer. Then I’ll explain in detail. Right now, I’m only interested in those blocks that end a chunk.

select this_block_chunk, block last_block,
  round(256 * (this_block_chunk / 12), 1) max_chunk_val,
  floor(256 * (this_block_chunk / 12)) floor_val,
  ceil (256 * (this_block_chunk / 12) - 1) right_val
from (
  select level-1 block,
  width_bucket(level-1,0,256,12) this_block_chunk,
  width_bucket(level,0,256,12) next_block_chunk
  from dual
  connect by level <= 256
)
where this_block_chunk < next_block_chunk;
THIS_BLOCK_CHUNK LAST_BLOCK MAX_CHUNK_VAL FLOOR_VAL RIGHT_VAL
1 21 21.3 21 21
2 42 42.7 42 42
3 63 64 64 63
4 85 85.3 85 85
5 106 106.7 106 106
6 127 128 128 127
7 149 149.3 149 149
8 170 170.7 170 170
9 191 192 192 191
10 213 213.3 213 213
11 234 234.7 234 234
12 255 256 256 255

 

For each block, I asked WIDTH_BUCKET what chunk it is in and what chunk the next block is in, and I kept only those blocks where the next block is in the next chunk. That means I have a list of the last blocks for each chunk.

In the third column, I calculate the maximum value for each chunk. Notice it is not always an integer value. How can we calculate the greatest block number that is less than that maximum value?

  • Using CEIL() or ROUND(), we will sometimes get a result that is greater than the maximum value.
  • Using FLOOR(), we will sometimes get a result that is equal to the maximum value – but we need to be less than, not equal to! You can see the problem in chunks 3, 6, 9 and 12.
  • The right answer is to subtract 1 from the maximum value and then use CEIL(). That way the result will always be less than the maximum value, but as close to it as possible.

Getting the lower chunk boundary

I’ll bet you thought of this yourself. The lower boundary of a chunk is one greater that the upper boundary of the previous chunk :-)

Coming next…

We have the extents we need, and we have a method for calculating all the chunk boundaries. In the next post, I’ll present the first of two complete solutions for chunking a table.

Current list of posts: 

Chunking tables 4: Histograms

After “only” 3 posts on chunking tables, we now have the raw materials for breaking up a table into 12 chunks with equal numbers of blocks, and for getting ROWID ranges that let us access the data. Now let’s chunk!

Current list of posts:

What needs to be done?

The basic idea is pretty simple:

  1. Treat all the table blocks as if they were one contiguous set
  2. Number all the blocks in ascending sequence
  3. Filter out the extents that do not contain a chunk boundary
    (yes, I do this before the next step!)
  4. Calculate the chunk boundaries
  5. Map each chunk boundary to the corresponding block in the right extent
  6. Calculate each ROWID

One contiguous set

Blocks within an extent are contiguous, at least as seen by us. Blocks in different extents may not be contiguous; they may even live in different files or data objects. We don’t care about any of that as long as our ROWID ranges work. For that, we just need to order the “raw material” by data_object_id, file_id and block_id. That way all the extents (and the blocks in the extents) will be ordered by ascending ROWID value.

Number the blocks in ascending sequence

For this we can use the analytic SUM() function to get the running sum of blocks as we go through the extents in the correct order.

One more thing: to calculate the chunk boundaries, we are going to need the total number of blocks in the table. A different analytic SUM() function will provide that total.

To better demonstrate, I’m going to create a bigger table.

create table t as
select rpad('x', 4000, 'x') x
from dual
connect by level <= 130;

with extents_data as (
  select /*+ qb_name(extents_data) */
    o.data_object_id, e.file_id, e.block_id, e.blocks
  from dba_extents e
  join all_objects o
  on e.owner = o.owner
    and e.segment_name = o.object_name
    and e.segment_type = o.object_type
    and decode(e.partition_name, o.subobject_name, 0, 1) = 0
  where e.segment_type like 'TABLE%'
    and e.owner = user
    and e.segment_name = 'T'
)
, extents_with_sums as (   
  select /*+ qb_name(extents_with_sums) */
    sum(blocks) over() as total_blocks, 
    sum(blocks) over(
      order by data_object_id, file_id, block_id
    ) - blocks as first_extent_block,   
    sum(blocks) over(
      order by data_object_id, file_id, block_id
    ) as next_extent_block, 
    e.*
  from extents_data e 
) 
select * from extents_with_sums;
TOTAL_BLOCKS FIRST_EXTENT_BLOCK NEXT_EXTENT_BLOCK BLOCK_ID BLOCKS
256 0 8 128 8
256 8 16 136 8
256 16 24 144 8
256 24 32 152 8
256 32 40 160 8
256 40 48 168 8
256 48 56 176 8
256 56 64 184 8
256 64 72 192 8
256 72 80 200 8
256 80 88 208 8
256 88 96 216 8
256 96 104 224 8
256 104 112 232 8
256 112 120 240 8
256 120 128 248 8
256 128 256 256 128

I removed two columns from the output to make it fit better.

There are a lot of things to notice here, so bear with me:

  • I break the entire SQL query into a series of subqueries using WITH clauses.
  • Each WITH clause gets a “query block name” (qb_name) equal to the subquery name. I hope this will make it easier to analyze the execution plan.
  • In the numbering scheme, I chose to start with 0 and not with 1 because the math is a bit easier.
  • SUM(blocks) OVER() gives me the total number of blocks on every line.
  • Since I start with block 0, The running SUM() of blocks actually gives me the block number of the beginning of the next extent. To get the beginning of this extent, I just subtract the current number of blocks.
    (I could use a fancy “windowing clause” in the analytic function, but this seemed easier to explain.)
  • Since I am numbering every block consecutively, I can calculate the last block of any extent: it is one less than the first block of the following extent.
  • Since I am using ASSM, the last extent jumped from 8 blocks to 128 blocks.

Did I say histograms?

A histogram is a range divided into intervals that have identical size. Isn’t that exactly what we want? The range goes from 0 (the first block) up to but not including TOTAL_BLOCKS, and the number of intervals is the number of chunks, which is 12 in our example. To make sure no block gets put in two chunks, each interval includes the lower boundary and excludes the upper boundary. This is called a “closed-open” interval.

There is a function that does exactly what I just described:
WIDTH_BUCKET(expression, included_min_value, excluded_max_value, number_of_intervals)
or in this case
WIDTH_BUCKET(block, 0, 256, 12).

Let’s take every block from 0 to 255 and find out what chunk it is in.

select chunk, min(n) first_block, max(n) last_block,
max(n) + 1 - min(n) num_blocks
from (
  select level-2 n, 
  width_bucket(level-2,0,256,12) chunk
  from dual
  connect by level <= 258
)
group by chunk
order by chunk;
CHUNK FIRST_BLOCK LAST_BLOCK NUM_BLOCKS
0 -1 -1 1
1 0 21 22
2 22 42 21
3 43 63 21
4 64 85 22
5 86 106 21
6 107 127 21
7 128 149 22
8 150 170 21
9 171 191 21
10 192 213 22
11 214 234 21
12 235 255 21
13 256 256 1

 

I deliberately went outside the boundaries to show that they get put into “illegal” chunks: 0 and 13.

Notice that the number of blocks in each chunk is as equal as possible. This is looking pretty good.

There is one problem though: WIDTH_BUCKET answers the question “what chunk am I in?” but it doesn’t answer the question “what are the lower and upper boundaries of each bucket?” We’ll see how to do that later.

Filter unnecessary extents

This is a little performance boost that Jonathan Lewis praised. A very large table, or a table with lots of partitions, will have many rows in DBA_EXTENTS, but we are only interested in the rows that contain a chunk boundary. In our example, that means 24 rows at the most.

When does an extent not contain a chunk boundary? When the end of the previous extent and the beginning of the next extent both belong to the same chunk. Thanks to WIDTH_BUCKET and the running totals I just calculated, I can filter out those extents right now.

with extents_data as (...)
, extents_with_sums as (...) 
, filtered_extents as (  
  select /*+ qb_name(filtered_extents)*/ * from (
    select
      width_bucket(first_extent_block-1, 0, total_blocks, 12)
        as prev_chunk, 
      width_bucket(next_extent_block, 0, total_blocks, 12)
        as next_chunk, 
      e.* 
    from extents_with_sums e   
  )
  where prev_chunk < next_chunk
)
select prev_chunk, next_chunk,
  first_extent_block, next_extent_block, blocks
from filtered_extents;
PREV_CHUNK NEXT_CHUNK FIRST_EXTENT_BLOCK NEXT_EXTENT_BLOCK BLOCKS
0 1 0 8 8
1 2 16 24 8
2 3 40 48 8
3 4 56 64 8
3 4 64 72 8
4 5 80 88 8
5 6 104 112 8
6 7 120 128 8
6 13 128 256 128

 

If you compare these results with the FIRST_BLOCK and LAST_BLOCK numbers we calculated previously, you can see that the chunk boundaries are all contained within the extents we retained.

Are we done yet?

I wish I could say yes, but I can’t. We have gotten pretty far though. We have the total number of blocks, we have numbered all the blocks consecutively in the right order and we have retained only those extents that contain chunk boundaries.

In the next post I’m going to show how to calculate the chunk boundaries. Afterwards, I’ll demonstrate two methods for mapping those boundaries to extents in order to get the ROWIDs we want.

Current list of posts: 

Chunking tables 3: working with blocks

So far we’ve decided to access a table chunk by chunk, each chunk containing one twelfth of the tables’s blocks. But first, how do we access data in a chunk of blocks? How do we even know what blocks a table has?

Current list of posts:

Basics first

As a reminder:

  • Oracle stores table data in blocks (of size 8K by default)
  • Oracle allocates logically contiguous blocks in extents
  • All the extents for a data object (non-partitioned table, partition or subpartition) belong to a segment
  • A ROWID returns the address of a row, which is based on the data object number, the relative file number, the block id and the position of the row in the block

There is no direct way to access data by block id, but there is a way to access data by ROWID. If we know what blocks interest us, and if we can calculate the ROWIDs of the interesting blocks, then we should be able to access the data we want.

ROWID ranges

Let’s assume for a moment we can determine the interesting blocks and generate ROWIDs from them. How would we query the table based on those ROWIDs? By using ROWID ranges. Would that query be efficient? Let’s see…

I’m going to create a table that, in my environment, is going to have one extent of 8 8K blocks. The first 3 blocks are “bitmap blocks” for ASSM and the segment header block. There will be 10 rows per block in the remaining 5 blocks, for a total of 50 rows.

create table t as
select rpad('x', 710, 'x') x
from dual
connect by level <= 50;

select relative_fno, block_id,
count(*) num_rows,
min(rid) min_rowid, max(rid) max_rowid
from (
  select rowid rid,
  dbms_rowid.rowid_relative_fno(rowid) relative_fno,
  dbms_rowid.rowid_block_number(rowid) block_id
  from t
)
group by relative_fno, block_id
order by relative_fno, block_id;
RELATIVE_FNO BLOCK_ID NUM_ROWS MIN_ROWID MAX_ROWID
7 131 10 AAAgz5AAHAAAACDA AAAgz5AAHAAAACDJ
7 132 10 AAAgz5AAHAAAACEA AAAgz5AAHAAAACEJ
7 133 10 AAAgz5AAHAAAACFA AAAgz5AAHAAAACFJ
7 134 10 AAAgz5AAHAAAACGA AAAgz5AAHAAAACGJ
7 135 10 AAAgz5AAHAAAACHA AAAgz5AAHAAAACHJ

 

If we access the whole table, we will get the 5 blocks with rows in them, plus 2 blocks of overhead:

SQL> select /*+ gather_plan_statistics */ count(*) from t;

  COUNT(*)
----------
        50

SQL> select * from table(dbms_xplan.display_cursor(
  null,null,'IOSTATS LAST -ROWS -PREDICATE -NOTE'
));

----------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |      1 |00:00:00.01 |       7 |
|   1 |  SORT AGGREGATE    |      |      1 |      1 |00:00:00.01 |       7 |
|   2 |   TABLE ACCESS FULL| T    |      1 |     50 |00:00:00.01 |       7 |
----------------------------------------------------------------------------

Now let’s access just the rows in block 133:

SQL> select /*+ gather_plan_statistics */ count(*) from t
where rowid between chartorowid('AAAgz5AAHAAAACFAAA')
  and chartorowid('AAAgz5AAHAAAACFAAJ');

  COUNT(*)
----------
        10

SQL> select * from table(dbms_xplan.display_cursor(
  null,null,'IOSTATS LAST -ROWS -PREDICATE -NOTE'
)); 

--------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Starts | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |      |      1 |      1 |00:00:00.01 |       3 |
|   1 |  SORT AGGREGATE              |      |      1 |      1 |00:00:00.01 |       3 |
|   2 |   TABLE ACCESS BY ROWID RANGE| T    |      1 |     10 |00:00:00.01 |       3 |
--------------------------------------------------------------------------------------

We now see the operation “Table access by ROWID range”, which (outside of the 2 blocks of overhead) accessed the one and only block containing the data we wanted.

This is great news. If we can just identify the blocks we want and generate ROWIDs from them, we will be able to access each chunk very efficiently.

Identifying blocks

At last, an easy part! Just query DBA_EXTENTS.

select relative_fno, block_id, blocks
from dba_extents
where (owner, segment_name) = ((user, 'T'));
RELATIVE_FNO BLOCK_ID BLOCKS
7 128 8

 

The blocks we need go from 128 through 128+8-1, or 135.

Generating the ROWIDs

Again we’re in luck: the package DBMS_ROWID has a ROWID_CREATE function. It asks us for:

  • rowid_type: trust me, it’s 1 since Oracle 8
  • object_number: this is the data object number, which we’ll get from DBA_OBJECTS
  • relative_fno: we have this from DBA_EXTENTS
  • block_number: we have this from DBA_EXTENTS
  • row_number: we make this 0 at the beginning of a block and 32767 at the end of a block.
    (I copied 32767 from Bryn.)

Putting it all together

Once we take partitions and subpartitions into account, we can join DBA_EXTENTS to DBA_OBJECTS to get all the raw material we need for creating ROWIDs.

select o.data_object_id, e.file_id, e.block_id, e.blocks
from dba_extents e
join all_objects o
on e.owner = o.owner
  and e.segment_name = o.object_name
  and e.segment_type = o.object_type
  and decode(e.partition_name, o.subobject_name, 0, 1) = 0
where e.segment_type in ('TABLE', 'TABLE PARTITION', 'TABLE SUBPARTITION')
  and e.owner = user
  and e.segment_name = 'T';
DATA_OBJECT_ID FILE_ID BLOCK_ID BLOCKS
134393 7 128 8

 

Sanity check

Let’s generate ROWIDs from the information we got here and see if we get all the rows in table T.

select count(*) from t
where rowid between dbms_rowid.rowid_create(1,134393,7,128,0)
                and dbms_rowid.rowid_create(1,134393,7,135,32767);

The answer is 50, as expected.

In the next post, we’ll start chunking!

Current list of posts: 

Chunking tables 2: Requirement

As I mentioned in my previous post, the basic idea is to divide a table into 12 “equal chunks”, each “chunk” being a rowid range that covers the same number of blocks (give or take 1). What does this mean? Why do this? Why divide by blocks and not rows? Here are my thoughts.

Current list of posts: 

Good old batch processing

Sometimes we have to do DML on many rows in a table, perhaps massive deletes or even more massive updates. Back in the old days these operations were called “batch jobs” and we spent half our time writing them. Guess what? Today in many shops we still spend half our time writing them! These processes can cause us problems such as:

  • Taking too long to finish;
  • Using lots of resources such as temp space, undo or redo;
  • Blocking concurrent online transactions.

This last problem is more common than ever, now that many OLTP systems need to be constantly available.

Parallelism

If our SQL is “taking too long” and we have unused resources, then we can take advantage of Oracle’s built-in parallelism. This is a terrific feature that works for both SELECTs and DML, that can be configured without changing any SQL, and that does all the parallel processing within one transaction.

Unfortunately built-in parallelism tends to increase resource consumption, not decrease it, and it interferes just as much with concurrent OLTP processing. Not only that, but it stinks when accessing remote databases because it uses only one DBLINK connection.

Do-it-yourself parallelism and intermediate commits

When built-in parallelism doesn’t help, we can help ourselves by splitting the processing up into chunks. Each chunk is processed separately as a separate transaction. We can process the chunks in parallel jobs or simply do one chunk at a time.

How can this chunk-based processing help us with our problems?

  • If we process chunks in parallel,
    • everything should finish faster
    • and when accessing a remote database, we can use more than one DBLINK connection at the same time.
  • If we process the chunks serially,
    • we use less temp and undo and free up resources when we commit at the end of each chunk
    • and by committing frequently we avoid blocking online transactions for long periods.

The major drawback of chunk-based processing comes from the intermediate commits. What happens if some exception occurs and we have only processed half the chunks? Changes to those chunks have been committed, so we mustn’t process them again. We need to be able to restart the job while processing only the remaining chunks.

Since version 11.2, the Oracle database provides the DBMS_PARALLEL_EXECUTE package to enable incremental DML (in parallel or not). This package keeps track of which chunks have committed and which have not, so that upon restart the committed chunks are not done again.

To Split into “equal chunks”: use rows or blocks?

Why are we splitting our table into chunks again? In order to process separate transactions that each take less time and use fewer resources.

What’s the use of that if one of the chunks contains almost the whole table?

We need to ensure that the chunks are equal in size so that each transaction takes about the same time and uses the same amount of resources.

So how do we define “equal”? At first glance, for exact equality each chunk should have the same number of rows. For our purposes, this is not always true. Oracle does some work at the row level and some work at the block level – including all access to disk and to the buffer cache. When it comes to time spent and resources used, blocks may be a better indicator than rows.

Here’s an extreme example: a table with large rows of 4000 bytes. With 100,000 rows, it takes about 3 seconds to count the number of rows. With 10 rows, it still takes just as long to count the number of rows!

SQL> create table t as
select rpad('x', 4000, 'x') x
from dual
connect by level <= 100000;

Table T created.

SQL> select count(*) from t;

 COUNT(*)
----------
 100000

Elapsed: 00:00:03.101

SQL> delete from t where rownum <= 100000 - 100;

99,900 rows deleted.

SQL> commit;

Commit complete.

SQL> select count(*) from t;

 COUNT(*)
----------
 100

Elapsed: 00:00:04.026

Did you see what I did there? I created a table with 100,000 rows and one row per block, so 100,000 blocks (plus a few blocks of overhead). When I deleted most of the rows, that emptied out most of the blocks, but Oracle still had to access those blocks to find out whether they were empty or not!

The point is that “equality” (in time and resources) depends on the number of blocks too, not just on the number of rows, especially when doing a full table scan – which is usually the best way to do DML on an entire table.

Finally, to split a table by row count can be a costly operation, whereas splitting by block count can be done without ever accessing the table. We’ll see how in the next post.

Fixed chunk size or fixed chunk number?

The DBMS_PARALLEL_EXECUTE package proposes to create chunks with a fixed size, such as 64 blocks, and not a fixed number. Each process just does chunk after chunk until all are done. I think this is probably the most common use case. Requiring a fixed number of chunks, as Bryn has done, may be helpful to access a remote database through multiple DBLINKs.

Conclusion

  • It may be useful to do DML on a table by breaking it up into chunks of equal size, each of which is processed in a separate transaction.
  • “Equal size” can be measured in rows or blocks, but block-based chunks can be created efficiently without accessing the table.
  • DBMS_PARALLEL_EXECUTE creates chunks of a fixed size, but here we want to create a fixed number of chunks.

Now we need a way to create a fixed number of chunks (with equal numbers of blocks), and a way to access the data in each chunk efficiently. Maybe the next post will help us do that…

Current list of posts:

Chunking tables 1: Genesis

When I helped answer a question from Jonathan Lewis on OTN, little did I know that I would become a participant in a presentation and white paper by Bryn Llewellyn on “Transforming one table to another: SQL or PL/SQL?

Jonathan wanted help in finishing up an efficient SQL solution for dividing a table into 12 “equal chunks”, each “chunk” being a rowid range that covers the same number of blocks (give or take 1). It turned out he was motivated by a conversation with Bryn about the possibility of solving the problem using only SQL.

Bryn incorporated into his white paper two solutions based on my work, and asked Jonathan and me to speak for a few minutes during his presentations at Oracle OpenWorld and UKOUG Tech 15. I was of course honoured and pleased to be heard in such company and I thank Bryn once again for his interest and kindness.

Bryn has asked me to explain my contributions “in plain English”. That has made me think more about the subject, so I’m going to write a series of blog posts about what I hope I have learned. I’ll cover whatever interests me, whether or not it relates directly to Bryn’s work. I do hope Bryn will find what he needs for his white paper.

Current list of posts: 

May I ask you one thing? Please do not comment on Bryn’s work here. The right place to discuss Bryn’s work is here: https://blogs.oracle.com/plsql-and-ebr/entry/transforming_one_table_to_another

You are welcome to comment on my words here (underneath the appropriate post), and on Bryn’s words beneath his post.

 

 

Joining Temporal Tables 4: ranges

If you have temporal tables with date ranges, and you are sure those date ranges cannot overlap, then you can join them using the technique in my previous post – with a few important changes!

Here’s a sample table with date ranges:

create table a_with_ranges (
  case_id varchar2(32),
  from_date date,
  to_date date not null,
  a_string varchar2(32)
);

Insert into a_with_ranges values
  ('01-precedes', date '2016-01-01', date '2016-01-02','First value');
Insert into a_with_ranges values
  ('01-precedes', date '2016-01-03', date '2016-01-04','Second value');

select * from a_with_ranges order by 1,2,3;
CASE_ID FROM_DATE TO_DATE A_STRING
01-precedes 2016-01-01 2016-01-02 First value
01-precedes 2016-01-03 2016-01-04 Second value

 

For my previous technique to work, we need data that looks like this:

CASE_ID FROM_DATE START_GAP A_STRING
01-precedes 2016-01-01 0 First value
01-precedes 2016-01-02 1
01-precedes 2016-01-03 0 Second value
01-precedes 2016-01-04 1

 

Basically, every line in the table becomes two lines: the first line has the FROM_DATE value; the second has the TO_DATE value and it “starts a gap”.

We can easily get this result with a UNION ALL:

select case_id, from_date, 0 start_gap, a_string
from a_with_ranges
union all
select case_id, to_date, 1, null
from a_with_ranges
order by 1,2,3;

I don’t like this code, because it scans the table twice.

If we have at least version 11 of the Oracle database, we can scan the table just once and use UNPIVOT to create the extra line:

select case_id, from_date, start_gap, a_string
from (
  select case_id, from_date, to_date,
    0 start_gap, 1 start_gap_b,
    a_string, null a_string_b
  from a_with_ranges
)
unpivot(
  (from_date, start_gap, a_string)
  for col in (
    (from_date, start_gap, a_string),
    (to_date, start_gap_b, a_string_b)
  )
)
order by 1,2;

You can integrate this with my “join” techniques by making one complicated SELECT, or you can create a VIEW based on the above code and just use my previous technique as is.

Oops! Not quite…

You may remember that in my previous post, my tables did not always have two rows per “virtual range”. The same row could be the start of one range and the end of the preceding range. I could not have two rows with the same CASE_ID and FROM_DATE because of the primary key.

Here, when I double the rows, I may wind up with unnecessary rows where START_GAP = 1 , in which case there will be more than one row with the same CASE_ID and FROM_DATE. Here is an example:

delete from a_with_ranges;

Insert into a_with_ranges values
  ('02-meets', date '2016-01-01', date '2016-01-03','First value');
Insert into a_with_ranges values
  ('02-meets', date '2016-01-03', date '2016-01-04','Second value');

select case_id, from_date, start_gap, a_string
from (
  select case_id, from_date, to_date,
    0 start_gap, 1 start_gap_b,
    a_string, null a_string_b
  from a_with_ranges
)
unpivot(
  (from_date, start_gap, a_string)
  for col in (
    (from_date, start_gap, a_string),
    (to_date, start_gap_b, a_string_b)
  )
)
order by 1,2,3;
CASE_ID FROM_DATE START_GAP A_STRING
02-meets 2016-01-01 0 First value
02-meets 2016-01-03 0 Second value
02-meets 2016-01-03 1
02-meets 2016-01-04 1

 

Man, that is all messed up! Not only is row 3 unnecessary, but it’s telling us that the previous row stopped at the same time it started!

Fortunately, we don’t have to do any extra work to get rid of that row. All we need to do is adjust the order of the rows in the previous techniques: ORDER BY FROM_DATE, START_GAP DESCENDING. Now that extra row will end a range and the next row will start a range, whether the FROM_DATEs are the same or not.

The adjusted solutions

create or replace view va as
select case_id, from_date, start_gap, a_string
from (
  select case_id, from_date, to_date,
    0 start_gap, 1 start_gap_b,
    a_string, null a_string_b
  from a_with_ranges
)
unpivot(
  (from_date, start_gap, a_string)
  for col in (
    (from_date, start_gap, a_string),
    (to_date, start_gap_b, a_string_b)
  )
);

drop table b_with_ranges purge;

create table b_with_ranges as
select case_id,
min(from_date) from_date,
max(to_date) to_date,
'B value' b_string
from a_with_ranges
group by case_id;

create or replace view vb as
select case_id, from_date, start_gap, b_string
from (
  select case_id, from_date, to_date,
    0 start_gap, 1 start_gap_b,
    b_string, null b_string_b
  from b_with_ranges
)
unpivot(
  (from_date, start_gap, b_string)
  for col in (
    (from_date, start_gap, b_string),
    (to_date, start_gap_b, b_string_b)
  )
);

select * from vb;
CASE_ID FROM_DATE START_GAP B_STRING
02-meets 01 0 B value
02-meets 04 1
select case_id, from_date, to_date, a_str a_string, b_str b_string
from (
  select case_id, from_date, start_gap, start_gap agap, a_string,
    null bgap, null b_string
  from va
  union all
  select case_id, from_date, start_gap, null, null, start_gap bgap, b_string
  from vb
)
match_recognize(
  partition by case_id order by from_date, start_gap desc
  measures next(from_date) to_date,
    nvl(a.agap,1) + nvl(b.bgap,1) abgap,
    case a.agap when 0 then a.a_string end a_str,
    case b.bgap when 0 then b.b_string end b_str
  all rows per match
  pattern( (a|b)+ )
  define a as agap is not null
)
where (to_date > from_date or to_date is null)
  and abgap < 2; 
 with all_rows as (   select case_id, from_date, start_gap,     start_gap agap, nvl(a_string, chr(0)) a_string,     null bgap, null b_string   from va   union all   select case_id, from_date, start_gap,     null, null,     start_gap bgap, nvl(b_string, chr(0)) b_string   from vb ) , analyzed_rows as (   select case_id, from_date,     lead(from_date) over(partition by case_id order by from_date, start_gap desc) to_date,     last_value(agap) ignore nulls       over(partition by case_id order by from_date, start_gap desc) agap,     last_value(bgap) ignore nulls       over(partition by case_id order by from_date, start_gap desc) bgap,     last_value(a_string) ignore nulls       over(partition by case_id order by from_date, start_gap desc) a_string,     last_value(b_string) ignore nulls       over(partition by case_id order by from_date, start_gap desc) b_string   from all_rows ) select case_id, from_date, to_date,   case when agap = 0 then nullif(a_string, chr(0)) end a_string,   case when bgap = 0 then nullif(b_string, chr(0)) end b_string from analyzed_rows where (to_date > from_date or to_date is null)
  and nvl(agap,1) + nvl(bgap,1) < 2;
CASE_ID FROM_DATE TO_DATE A_STRING B_STRING
02-meets 01 03 First value B value
02-meets 03 04 Second value B value

 

Conclusion

This series of posts has focused on temporal tables that should not allow overlaps. The easiest way to avoid overlaps is for each row to store a date, not a range. A flag says whether the date is the start of a range or the start of a gap. When there is no gap, the end of a range is simply the date in the following row.

Whether you use this design or store date ranges, the above solutions will allow you to “join” two temporal tables – as long as there really are no overlaps.