From dev-return-54745-archive-asf-public=cust-asf.ponee.io@phoenix.apache.org Tue Dec 4 08:38:45 2018 Return-Path: X-Original-To: archive-asf-public@cust-asf.ponee.io Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx-eu-01.ponee.io (Postfix) with SMTP id 03F99180652 for ; Tue, 4 Dec 2018 08:38:44 +0100 (CET) Received: (qmail 19038 invoked by uid 500); 4 Dec 2018 07:38:44 -0000 Mailing-List: contact dev-help@phoenix.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@phoenix.apache.org Delivered-To: mailing list dev@phoenix.apache.org Received: (qmail 19026 invoked by uid 99); 4 Dec 2018 07:38:43 -0000 Received: from pnap-us-west-generic-nat.apache.org (HELO spamd1-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 04 Dec 2018 07:38:43 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd1-us-west.apache.org (ASF Mail Server at spamd1-us-west.apache.org) with ESMTP id 6B45DCAB18 for ; Tue, 4 Dec 2018 07:38:43 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd1-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: -110.301 X-Spam-Level: X-Spam-Status: No, score=-110.301 tagged_above=-999 required=6.31 tests=[ENV_AND_HDR_SPF_MATCH=-0.5, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, USER_IN_DEF_SPF_WL=-7.5, USER_IN_WHITELIST=-100] autolearn=disabled Received: from mx1-lw-us.apache.org ([10.40.0.8]) by localhost (spamd1-us-west.apache.org [10.40.0.7]) (amavisd-new, port 10024) with ESMTP id oLvl7fxLU30y for ; Tue, 4 Dec 2018 07:38:42 +0000 (UTC) Received: from mailrelay1-us-west.apache.org (mailrelay1-us-west.apache.org [209.188.14.139]) by mx1-lw-us.apache.org (ASF Mail Server at mx1-lw-us.apache.org) with ESMTP id C358F61070 for ; Tue, 4 Dec 2018 07:28:01 +0000 (UTC) Received: from jira-lw-us.apache.org (unknown [207.244.88.139]) by mailrelay1-us-west.apache.org (ASF Mail Server at mailrelay1-us-west.apache.org) with ESMTP id 0E285E0E3E for ; Tue, 4 Dec 2018 07:28:01 +0000 (UTC) Received: from jira-lw-us.apache.org (localhost [127.0.0.1]) by jira-lw-us.apache.org (ASF Mail Server at jira-lw-us.apache.org) with ESMTP id 3835924DD7 for ; Tue, 4 Dec 2018 07:28:00 +0000 (UTC) Date: Tue, 4 Dec 2018 07:28:00 +0000 (UTC) From: "Bin Shi (JIRA)" To: dev@phoenix.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Updated] (PHOENIX-4925) Use Segment/SUM tree to organize Guide Post Info MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/PHOENIX-4925?page=3Dcom.atlass= ian.jira.plugin.system.issuetabpanels:all-tabpanel ] Bin Shi updated PHOENIX-4925: ----------------------------- Summary: Use Segment/SUM tree to organize Guide Post Info (was: Use SU= M tree to organize Guide Post Info) > Use Segment/SUM tree to organize Guide Post Info > ------------------------------------------------ > > Key: PHOENIX-4925 > URL: https://issues.apache.org/jira/browse/PHOENIX-4925 > Project: Phoenix > Issue Type: Improvement > Reporter: Bin Shi > Assignee: Bin Shi > Priority: Major > > As reported, Query compilation (for the sample queries showed below), esp= ecially deriving estimation and generating parallel scans from guide posts,= becomes much slower after we introduced Phoenix Stats.=C2=A0 > a. SELECT f1__c FROM MyCustomBigObject__b ORDER BY Pk1__c > b. SELECT f1__c FROM MyCustomBigObject__b WHERE nonpk1__c =3D =E2=80=98x= =E2=80=99 ORDER BY Pk1__c > c. SELECT f1__c FROM MyCustomBigObject__b WHERE pk2__c =3D =E2=80=98x=E2= =80=99 ORDER BY pk1__c,pk2__c > d. SELECT f1__c FROM MyCustomBigObject__b WHERE pk1__c =3D =E2=80=98x=E2= =80=99 AND nonpk1__c ORDER BY pk1__c,pk2__c > e. SELECT f1__c FROM MyCustomBigObject__b WHERE pk__c >=3D 'd' AND pk__c= <=3D 'm' OR pk__c >=3D 'o' AND pk__c <=3D 'x' ORDER BY pk__c // pk__c is t= he only column to make the primary key. > =C2=A0 > By using prefix encoding for guide post info, we have to decode and trav= erse guide posts sequentially, which causes time complexity in BaseResultIt= erators.getParallelScan(...) to be O(n) , where n is the total count of gui= de posts. > According to PHOENIX-2417, to reduce footprint in client cache and over t= ransmition, the prefix encoding is used as in-memory and over-the-wire enco= ding for guide post info. > We can use something like Sum Tree (even Binary Indexed Tree) to address = both memory and performance concerns. The guide posts are partitioned to k= =C2=A0chunks (k=3D1024?), each=C2=A0chunk is encoded by prefix encoding and= the encoded data is a leaf node of the tree. The inner node contains summa= ry info (the count of rows, the data size) of the sub tree rooted at the in= ner node. > With this tree like data structure, compared to the current data structur= e, the increased size (mainly coming from the n/k-1 inner nodes) is ignorab= le. The time complexity for queries a, b, c can be reduced to O(m) where m = is the total count of regions; the time complexity for "EXPLAN" queries a, = b, c can be reduced to O(m) too, and if we support "EXPLAIN (ESTIMATE ONLY)= ", it can even be reduced to O(1). For queries d and e, the time complexity= to find the start of target scan ranges can be reduced to O(log(n/k)). > The tree can also integrate AVL and B+ characteristics to support partial= load/unload when interacting with stats client cache. > =C2=A0 -- This message was sent by Atlassian JIRA (v7.6.3#76005)