クエリは、私は有向グラフを表すDjangoのORMモデルのセットを持っている、と私はエッジ方向を無視して頂点与えに隣接するすべての頂点を取得しようとしている遅すぎる

Question

ですクエリVertex.objects.filter(Q(edge_orig__dest=v) | Q(edge_dest__orig=v)).distinct()は正しい結果を返しますが、私の場合は実行に時間がかかりすぎます。

通常、私のアプリケーションでは、いつでも約50-100の頂点があり、約100万のエッジがあります。でも唯一の20の頂点と100000のエッジにそれを減らし、そのクエリを実行するためにおよそ分半かかる。一方

for i in range(20): 
    Vertex().save() 

vxs = list(Vertex.objects.all()) 
for i in tqdm.tqdm(range(100000)): 
    Edge(orig = random.sample(vxs,1)[0], dest = random.sample(vxs,1)[0]).save() 

v = vxs[0] 
def f1(): 
    return list(Vertex.objects.filter(
     Q(edge_orig__dest=v) | Q(edge_dest__orig=v)).distinct()) 

t1 = timeit.Timer(f1) 

print(t1.timeit(number=1)) # 84.21138522100227 

を私は2つの部分にクエリを分割すれば、私は正確に同じを得ることができます結果は、ミリ秒のほんの一握りに：

def f2(): 
    q1 = Vertex.objects.filter(edge_orig__dest=v).distinct() 
    q2 = Vertex.objects.filter(edge_dest__orig=v).distinct() 
    return list({x for x in itertools.chain(q1, q2)}) 

t2 = timeit.Timer(f2) 
print(t2.timeit(number=100)/100) # 0.0109818680600074 

この第二版は、しかし問題があります。

• それはアトミックではありません。アプリケーションの2つのクエリ間でエッジのリストがほとんど変化することが保証されます。つまり、結果は単一の時点を表しません。
• 手動でループせずに、結果に対して追加の処理と集計を実行することはできません。 （例：Vertex.objects.filter(Q(edge_orig__dest=v) | Q(edge_dest__orig=v)).distinct().aggregate(avg=Avg('some_field'))）

なぜ、2番目のバージョンが最初のバージョンよりもはるかに高速に動作しますか？ これを行うにはどうすればよいのですか？また、最初のものを実際の使用に十分速く動かす方法はありますか？

私は現在、Python 3.5.2、PostgreSQL 9.5.6、およびDjango 1.11でテストしていますが、これは私がそれらの問題に取り組んでいない問題の1つです。ここで

---

は、各クエリによって生成されたSQLだけでなく、Postgresののexplanです：

最初の1：

Vertex.objects.filter(Q(edge_orig__dest=v) | Q(edge_dest__orig=v)) 

SELECT DISTINCT "app_vertex"."id" 
FROM "app_vertex" 
LEFT OUTER JOIN "app_edge" ON ("app_vertex"."id" = "app_edge"."orig_id") 
LEFT OUTER JOIN "app_edge" T4 ON ("app_vertex"."id" = T4."dest_id") 
WHERE ("app_edge"."dest_id" = 1061 
     OR T4."orig_id" = 1061) 

HashAggregate (cost=8275151.47..8275151.67 rows=20 width=4) 
    Group Key: app_vertex.id 
    -> Hash Left Join (cost=3183.45..8154147.45 rows=48401608 width=4) 
     Hash Cond: (app_vertex.id = app_edge.orig_id) 
     Filter: ((app_edge.dest_id = 1061) OR (t4.orig_id = 1061)) 
     -> Hash Right Join (cost=1.45..2917.45 rows=100000 width=8) 
       Hash Cond: (t4.dest_id = app_vertex.id) 
       -> Seq Scan on app_edge t4 (cost=0.00..1541.00 rows=100000 width=8) 
       -> Hash (cost=1.20..1.20 rows=20 width=4) 
        -> Seq Scan on app_vertex (cost=0.00..1.20 rows=20 width=4) 
     -> Hash (cost=1541.00..1541.00 rows=100000 width=8) 
       -> Seq Scan on app_edge (cost=0.00..1541.00 rows=100000 width=8) 

第二のもの：khampsonさん@

Vertex.objects.filter(edge_orig__dest=v).distinct() 

SELECT DISTINCT "app_vertex"."id" 
FROM "app_vertex" 
INNER JOIN "app_edge" ON ("app_vertex"."id" = "app_edge"."orig_id") 
WHERE "app_edge"."dest_id" = 1061 

