Oracle Scratchpad

August 24, 2014

In-memory Aggregation

Filed under: 12c,in-memory,Oracle,Performance — Jonathan Lewis @ 8:05 pm GMT Aug 24,2014

The title of this piece is the name given to a new feature in 12.1.0.2, and since I’ve recently blogged about a limitation of the in-memory option I thought I’d pick this feature as the next obvious thing to blog about. This is a bit of a non sequitur, though, as the feature seems to have nothing whatsoever to do with the in-memory option; instead it’s a cunning mechanism combining aspects of the star-transformation (but without the bitmap indexes), Bloom filters, and “group-by” placement to minimise the cost of aggregation over high-volume joins.

Here’s a small data set I’ll use to demonstrate the feature:

create table towns
as
select
        rownum                                          id,
        trunc(dbms_random.value(1,51))                  id_state,
        rpad(dbms_random.string('U',3),12)              name,
        cast (rpad('x',trunc(dbms_random.value(50,60)),'x') as varchar2(60))    padding
from
        all_objects
where
        rownum <= 2000
;

alter table towns add constraint to_pk primary key(id);
create index to_i1 on towns(name);

create table people(
        id_town_work    number(6,0)     not null
                constraint pe_fk_wo references towns,
        id_town_home    number(6,0)     not null
                constraint pe_fk_ho references towns,
        dummy1          varchar2(10),
        dummy2          varchar2(10),
        padding         varchar2(110)
);

insert /*+ append */  into people
with generator as (
        select  --+ materialize
                rownum id
        from dual
        connect by
                level <= 1e4
)
select
        trunc(dbms_random.value(1,2001)),
        trunc(dbms_random.value(1,2001)),
        lpad(rownum,10),
        lpad(rownum,10),
        cast (rpad('x',trunc(dbms_random.value(50,60)),'x') as varchar2(60))    padding
from
        generator       v1,
        generator       v2
where
        rownum <= 1e5
;

commit;

begin
        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'Towns',
                method_opt       => 'for all columns size 1'
        );
        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'People',
                method_opt       => 'for all columns size 1'
        );
end;
/

I have a “large” table of people, and people can live in one town and work in another. Towns are in states and I’m interested in a report about people who live in one specific state but work in another (e.g. New Hampshre vs. Massachusetts). There are a couple of “padding” columns to represent the data associated with each town and person that I might want in a report. To keep things simple I haven’t extended the query out to select the name of the state. Here’s the query I might use to get the report I want:

select
        wt.padding,
        ht.padding,
        max(pe.padding)
from
        towns   wt,
        towns   ht,
        people  pe
where
        wt.id_state     = 1
and     pe.id_town_work = wt.id
and     ht.id_state     = 2
and     pe.id_town_home = ht.id
group by
        wt.padding,
        ht.padding
;

You might expect something like the following as the execution plan:

-------------------------------------------------------------------------------
| Id  | Operation            | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |        |    40 |  7600 |   179   (6)| 00:00:01 |
|   1 |  HASH GROUP BY       |        |    40 |  7600 |   179   (6)| 00:00:01 |
|*  2 |   HASH JOIN          |        |    40 |  7600 |   178   (6)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL | TOWNS  |    40 |  2520 |     5   (0)| 00:00:01 |
|*  4 |    HASH JOIN         |        |  2000 |   248K|   173   (6)| 00:00:01 |
|*  5 |     TABLE ACCESS FULL| TOWNS  |    40 |  2520 |     5   (0)| 00:00:01 |
|   6 |     TABLE ACCESS FULL| PEOPLE |   100K|  6250K|   165   (4)| 00:00:01 |
-------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("PE"."ID_TOWN_HOME"="HT"."ID")
   3 - filter("HT"."ID_STATE"=2)
   4 - access("PE"."ID_TOWN_WORK"="WT"."ID")
   5 - filter("WT"."ID_STATE"=1)

