Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Windows analytical functions optimization using locality preserving, dynamic hash function in MPP environment

IP.com Disclosure Number: IPCOM000240153D
Publication Date: 2015-Jan-07
Document File: 9 page(s) / 110K

Publishing Venue

The IP.com Prior Art Database

Abstract

Method of parallel processing window analytical functions on MPP environment based on locality-preserving dynamically created hash functions redistribution function.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 19% of the total text.

Page 01 of 9

Windows analytical functions optimization using locality preserving , ,

function in MPP environment

Window functions are quite often used with analytical queries. Window functions require data partitioning and ordering. Moreover because window functions work on final data set (after applying other operators like WHER, JOIN or GROUP BY) they are often the last operation performed on the host. This approach has the following drawbacks, visible especially in the MPP field:


• because host has to perform calculations of window functions it can become a bottleneck and the overall performance can decrease,


• because host is processing window functions feature of processing parallelization of MPP system is not used,


• data to be processed has to be sent to the host so feature of 'shared nothing' architecture (if applicable) is not used

The following article propose different approach to processing of window functions. The approach is to move window functions' processing from the host to the compute nodes where the processing will be done in parallel. To be able to evenly distribute data to be processed on the nodes the article proposes usage of locality-preserving dynamically created hash functions.

Background

Windows analytical functions are kind of operations which allow to perform operation like SUM, LEAD, LAG etc on some pre-partitioned and ordered data windows. Exemplary query using

windowing functions is shown below:
select
last_value ( case when l.l_log like '%disconnect%' then l.l_when else null end )

over ( partition by l.l_session, v_conn.l_session_no order by l.l_when range between unbounded

preceding and unbounded following) as l_ss_end_date,
lead (l_when ,1, current_timestamp) over ( partition by l_session order by l_when ) as l_max_to, rank ( ) over ( partition by l.l_sessio, v_conn.l_session_no order by l.l_when) as l_ss_is_ended, from raw_logs l
inner join v_conn on l.l_session = v_conn.l_session ;

Due to fact that such operation requires to partition the data and do the order by, common approach is to perform this as a final task on the host. In case of really complicated queries,

with many windows functions, host can become the bottleneck of whole query execution.

There are three main challenges to parallelize the windows functions:

1. node to be able to perform lead, lag, last_value, first_value on the particular partition needs to know all rows from one bucket

2. there are usually several windows function within one query (which means several different ways of partitioning)


3. partitions may be unequal

Approach proposed in this article is moving the windows functions processing from host to nodes, address common problem of not even data distribution between nodes using at least one dedicated hash function(s) and deals with many different ways of partitioning by grouping them in optimal way.

Details of the approach

dynamic hash

dynamic hash

1


Page 02 of 9

The proposed approach contains following steps (visualized on...