HashAggregate (cost=1531.42..1531.62 rows=20 width=4) 
    Group Key: app_vertex.id 
    -> Hash Join (cost=848.11..1519.04 rows=4950 width=4) 
     Hash Cond: (app_edge.orig_id = app_vertex.id) 
     -> Bitmap Heap Scan on app_edge (cost=846.65..1449.53 rows=4950 width=4) 
       Recheck Cond: (dest_id = 1061) 
       -> Bitmap Index Scan on app_edge_dest_id_4254b90f (cost=0.00..845.42 rows=4950 width=0) 
        Index Cond: (dest_id = 1061) 
     -> Hash (cost=1.20..1.20 rows=20 width=4) 
       -> Seq Scan on app_vertex (cost=0.00..1.20 rows=20 width=4) 

バージョンも実行するのに1分半かかります。だから、それはまた無駄です。

Vertex.objects.raw(...) 

SELECT DISTINCT "app_vertex"."id" 
FROM "app_vertex" 
JOIN "app_edge" ON ("app_vertex"."id" = "app_edge"."orig_id") 
JOIN "app_edge" T4 ON ("app_vertex"."id" = T4."dest_id") 
WHERE ("app_edge"."dest_id" = 1061 
     OR T4."orig_id" = 1061); 

HashAggregate (cost=8275347.47..8275347.67 rows=20 width=4) 
    Group Key: app_vertex.id 
    -> Hash Join (cost=3183.45..8154343.45 rows=48401608 width=4) 
     Hash Cond: (app_vertex.id = app_edge.orig_id) 
     Join Filter: ((app_edge.dest_id = 1061) OR (t4.orig_id = 1061)) 
     -> Hash Join (cost=1.45..2917.45 rows=100000 width=12) 
       Hash Cond: (t4.dest_id = app_vertex.id) 
       -> Seq Scan on app_edge t4 (cost=0.00..1541.00 rows=100000 width=8) 
       -> Hash (cost=1.20..1.20 rows=20 width=4) 
        -> Seq Scan on app_vertex (cost=0.00..1.20 rows=20 width=4) 
     -> Hash (cost=1541.00..1541.00 rows=100000 width=8) 
       -> Seq Scan on app_edge (cost=0.00..1541.00 rows=100000 width=8) 

Answer 1

これら2つのクエリのクエリプランは根本的に異なります。最初の（遅い）インデックスはヒットしておらず、2つの処理を実行しています。両方とも処理され、返される行が増えます。 Django ORM構文の意図を解釈したところから、実際にはleft joinをここで実行したいと思うようには聞こえません。

私はDjangoのORMの中から、この場合には、生のSQLに落下検討をお勧めします、と2をハイブリダイズします。例えばあなたが最初のものを取り、このような何かにそれを変換する場合：そこ

SELECT DISTINCT "app_vertex"."id" 
FROM "app_vertex" 
JOIN "app_edge" ON ("app_vertex"."id" = "app_edge"."orig_id") 
JOIN "app_edge" T4 ON ("app_vertex"."id" = T4."dest_id") 
WHERE ("app_edge"."dest_id" = 1061 
     OR T4."orig_id" = 1061); 

つの質問：どのようにそのバージョンは行わず、それはあなたが探している結果が得られていますか？

生のクエリの詳細については、Django docのthis sectionをご覧ください。 OPからコメントする

---

応答：

私も示唆したクエリのクエリプランは、それがどのインデックスを打っていないことを示しています。

関連する列の両方の表に索引がありますか？特にこの特定のクエリでは、単一の値を探しているので、クエリプランナがシーケンシャルスキャンがより良い選択であると判断した場合、インデックスには驚くはずです（OTOH、たとえば、テーブルの行の10％を超える広い範囲の行を検索すると、クエリプランナーはそのような決定を正しく行う可能性があります）。

Answer 2

私は別のクエリは可能性が提案する：

# Get edges which contain Vertex v, "only" optimizes fields returned 
edges = Edge.objects.filter(Q(orig=v) | Q(dest=v)).only('orig_id', 'dest_id') 
# Get set of vertex id's to discard duplicates 
vertex_ids = {*edges.values_list('orig_id', flat=True), *edges_values_list('dest_id', flat=True)} 
# Get list of vertices, excluding the original vertex 
vertices = Vertex.objects.filter(pk__in=vertex_ids).exclude(pk=v.pk) 

これは、任意の結合とあなたが言及競合状態に苦しむべきではありません必要はありません。