The order of operation (row source generation) is: 3,5,6,4,2,1 – we build a hash table from the towns in state 2; build a hash table from the towns in state 1; scan the people table and probe the state 1 hash table, any row that survives is used to probe the state 2 hash table, and the rows that survive the second probe are aggregated to produce the answer.

When you do this type of thing with very large data sets one of the potential performance threats comes from the volume of data you have to aggregate. As we’ve joined the three tables the row length grows significantly before we finally aggregate (admittedly my data set is small, and the number of rows we’re going to aggregate also appears to be very small according to the predictions). There’s also (in the early stages at least) the potential for passing a very large number of rows from the fact table through the first (and possibly subsequent) hash join, doing a lot of work to eliminate the rows you don’t need.

In 12c the optimizer can choose to minimise both these threat points using “vector transformation”. (The name may also reflect the possibility that the code path will take advantage of vector processing (SIMD) operations if they’re available in the CPU.) Here’s the execution path I got when I added the /*+ vector_transform(@sel$1) */ hint to my query – it’s not sensible for this tiny data set, of course, but the hint is a way of learning what Oracle can do:

-----------------------------------------------------------------------------------------------------------
| Id  | Operation                     | Name                      | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |                           |    71 | 15975 |   184   (6)| 00:00:01 |

|   1 |  TEMP TABLE TRANSFORMATION    |                           |       |       |            |          |

|   2 |   LOAD AS SELECT              | SYS_TEMP_0FD9D6661_31399B |       |       |            |          |
|   3 |    VECTOR GROUP BY            |                           |    10 |   670 |     6  (17)| 00:00:01 |
|   4 |     KEY VECTOR CREATE BUFFERED| :KV0000                   |    40 |  2680 |     6  (17)| 00:00:01 |
|*  5 |      TABLE ACCESS FULL        | TOWNS                     |    40 |  2520 |     5   (0)| 00:00:01 |

|   6 |   LOAD AS SELECT              | SYS_TEMP_0FD9D6662_31399B |       |       |            |          |
|   7 |    VECTOR GROUP BY            |                           |    10 |   670 |     6  (17)| 00:00:01 |
|   8 |     KEY VECTOR CREATE BUFFERED| :KV0001                   |    40 |  2680 |     6  (17)| 00:00:01 |
|*  9 |      TABLE ACCESS FULL        | TOWNS                     |    40 |  2520 |     5   (0)| 00:00:01 |

|  10 |   HASH GROUP BY               |                           |    71 | 15975 |   172   (6)| 00:00:01 |
|* 11 |    HASH JOIN                  |                           |    71 | 15975 |   171   (5)| 00:00:01 |
|  12 |     TABLE ACCESS FULL         | SYS_TEMP_0FD9D6662_31399B |    10 |   670 |     2   (0)| 00:00:01 |
|* 13 |     HASH JOIN                 |                           |    71 | 11218 |   169   (5)| 00:00:01 |
|  14 |      TABLE ACCESS FULL        | SYS_TEMP_0FD9D6661_31399B |    10 |   670 |     2   (0)| 00:00:01 |
|  15 |      VIEW                     | VW_VT_C444E4CB            |    71 |  6461 |   167   (5)| 00:00:01 |
|  16 |       HASH GROUP BY           |                           |    71 |  5112 |   167   (5)| 00:00:01 |
|  17 |        KEY VECTOR USE         | :KV0000                   |    71 |  5112 |   167   (5)| 00:00:01 |
|  18 |         KEY VECTOR USE        | :KV0001                   |  2000 |   132K|   167   (5)| 00:00:01 |
|* 19 |          TABLE ACCESS FULL    | PEOPLE                    |   100K|  6250K|   165   (4)| 00:00:01 |
-----------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   5 - filter("WT"."ID_STATE"=1)
   9 - filter("HT"."ID_STATE"=2)
  11 - access("ITEM_10"=INTERNAL_FUNCTION("C0") AND "ITEM_11"="C2")
  13 - access("ITEM_8"=INTERNAL_FUNCTION("C0") AND "ITEM_9"="C2")
  19 - filter(SYS_OP_KEY_VECTOR_FILTER("PE"."ID_TOWN_HOME",:KV0001) AND
              SYS_OP_KEY_VECTOR_FILTER("PE"."ID_TOWN_WORK",:KV0000))

