Return-Path: Delivered-To: apmail-cassandra-dev-archive@www.apache.org Received: (qmail 25298 invoked from network); 24 Aug 2010 17:31:23 -0000 Received: from unknown (HELO mail.apache.org) (140.211.11.3) by 140.211.11.9 with SMTP; 24 Aug 2010 17:31:22 -0000 Received: (qmail 9558 invoked by uid 500); 24 Aug 2010 17:31:22 -0000 Delivered-To: apmail-cassandra-dev-archive@cassandra.apache.org Received: (qmail 9501 invoked by uid 500); 24 Aug 2010 17:31:21 -0000 Mailing-List: contact dev-help@cassandra.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@cassandra.apache.org Delivered-To: mailing list dev@cassandra.apache.org Received: (qmail 9493 invoked by uid 99); 24 Aug 2010 17:31:21 -0000 Received: from Unknown (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 24 Aug 2010 17:31:21 +0000 X-ASF-Spam-Status: No, hits=0.0 required=10.0 tests=FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS,T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of jbellis@gmail.com designates 209.85.216.44 as permitted sender) Received: from [209.85.216.44] (HELO mail-qw0-f44.google.com) (209.85.216.44) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 24 Aug 2010 17:31:00 +0000 Received: by qwc9 with SMTP id 9so6886349qwc.31 for ; Tue, 24 Aug 2010 10:30:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:mime-version:received:in-reply-to :references:from:date:message-id:subject:to:content-type; bh=0G/A3MpxG4YdgmaUyAOl7nVU3ZoBTVgepWE2DfkyMdc=; b=la+RONRUpJpDxD+6vMe9pbnx2o+25oiAmXpTPxZ2lVIAQlcrBV1Wj2CDiiw/CleqCD P37hYI59UEs83OWlSEtEci/TOTCrgINX3IUyZS/CdGwqstOG6d945K7nHGuoX2gxK4+f jr7tB1y5L2ScDezP5QIJ8csYo7iLHdT9ndoPA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; b=GieF37GYO72EXVE+tSLRrNgpT5iMA8DX36sO2VUakVQdxL1SFwqleZaa3kzohsr885 tM7XsA90Rkh77+ZeQm5QFmloYpJ8J3NT9Dx6vuB1RnYgnrg0rEdpSBiw2lA3oiMGcNdb TjGfkTDm2Uk07chD/TEYQQ+vYbtdugLGfz7Nw= Received: by 10.220.76.74 with SMTP id b10mr4431257vck.218.1282671039236; Tue, 24 Aug 2010 10:30:39 -0700 (PDT) MIME-Version: 1.0 Received: by 10.220.103.204 with HTTP; Tue, 24 Aug 2010 10:30:18 -0700 (PDT) In-Reply-To: References: <90C9BAECF271EE4399D936115703855BB86B558B94@MBXFOC.vinagame.com.vn> From: Jonathan Ellis Date: Tue, 24 Aug 2010 12:30:18 -0500 Message-ID: Subject: Re: Order preserving partitioning strategy To: dev@cassandra.apache.org Content-Type: text/plain; charset=ISO-8859-1 X-Virus-Checked: Checked by ClamAV on apache.org What are some good papers to read for background? On Tue, Aug 24, 2010 at 12:26 PM, J. Andrew Rogers wrote: > On Mon, Aug 23, 2010 at 8:36 PM, Hien. To Trong wrote: >> OrderPreservingPartitioner is efficient range queries but can cause >> unevently distributed data. Does anyone has an idea of a >> HybridPartitioner which takes advantages of both RandomPartitioner >> and OPP, or at least a partitioner trade off between them. > > > What you are looking for is skew adaptive partitioning i.e. like a > B+Tree except distributable. > > A couple different methods for doing something like this exist, but > you rarely see them and they have their own (different) tradeoffs. To > the best of my knowledge, implementation requires a fairly deep > architectural commitment; it is more involved than simply defining a > partitioning function and the "adaptive" aspect must be distribution > friendly. It is an active area of research in the literature with no > obvious and simple solutions that can be lashed onto a database engine > "as is". > > -- > J. Andrew Rogers > -- Jonathan Ellis Project Chair, Apache Cassandra co-founder of Riptano, the source for professional Cassandra support http://riptano.com