There are three critical components to this plan: first, we create a couple of “Key Vectors” from the towns table, then we use those key vectors while scanning the people table and aggregate a minimal data set, finally we join back to the data associated with the key vectors. Reprising my introductory paragraph: the creation and use of the key vectors is similar to the Bloom filter approach; the final join-back is similar to the strategy used in Star Transformations (especially the ones where temp tables appear), and the key vector allows the high-volume fact data to be aggregated as much as possible before adding extra row-length from the dimensions.

In outline Oracle does the following:

  • scan the towns table to extract the id, and padding columns for id_state = 1 / work town – this produced 50 rows with my data set
  • manipulate the result to extract the distinct values of padding, and give each value a unique numeric identifier – this is the information that goes into the temp table (with one extra column) – this produced 10 rows
  • manipulate the result again to produce an in-memory array of (town.id, temp_table.identifier) – this is the key vector, containing 50 elements.

The second temp table and key vector for (id_state = 2 /work town ) will be created in the same way.

As the fact table is scanned Oracle can apply the key vectors very efficiently (we hope) to pick out the people rows that would be involved in the final aggregate and associate with each relevant row the two padding identifiers that belong to that row (this step is a bit like doing 2 hash joins – but presumably much more efficient; Bloom filtering does something very similar). After selecting the minimum number of rows we can aggregate them on the  two padding identifiers (an example of the “aggregate early”/”place group by” principle – aggregate before joining); finally we join back to the two temporary tables to translate the short padding identifiers into the long padding values (just as we do in star transformations with temporary table transformation).

Strangely we aggregate again after the join-back. I don’t think it’s necessary in this case because I’m fairly sure that the join back is on a unique set of columns – but perhaps this is a generic strategy allowing for variations in the mechanism, including such things as cases where the vector transform is only applied to a subset of the dimension tables.

Technically you could almost emulate this strategy in any version of Oracle (and I probably have at various times over the last few years) with the major limitation that the “KEY VECTOR USE” operations at lines 17 and 18 would have to be replaced with hash joins; no doubt, though, the major CPU saving of this approach is the difference between consecutive hash joins and what appears to be (from the execution stats) concurrent vector filtering. At some point – if a client needs the extra performance edge before they get to 12c – I’ll have to see if I can engineer an example in 11g that emulates the whole plan but uses Bloom filtering to approximate the key vector filtering.

 

4 Comments »

  1. Reblogged this on Dinesh Ram Kali..

    Comment by dineshramitc — August 24, 2014 @ 11:53 pm GMT Aug 24,2014 | Reply

  2. Here are some additional details:

    – In-memory aggregation (IMA; the vector transformation plan) is a feature of Oracle Database In-Memory. This plan will not be chosen unless the In-Memory option is enabled.

    – Vector transformation is best with in-memory tables, but can be used and is beneficial with row store tables. The optimizer will not often choose vector transformation with row store tables, so try the /*+ vector_transform */ hint.

    – The KEY VECTOR USE operation is similar to a Bloom filter in that it transforms the join into a filter on the fact table. It’s different from a Bloom filter in that it has no false positives.

    – The KEY VECTOR USE operation uses fast vector look-ups when scanning the fact table. This is much more efficient than calculating hash values. This is one of the reasons why the vector transformation plan uses less CPU as compared to other plans.

    – The plan in this example is not typical of a vector transformation plan. I suspect this is because of @sel$1 in the vector_transform hint. Normally there would be a vector group by operation preceding the hash group by at ID 16. The vector group by operation would attempt to aggregate data into an array structure indexed by the ‘dense grouping keys’ of the key vector, which is more efficient for smaller aggregate row sets. If the vector group by array grows too large (it’s the Cartisean product of the dense grouping keys), it will fail over to the first hash group by (ID 16).

    – The final hash group by (ID 10) combines aggregates in the vector group by array and the hash group by row set (rows in the temp tables are already unique, so that’s not the purpose of the final hash group by).

    Comment by Bud Endress — August 29, 2014 @ 3:00 pm GMT Aug 29,2014 | Reply

    • Bud,

      Thanks for the comments. Since the plan is only available when the in-memory store is available does this mean it’s using memory from the inmemory_size, to create the vector group by array; or is this just a case of the plan (like bitmap transformations) being dependent on a licensed option ?

      I did try putting in the vector_transform hint without specifying @sel$1 and it made no difference to the plan. In fact the full hint from the outline was this:

      VECTOR_TRANSFORM(@"SEL$1" FACT("PE"@"SEL$1") DIMENSION("HT"@"SEL$1") DIMENSION("WT"@"SEL$1"))
      

      Comment by Jonathan Lewis — September 1, 2014 @ 10:59 am GMT Sep 1,2014 | Reply

  3. Here’s an example of a plan with VECTOR GROUP BY. Note that I used the no_parallel hint to simply the plan for easier reading.

    explain plan for
    SELECT /*+ no_parallel */ d1.calendar_year_name,
      d3.region_name,
      SUM(f.sales)
    FROM time_dim_v d1,
      customer_dim_10m_10 d3,
      units_fact_10m_10 f
    WHERE d1.day_id          = f.day_id
    AND d3.customer_id       = f.customer_id
    AND d1.calendar_year_name='CY2009'
    GROUP BY d1.calendar_year_name,
      d3.region_name
    ORDER BY d1.calendar_year_name,
      d3.region_name;
    
    --------------------------------------------------------------------------
    | Id  | Operation                           | Name                       |
    --------------------------------------------------------------------------
    |   0 | SELECT STATEMENT                    |                            |
    |   1 |  TEMP TABLE TRANSFORMATION          |                            |
    |   2 |   LOAD AS SELECT                    | SYS_TEMP_0FD9D6713_205B37  |
    |   3 |    RESULT CACHE                     | a9nz6nsmjcja9drqj973jfsm99 |
    |   4 |     VECTOR GROUP BY                 |                            |
    |   5 |      HASH GROUP BY                  |                            |
    |   6 |       KEY VECTOR CREATE BUFFERED    | :KV0000                    |
    |   7 |        PARTITION RANGE ALL          |                            |
    |   8 |         TABLE ACCESS INMEMORY FULL  | TIME_DIM                   |
    |   9 |   LOAD AS SELECT                    | SYS_TEMP_0FD9D6714_205B37  |
    |  10 |    RESULT CACHE                     | 9f561j3rbgpx93jxvjrbx8mqug |
    |  11 |     VECTOR GROUP BY                 |                            |
    |  12 |      KEY VECTOR CREATE BUFFERED     | :KV0001                    |
    |  13 |       TABLE ACCESS INMEMORY FULL    | CUSTOMER_DIM_10M_10        |
    |  14 |   SORT GROUP BY                     |                            |
    |  15 |    HASH JOIN                        |                            |
    |  16 |     MERGE JOIN CARTESIAN            |                            |
    |  17 |      TABLE ACCESS FULL              | SYS_TEMP_0FD9D6713_205B37  |
    |  18 |      BUFFER SORT                    |                            |
    |  19 |       TABLE ACCESS FULL             | SYS_TEMP_0FD9D6714_205B37  |
    |  20 |     VIEW                            | VW_VT_6DC88229             |
    |  21 |      VECTOR GROUP BY                |                            |
    |  22 |       HASH GROUP BY                 |                            |
    |  23 |        KEY VECTOR USE               | :KV0001                    |
    |  24 |         KEY VECTOR USE              | :KV0000                    |
    |  25 |          PARTITION RANGE SUBQUERY   |                            |
    |  26 |           TABLE ACCESS INMEMORY FULL| UNITS_FACT_10M_10          |
    --------------------------------------------------------------------------
    

    Comment by Bud Endress — August 29, 2014 @ 3:06 pm GMT Aug 29,2014 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 4,521 other followers